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

Motivations for Virtual Memory

  • ใช้ DRAM ทางกายภาพเป็นแคชสำหรับดิสก์
พื้นที่ที่อยู่ของกระบวนการสามารถเกินขนาดหน่วยความจำทางกายภาพ
ผลรวมของพื้นที่ที่อยู่ของกระบวนการหลายเกินทางกายภาพหน่วยความจำ
  • จัดการหน่วยความจำลดความซับซ้อน
มีถิ่นที่อยู่หลายกระบวนการในหน่วยความจำ
*แต่ละกระบวนการที่มีอยู่ของตัวเอง
เท่านั้น "งาน" รหัสและข้อมูลที่เป็นจริงในความทรงจำ
*จัดสรรหน่วยความจำมากขึ้นในการดำเนินการตามที่จำเป็น
  • Provide Protection
หนึ่งกระบวนการที่ไม่สามารถยุ่งเกี่ยวกับคนอื่น
*เพราะพวกเขาทำงานอยู่ในพื้นที่ที่แตกต่างกัน
กระบวนการผู้ใช้ไม่สามารถเข้าถึงข้อมูลได้รับการยกเว้น
*ส่วนต่าง ๆ ของช่องว่างอยู่มีสิทธิ์ที่แตกต่างกัน

Possibility of Thrashing

  • เพื่อรองรับกระบวนการมากที่สุดเท่าที่เป็นไปได้เพียงไม่กี่หน้าของแต่ละขั้นตอนจะถูกเก็บไว้ในหน่วยความจำ
  • แต่หน่วยความจำอาจจะเต็มเมื่อระบบปฏิบัติการนำหน้าหนึ่งในมันต้องสลับชิ้นหนึ่งออกมา
  • ระบบปฏิบัติการไม่ต้องสลับออกหน้าของกระบวนการก่อนที่หน้าเป็นสิ่งจำเป็น
  • ถ้ามันทำอย่างนี้บ่อยเกินไปนี้นำไปสู่thrashing:
ประมวลผลใช้เวลาส่วนใหญ่สลับหน้าเว็บของตนค่อนข้างกว่าการดำเนินการคำแนะนำของผู้ใช้

Process Execution(การดำเนินการกระบวนการ)

  • ระบบปฏิบัติการที่จะนำเข้ามาในหน่วยความจำเพียงไม่กี่หน้าของโปรแกรม (รวมถึงจุดเริ่มต้นของมัน)
  • รายการตารางแต่ละหน้าจะมีบิตปัจจุบัน (P บิต) ที่ถูกตั้งค่าเฉพาะในกรณีที่หน้าที่เกี่ยวข้องอยู่ในหน่วยความจำหลัก
ชุดถิ่นที่อยู่เป็นส่วนหนึ่งของกระบวนการที่อยู่ในหน่วยความจำหลักที่
  • ข้อยกเว้น (ผิดหน้า) จะเพิ่มขึ้นโดย MMU เมื่ออ้างอิงหน่วยความจำที่อยู่บนหน้าไม่ได้อยู่ในหน่วยความจำหลัก (กล่าวคืออยู่ในชุด Non-resident)
  • OS วางกระบวนการในสถานะที่ถูกบล็อค

แน่นอนบันทึกสถานะกับ PCB ที่สอดคล้องกัน
  • ปัญหา OS ดิสก์ I / O อ่านขอให้นำเข้ามาในหน่วยความจำหลักหน้าอ้างอิงกับ
  • กระบวนการก็คือการส่งไปทำงานในขณะที่ดิสก์ I / O ที่จะเกิดขึ้น
  • ขัดจังหวะออกเมื่อดิสก์ I / O เสร็จสมบูรณ์

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

Sparse Address Space


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



                                                                       Disk (Swap Area)

Linux/x86 Process Memory Image

วิธีจัดหน่วยความจำเสมือนของLinux

  • PGD:

ที่อยู่ไดเรกทอรีหน้า
  • vm_prot:

การอ่าน / เขียนสิทธิ์สำหรับพื้นที่นี้
  • vm_flags

ที่ใช้ร่วมกันกับคนอื่น ๆ กระบวนการหรือเอกชนที่จะ กระบวนการนี้

Linux Page Fault Handling(หน้าการจัดการความผิดพลาด)

  • เป็น VA กฎหมายหรือไม่

กล่าวคือมันมีอยู่ในพื้นที่กำหนดโดย vm_area_struct?
ถ้าไม่แล้วส่งสัญญาณการแบ่งส่วนการละเมิด (เช่น.,(1)read )
  • คือการดำเนินการตามกฎหมาย?

กล่าวคือสามารถกระบวนการ อ่าน / เขียนพื้นที่นี้หรือไม่?
ถ้าไม่แล้วส่งสัญญาณ การป้องกันการละเมิด (เช่น.,(2)read  )
  • ถ้าตกลงจัดการกับความผิด

เช่น (3)write)

Support Needed for Virtual Memory(การสนับสนุนที่จำเป็นสำหรับหน่วยความจำเสมือน)

  • ฮาร์ดแวร์จัดการหน่วยความจำจะต้องสนับสนุนเพจ
  • ระบบปฏิบัติการจะต้องสามารถที่จะจัดการกับการเคลื่อนไหวของหน้าระหว่างหน่วยความจำรองและหน่วยความจำหลัก
  • ก่อนอื่นเราจะหารือเกี่ยวกับฮาร์ดแวร์และโครงสร้างการควบคุม; จากนั้นขั้นตอนวิธีการที่ใช้ระบบปฏิบัติการ

Paging

  • โดยปกติแต่ละขั้นตอนมีตารางเพจของตัวเอง
  • รายการตารางแต่ละหน้าจะมีบิตปัจจุบันpresent bit (P bit) เพื่อบ่งชี้ว่าหน้าอยู่ในหน่วยความจำหลักหรือไม่

ถ้ามันอยู่ในหน่วยความจำหลักรายการมีจำนวนเฟรมของหน้าเว็บที่เกี่ยวข้องในหน่วยความจำหลัก
ถ้ามันไม่ได้อยู่ในหน่วยความจำหลักรายการอาจมีอยู่ของหน้าเว็บที่บนดิสก์หรือหมายเลขหน้าอาจจะใช้ดัชนีตารางอื่น (มักจะอยู่ในแผ่น PCB) เพื่อให้ได้ที่อยู่ของหน้าบนดิสก์ว่า
  • บิตการปรับเปลี่ยน modified bit (M bit) ระบุว่าหน้ามีการเปลี่ยนแปลงตั้งแต่มันถูกที่แล้วโหลดลงในหน่วยความจำหลัก
หากไม่มีการเปลี่ยนแปลงที่ได้รับการทำหน้าไม่ได้จะต้องมีการเขียนไปยังดิสก์เมื่อจะต้องมีการสลับออก
  • บิตการควบคุมอื่น ๆ อาจจะนำเสนอการป้องกันหากมีการจัดการในระดับเพจ
อ่านอย่างเดียว / อ่านเขียนบิต
ระดับการป้องกันบิต: หน้าเคอร์เนลหรือหน้าผู้ใช้ (บิตมากขึ้นจะใช้เมื่อประมวลผลสนับสนุนมากกว่า 2 ระดับการป้องกัน)

P6 Page Table Entry

Page base address: 20 บิตที่สำคัญที่สุดของหน้าทางกายภาพ ที่อยู่ (หน้ากองกำลังจะเป็น 4 กิโลไบต์ชิด)
Avail: สามารถเขียนโปรแกรมระบบ
G: หน้าทั่วโลก (ไม่ได้ขับไล่จาก TLB งานสวิทช์)
D: สกปรก (ที่กำหนดโดย MMU ในการเขียน)
A: เข้าถึงได้ (กำหนดโดย MMU ในการอ่านและเขียน)
CD: แคชปิดการใช้งานหรือเปิดใช้งาน
WT: เขียนผ่านหรือเขียนกลับนโยบายแคชสำหรับเพจนี้
U / S: ผู้ใช้ / ผู้บังคับบัญชา
R / W: การอ่าน / เขียน
P: หน้าอยู่ในหน่วยความจำกายภาพ (1) หรือไม่ (0)

TLB and Virtual Memory

  • ป.ร. ให้ไว้เป็นที่อยู่ตรรกะประมวลผลตรวจสอบแบบ TLB
  • ถ้ารายการตารางเพจที่เป็นปัจจุบัน (ตี) จำนวนเฟรมถูกดึง และจริง (ทางกายภาพ) ที่อยู่จะเกิดขึ้น
  • ถ้ารายการตารางหน้าจะไม่พบใน TLB (พลาด) หน้าจำนวนที่ใช้ในการดัชนีตารางหน้ากระบวนการ
ถ้าบิตในปัจจุบันมีการตั้งค่าแล้วกรอบที่สอดคล้องกันมีการเข้าถึง
ถ้าไม่ผิดหน้าออกเพื่อนำมาในหน้าอ้างอิงในหน่วยความจำหลัก
  • TLB มีการปรับปรุงเพื่อรวมรายการหน้าใหม่

Page Tables and Virtual Memory(ตารางหน้าและหน่วยความจำเสมือน)

  • ระบบคอมพิวเตอร์ส่วนใหญ่สนับสนุนพื้นที่ที่อยู่เสมือนมีขนาดใหญ่มาก
 32-64 บิตจะใช้สำหรับที่อยู่ตรรกะ
ถ้า (เท่านั้น) 32 บิตจะถูกนำมาใช้กับหน้า 4KB โต๊ะหน้าอาจจะมี 220 รายการ
  • ตารางหน้าทั้งหมดอาจใช้เวลาถึงหน่วยความจำมากเกินไป ดังนั้นตารางหน้ามักจะเก็บไว้ในหน่วยความจำเสมือนและยัดเยียดให้เพจ
เมื่อกระบวนการที่กำลังทำงานเป็นส่วนหนึ่งของตารางเพจของมันจะต้องอยู่ในหน่วยความจำหลัก (รวมถึงรายการตารางหน้าของหน้าการดำเนินงานในขณะนี้)
จะเกิดอะไรขึ้นถ้ามันไม่ได้อยู่ในหน่วยความจำหลัก?

Page tablesอื่นๆที่ไม่ใช่ไดเรกทอรีจะสลับเข้าและออกตามความจำเป็น

OS Policies for Virtual Memory(นโยบายของOS สำหรับหน่วยความจำเสมือน)

Replacement policy (นโยบายเปลี่ยน): เป็นที่หนึ่งที่จะสลับออกเมื่อไม่มีกรอบที่ไม่ได้ใช้?
Resident set management (การจัดการชุดถิ่นที่อยู่): กระบวนการ C มักจะมี 2 เฟรม?
Cleaning policy(นโยบายการทำความสะอาด): 0 หน้าในแรมจะแตกต่างจากภาพในพื้นที่แลกเปลี่ยน เมื่อการปรับปรุง?
Fetch policy (Fetch นโยบาย):เมื่อ OS เรียก 2 หน้าก็ควรเรียกหน้าอื่น ๆ ใกล้?

Fetch Policy

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

Placement policy(นโยบายการจัดตำแหน่ง)

  • ที่กำหนดในหน่วยความจำที่แท้จริงหน้ากระบวนการอยู่
  • ที่ไหนที่จะวางหน้าไม่เกี่ยวข้องตั้งแต่เฟรมหน่วยความจำทั้งหมดจะเทียบเท่า (ไม่เป็นปัญหา)

Replacement Policy(นโยบายเปลี่ยน)

  • ข้อเสนอกับการเลือกของหน้าในหน่วยความจำจะถูกแทนที่เมื่อหน้าใหม่จะมาใน
  • นี้เกิดขึ้นเมื่อใดก็ตามที่หน่วยความจำเต็ม (ไม่มีกรอบฟรีที่มีอยู่)
  • เกิดขึ้นบ่อยครั้งตั้งแต่ OS พยายามที่จะนำเข้ามาในกระบวนการหน่วยความจำให้มากที่สุดเท่าที่จะสามารถเพิ่มระดับ multiprogramming
  • ไม่ทุกหน้าในหน่วยความจำที่สามารถเลือกเพื่อทดแทน
  • เฟรมบางส่วนจะถูกล็อค (ไม่สามารถเพจหมด):
มากของเมล็ดจะจัดขึ้นในเฟรมล็อคเช่นเดียวกับโครงสร้างการควบคุมที่สำคัญและ I / O บัฟเฟอร์

  • ระบบปฏิบัติการอาจตัดสินใจว่าชุดของหน้าการพิจารณาให้เปลี่ยนควรจะ:

 จำกัด เหล่านั้นของกระบวนการที่ได้รับความเดือดร้อนความผิดหน้า
ชุดของทุกหน้าในกรอบปลดล็อค
  • การตัดสินใจสำหรับการตั้งค่าของหน้าเว็บที่จะได้รับการพิจารณาสำหรับการทดแทนที่เกี่ยวข้องกับresident set management strategy:

วิธีเฟรมหน้าจำนวนมากกำลังจะจัดสรรให้แต่ละขั้นตอน? เราจะพูดถึงเรื่องนี้ในภายหลัง
  • ไม่ว่าสิ่งที่เป็นชุดของหน้าการพิจารณาการเปลี่ยนข้อเสนอreplacement policy(นโยบายการเปลี่ยน)กับขั้นตอนวิธีที่จะเลือกหน้าภายในชุดที่
  • ต้องการขั้นตอนวิธีการที่ก่อให้เกิดอัตราต่ำสุดหน้าผิด
  • ประเมินโดยขั้นตอนวิธีการทำงานบนสตริงโดยเฉพาะอย่างยิ่งของการอ้างอิงหน่วยความจำ (สตริงอ้างอิง) หรือคำสั่งอ้างอิงหน้าและการคำนวณจำนวนผิดหน้าและเปลี่ยนหน้าในสตริงที่
  • ในตัวอย่างทั้งหมด
สตริงอ้างอิงคือ 2, 3, 2, 1, 5, 2, 4, 5, 3, 2, 5, 2
ขนาดชุดที่มีถิ่นที่อยู่ (เช่นจำนวนเฟรม) คือ 3

  • โดยทั่วไปเป็นตัวเลขของการเพิ่มขึ้นของเฟรมจำนวนหน้าหยดความผิดพลาด

Note on Counting Page Faults(หมายเหตุนับผิดหน้า)



  • เมื่อหน่วยความจำที่ว่างเปล่าในแต่ละหน้าใหม่ที่เรานำมาเป็นผลมาจากความผิดพลาดหน้า
  • เพื่อประโยชน์ในการเปรียบเทียบขั้นตอนวิธีการที่แตกต่างกันเราจะไม่นับความผิดพลาดเหล่านี้เริ่มต้นหน้า

เพราะจำนวนเหล่านี้จะเหมือนกันสำหรับขั้นตอนวิธีการทั้งหมด

  •  แต่ในทางตรงกันข้ามกับสิ่งที่จะปรากฏในตัวเลขเหล่านี้อ้างอิงเริ่มต้นจริงๆการผลิตผิดหน้า

Replacement Policy


  • เราจะศึกษานโยบายการเปลี่ยนสี่:

ที่เหมาะสม
 LRU (ใช้น้อยที่สุดเมื่อเร็ว ๆ นี้)
 FIFO (ครั้งแรกในครั้งแรกออก)
นาฬิกา

                  Comparison
  Performance  to implement
Optimal Optimal Impossible
LRU Near optimal Expensive
FIFO Not good Simple
Clock Good OK

The Optimal Policy(นโยบายที่เหมาะสม)

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

The LRU Policy

  • แทนที่หน้าเว็บที่ยังไม่ได้รับการอ้างอิงเวลาที่ยาวที่สุด
ตามหลักการของถิ่นนี้ควรจะเป็นหน้าอย่างน้อยน่าจะถูกอ้างถึงในอนาคตอันใกล้
ดำเนินการเกือบทั้งเป็นนโยบายที่ดีที่สุด
ตัวอย่าง:  กระบวนการของ5หน้าเว็บที่มีระบบปฏิบัติการที่แก้ไขขนาดชุดที่resident set size to 3

Implementation of the LRU Policy(การดำเนินการตามนโยบายอาร์)

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

The FIFO Policy (นโยบาย FIFO)

  • แทนที่หน้าเว็บที่ได้รับในหน่วยความจำที่ยาวที่สุด
  • ง่ายที่จะใช้
ขนมกรอบหน้าจัดสรรให้กระบวนการเป็นกันชนกลม (เช่นรายการกลม)
*เมื่อบัฟเฟอร์เต็มหน้าที่เก่าแก่ที่สุดจะถูกแทนที่
ดังนั้นต้องมีเพียงตัวชี้ว่าวงการผ่านกรอบหน้าของกระบวนการ
ผลงานที่ดีไม่ - หน้าแทนที่อาจมีความจำเป็นอีกครั้งเร็ว ๆ นี้
  • หน้าใช้บ่อยมักจะเป็นที่เก่าแก่ที่สุดดังนั้นมันจะเป็น
ซ้ำแล้วซ้ำอีกเพจโดย FIFO

เธรด(Thread)

เธรดคืออะไร

      หน่วยการทำงานของโปรเซส ซึ่งเธรดต้องรันอยู่ในโปรเซสอีกที่หนึ่ง เป็นLightweight process(LWP) ส่วนโปรเซสเป็น Heavyweight process(HWP) เธรดหนึ่งจะต้องประกอบไปด้วยโปรเซสอย่างน้อย 1 ตัวแต่อาจมีมากกว่า เธรดในโปรเซสหนึ่งๆได้ ซึ่งเธรดต่างๆอยู่ภายใต้โปสเซสจะแบ่งกันใช้ทรัพยากรของโปรเซสรวมกันกับเธรดอื่น
      การประมวลผงเธรดแต่ละตัวทำขนาดกันไป คือ กำลังประมวลผลเธรด1 อยู่ก็สามารถประมวลผลเธรดอื่นไปพร้อมกันได้ โดยแต่ละเธรดทำงานในลักษณะเป็นอิสระต่อกัน ไม่เกี่ยวข้องกัน เรียกว่าMultihreading
-Bornคือ สถานะเริ่มต้นของเธรดทุกตัว
-ready(Runnable)เมื่อโปรแกรมสั่งสตารทเธรดให้เริ่มต้นทำงานเธรดจะเปลี่ยนสถานะจาก born เป็น ready เมื่อเธรดพร้อมประมวลผล และ รอคอยการประมวลผลของโปรเซสเซอร์
-Running สถานะเธรดที่ได้รับการประมวลผลจากโปรเซสเซอร์ โดยเธรดที่อยู่ในสถานะreddy และมีความสำคัญมากที่สุดจะได้รับการประมวลผลก่อน
-Deadกรณีที่เธรดได้รับการประมลผลเสร็จสมบูรณ์ กรณีที่เธรดถูกสั่งให้สิ้นสุดการทำงาน เธรดจะถูกเปลี่ยนสถานะจากRunning มาเป็นDeadโดยเมื่อเธรดอยู่สถานะ Dead แล้วทรัพยากรณ์ที่ครองอยู่จะถูกคืนระบบ และเธรดนั้นจะถูกกำจัดออกไปจากระบบ
-Blocked เมื่อเธรดรอคอยการทำงานจากI/Oเช่น การรออ่านข้มูลจากฮาร์ดิสก์ เธรดจะถูกเปลี่ยนสถานะจาก Running มาเป็น Blockedซึ่งเธรดจะยังคงในสถานะนี้จนกว่าการร้องขอการทำงานจากi/oจะเสร็จสมบูรณ์

Process Scheduling

Multiprogramming

  • ในระบบ multiprogramming เราพยายามที่จะเพิ่มการใช้งาน CPUโดยทับซ้อน I / O และกิจกรรม CPU
การทำเช่นนี้ต้องมีการรวมกันของกลไกและนโยบาย
  • เราได้ครอบคลุมกลไก
บริบทเปลี่ยนวิธีการและเมื่อมันเกิดขึ้น
คิวในกระบวนการและขั้นตอนการรัฐ
  • ตอนนี้เราจะดูที่นโยบาย
ซึ่งกระบวนการในการทำงานนานเท่าไหร่ ฯลฯ
  • หน่วยงาน schedulable มักจะเรียกว่างาน
พวกเขาอาจจะเป็นกระบวนการกระทู้, คนแขนดิสก์ การเคลื่อนไหว ฯลฯ

Types of Scheduling

  • การจัดตารางการทำงานที่สองระดับในระบบปฏิบัติการ
การตรวจสอบระดับ multi programming - การจำนวนของงานที่โหลดในหน่วยความจำหลัก
*งานย้ายไป / จากหน่วยความจำมักจะเรียกว่าการแลกเปลี่ยน(swapping)
*ขั้นตอนการคัดเลือกนี้จะดำเนินการโดยกำหนดการระยะยาวหรือกำหนดการหน่วยความจำ
(long-term scheduler , memory scheduler)
-เกิดขึ้นค่อนข้างบ่อย(infrequently)
เพื่อตัดสินใจว่าการทำงานของงานพร้อมที่จะทำงานต่อไปเพื่อรับประกัน "การบริการที่ดี"
*การบริการที่ดีอาจจะเป็นหนึ่งในเกณฑ์ที่แตกต่างกัน
*ขั้นตอนการคัดเลือกนี้จะดำเนินการโดยการจัดตารางเวลาระยะสั้นหรือกำหนดการ CPU 
(short-term scheduler or CPU scheduler)
-เกิดขึ้นค่อนข้างบ่อย(frequently)

CPU Scheduler

  • กำหนดการ CPU เป็นโมดูลที่ปรุงแต่งคิวย้ายงานจากคิวคิว
  • ขั้นตอนวิธีการจัดตารางเวลาที่กำหนดซึ่งการทำงานของงานพร้อมที่จะเลือกที่จะทำงานต่อไปและนานเท่าไหร่
  • กำหนดการจะถูกเรียกเมื่อใดก็ตามที่เหตุการณ์เกิดขึ้นที่อาจนำไปสู่การระงับการงานปัจจุบันหรือที่อาจให้โอกาสในการจองงานที่กำลังทำงานอยู่ในความโปรดปรานของอื่น
 Hardware interrupts
 Exceptions
 System calls

Scheduling Goals(เป้าหมายการจัดตารางเวลา)

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

Scheduling Non-goals(การตั้งเวลาไม่เป้าหมาย)

  • Starvationเป็นสถานการณ์ที่กระบวนการที่ถูกขัดขวางจากการทำให้ความคืบหน้าเพราะบางขั้นตอนอื่น ๆ ที่มีทรัพยากรที่จำเป็นต้องใช้
ทรัพยากรอาจจะเป็น CPU หรือล็อค
  • ความอดอยากโดยปกติจะเป็นผลข้างเคียงของขั้นตอนวิธีการตั้งเวลา
กระบวนการลำดับความสำคัญสูงมักจะป้องกันไม่ให้เป็นกระบวนการที่มีความสำคัญในระดับต่ำจากการทำงานบน CPU
  • Starvation อาจจะเป็นผลข้างเคียงของการประสาน

Characterization of Scheduling Policies(ลักษณะของนโยบายการจัดตารางเวลา)

  • The selection function(ฟังก์ชั่นการเลือก): กำหนดงานในคิวพร้อมเป็นเลือกต่อไปสำหรับการดำเนินการ
  • The decision mode(โหมดการตัดสินใจ): ระบุ instants ในเวลาที่ฟังก์ชั่นการเลือกใช้สิทธิ
 Nonpreemptive
 Preemptive

Characterization of Scheduling Policies(ลักษณะของนโยบายการจัดตารางเวลา)

  • Nonpreemptive
เมื่องานที่อยู่ในสถานะที่ทำงานก็จะดำเนินต่อไปจนถึงจะสิ้นสุดหรือ
-บล็อกตัวเองเพื่อรอ I / O หรือขอบริการระบบปฏิบัติการบางอย่าง
  • Preemptive
ปัจจุบันทำงานงานอาจจะหยุดชะงักและย้ายไปอยู่ที่สถานะพร้อมระบบปฏิบัติการ
การตัดสินใจที่จะยึดเอาเสียก่อนอาจจะดำเนินการ
-เมื่องานใหม่มาถึง (ถูกสร้างขึ้น)
-เมื่อขัดจังหวะเกิดขึ้นที่สถานที่ทำงานที่ถูกปิดกั้นในสถานะพร้อมหรือ
-ตามระยะบนนาฬิกาขัด
ช่วยให้การบริการที่ดีขึ้นตั้งแต่งานคนใดคนหนึ่งไม่สามารถผูกขาด
หน่วยประมวลผลนานมาก

CPU-I/O Burst Cycle

  • เราสังเกตว่างานที่ต้องใช้อื่นของ CPU และ I / O ในแฟชั่นซ้ำ
  • แต่ละรอบประกอบด้วยระเบิด CPU (ปกติ 5 มิลลิวินาที) ตามมาด้วย(โดยปกติจะนานกว่านั้น) I / O ระเบิด
  • งานสิ้นสุดระเบิดซีพียู
  • งาน CPU ที่ถูกผูกไว้:
งานที่ทำงานผมน้อยมาก / O
มีแนวโน้มที่จะมีการระเบิดของ CPU ที่ยาวมาก
  •  I / O งานที่ถูกผูกไว้:
งานที่มีประสิทธิภาพจำนวนมาก I / O
มีแนวโน้มที่จะมีการระเบิดของ CPU สั้น
  • ระเบิดของการใช้งาน CPU สลับกับระยะเวลาของ I / O รอ

 (ก) งาน CPU ที่ถูกผูกไว้
 (ข) I / O งานที่ถูกผูกไว้

Our Running Example to Discuss Various Scheduling Policies(ตัวอย่างการการจัดตารางเวลา)


Job Arrival Time Service Time
1 0 3
2 2 6
3 4 4
4 6 5
5 8 2

  • เวลาบริการ = เวลาประมวลผลรวมที่จำเป็นในหนึ่ง (CPU-I / O ระเบิด) วงจร
  • งานกับเวลาการให้บริการที่มีความยาวงาน CPU ที่ถูกผูกไว้และได้รับการเรียกว่า "งานนาน"

First Come First Served

  • ฟังก์ชั่นการคัดเลือก: งานที่ได้รับการรอที่ยาวที่สุดในคิวพร้อม (เพราะฉะนั้น, FCFS)
  • โหมดการตัดสินใจ: nonpreemptive
  • ง่ายที่จะใช้
  • ใช้เป็นหลักสำหรับพื้นหลังและงานชุด
  • ดำเนินการที่ดีมากสำหรับงานที่ยาวกว่าสำหรับคนที่สั้น
    ตัวอย่าง: การวัดเวลาตอบสนองโดยปกติเวลาการให้บริการ (TQ / Ts)
    • ของชำร่วยงาน CPU ที่ถูกผูกไว้มากกว่า I / O งานที่ถูกผูกไว้

     I / O งานที่ถูกผูกไว้ต้องรอจนกว่างาน CPU ที่ถูกผูกไว้เสร็จสมบูรณ์
    พวกเขาอาจจะต้องรอแม้ในขณะที่ผมของพวกเขา / O จะเสร็จสมบูรณ์ (การใช้อุปกรณ์ที่ไม่ดี)
    เราจะได้เก็บอุปกรณ์ I / O ที่วุ่นวายโดยให้บิตความสำคัญมากขึ้นในการ I / O งานที่ถูกผูกไว้
    • ไม่สามารถยอมรับได้สำหรับระบบแบบโต้ตอบ

    Round Robin

    • ฟังก์ชั่นการคัดเลือก: เช่นเดียวกับ FCFS
    • โหมดการตัดสินใจ: มาตรการ

    งานที่ได้รับอนุญาตให้ทำงานจนกว่าtime slice หรือ quantumได้หมดอายุแล้ว
    แล้วขัดจังหวะนาฬิกาเกิดขึ้นและงานที่ทำงานอยู่บนคิวพร้อม
    • ดีสำหรับงานที่มีความสำคัญเท่าเทียมกัน
    • ใช้กันอย่างแพร่หลายสำหรับผู้ใช้หลายระบบการโต้ตอบและระบบผู้ใช้คนเดียวกับกิจกรรมต่างๆในความคืบหน้า
    • ปัญหาหลักคือความยาวของเวลาชิ้น (หรือควอนตัม):
    เพื่อเพิ่มประสิทธิภาพการตอบสนองแบบโต้ตอบให้ควอนตัมเพียงเล็กน้อยนานกว่าการทำงานร่วมกันโดยทั่วไป
      กล่าวคือควรจะเสร็จสมบูรณ์ภายใน time-slice แรก
      • ถ้าquantumไม่ใหญ่พอที่:

      มากกว่าหนึ่งquantumหมายถึงความล่าช้าไปเรื่อยเพิ่มเติม
      • Short time-slices :

      งานทั้งหมดในคิวรอบโรบินได้รับไปบน CPU ได้อย่างรวดเร็ว
      งานสั้นสมบูรณ์ในหนึ่งไป
      Overheadsจะเพิ่มขึ้นเนื่องจากการเปลี่ยนบริบทบ่อยมากขึ้น
      •  Large time-slices :

      เวลารอบโรบินมีความยาว
      งานบางคนมักจะใช้เวลาของพวกเขาเต็มชิ้น
      Overheadsต่ำ

      *Tooระยะสั้น: สวิทช์มากเกินไปประสิทธิภาพ CPU ต่ำ
      *Tooยาวที่มีประสิทธิภาพสูง แต่เวลาตอบสนองที่ไม่ดี
      • ยังโปรดปรานงาน CPU ที่ถูกผูกไว้

       I / O ที่ถูกผูกไว้ใช้งาน CPU เป็นเวลาน้อยกว่าเวลาควอนตัมและจากนั้นจะถูกปิดกั้นการรอคอยสำหรับ I / O
      วิ่งงาน CPU ที่ถูกผูกไว้สำหรับทุกชิ้นเวลาและใส่กลับเข้าไปในคิวพร้อม (จึงได้รับในด้านหน้าของงานบล็อก)
      • การแก้ปัญหา: โรบินเสมือนจริง

      เมื่อ I / O ได้เสร็จสิ้นการที่งานบล็อกจะถูกย้ายไปคิวเสริมที่ได้รับการตั้งค่าในช่วงคิวพร้อมหลัก
      งานส่งจากคิวเสริมทำงานไม่เกินเวลาควอนตัมพื้นฐานลบใช้เวลาการทำงานตั้งแต่มันได้รับเลือกจากคิวพร้อม

      Queuing for Virtual Round Robin(การจัดคิวสำหรับเสมือน Round Robin)

      Shortest Job First (SJF)

      • ฟังก์ชั่นการคัดเลือก: งานที่มีซีพียูเวลาคาดว่าระเบิดที่สั้นที่สุด

      โหมดการตัดสินใจ: nonpreemptive
       I / O งานที่ถูกผูกไว้จะได้รับเลือกเป็นครั้งแรก
      -เราจำเป็นต้องประเมินเวลาการประมวลผลที่ต้องการ (CPU เวลาระเบิด) สำหรับงานแต่ละงาน

      Estimating the Required CPU Burst(ประมาณ Burst CPU ต้องใช้)

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

      ให้ค่าเฉลี่ยของการทำงานของสิ่งที่ถูกนำมาใช้ในการระเบิดก่อนหน้าของการใช้งาน CPU:
       Sn+1 = (  Ti ) / n , (i = 1, 2, …, n)

      เพื่อหลีกเลี่ยงการคำนวณผลรวมทั้งหมดเราสามารถเขียนนี้เช่น:
       Sn+1 = Tn/n + Sn*(n-1)/n

      Tn = actual length of nth CPU burst (ระยะเวลาที่เกิดขึ้นจริงของCPU burst ที่ n)
      Sn+1 = predicted value for the next CPU burst(คาดการณ์ค่าสำหรับ CPU burst ต่อไป)

       แต่นี้รวมกันจะช่วยให้นูนน้ำหนักเท่ากับแต่ละกรณี
       แต่กรณีที่ผ่านมามีแนวโน้มที่จะสะท้อนให้เห็นถึงพฤติกรรมในอนาคต
      เทคนิคทั่วไปว่าคือการใช้ค่าเฉลี่ยชี้แจง

       Sn+1 = Tn + (1-)*Sn , 0 <  < 1

      โดยการขยายสมการนี้เราจะเห็นว่าน้ำหนักของอินสแตนซ์ที่ผ่านมาลดลงชี้แจง
       Sn+1 = Tn + (1-)Tn-1 + ... + (1-)i Tn-i
                       + ... + (1-)n S1

      S1 = predicted value of 1st instance; not calculated (usually set to 0 to give priority to new jobs) 
               คาดการณ์มูลค่าของเช่น 1; ไม่ได้คำนวณ(โดยปกติจะตั้งค่าเป็น 0 ที่จะให้ความสำคัญกับงานใหม่)

      Exponentially Smoothing Coefficients(ค่าสัมประสิทธิ์ Smoothing)

      • นี่ S1 = 0 จะให้ความสำคัญในการงานใหม่
      • ชี้แจงเฉลี่ยติดตามการเปลี่ยนแปลงในพฤติกรรมของงานเร็วกว่าค่าเฉลี่ยที่เรียบง่าย
      • มีวัตถุประสงค์เพื่อลดอคติที่มีต่องานนาน
      • บรรลุเวลาตอบสนองที่ดีขึ้นกว่า FCFS โดยเฉลี่ย
      • ความเสี่ยงบางส่วนของความอดอยากงานอีกต่อไป (ถ้ามีอุปทานคงที่ของงานที่สั้นกว่า)
      • ไม่เหมาะในสภาพแวดล้อมที่ใช้ร่วมกันเวลาเนื่องจากการขาดการใบจอง
      • ปริยายประกอบด้วยลำดับความสำคัญ: งานที่สั้นที่สุดจะได้รับการตั้งค่า
      • เวลาที่เหลือสั้นเป็นครั้งแรก (SRTF) รุ่นมาตรการของ SJF, penalizes งานโดยตรงอีกต่อไป


      ดีกว่าหันไปรอบ ๆ เวลากว่า SJF
      หมายเหตุ: โหมดการเลือก: งานที่มีอย่างน้อยคาดว่าใช้เวลาที่จะเสร็จสิ้น

      Highest Response Ratio Next(การตอบสนองอัตราส่วนสูงสุดถัดไป)

      • การตอบสนองอัตราส่วนสูงสุดถัดไป (HRRN) มีจุดมุ่งหมายเพื่อลด Tq / Ts (เวลาตอบสนองโดยปกติเวลาการให้บริการ) สำหรับงานแต่ละงาน
      • อัตราส่วนการตอบสนอง = (w + S) / s
      W = เวลาที่รอคอย

      s = เวลาการให้บริการคาดว่า

      เวลาการให้บริการที่คาดว่าจะต้องถูกประเมินอีกครั้ง (เช่นเดียวกับ SJF และ SRTF)
      เวลารอวัดเป็นเวลาผ่านไปเรื่อย

      • ฟังก์ชั่นการเลือก: เลือกงานต่อไปที่มีอัตราการตอบสนองสูงสุดเวลา
      อีกต่อไปรอที่สูงกว่าความสำคัญ
      งานสั้น แต่ได้รับการสนับสนุนงานนานไม่หิว
      ความสมดุลที่ดีในทั้ง
      • โหมดการตัดสินใจ: nonpreemptive ตามที่กำหนดไว้ แต่อาจจะทำให้เป็นมาตรการ STRF
      • ค่าโสหุ้ยในอัตราส่วนเวลาตอบสนอง recomputing

      Priority Scheduling

      • กำหนดลำดับความสำคัญเพื่อให้งานแต่ละงาน
      • งานพร้อมกับความสำคัญสูงสุดจะดำเนินการต่อไป
      • งานวิ่งอาจจะหยุดชะงักหลังจากที่ควอนตัมของ
      • อาจได้รับมอบหมายลำดับความสำคัญแบบไดนามิก
      ลดลงเมื่องานใช้เวลา CPU
      เพิ่มขึ้นเมื่องานรอ I / O
      • บ่อยครั้งที่งานถูกแบ่งออกเป็นหลายคิวขึ้นอยู่กับการจัดลำดับความสำคัญและเรียกโรบินต่อคิว

      Combining Algorithm(รวมขั้นตอนวิธี)

      • การตั้งเวลาสามารถนำมารวม
      มีหลายคิว
      ใช้ขั้นตอนวิธีการที่แตกต่างกันสำหรับแต่ละคิว
      งานย้ายในหมู่คิว
      • ตัวอย่าง
      หลายข้อเสนอแนะคิว (MLFQ) การตั้งเวลา
      จัดตารางเวลาระบบปฏิบัติการยูนิกซ์

      Multilevel Feedback-Queue Scheduling(หลายข้อเสนอแนะการจัดตารางคิว)

      • การตั้งเวลา Preemptive กับลำดับความสำคัญแบบไดนามิก
      • หลายพร้อมที่จะดำเนินการรอคิวลำดับความสำคัญลดลง:
       P(RQ0) > P(RQ1) > ... > P(RQn)
      • งานใหม่จะอยู่ใน RQ0
      • เมื่อพวกเขามาถึงควอนตัมเวลาที่พวกเขาจะอยู่ใน RQ1 ถ้าพวกเขาถึงมันอีกครั้งที่พวกเขาจะอยู่ใน RQ2 ... จนกว่าจะถึง RQn
      • I / O งานที่ถูกผูกไว้จะอยู่ในคิวลำดับความสำคัญสูง งาน CPU ที่ถูกผูกไว้จะลอยลง
      • รีบเลือกสมัครงานสำหรับการดำเนินการใน RQi เฉพาะในกรณีที่ RQi-1 เพื่อ RQ0ที่ว่างเปล่า

      Multilevel Feedback Queues

      • FCFS ใช้ในแต่ละคิวยกเว้นคิวลำดับความสำคัญต่ำสุดที่ Round Robin ถูกนำมาใช้

      Time Quantum for feedback Scheduling


      • ด้วยเวลาควอนตัมคงที่เวลาตอบสนองของงานอีกต่อไปสามารถยืดออกอย่างน่าตกใจ
      • เพื่อชดเชยเราสามารถเพิ่มควอนตัมเวลาตามความลึกของคิว
       Ex: time quantum of RQi = 2i-1

      • งานอีกต่อไปอาจจะยังคงประสบความอดอยาก
      • การแก้ไขที่เป็นไปได้คือการส่งเสริมงานลำดับความสำคัญที่สูงขึ้นหลังจากที่บางเวลา
      ตัวอย่างเช่นช่วยให้งานที่จะเลื่อนขึ้นระดับหนึ่งทุกครั้งที่สมัครใจให้ขึ้น CPU ก่อนที่จะหมดอายุควอนตัม

      Unix Scheduler

      • กำหนดการ Unix ยอมรับใช้ MLFQ
       3-4 ชั้นเรียนทอด ~ 170 ระดับความสำคัญ
      * Timesharing, ระบบ, Real-time, ขัดจังหวะ (Solaris 2)
      • การจัดตารางการจัดลำดับความสำคัญทั่วคิว RR ภายในคิว
      กระบวนการที่มีความสำคัญสูงสุดเสมอทำงาน
      กระบวนการที่มีความสำคัญเดียวกันมีกำหนด RR
      • กระบวนการแบบไดนามิกเปลี่ยนลำดับความสำคัญ
      เพิ่มขึ้นเมื่อเวลาผ่านไปถ้าบล็อกขั้นตอนก่อนที่จะสิ้นสุดของควอนตัม
      ลดลงเมื่อเวลาผ่านไปหากกระบวนการทั้งหมดใช้ควอนตัม

      Motivation of Unix Scheduler

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

      Algorithm Comparison(ขั้นตอนวิธีการเปรียบเทียบ)

      • เป็นที่หนึ่งที่ดีที่สุด?
      • คำตอบขึ้นอยู่กับ:
      ภาระงานระบบ (ตัวแปรมาก)
      การสนับสนุนฮาร์ดแวร์สำหรับรีบ
      น้ำหนักสัมพัทธ์ของเกณฑ์การปฏิบัติงาน (เวลาตอบสนองการใช้งาน CPU, ผ่าน ... )
      วิธีการประเมินผลที่ใช้ (แต่ละคนมีข้อ จำกัด ของมัน ... )
      • ดังนั้นคำตอบขึ้นอยู่กับปัจจัยหลายอย่างเกินไปที่จะให้ใด ๆ ...


      การจัดการหน่วยความจำ (memory management)

      การกำหนดตำแหน่ง (Address Binding)

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

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

      Compile time: ถ้าตำแหน่งหน่วยความจำที่รู้จักกันในเบื้องต้นรหัสแน่นอนสามารถสร้างขึ้น; ต้องคอมไพล์รหัสของการเริ่มต้นที่ตั้งการเปลี่ยนแปลง
      Load time: ต้องสร้างรหัส relocatable ถ้าตำแหน่งหน่วยความจำไม่เป็นที่รู้จักที่รวบรวมเวลา
      Execution time: ผลผูกพันล่าช้าจนเวลาทำงานถ้ากระบวนการสามารถเคลื่อนย้ายระหว่างการดำเนินการจากหน่วยความจำส่วนหนึ่งไปยังอีก ต้องการการสนับสนุนฮาร์ดแวร์สำหรับแผนที่ที่อยู่

      Logical vs. Physical addresses

      • logical addressสร้างขึ้นโดย CPU,
      • physical addressเป็นอยู่เห็นได้จากหน่วยหน่วยความจำ
      • ที่อยู่ตรรกะและทางกายภาพเดียวกันในเวลารวบรวมและโหลดเวลาที่อยู่รูปแบบที่มีผลผูกพัน; logical (virtual) และที่อยู่ทางกายภาพที่แตกต่างกันในการดำเนินการเวลาที่อยู่โครงการที่มีผลผูกพัน
      • อ้างอิงเพื่อlogical addressesที่มีการแปลโดยฮาร์ดแวร์เป็นphysical addresses
      • ขนาดของพื้นที่ที่อยู่ที่โดดเด่นด้วยจำนวนบิตที่มีความจำเป็นที่จะเป็นตัวแทนอยู่ที่ใหญ่ที่สุด
      • บางระบบต้นเช่นDEC PDP-11/70 สนับสนุนพื้นที่ที่อยู่ที่มีขนาดเล็กกว่าหน่วยความจำกายภาพ
      • ด้วยวิธีนี้เป็นกระบวนการที่สามารถเติมให้เต็มพื้นที่ที่อยู่และจะมีห้องพักเพียงพอในหน่วยความจำหลักที่จะถือไว้ทั้งหมด
      • ระบบสมัยใหม่มักจะสนับสนุนทั้ง 32 บิตหรือพื้นที่ที่อยู่ 64 บิตซึ่งมักจะมีขนาดใหญ่กว่าหน่วยความจำกายภาพ
      • ในกรณีนี้เทคนิคที่เรียกว่าหน่วยความจำเสมือนเป็นสิ่งจำเป็น
      • กระบวนการแต่ละคนมีพื้นที่ที่อยู่ของตัวเองเป็นอิสระจากผู้ที่เป็นกระบวนการอื่น ๆ (ยกเว้นในกรณีพิเศษบางอย่างที่กระบวนการต้องการที่จะแบ่งปันพื้นที่อยู่ของพวกเขา)

      Assumption

      • พื้นที่ที่อยู่ของกระบวนการมีขนาดเล็กกว่าที่มีอยู่จริงหน่วยความจำ
      • กระบวนการดำเนินการต้องโหลดทั้งหมดในหน่วยความจำหลัก(ไม่มีหน่วยความจำเสมือน)

      Simple Memory Management

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

      การจัดสรรที่อยู่ติดกัน(Contiguous Allocation)

      • หน่วยความจำหลักมักจะแบ่งออกเป็นสองพาร์ทิชัน
      ระบบปฏิบัติการถิ่นที่มักจะจัดขึ้นในหน่วยความจำน้อยinterrupt vector
      ผู้ใช้กระบวนการจัดขึ้นแล้วในหน่วยความจำสูง
      • กระบวนการที่ผู้ใช้แต่ละคนจะได้รับการจัดสรรว่าหน่วยความจำมากที่สุดเท่าที่จะต้องใช้
      • หลุมในที่สุดจะเกิดขึ้นในหน่วยความจำ
      • ระบบปฏิบัติการเก็บรักษาข้อมูลเกี่ยวกับ:
      พาร์ทิชันจัดสรร
      พาร์ทิชันฟรี (หลุม)
      • ต้องใช้การบดอัดที่จะเปลี่ยนกระบวนการเพื่อให้พวกเขามีความต่อเนื่องกันและหน่วยความจำฟรีทั้งหมดเป็นหนึ่งในบล็อก
      • ใช้ในไอบีเอ็ม OS / MVT (Multiprogramming มีจำนวนตัวแปรของงาน)
      Example

      หลุมปรากฏเป็นกระบวนการที่มีการสร้างและการยกเลิก ในตัวอย่างนี้เรามีทั้งหมด 6M ของหน่วยความจำฟรี แต่ไม่มีภูมิภาคที่อยู่ติดกันมีขนาดใหญ่พอสำหรับกระบวนการใหม่ นี้เรียกว่าการกระจายตัวภายนอก เราจำเป็นต้องดำเนินการบดอัด

      Compaction

      • เป้าหมาย
      เพื่อสับเปลี่ยนหน่วยความจำเนื้อหาที่จะวางหน่วยความจำฟรีทั้งหมด
      ร่วมกันในบล็อกขนาดใหญ่หนึ่ง
      • ความต้องการ
      กระบวนการเป็นแบบไดนามิก relocatable
      • ปัญหา
      ค่าใช้จ่าย
      กลยุทธ์การบดอัดที่เหมาะสมเป็นเรื่องยาก(NP)

      Placement Algorithm(ขั้นตอนวิธีการจัดตำแหน่ง)

      • ใช้ในการตัดสินใจที่บล็อกมีอิสระที่จะจัดสรรให้กับกระบวนการ
      • เป้าหมาย: เพื่อลดการใช้งานของcompaction(เสียเวลา)
      ครั้งแรกพอดี: ใช้บล็อกแรกที่มีขนาดใหญ่พอ
      ถัดไปพอดี: ใช้บล็อกแรกมีขนาดใหญ่พอหลังจากที่ตำแหน่งสุดท้าย
      ที่ดีที่สุดพอดี: ออกจากHOLD

      Comments

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

      Hardware Support for Dynamic Partitioning

      • เมื่อกระบวนการที่ได้รับมอบหมายให้ทำงานลงทะเบียนฐานได้รับเต็มไปด้วยที่อยู่ทางกายภาพเริ่มต้นของกระบวนการ
      • ทะเบียนขีดจำกัด ได้รับเต็มไปด้วยช่วงของที่อยู่ตรรกะ
      • เมื่อญาติที่อยู่ที่พบก็จะถูกลงทะเบียนเมื่อเทียบกับขีดจำกัด;ถ้าถูกต้องก็จะถูกเพิ่มเนื้อหาของฐานลงทะเบียนจะได้รับที่อยู่ทางกายภาพ

      Simple Segmentation

      • แต่ละโปรแกรมจะแบ่งออกเป็นบล็อกที่มีขนาดไม่เท่ากันเรียกว่า กลุ่ม
      • ส่วนเป็นหน่วยตรรกะเช่น:
      1. โปรแกรมหลัก
      2. ขั้นตอน
      3. ฟังก์ชั่น
      4. วิธี
      5. วัตถุ
      6. สแต็ค
      7. อาร์เรย์
      8. local variables
      9. global variables
      10. บล็อกที่พบบ่อย
      11. ตารางสัญลักษณ์
      • การแบ่งกลุ่มให้เป็นความสะดวกสบายในการจัดระเบียบเหตุผลโปรแกรมที่เป็นกลุ่ม (เช่นข้อมูลในส่วนหนึ่งของรหัสในส่วนอื่น)
           การแบ่งกลุ่มจะมองเห็นโปรแกรมเมอร์
      • เมื่อกระบวนการได้รับการโหลดลงในหน่วยความจำส่วนที่แตกต่างกันสามารถอยู่ที่ใดก็ได้
      • แต่ละส่วนจะเต็มไปเต็มไปด้วยคำแนะนำ / ข้อมูล: ไม่มีการกระจายตัวของภายใน
      • มีการกระจายตัวของภายนอก; มันจะลดลงเมื่อใช้กลุ่มเล็ก ๆ

      Logical Address Used in Segmentation

      • ระบบปฏิบัติการรักษาsegment tableสำหรับแต่ละขั้นตอน แต่ละรายการจะประกอบด้วย:
      ฐาน - มีที่อยู่ทางกายภาพเริ่มต้นที่กลุ่มที่อาศัยอยู่ในหน่วยความจำ
      ขีด จำกัด - ระบุความยาวของส่วน (สำหรับการป้องกัน) คำ
      • เมื่อกระบวนการเข้าสู่รัฐวิ่งลงทะเบียน CPU ได้รับเต็มไปด้วยที่อยู่เริ่มต้นของตารางส่วนของกระบวนการ
      • นำเสนอกับที่อยู่ตรรกะ (หมายเลขส่วนชดเชย) = (n, m) ดัชนี CPU (มี n) ตารางส่วนที่จะได้รับที่อยู่ทางกายภาพและเริ่มต้น k ลิตรความยาวของส่วนที่ว่า
      • ที่อยู่ทางกายภาพได้โดยการเพิ่มม k (ในทางตรงกันข้ามกับเพจจิ้ง)
      ฮาร์ดแวร์ยังเปรียบเทียบเมตรชดเชยลิตรกับความยาวของส่วนที่เพื่อตรวจสอบว่าที่อยู่ที่ถูกต้อง

      Hardware Support for Segmentation

      กระบวนการแต่ละคนมีตารางส่วนของตัวเอง
      ตารางส่วนงานจะถูกเก็บไว้ในหน่วยความจำ
      ฮาร์ดแวร์ MMU มี
       Segment ตารางฐานลงทะเบียน (STBR): คะแนนในตารางส่วน

      Hardware for Address Translation in a Segmentation System

      Sharing in Segmentation Systems(ร่วมกันในระบบการแบ่งกลุ่ม)

      • ส่วนที่ใช้ร่วมกันเมื่อรายการในส่วนของตาราง 2 กระบวนการที่แตกต่างชี้ไปที่สถานที่ทางกายภาพเดียวกัน
      • Ex:รหัสเดียวกันของโปรแกรมแก้ไขข้อความที่สามารถใช้ร่วมกันโดยผู้ใช้หลายคน
      • สำเนาเดียวเท่านั้นจะถูกเก็บไว้ในหน่วยความจำ
      • แต่ผู้ใช้แต่ละคนจะยังคงต้องมีส่วนข้อมูลส่วนตัว

      Sharing of Segments: A Text Editor

      Placement Policy

      • ที่กำหนดในหน่วยความจำจริงกระบวนการชิ้น segmentations อาศัยอยู่
      • สำหรับระบบการแบ่งส่วนบริสุทธิ์
      • แรกพอดีพอดีต่อไป ... เป็นไปได้ที่เป็นตัวเลือก

      Advantage & Disadvantage(ข้อดีข้อเสีย)

      • ข้อดี
      มุมมองตรรกะ (มุมมองของโปรแกรมเมอร์) ของหน่วยความจำ
      ไม่มีการกระจายตัวของภายใน
      ไม่จำเป็นต้องมีการจัดสรรหน่วยความจำที่อยู่ติดกันสำหรับแต่ละขั้นตอน (cf จัดสรรที่อยู่ติดกัน)
      กระบวนการอาจใช้มากกว่าหนึ่งพาร์ติชัน (เช่นส่วน)
      และพาร์ทิชันเหล่านี้ไม่จำเป็นต้องต่อเนื่องกัน
      • ข้อเสีย
      การกระจายตัวภายนอกต้องบดอัด

      Simple Paging
      • แต่ละขั้นตอนจะถูกแบ่งออกเป็นชิ้นขนาดเดียวกันที่เรียกว่าหน้า
      • หน่วยความจำหลักยังเป็นพาร์ทิชันคงเป็นชิ้นขนาดเท่ากัน (ที่มีขนาดค่อนข้างเล็ก) ที่เรียกว่าframes หรือ page frames
      • หน้ากระบวนการจึงสามารถกำหนดให้กรอบที่มีอยู่
      • ผล: กระบวนการที่ไม่จำเป็นต้องที่จะครอบครองส่วนของหน่วยความจำที่อยู่ติดกัน
      • จำเป็นที่จะต้องตั้งค่าpage tableในการแปลตรรกะหน้าทางกายภาพ / ที่อยู่
      • การกระจายตัวที่เป็นไปได้ภายใน (สำหรับหน้าสุดท้าย)
      จัดสรรหน่วยความจำอาจจะมีขนาดใหญ่กว่าเล็กน้อยหน่วยความจำที่ร้องขอ; ความแตกต่างขนาดนี้หน่วยความจำภายในพาร์ทิชัน แต่ไม่ได้ใช้
      • ต้องการเรียกใช้กระบวนการของหน้า n ขนาดต้องไปหาเฟรมฟรี n ใด ๆ และโหลดหน้าเว็บทั้งหมด
      • OS ดังนั้นความต้องการที่จะติดตามเฟรมฟรีทั้งหมดในหน่วยความจำกายภาพ
      • ตอนนี้สมมติว่ากระบวนการ B เสร็จสมบูรณ์ในงานของตน
      • เมื่อกระบวนการ A และ C จะถูกบล็อกเพจเจอร์โหลดกระบวนการใหม่ D ประกอบด้วย 5 หน้า
      • กระบวนการ D ไม่ได้ครอบครองเป็นส่วนหนึ่งของหน่วยความจำที่อยู่ติดกัน
      • ไม่มีการกระจายตัวภายนอก
      • การกระจายตัวของภายในประกอบด้วยเดียวของหน้าสุดท้ายของแต่ละขั้นตอน
      • ระบบปฏิบัติการในขณะนี้ต้องการที่จะรักษา (ในหน่วยความจำ) ตารางหน้าสำหรับแต่ละขั้นตอน
      • การเข้ามาของตารางเพจแต่ละประกอบด้วยจำนวนเฟรมที่สอดคล้องกันหน้าตั้งอยู่ทางร่างกาย
      • ตารางหน้าการจัดทำดัชนีจากจำนวนหน้าเพื่อให้ได้จำนวนเฟรม
      • รายการกรอบฟรีสามารถใช้ได้สำหรับหน้าจะยังคงอยู่

      Logical Address Used in Paging


      • ภายในแต่ละโปรแกรมแต่ละที่อยู่ตรรกะต้องประกอบด้วยหมายเลขหน้าและชดเชยภายในหน้า
      • ลงทะเบียน CPU เสมอถือที่อยู่ทางกายภาพเริ่มต้นของตารางหน้าของกระบวนการที่กำลังทำงานอยู่
      • นำเสนอด้วยที่อยู่ตรรกะ (หมายเลขหน้า offset) โปรเซสเซอร์เข้าถึงตารางหน้าจะได้รับที่อยู่ทางกายภาพ (หมายเลขกรอบชดเชย)
      • Ex: ถ้า 16 บิตที่อยู่มีการใช้และขนาดหน้า = 1K เราต้อง 10 บิตสำหรับ และมีการชดเชย 6 บิตสามารถใช้ได้สำหรับหมายเลขหน้า
      • แล้วที่อยู่ 16 บิตที่ได้รับมีน้อยอย่างมีนัยสำคัญ 10 บิตเป็นชดเชยและ 6 บิตที่สำคัญที่สุดเป็นหมายเลขหน้าเป็นสถานที่ที่มีความสัมพันธ์กับจุดเริ่มต้นของกระบวนการ
      • โดยใช้ขนาดหน้าของการใช้พลังงานของ 2, หน้าเว็บที่มองไม่เห็นโปรแกรมเมอร์คอมไพเลอร์ / ประกอบและลิงเกอร์
      • การแปลที่อยู่ที่ใช้เวลาเป็นแล้วง่ายต่อการใช้ในฮาร์ดแวร์
      • อยู่ตรรกะ(n,m) ได้รับการแปลเป็นที่อยู่ทางกายภาพ (k,m) โดยการจัดทำดัชนีตารางหน้าและท้ายเดียวกันชดเชยเมตรจำนวนเฟรม k

      Address Translation Example

      Hardware Support for Paging

      กระบวนการแต่ละคนมีตารางเพจของตัวเอง
      ตารางหน้าจะถูกเก็บไว้ในหน่วยความจำ
      • ฮาร์ดแวร์ MMU มี
      หน้าตารางฐานลงทะเบียน (PTBR): จุดตารางหน้า

      Hardware for Address Translation ina Paging System

      Translation Lookaside Buffer

      • เพราะตารางหน้าอยู่ในหน่วยความจำหลักอ้างอิงแต่ละหน่วยความจำเสมือนเป็นสาเหตุอย่างน้อยสองหน่วยความจำกายภาพเข้าถึง
      หนึ่งสามารถดึงข้อมูลรายการตารางหน้า
      หนึ่งที่จะดึงข้อมูล
      • ที่จะเอาชนะปัญหานี้แคชเป็นพิเศษคือการตั้งค่าสำหรับรายการตารางเพจ
      เรียกว่า TLB - แปล Look aside บัฟเฟอร์
      -มีรายการตารางเพจที่มีการใช้มากที่สุดเมื่อเร็ว ๆ นี้
      -การทำงานคล้ายกับหน่วยความจำแคชหลัก
      ค้นหาขนาน
      การแปลที่อยู่
      หากหน้า # ในทะเบียนสมาคม (TLB ตี) ได้รับกรอบ # ออก
      มิฉะนั้น(TLB พลาด) รับกรอบ # จากตารางหน้าในหน่วยความจำ

      Paging Hardware With TLB

      Use of a TLB

       TLB จะต้องล้างทุกครั้งที่เข้าสู่กระบวนการใหม่รัฐทำงาน
      บางทีเก็บ / การโหลดข้อมูลใน TLB / จาก PCB

      การปฏิบัติงานของ TLB

      • กำหนดโดย
      อัตราส่วนตี (%) อัตราร้อยละของเวลาที่มีจำนวนหน้าจะพบใน TLB
      • หน่วยความจำที่มีประสิทธิภาพเวลาในการเข้าถึง
      อัตราส่วนตี: H%
      ใช้เวลาในการค้นหา TLB: และ
      เวลาในการเข้าถึงหน่วยความจำ: M ns การ
       Effective access time =
       Actual Implementation
       Motorola 68030 : 22 registers
       Intel 80486, Pentium : 32 registers (claims 98% hit ratio)
      • การดำเนินงานที่เกิดขึ้นจริง
      โมโตโรล่า 68030: 22 ลงทะเบียน
       Intel 80486, Pentium: 32 ลงทะเบียน (อ้างว่า 98% อัตราส่วนตี)

      Sharing Pages

      ถ้าเราแบ่งปันรหัสเดียวกันในหมู่ผู้ใช้ที่แตกต่างกันก็จะเพียงพอที่จะเก็บเฉพาะสำเนาในหน่วยความจำ
      รหัสที่ใช้ร่วมกันจะต้อง reentrant (คือไม่ใช่ตัวเองแก้ไข) เพื่อให้สองหรือกระบวนการอื่น ๆ สามารถรันรหัสเดียวกัน
      ถ้าเราใช้เพจจิ้งขั้นตอนการใช้งานร่วมกันแต่ละคนจะมีตารางเพจที่มีจุดเข้าเฟรมเดียวกันเพียงหนึ่งสำเนาอยู่ในหน่วยความจำหลัก
       แต่ผู้ใช้แต่ละคนจะต้องมีหน้าข้อมูลส่วนตัว

      โปรแกรมแก้ไขข้อความ

      Placement Policy(นโยบายการจัดตำแหน่ง)

      • ที่กำหนดในหน่วยความจำจริงกระบวนการ 'หน้าเว็บอาศัยอยู่
      • ที่ไหนที่จะวางหน้าไม่เกี่ยวข้องตั้งแต่เฟรมหน่วยความจำทั้งหมดจะเทียบเท่า (ไม่เป็นปัญหา)

      ข้อดี&ข้อเสีย

      • ข้อดี
      ไม่มีการกระจายตัวภายนอก
      ไม่จำเป็นต้องมีการจัดสรรหน่วยความจำที่อยู่ติดกันสำหรับแต่ละขั้นตอน
      กระบวนการอาจใช้มากกว่าหนึ่งพาร์ติชัน (เช่นหน้า) และพาร์ทิชันเหล่านี้ไม่จำเป็นต้องต่อเนื่องกัน
      • ข้อเสีย
      ยังคงมีการกระจายตัวภายใน แต่เฉพาะในหน้าสุดท้าย

      Simple Segmentation and Paging Comparison(การแบ่งกลุ่มที่เรียบง่ายและเพจเปรียบเทียบ)

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

      Combined Segmentation and Paging(รวมการแบ่งกลุ่มและเพจ)

      • การรวมข้อดีของพวกเขาประมวลผลและระบบปฏิบัติการส่วนหน้า
      • รวมกันอยู่หลายคน นี่คือง่ายๆ
      • กระบวนการแต่ละคนมี:
      ตารางส่วนหนึ่ง
      หน้าตารางหลายตารางหน้าต่อหนึ่งส่วน
      • ที่อยู่เสมือนประกอบด้วย:
      A segment number: ใช้ในการดัชนีตารางที่มีส่วนช่วยให้รายการที่อยู่เริ่มต้นของตารางหน้าสำหรับส่วนที่
      A page number: ใช้ในการดัชนีตารางหน้าเว็บที่จะได้รับจำนวนเฟรมที่สอดคล้องกัน
      An offset:ใช้ในการค้นหาคำที่อยู่ในกรอบ

      Address Translation in a (Simple) Combined Segmentation/Paging System(แปลที่อยู่ใน (แบบง่าย)รวมการแบ่งกลุ่ม / ระบบเพจ)