อยากรู้ว่าการเรียกใช้ข้อมูลใน Memory ของ CPU ทำยังไงมาดูกัน ด้วย Most Frequently Used (MFU) Algorithms !!

Page Replacement
คือ การเรียกใช้และจัดเรียงข้อมูลใน Memory ของ CPU โดย CPU จะจัดข้อมูลที่จะเรียกใช้ลงใน Memory ก่อนที่จะเรียกใช้งาน

Page Replacement มี Algorithm หลักๆ คือ Least Frequently Used(LFU), First In First Out(FIFO), Optimal, Least Recently Used(LRU)
แต่ Algorithm ที่เราเลือกมาใช้นั้นจะเป็นแบบ Most Frequently Used(MFU) ซึ่งเป็น Algorithm ที่พัฒนามาหลังจาก Least Frequently Used(LFU)
โดยใช้หลักการคล้ายๆกันคือ จากที่จะนำข้อมูลที่ใช้น้อยๆออกจากตัว Memory จะนำข้อมูลตัวที่ใช้บ่อยๆออกจาก Memory แทนซึ่งถามว่ามีข้อดีหรือข้อคิดอะไรที่ทำให้ Algorithm นี้เกิดขึ้นมา
หลักๆเลย คือ การทำให้ Page ที่เข้ามาทำงานได้เท่าๆกันไม่มีตัวไหนทำงานบ่อยมากกว่าตัวอื่นมากนัก แต่ก็จากความคิดนี้เองทำให้ตัว Algorithm นี้ไม่เป็นที่นิยมในการใช้เลยเนื่องจาก
หากมี Page ใช้บ่อยๆที่เป็น Process สำคัญใน Memory จะต้องนำ Page นั้นเข้ามาใส่ใน Memory ทุกครั้งเนื่องจากจะทุกเตะออกจาก Memory ตลอดทำให้ มี Overhead จากการใช้งานสูงมาก
แทนที่จะทำให้ตัว CPU ทำงานได้เร็วขึ้น

Source code and Output

a = [11, 12, 13, 15, 17, 15, 5,
14, 12, 1, 19, 11, 20, 1, 12] // กำหนดค่าและลำดับการ Page In
n = len(a) // นับจำนวน Page ทั้งหมดใน a
m = 5 // กำหนดจำนวน Page

#Main Algorithm Function
def __mfu(): // Main Function
global a,n,m // ตัวแปรที่กำหนดค่าไว้ด้านบน
x = 0
page_faults = 0 // Set Page Faults เป็น 0
page = [] // สร้าง Array เก็บค่า page
time={} // List เก็บค่า Hit
b=list(a) // List ค่าทั้งหมดใน a

for i in range(m): // รัน For Loop ของ m ใส่ค่า -1 ลงในจำนวน Page ทั้งหมด
page.append(-1)

for i in a: // รัน For Loop ของ a เก็บค่า Hit ของ Page In แต่ล่ะตัว
time[i]=0

for i in range(n): // รัน For Loop ของ n เพื่อเช็คว่าค่าที่ Page In ตรงกับค่าใน Page Memory หรือไม่
flag = 0
for j in range(m):
if(page[j] == a[i]): // หาก Hit Page memory จะบวกค่า Hit(time) +1
flag = 1
time[a[i]]+=1
break

if flag == 0: // หากค่าไม่ตรงกับใน Page Memory
rpage = -1
if page[x] != -1: //หากค่าใน Page Memory ไม่ใช่ -1

t=[] // Array เก็บค่าแยก
for k in page: // รัน For Loop ตามจำนวนที่มีใน Page Memory เพื่อเก็บค่า Hit
t.append(time[k])

most=max(t) //กำหนดให้ most มีค่าเท่ากับตัวที่ Hit สูงสุด

gpage=[] //Array เก็บค่าแยก
for k in page: //รัน For loop ตามจำนวนใน Page Memory
if time[k] == most: //ถ้าเช็คเจอตัวที่มี Hit มากที่สุด
gpage.append(k) //เก็บค่าลง gpage

maxi = -1
flag = 0 // เซ็ตให้ Flag เป็น 0 เพื่อให้ทำ For ใน if ด้านบนต่อไปได้

for k in gpage: // Check ค่าสูงสุดที่เก็บไว้ใน gpage ของ Memory แต่ล่ะตัว
for n in range(0,i): // For Loop หาค่าตามตัวใน Page In
if(k == b[n]): //หากมีตัวใด ตรงกันตัวตัวใน Page In
if maxi == -1: //หากเจอ -1(Page Memory ที่ว่าง) ให้มีค่าเป็นตัว Page In
maxi = n
rpage = k
elif n ” % (a[i])) // Print บอกค่า Page In
for j in range(m): // ปริ้นค่าที่ใส่ในแต่ล่ะ Page In
if page[j] != -1:
print (page[j])
else:
print (“-“)
else: // Print หากเป็น Page Hit
print (“\n%d -> Hit” % (a[i]))
print (“Frequencies: “,time[a[i]])

print (“\nTotal page faults : %d.” % (page_faults)) // Print page Fault
print (“\nFrequencies of pages: “, time) // Print current Page in frequency

__mfu() //เรียกใช้ Function หา Page Replacement

อันนี้จะเป็นรูปผลลัพธ์ Output ที่ได้จากโปรแกรม Python IDLE โดยจะเห็นได้ว่าตัวที่มี Page Hit หรือการเรียกใช้เยอะที่สุดนั้นจะโดยนำออกจาก Page Memory

ประโยชน์ที่ได้รับจากการทำ

ได้ความรู้เกี่ยวกับการนำ For loop มาใช้ในภาษา Python และทำให้เข้าใจ Algorithm ในการทำงานของภาษา Python มากขึ้นจากที่ตอนต้นๆเทอมนั้นแทบจะไม่เข้าใจอะไรเกี่ยวกับภาษานี้เลย
ทำให้สามารถนำความรู้จากแลปและข้อมูลจากการทำ Project นี้ไปใช้ทำความเข้าใจเรื่องอื่นๆในวิชา CE311 ได้

Youtube