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(แปลที่อยู่ใน (แบบง่าย)รวมการแบ่งกลุ่ม / ระบบเพจ)