บทที่ 5ระบบหน่วยความจำเสมือน

โดย นายอาทิตย์ ยลระบิล  รหัสนักศึกษา : 6031280069

บทที่ 5ระบบหน่วยความจำเสมือน

(Virtual Memory)

ประเภทของการจัดการหน่วยความจำ

การจัดการหน่วยความจำ

ระบบหน่วยความจำเสมือน (Virtual Memory)

•การจัดการหน่วยความจำสามารถแบ่งออกเป็น 2 ประเภทใหญ่ ๆ
–ระบบหน่วยความจำจริง

ขนาดของโปรแกรมจะต้องไม่ใหญ่กว่าขนาดของหน่วยความจำที่มีอยู่ ลบด้วยขนาดของหน่วยความจำที่เป็นส่วนของ OS
–ระบบหน่วยความจำเสมือนขนาดของโปรแกรมจะมีขนาดเท่าใดก็ได้

แนวคิดของหน่วยความจำเสมือน

•ผู้เขียนโปรแกรมหรือผู้ใช้จะไม่ถูกจำกัดในเรื่องของขนาดของหน่วยความจำอีกต่อไป
•OS จะจัดการให้ผู้ใช้สามารถใช้หน่วยความจำได้มากกว่าหน่วยความจำจริงที่มีอยู่
•โปรแกรมทั้งโปรแกรมโดยส่วนใหญ่ไม่ได้ถูกใช้งานพร้อมกันทั้งหมด ซึ่งการทำงานของโปรแกรมจะเริ่มทำงานจากส่วนต้นโปรแกรม แล้วค่อย ๆ เลื่อนลงมาจนกระทั่งถึงท้ายโปรแกรม


•ในขณะที่โปรแกรมกำลังทำงานอยู่ที่ส่วนต้นโปรแกรม ที่ปลายโปรแกรมก็ยังไม่ถูกใช้งาน เมื่อโปรแกรมทำงานมาถึงส่วนท้าย ๆ โปรแกรม ส่วนต้น ๆ โปรแกรมก็ไม่ถูกใช้งาน

การแปลงแอดเดรส (Address Mapping)

•เนื่องจากขนาดของโปรแกรมมีขนาดใหญ่กว่าขนาดของหน่วยความจำ ดังนั้นจึงต้องมีการอ้างอิงแอดเดรสระหว่างแอดเดรสของหน่วยความจำจริงกับแอดเดรสของโปรแกรม
•แอดเดรสจริง (Real Address หรือ Physical Address) หมายถึงแอดเดรสในหน่วยความจำจริงเท่านั้น
•แอดเดรสเสมือน (Virtual Address หรือ Logical Address) หมายถึงแอดเดรสที่โปรแกรมอ้างถึง

•ดังนั้นจึงต้องมีกลไกการแปลงแอดเดรสจากแอดเดรสเสมือนให้เป็นแอดเดรสจริง ณ.ตำแหน่งที่โปรแกรมส่วนนั้นถูกวางลงไป ซึ่งเราเรียกว่าการแปลงส่งแอดเดรส (Address Mapping)

•เทคนิคการแปลงแอดเดรสมีอยู่หลายวิธี แต่วิธีที่นิยมใช้กันอย่างแพร่หลายคือ dynamic address translation (DAT) 

•วิธีการที่จะจัดการหน่วยความจำจริงให้สามารถทำงานโปรแกรมที่มีขนาดใหญ่ จะใช้หลักการแบ่งโปรแกรมออกเป็นส่วนย่อย ๆ หลาย ๆ ส่วนเรียกว่าบล็อก (Block)

 
•ขนาดของบล็อกแบ่งออกเป็น 2 แบบคือทุกบล็อกมีขนาดเท่ากัน หรือบล็อกมีขนาดไม่เท่ากัน ดังนั้น

ระบบหน่วยความจำเสมือนจึงแบ่งได้เป็น 2 แบบ

–หน่วยความจำเสมือนระบบหน้า (Paging system)
–หน่วยความจำเสมือนระบบเซกเมนต์ (Segment system)

การแปลงส่งแอดเดรส

1.การแปลงส่งแบบตรง (direct mapping)
2.การแปลงส่งแบบสาระ(associative mapping)
3.การแปลงส่งแบบผสมระหว่างสาระและแบบตรง combined associative/direct mapping

หน่วยความจำเสมือนระบบหน้า (Paging system)

•เป็นการจัดแบ่งโปรแกรมออกเป็นบล็อกที่มีขนาดเท่า ๆ กันทุกบล็อก โดยจะเรียกบล็อกแต่ละบล็อกว่าหน้า (Page)

•ตัวอย่างการทำงานในระบบหน้า
–ระบบมีหน่วยความจำขนาด 100 Kbyte = 100,000 Byte = 105 Byte
–ต้องการรันโปรแกรมที่มีขนาด 1000 Kbyte = 1,000,000 Byte = 106 Byte

การแปลงแอดเดรสในระบบหน้า

•OS จะสร้างตารางไว้สำหรับโปรเซส คือ ตารางหน้า (Page table)
•สมมุติว่าหน่วยความจำเสมือนมีขนาด 1000 หน้า และหน่วยความจำจริงมีขนาด 100 หน้า
•ตารางหน้าก็จะมีขนาด 1000 ช่อง ได้แก่ช่องที่ 000-999
–ช่องที่ 000 สำหรับหน้าที่ 000
–ช่องที่ 001 สำหรับหน้าที่ 001
•ในตารางหน้าจะมี 3 คอลัมภ์

•คอลัมภ์ที่ 1 จะบอกแอดเดรสของหน้านั้น ๆ ที่อยู่ในดิสก์เพื่อที่จะได้รู้ว่าหน้าต่าง ๆ ของโปรแกรมเก็บไว้ที่หน้าใดของดิสก์ 

•คอลัมภ์ที่ 2 จะบอกว่าหน้านั้น ๆ อยู่ในหน่วยความจำจริงหรือไม่
–ถ้าค่าเป็น 0 หมายถึง หน้านั้นไม่ได้อยู่ในหน่วยความจำจริง (อยู่ในหน่วยความจำสำรอง)
–ถ้าค่าเป็น 1 หมายถึง หน้านั้นอยู่ในหน่วยความจำจริง 

•คอลัมภ์ที่ 3 จะบอกถึงแอดเดรสเริ่มต้นของหน้าในหน่วยความจำจริง คือหมายเลขหน้าในหน่วยความจำจริงตามด้วยดีสเพรสเมนต์


ถ้าต้องการทราบว่าแอดเดรสเสมือน 123983 ไปอยู่ ณ. ตำแหน่งใดในหน่วยความจำจริง

1. OS จะนำเอาแอดเดรสเสมือนมาหาค่าหมายเลขหน้าและดีสเพลซเมนต์ ในกรณีนี้ หมายเลขหน้าคือ 123 และดีสเพลซเมนต์คือ 983

2. OS จะตรวจสอบที่ตารางหน้าในช่องที่ 123

3. อ่านค่าคอลัมภ์ที่ 2 ในตารางหน้าช่องที่ 123 ว่ามีค่า 1 หรือ 0 ในกรณีนี้มีค่าเป็น 1 (แสดงว่าเก็บอยู่ในหน่วยความจำจริง)

ถ้าต้องการทราบว่าแอดเดรสเสมือน 123983 ไปอยู่ ณ. ตำแหน่งใดในหน่วยความจำจริง

4. OS จะอ่านค่าในคอลัมภ์ที่ 3 ของตารางหน้าเพื่อหาแอดเดรสเริ่มต้นของหน้าในหน่วยความจำจริง ซึ่งค่าคอลัมภ์ 3 คือ 54000

5. นำเอาค่าในคอลัมภ์ที่ 3 มารวมกับดีสเพรสเมนต์ จะได้แอดเดรสในหน่วยความจำจริงที่ตรงกับแอดเดรสเสมือน (ซึ่งค่าคอลัมภ์ที่3 คือ 54000 ค่าดีสเพรสเมนต์คือ 983 ค่าที่ได้คือ 54000+983=54983

6. ดังนั้น แอดเดรสเสมือน 123983 จะอยู่ที่

หน้า 54 ของหน่วยความจำจริง และมี
ค่าดีสเพรสเมนต์ คือ 983








กรณีข้อมูลไม่ได้อยู่ในหน่วยความจำจริง (อยู่ในหน่วยความจำสำรอง)
1. OS จะนำเอาแอดเดรสเสมือนมาหาค่าหมายเลขหน้าและดีสเพลซเมนต์ ในกรณีนี้ หมายเลขหน้าคือ 123 และดีสเพลซเมนต์คือ 983 OS จะตรวจสอบที่ตารางหน้าในช่องที่ 123

2. อ่านค่าคอลัมภ์ที่ 2 ในตารางหน้าช่องที่ 123 ว่ามีค่า 1 หรือ 0 ในกรณีนี้มีค่าเป็น 0 (แสดงว่าเก็บอยู่ในหน่วยความจำสำรอง)
3. OS จะอ่านค่าคอลัมภ์ที่ 1 ซึ่งเป็นแอดเดรสในดิสก์ ในดิสก์เป็นจำนวน 1 หน้า (1 Kbyte ) (ค่าแอดเดรสในดิสก์คือ 5146789)

4. OS จะไปหาหน้าที่ว่างในหน่วยความจำจริง (หน้าที่ว่างคือหน้าที่ 03000)

กรณีข้อมูลไม่ได้อยู่ในหน่วยความจำจริง (อยู่ในหน่วยความจำสำรอง)
5. นำข้อมูลที่อ่านมาจากดิสก์ไปวางไว้ในหน่วยความจำจริง

6. OS จะทำการแก้ไขข้อมูลในตารางหน้าช่องที่ 123 โดยเปลี่ยนค่าคอลัมภ์ที่ 2 เป็น 1 

7. ใส่ค่าหน้าที่หามาได้ของหน่วยความจำจริงบวกกับตำแหน่งเริ่มต้น (000) ของดีสเพรสเมนต์ลงในคอลัมภ์ที่ 3 ของตารางหน้า (ค่าแอดเดรสจริง 03983 (03000+983) ซึ่งตรงกับแอดเดรสเสมือน 123983
•กรณีถ้าไม่มีหน้าว่างในหน่วยความจำจริง OS ต้องเลือกเอาหน้าหนึ่งออกจากหน่วยความจำจริง
•หน้าใดจะถูกเลือกออก OS จะมีวิธีการที่เรียกว่า การสับเปลี่ยนหน้า (Page Replacement)
•หน้าที่ถูกเลือกออก OS จะทำการบันทึกข้อมูลและสถานะปัจจุบันของหน้านั้นกลับลงในดิสก์ ณ.ตำแหน่งแอดเดรสของดิสก์ตามตารางหน้า จากนั้นจึงโหลดหน้าใหม่ทับลงไป
•แก้ไขข้อมูลในตารางหน้าของทั้งของหน้าที่ถูกเขียนทับและหน้าที่โหลดเข้าไปใหม่

การสับเปลี่ยนหน้า (Page Replacement)

•เมื่อเกิดความผิดพร่องของหน้าในระบบหน้า และหน่วยความจำไม่มีหน้าใดว่างอยู่เลย
•ก่อนที OS จะโหลดเอาหน้าใหม่เข้ามาในหน่วยความจำนั้น OS ต้องตัดสินใจก่อนว่าควรจะเลือกหน้าใดเพื่อที่จะวางหน้าใหม่ทับลงไป
•สิ่งที่ OS ใช้ในการตัดสินใจเลือกหน้าเรียกว่า การสับเปลี่ยนหน้า Page Replacement หรือ
ยุทธวิธีการแทนที่(replacement strategy)

การสับเปลี่ยนหน้ามีวิธีการ 5 วิธีดังนี้

–การสับเปลี่ยนหน้าแบบสุ่ม (Random) ทุกหน้ามีโอกาสถูกเลือกเท่ากันหมด
–การสับเปลี่ยนหน้าแบบมาก่อนออกก่อน (First in First out :FIFO)
–การสับเปลี่ยนหน้าแบบหน้าที่ถูกใช้น้อยที่สุดออกก่อน (Not frequently used :NFU)
–การสับเปลี่ยนหน้าแบบหน้าใดที่ไม่ถูกใช้นานที่สุดออกก่อน (Least recently used :LRU)
–การสับเปลี่ยนหน้าแบบหน้าใดไม่ได้ถูกใช้งานออกก่อน (Not recently used :NUR)

การแปลงแอดเดรสในระบบ Segment

•หมายเลขหน้าจากแอดเดรสเสมือนถูกส่งเข้าไปตรวจสอบในตารางที่เรียกว่า ตารางหน้าแบบสาระ(associative page table)พร้อมกันทุกช่อง
•จะได้ค่าแอดเดรสเริ่มต้นของหน้าในหน่วยความจำจริงที่เก็บหน้านี้เอาไว้ออกมาทันที
•แอดเดรสที่ได้นี้ก็จะนำไปบวกดีสเพลซเมนต์ผลลัพธ์ที่ได้ก็คือแอดเดรสจริงในหน่วยความจำ

ตารางหน้าแบบสาระ(associative page table)

หน่วยความจำเสมือนระบบเซกเมนต์(Segment System)




•มีลักษณะการทำงานคล้ายกับระบบหน้า (Page System) ต่างกันตรงที่ขนาดของบล็อกไม่จำเป็นต้องเท่ากัน

•ตารางเซกเมนต์ (Segment table) จะมีคอลัมน์มากกว่าตารางหน้าอยู่ 1 คอลัมน์ใช้เก็บขนาดของเซกเมนต์นั้นไว้ เพื่อให้ OS ทราบว่าแต่ละเซกเมนต์มีขนาดเท่าใด

•การอ่านหรือเขียนข้อมูลจากหน่วยความจำรองและการหาเนื้อที่ในหน่วยความจำจริงจะกระทำตามขนาดของเซกเมนต์ เช่นถ้าเซกเมนต์มีขนาด 5 Kbytes การโหลดจากดิสก์ต้องโหลดข้อมูลขึ้นมา 5 Kbytes ในขณะเดียวกันก็ต้องหาเนื้อที่ว่างในหน่วยความจำที่มีขนาด 5 Kbytes ด้วยเช่นกัน

•การผสมเอาระบบหน้าและเซกเมนต์เข้าด้วยกันทำให้ประสิทธิภาพการทำงานของระบบดีขึ้น 

•ระบบผสมนี้ แอดเดรสเสมือนจะแบ่งออกเป็น 3 ส่วน คือ หมายเลขหน้าเซกเมนต์ หมายเลขหน้า และดีส

เพลซเมนต์ 

•นำหมายเลขเซกเมนต์ (S)ของแอดเดรสเสมือนไปหาแอดเดรสของตารางหน้าที่เก็บอยู่ในตารางเซกเมนต์ 

•เมื่อทราบว่าตารางหน้าอยู่ที่ใดในหน่วยความจำแล้ว 

•ใช้หมายเลขหน้า P เพื่อหาแอดเดรสของหน้า P’ในหน่วยความจำ 

• นำค่าแอดเดรสนี้บวกกับดีสเพลซเมนต์ก็จะได้แอดเดรสจริงในหน่วยความจำ

1.สมมุติว่าโปรเซสหนึ่งมี 3 เซกเมนต์ (0-2) 

2.เซกเมนต์ 0 และ 1 มี 5 หน้า และเซกเมนต์ 2 มี 10 หน้า แต่ละหน้ามีขนาด 100 ไบต์ (00-99) ดังนั้นดีสเพลซเมนต์เป็นเลข 2 หลัก 

3.สมมติว่าต้องการแปลงแอดเดรสเสมือน 1490 เป็นแอดเดรสจริง 

4.หมายเลขเซกเมนต์คือ 1 หมายเลขหน้าคือ 4 ดีสเพลซเมนต์คือ 90

5. ขั้นแรกอ่านค่าที่เก็บไว้ในช่อง 1 ของตารางเซกเมนต์ ได้ค่า 900 หมายความว่าตารางหน้าของเซกเมนต์ 1 อยู่ที่แอดเดรส 900

6. ต่อมาตรวจสอบค่าในช่องที่ 4 ของตารางหน้าที่แอดเดรส 900 เพื่อหาดูว่าหน้า 4 ของเซกเมนต์ 1 เก็บอยู่ที่ใดในหน่วยความจำ

7. เมื่อได้ค่าแอดเดรสหน้าในหน่วยความจำแล้ว (500)ก็นำไปบวกกับดีสเพลซเมนต์ก็จะได้ค่าแอดเดรสจริงในหน่วยความจำ คือ 590

ยุทธวิธีการเฟตซ์

•ยุทธวิธีการเฟตซ์ (Fetch Strategy) หมายถึงการโหลดหน้าหรือเซกเมนต์จากดิสก์เข้าไปในหน่วยความจำ แบ่งออกได้เป็น 2 วิธี คือ

–การเฟตซ์แบบต้องการ (demand fetch) OS จะโหลดเฉพาะหน้าหรือเซกเมนต์ ที่ต้องการใช้เท่านั้นเข้าไปในหน่วยความจำ

–การเฟตซ์แบบคาดเดา (anticipate fetch) จะมีการคาดเดาว่าหน้าหรือ เซกเมนต์ไหนจะถูกใช้เป็นหน้าหรือเซกเมนต์ต่อไป และจะโหลดหน้าหรือเซกเมนต์นั้นเข้าไปไว้ในหน่วยความจำล่วงหน้า (ก่อนเกิดการใช้งานจริง)ทำให้โปรแกรมทำงานได้เร็วขึ้น

ลำดับชั้นของหน่วยความจำ

•ระบบหน่วยความจำเสมือน สามารถทำให้ผู้ใช้ใช้หน่วยความจำขนาดใหญ่กว่าหน่วยความจำจริงได้ ก็เพราะอาศัยการเก็บข้อมูล(หรือโปรแกรม)ไว้ในหน่วยความจำรอง ลักษณะการเคลื่อนย้ายข้อมูลจะมีการส่งไปมาระหว่างหน่วยความจำรอง กับหน่วยความจำหลัก ลักษณะเช่นนี้เรียกว่าหน่วยความจำ 2 ระดับ หมายถึงว่าข้อมูลมีการขนย้ายจากหน่วยความจำประเภทหนึ่งไปยังหน่วยความจำอีกประเภทหนึ่ง

ลำดับชั้นของหน่วยความจำ

•มีการพัฒนาหน่วยความจำให้เป็นลำดับขั้นมากกว่า 1 หรือ 2 ระดับ
•หน่วยความจำแคช(cache memory) จึงได้ถูกพัฒนาขึ้นมาใช้งาน แคชมีความเร็วกว่าหน่วยความจำแรมหลายเท่า แคชจะอยู่ระหว่างซีพียูกับหน่วยความจำหลัก
•เมื่อซีพียูต้องการข้อมูล
–ซีพียูกำหนดตำแหน่งของข้อมูลที่ต้องการด้วยแอดเดรส ค่าแอดเดรสนี้จะถูกนำไปตรวจสอบในแคชด้วยความเร็วสูง
–ถ้าในแคชมีข้อมูลในตำแหน่งที่บ่งโดยแอดเดรสซีพียูก็จะได้รับข้อมูลในแอดเดรสนั้นจากแคชทันที
–แต่ถ้าไม่มีข้อมูลนั้นจะถูกส่งมาจากหน่วยความจำหลักมาเก็บลงในแคชก่อนแล้วค่อยส่งไปให้ซีพียู 

•การขนย้ายข้อมูลระหว่างแคชกับแรม
–มีลักษณะการทำงานเหมือนกับการขนย้ายข้อมูลระหว่างดิสก์กับแรมในระบบหน่วยความจำเสมือน 

•ความแตกต่างกันระหว่างแคชกับแรม
–ในการขนย้ายข้อมูลเป็นไปโดยวงจรทางฮาร์ดแวร์ ไม่มีส่วนเกี่ยวข้องกับโปรแกรมใดๆทั้งสิ้น(รวมทั้ง OS เองด้วย)ซีพียูบางตัวถูกสร้างขึ้นโดยมีแคชติดมาด้วย ทำให้การทำงานของซีพียูมีความเร็วสูงขึ้น
•ระบบหน่วยความจำ 3 ระดับ โดยใช้ Cache

 

แหล่งที่มาของข้อมูล

http://www.chantra.sru.ac.th/OS.html