การตั้งเวลาซีพียู Algorithms in Operaระบบติ้ง

ประเภทของการจัดตารางเวลา CPU

ต่อไปนี้เป็นวิธีการจัดกำหนดการสองประเภท:

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

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

การจัดกำหนดการแบบไม่ยึดถือล่วงหน้า

ในวิธีการกำหนดเวลาประเภทนี้ CPU ได้รับการจัดสรรให้กับกระบวนการเฉพาะ กระบวนการที่ทำให้ CPU ไม่ว่างจะปล่อย CPU โดยการสลับบริบทหรือยุติ เป็นวิธีเดียวที่สามารถใช้ได้กับแพลตฟอร์มฮาร์ดแวร์ต่างๆ นั่นเป็นเพราะว่าไม่จำเป็นต้องใช้ฮาร์ดแวร์พิเศษ (เช่น ตัวจับเวลา) เช่น การตั้งเวลาล่วงหน้า

เมื่อการกำหนดเวลาเป็นแบบยึดถือหรือไม่ยึดเสียก่อน?

เมื่อต้องการตรวจสอบว่าการจัดกำหนดการเป็นแบบยึดถือหรือไม่ยึดเสียก่อน ให้พิจารณาพารามิเตอร์สี่ตัวเหล่านี้:

1. กระบวนการเปลี่ยนจากการทำงานเป็นสถานะรอ
2. กระบวนการเฉพาะจะเปลี่ยนจากสถานะกำลังทำงานไปเป็นสถานะพร้อม
3. กระบวนการเฉพาะจะเปลี่ยนจากสถานะรอเป็นสถานะพร้อม
4. กระบวนการเสร็จสิ้นการดำเนินการและยุติลง

ใช้เฉพาะเงื่อนไขที่ 1 และ 4 เท่านั้น การกำหนดเวลาเรียกว่าไม่ยึดเสียก่อน

การกำหนดเวลาอื่นๆ ทั้งหมดถือเป็นการยึดถือไว้ก่อน

คำศัพท์สำคัญในการตั้งเวลา CPU

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

เกณฑ์การกำหนดเวลา CPU

อัลกอริทึมการกำหนดการ CPU พยายามที่จะเพิ่มและลดสิ่งต่อไปนี้ให้สูงสุดและลดให้น้อยที่สุด:

เพิ่ม

การใช้งานซีพียู:การใช้งาน CPU เป็นงานหลักที่ระบบปฏิบัติการจำเป็นต้องทำเพื่อให้แน่ใจว่า CPU ยังคงทำงานหนักที่สุดเท่าที่จะเป็นไปได้ โดยอาจอยู่ระหว่าง 0 ถึง 100 เปอร์เซ็นต์ อย่างไรก็ตาม สำหรับ RTOS อาจอยู่ระหว่าง 40 เปอร์เซ็นต์สำหรับระบบระดับต่ำและ 90 เปอร์เซ็นต์สำหรับระบบระดับสูง

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

ลด

รอเวลา: เวลารอคือจำนวนเงินที่กระบวนการเฉพาะต้องรอในคิวที่พร้อม

เวลาตอบสนอง: คือระยะเวลาที่คำขอถูกส่งไปจนกว่าจะมีการตอบกลับครั้งแรก

เวลาตอบสนอง: เวลาตอบสนองคือระยะเวลาในการดำเนินการตามกระบวนการเฉพาะ เป็นการคำนวณเวลาทั้งหมดที่ใช้ในการรอเข้าหน่วยความจำ รอคิว และดำเนินการบน CPU ระยะเวลาระหว่างเวลาที่ยื่นกระบวนการจนถึงเวลาที่เสร็จสิ้นคือเวลาตอบสนอง

จับเวลาช่วง

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

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

Dispatcher คืออะไร?

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

ฟังก์ชั่นที่ดำเนินการโดย Dispatcher:

• การสลับบริบท
• เปลี่ยนเป็นโหมดผู้ใช้
• การย้ายไปยังตำแหน่งที่ถูกต้องในโปรแกรมที่โหลดใหม่

ประเภทของอัลกอริทึมการตั้งเวลา CPU

ส่วนใหญ่มีหกประเภท อัลกอริทึมการจัดตารางกระบวนการ

1. มาก่อนได้ก่อน (FCFS)
2. การจัดกำหนดการงานแรกที่สั้นที่สุด (SJF)
3. เวลาที่เหลือสั้นที่สุด
4. การจัดลำดับความสำคัญ
5. กำหนดการ Round Robin
6. การจัดตารางคิวหลายระดับ

มาก่อนได้ก่อน

First Come First Serve คือรูปแบบเต็มของ FCFS มันเป็นอัลกอริธึมการตั้งเวลา CPU ที่ง่ายและง่ายที่สุด ในอัลกอริทึมประเภทนี้ กระบวนการที่ร้องขอ CPU จะได้รับการจัดสรร CPU ก่อน วิธีการกำหนดเวลานี้สามารถจัดการได้ด้วยคิว FIFO

เมื่อกระบวนการเข้าสู่คิวที่พร้อม PCB (Process Control Block) จะเชื่อมโยงกับส่วนท้ายของคิว ดังนั้นเมื่อ CPU ว่าง ควรกำหนดให้กับกระบวนการที่จุดเริ่มต้นของคิว

ลักษณะของวิธี FCFS

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

เวลาที่เหลือสั้นที่สุด

รฟท. แบบเต็มคือเวลาที่เหลือสั้นที่สุด เรียกอีกอย่างว่าการตั้งเวลาล่วงหน้าของ SJF ในวิธีนี้ กระบวนการจะถูกจัดสรรให้กับงานซึ่งใกล้จะเสร็จสมบูรณ์มากที่สุด วิธีนี้จะป้องกันไม่ให้กระบวนการสถานะพร้อมที่ใหม่กว่าระงับความสมบูรณ์ของกระบวนการที่เก่ากว่า

ลักษณะของวิธีการจัดตารางเวลาของ SRT

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

การจัดตารางเวลาตามลำดับความสำคัญ

การจัดลำดับความสำคัญ เป็นวิธีการจัดกำหนดการกระบวนการตามลำดับความสำคัญ ในวิธีนี้ ผู้จัดกำหนดการจะเลือกงานที่จะทำงานตามลำดับความสำคัญ

การกำหนดเวลาลำดับความสำคัญยังช่วยให้ OS เกี่ยวข้องกับการกำหนดลำดับความสำคัญอีกด้วย กระบวนการที่มีลำดับความสำคัญสูงกว่าควรดำเนินการก่อน ในขณะที่งานที่มีลำดับความสำคัญเท่ากันจะดำเนินการแบบ Round-robin หรือ FCFS ลำดับความสำคัญสามารถตัดสินใจได้ตามความต้องการของหน่วยความจำ ความต้องการด้านเวลา ฯลฯ

การจัดตารางเวลาแบบ Round-Robin

Round-robin เป็นอัลกอริทึมการจัดตารางเวลาที่เก่าแก่ที่สุดและง่ายที่สุด ชื่อของอัลกอริทึมนี้มาจากหลักการ Round-robin ซึ่งทุกคนจะได้รับส่วนแบ่งเท่าๆ กัน อัลกอริทึมนี้มักใช้สำหรับอัลกอริทึมการจัดตารางเวลาในการทำงานหลายอย่างพร้อมกัน วิธีการของอัลกอริทึมนี้ช่วยให้สามารถดำเนินการขั้นตอนต่างๆ ได้โดยไม่มีการหยุดชะงัก

ลักษณะของการจัดตารางเวลาแบบ Round-Robin

• Round robin เป็นรุ่นไฮบริดซึ่งขับเคลื่อนด้วยนาฬิกา
• การแบ่งเวลาควรเป็นขั้นต่ำ ซึ่งกำหนดให้กับงานเฉพาะที่จะประมวลผล อย่างไรก็ตาม อาจแตกต่างกันไปตามกระบวนการที่แตกต่างกัน
• เป็นระบบเรียลไทม์ที่ตอบสนองต่อเหตุการณ์ภายในระยะเวลาที่กำหนด

งานที่สั้นที่สุดก่อน

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

ลักษณะของการจัดตารางเวลา SJF

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

การจัดตารางเวลาคิวหลายระดับ

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

อย่างไรก็ตาม นี่ไม่ใช่อัลกอริธึมระบบปฏิบัติการการกำหนดตารางเวลาอิสระ เนื่องจากจำเป็นต้องใช้อัลกอริธึมประเภทอื่นเพื่อกำหนดตารางเวลาของงาน

ลักษณะของการจัดตารางเวลาคิวหลายระดับ

• ควรรักษาหลายคิวไว้สำหรับกระบวนการที่มีคุณสมบัติบางอย่าง
• คิวแต่ละคิวอาจมีอัลกอริธึมการกำหนดตารางเวลาแยกจากกัน
• ลำดับความสำคัญจะได้รับสำหรับแต่ละคิว

วัตถุประสงค์ของอัลกอริทึมการจัดกำหนดการ

ต่อไปนี้เป็นเหตุผลในการใช้อัลกอริทึมการตั้งเวลา:

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

สรุป

• การกำหนดเวลา CPU เป็นกระบวนการในการพิจารณาว่ากระบวนการใดจะเป็นเจ้าของ CPU สำหรับการดำเนินการในขณะที่กระบวนการอื่นถูกพักไว้
• ในการจัดกำหนดการล่วงหน้า งานส่วนใหญ่จะได้รับมอบหมายตามลำดับความสำคัญ
• ในวิธีการกำหนดเวลาแบบไม่ยึดเอาเสียก่อน CPU ได้รับการจัดสรรให้กับกระบวนการเฉพาะ
• เวลาต่อเนื่องคือเวลาที่ต้องใช้เพื่อให้กระบวนการดำเนินการให้เสร็จสิ้น เรียกอีกอย่างว่าเวลาทำงาน
• การใช้งาน CPU เป็นงานหลักที่ระบบปฏิบัติการจำเป็นต้องทำเพื่อให้แน่ใจว่า CPU ยังคงทำงานหนักที่สุดเท่าที่จะเป็นไปได้
• จำนวนกระบวนการที่เสร็จสิ้นการดำเนินการต่อหน่วยเวลาเรียกว่าปริมาณงาน
• เวลารอคือจำนวนเงินที่กระบวนการเฉพาะต้องรอในคิวที่พร้อม
• คือระยะเวลาที่ส่งคำขอจนกว่าจะมีการตอบกลับครั้งแรก
• เวลาตอบสนองคือระยะเวลาในการดำเนินการตามกระบวนการเฉพาะ
• การหยุดชะงักของตัวจับเวลาเป็นวิธีการที่เกี่ยวข้องอย่างใกล้ชิดกับการขอจอง
• โปรแกรมเลือกจ่ายงานคือโมดูลที่ให้การควบคุม CPU แก่กระบวนการ
• อัลกอริทึมการกำหนดตารางกระบวนการ 2 ประเภท ได้แก่ First Come First Serve (FCFS), 3) การกำหนดตารางงานสั้นที่สุดก่อน (SJF), 4) เวลาที่เหลือสั้นที่สุด, 5) การกำหนดตารางงานตามลำดับความสำคัญ, 6) การกำหนดตารางงานแบบ Round Robin และ XNUMX) การกำหนดตารางงานคิวหลายระดับ
• ตัว Vortex Indicator ได้ถูกนำเสนอลงในนิตยสาร วิธีมาก่อนได้ก่อนกระบวนการที่ร้องขอ CPU จะได้รับการจัดสรร CPU ก่อน
• ในระยะเวลาที่เหลือสั้นที่สุด กระบวนการจะถูกจัดสรรให้กับงานที่ใกล้จะสำเร็จมากที่สุด
• ในการจัดลำดับความสำคัญ ผู้จัดกำหนดการจะเลือกงานที่จะทำงานตามลำดับความสำคัญ
• กำหนดการแบบ Round Robin ทำงานบนหลักการที่แต่ละคนได้รับส่วนแบ่งเท่ากันในบางสิ่งบางอย่างตามลำดับ
• ในงานที่สั้นที่สุดก่อน ควรเลือกเวลาดำเนินการที่สั้นที่สุดสำหรับการดำเนินการถัดไป
• วิธีการจัดกำหนดการแบบหลายระดับจะแยกคิวที่พร้อมใช้งานออกเป็นคิวที่แยกจากกันต่างๆ ในวิธีนี้ กระบวนการถูกกำหนดให้กับคิวตามคุณสมบัติเฉพาะ
• CPU ใช้การตั้งเวลาเพื่อปรับปรุงประสิทธิภาพ