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
- ง่ายที่จะใช้
- ใช้เป็นหลักสำหรับพื้นหลังและงานชุด
- ดำเนินการที่ดีมากสำหรับงานที่ยาวกว่าสำหรับคนที่สั้น
- ของชำร่วยงาน CPU ที่ถูกผูกไว้มากกว่า I / O งานที่ถูกผูกไว้
I / O งานที่ถูกผูกไว้ต้องรอจนกว่างาน CPU ที่ถูกผูกไว้เสร็จสมบูรณ์
พวกเขาอาจจะต้องรอแม้ในขณะที่ผมของพวกเขา / O จะเสร็จสมบูรณ์ (การใช้อุปกรณ์ที่ไม่ดี)
เราจะได้เก็บอุปกรณ์ I / O ที่วุ่นวายโดยให้บิตความสำคัญมากขึ้นในการ I / O งานที่ถูกผูกไว้
- ไม่สามารถยอมรับได้สำหรับระบบแบบโต้ตอบ
Round Robin
- ฟังก์ชั่นการคัดเลือก: เช่นเดียวกับ FCFS
- โหมดการตัดสินใจ: มาตรการ
งานที่ได้รับอนุญาตให้ทำงานจนกว่าtime slice หรือ quantumได้หมดอายุแล้ว
แล้วขัดจังหวะนาฬิกาเกิดขึ้นและงานที่ทำงานอยู่บนคิวพร้อม
- ดีสำหรับงานที่มีความสำคัญเท่าเทียมกัน
- ใช้กันอย่างแพร่หลายสำหรับผู้ใช้หลายระบบการโต้ตอบและระบบผู้ใช้คนเดียวกับกิจกรรมต่างๆในความคืบหน้า
- ปัญหาหลักคือความยาวของเวลาชิ้น (หรือควอนตัม):
- ถ้า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, ผ่าน ... )
วิธีการประเมินผลที่ใช้ (แต่ละคนมีข้อ จำกัด ของมัน ... )
- ดังนั้นคำตอบขึ้นอยู่กับปัจจัยหลายอย่างเกินไปที่จะให้ใด ๆ ...
