บทที่ 5 ระบบหน่วยความจำเสมือน
จัดทำโดย นายพัทธนันท์ อุรัตน์ รหัสนักศึกษา 6031280059
ระบบหน่วยความจำเสมือน
(Virtual Memory)
ประเภทของการจัดการหน่วยความจำ
การจัดการหน่วยความจำ
ระบบหน่วยความจำเสมือน (Virtual Memory)
การจัดการหน่วยความจำสามารถแบ่งออกเป็น
2 ประเภทใหญ่ ๆ
–ระบบหน่วยความจำจริง
ขนาดของโปรแกรมจะต้องไม่ใหญ่กว่าขนาดของหน่วยความจำที่มีอยู่ ลบด้วยขนาดของหน่วยความจำที่เป็นส่วนของ OS
–ระบบหน่วยความจำเสมือน
ขนาดของโปรแกรมจะมีขนาดเท่าใดก็ได้
ระบบหน่วยความจำเสมือน (Virtual Memory)
หน่วยความจำเสมือนมีขนาดใหญ่กว่าหน่วยความจำจริง
แนวคิดของหน่วยความจำเสมือน
•ผู้เขียนโปรแกรมหรือผู้ใช้จะไม่ถูกจำกัดในเรื่องของขนาดของหน่วยความจำอีกต่อไป
•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)
•ระบบหน่วยความจำเสมือนจึงแบ่งได้เป็น
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)
มีขนาด 1 Kbyte = 1,000 Byte = 103 Byte
•ต้องการรันโปรแกรม
1000 Kbyte
ดังนั้นโปรแกรมจะถูกแบ่งออกเป็น 1000
หน้า (1000 Page) ดังรูป
•โปรแกรมของผู้ใช้ไม่ว่าจะมีขนาดใหญ่เท่าใด
จะต้องถูกเก็บอยู่ในหน่วยความจำรอง ซึ่งโดยส่วนมากได้แก่ ดิสก์
เนื่องจากมีความจุสูง
•เมื่อผู้ใช้สั่งรันโปรแกรม
OS จะโหลดเอาโปรแกรมจากดิสก์เข้าไปในหน่วยความจำครั้งละ
1 หน้า นั่นคือ 1 หน้าในโปรแกรมก็จะเข้าไปใช้เนื้อที่ในหน่วยความจำ 1 หน้าเช่นกัน
•เมื่อโปรแกรมหนึ่งครอบครองหน้าใดในหน่วยความจำแล้ว
โปรแกรมอื่นจะใช้หน้านั้นอีกไม่ได้
•โปรแกรมจะครอบครองหน่วยความจำจริงเป็นจำนวนเต็มของหน้า
•ดังนั้นต้องมีวิธีการแปลงแอดเดรสจากแอดเดรสเสมือนเป็นแอดเดรสจริง
การแปลงแอดเดรสในระบบหน้า
•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 (แสดงว่าเก็บอยู่ในหน่วยความจำจริง)
กรณีข้อมูลไม่ได้อยู่ในหน่วยความจำจริง (อยู่ในหน่วยความจำสำรอง)
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)
การสับเปลี่ยนหน้า (Page Replacement)
•การสับเปลี่ยนหน้ามีวิธีการ
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)
การแปลงส่งแบบผสมระหว่างแบบสาระและแบบตรง
(combined associative/direct
mapping)
หน่วยความจำเสมือนระบบเซกเมนต์(Segment System)
•มีลักษณะการทำงานคล้ายกับระบบหน้า
(Page System) ต่างกันตรงที่ขนาดของบล็อกไม่จำเป็นต้องเท่ากัน
•ตารางเซกเมนต์
(Segment table) จะมีคอลัมน์มากกว่าตารางหน้าอยู่
1 คอลัมน์ใช้เก็บขนาดของเซกเมนต์นั้นไว้ เพื่อให้ OS
ทราบว่าแต่ละเซกเมนต์มีขนาดเท่าใด
•การอ่านหรือเขียนข้อมูลจากหน่วยความจำรองและการหาเนื้อที่ในหน่วยความจำจริงจะกระทำตามขนาดของเซกเมนต์
เช่นถ้าเซกเมนต์มีขนาด 5 Kbytes
การโหลดจากดิสก์ต้องโหลดข้อมูลขึ้นมา
5 Kbytes ในขณะเดียวกันก็ต้องหาเนื้อที่ว่างในหน่วยความจำที่มีขนาด
5 Kbytes
ด้วยเช่นกัน
•ระบบจะแบ่งหน่วยความจำออกเป็นหน้าที่มีขนาดเท่ากัน
•ในโปรแกรมของผู้ใช้
จะถูกแบ่งออกเป็นเซกเมนต์
•ภายในเซกเมนต์จะถูกแบ่งออกเป็นหลายๆหน้า
•ดังนั้นขนาดของเซกเมนต์จะเป็นจำนวนเท่าของหน้า
•แต่ละเซกเมนต์ของโปรแกรมไม่จำเป็นต้องอยู่เรียงกันในหน่วยความจำ
•แต่ละหน้าในเซกเมนต์เดียวกันก็ไม่จำเป็นต้องอยู่เรียงติดกันในหน่วยความจำจริง
•การผสมเอาระบบหน้าและเซกเมนต์เข้าด้วยกันทำให้ประสิทธิภาพการทำงานของระบบดีขึ้น
•ระบบผสมนี้
แอดเดรสเสมือนจะแบ่งออกเป็น 3 ส่วน
คือ หมายเลขหน้าเซกเมนต์ หมายเลขหน้า และดีสเพลซเมนต์
•
ยุทธวิธีการเฟตซ์
•ยุทธวิธีการเฟตซ์ (Fetch Strategy) หมายถึงการโหลดหน้าหรือเซกเมนต์จากดิสก์เข้าไปในหน่วยความจำ
แบ่งออกได้เป็น 2 วิธี คือ
–การเฟตซ์แบบต้องการ
(demand fetch)
OS จะโหลดเฉพาะหน้าหรือเซกเมนต์
ที่ต้องการใช้เท่านั้นเข้าไปในหน่วยความจำ
–การเฟตซ์แบบคาดเดา
(anticipate
fetch)
จะมีการคาดเดาว่าหน้าหรือ เซกเมนต์ไหนจะถูกใช้เป็นหน้าหรือเซกเมนต์ต่อไป
และจะโหลดหน้าหรือเซกเมนต์นั้นเข้าไปไว้ในหน่วยความจำล่วงหน้า (ก่อนเกิดการใช้งานจริง)ทำให้โปรแกรมทำงานได้เร็วขึ้น
ลำดับชั้นของหน่วยความจำ
•ระบบหน่วยความจำเสมือน
สามารถทำให้ผู้ใช้ใช้หน่วยความจำขนาดใหญ่กว่าหน่วยความจำจริงได้
ก็เพราะอาศัยการเก็บข้อมูล(หรือโปรแกรม)ไว้ในหน่วยความจำรอง
ลักษณะการเคลื่อนย้ายข้อมูลจะมีการส่งไปมาระหว่างหน่วยความจำรอง
กับหน่วยความจำหลัก ลักษณะเช่นนี้เรียกว่าหน่วยความจำ
2
ระดับ
หมายถึงว่าข้อมูลมีการขนย้ายจากหน่วยความจำประเภทหนึ่งไปยังหน่วยความจำอีกประเภทหนึ่ง
•หน่วยความจำแคช(cache memory) จึงได้ถูกพัฒนาขึ้นมาใช้งาน แคชมีความเร็วกว่าหน่วยความจำแรมหลายเท่า แคชจะอยู่ระหว่างซีพียูกับหน่วยความจำหลัก
•เมื่อซีพียูต้องการข้อมูล
–ซีพียูกำหนดตำแหน่งของข้อมูลที่ต้องการด้วยแอดเดรส ค่าแอดเดรสนี้จะถูกนำไปตรวจสอบในแคชด้วยความเร็วสูง
–ถ้าในแคชมีข้อมูลในตำแหน่งที่บ่งโดยแอดเดรสซีพียูก็จะได้รับข้อมูลในแอดเดรสนั้นจากแคชทันที
–แต่ถ้าไม่มีข้อมูลนั้นจะถูกส่งมาจากหน่วยความจำหลักมาเก็บลงในแคชก่อนแล้วค่อยส่งไปให้ซีพียู
•การขนย้ายข้อมูลระหว่างแคชกับแรม
–มีลักษณะการทำงานเหมือนกับการขนย้ายข้อมูลระหว่างดิสก์กับแรมในระบบหน่วยความจำเสมือน
•ความแตกต่างกันระหว่างแคชกับแรม
–ในการขนย้ายข้อมูลเป็นไปโดยวงจรทางฮาร์ดแวร์ ไม่มีส่วนเกี่ยวข้องกับโปรแกรมใดๆทั้งสิ้น(รวมทั้ง OS เองด้วย)ซีพียูบางตัวถูกสร้างขึ้นโดยมีแคชติดมาด้วย ทำให้การทำงานของซีพียูมีความเร็วสูงขึ้น
ลำดับชั้นของหน่วยความจำ
•ระบบหน่วยความจำ 3 ระดับ โดยใช้ Cache
Quiz
1.การจัดการหน่วยความจำเสมือนกับหน่วยความจำหลักแตกต่างกันอย่างไร
2.จงเปรียบเทียบการทำหน่วยความจำเสมือนระบบหน้าและหน่วยความจำเสมือนระบบเซกเมนต์
3.นักศึกษาคิดว่าทำไมจึงต้องทำหน่วยความจำเสมือน4.หน่วยความจำ
cache มีประโยชน์อย่างไร
5.
ระบบการแบ่งหน่วยความจำเสมือนระบบ page
กับ ระบบ Segment
แตกต่างกันอย่างไร
6.
การแปลงส่งแอดเดรส address Mapping คืออะไร7.
การสับเปลี่ยนหน้ามีกี่แบบอะไรบ้าง8.
ระบบหน่วยความจำแบบ 2 ระดับกับ 3 ระดับแตกต่างกันอย่างไร9.
แอดเดรสเสมือนที่
123456 มีความหมายอย่างไร10.
จงอธิบายภาพต่อไปนี้
อ้างอิง https://sites.google.com/site/operatingsytemsyvc/hnwy-khwam-ca-semuxn
http://www.chantra.sru.ac.th/OS.html
ความคิดเห็น
แสดงความคิดเห็น