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

CPU Scheduling คืออะไร?

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

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

วิธีการจัดตารางเวลามีอยู่สองประเภท:

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

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

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

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

การจัดตารางเวลาแบบแทรกแซงได้ (Preemptive) หรือแบบไม่แทรกแซง (Non-Preemptive) เกิดขึ้นเมื่อใด?

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

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

ถ้าเงื่อนไขข้อ 1 และ 4 เท่านั้นที่ใช้ได้ การจัดตารางเวลาจะเรียกว่าแบบไม่แทรกแซง (non-preemptive) สถานการณ์การจัดตารางเวลาอื่นๆ ทั้งหมดจะเป็นแบบแทรกแซง (preemptive)

คำศัพท์สำคัญเกี่ยวกับการจัดตารางการทำงานของ CPU

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

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

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

เพิ่ม

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

ผ่าน: จำนวนกระบวนการที่เสร็จสิ้นการทำงานต่อหน่วยเวลาเรียกว่าปริมาณงาน (throughput) ดังนั้น เมื่อซีพียูกำลังประมวลผลกระบวนการใดกระบวนการหนึ่งอยู่ งานก็จะดำเนินไป และปริมาณงานที่เสร็จสมบูรณ์ต่อหน่วยเวลาเรียกว่าปริมาณงาน

ลด

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

เวลาตอบสนอง: คือระยะเวลาตั้งแต่ส่งคำขอจนถึงได้รับคำตอบแรก

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

จับเวลาช่วง

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

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

Dispatcher คืออะไร?

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

หน้าที่ที่ผู้ประสานงานปฏิบัติ:

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

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

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

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

การกำหนด Algorithms

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

FCFS ย่อมาจาก มาก่อนได้ก่อนเป็นอัลกอริธึมการจัดตารางการทำงานของ CPU ที่ง่ายและเรียบง่ายที่สุด ในอัลกอริธึมประเภทนี้ กระบวนการที่ร้องขอการใช้งาน CPU จะได้รับการจัดสรร CPU ก่อน วิธีการจัดตารางการทำงานนี้สามารถจัดการได้ด้วยคิวแบบ FIFO (First-In, First-Out)

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

ลักษณะเฉพาะของวิธีการ FCFS

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

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

ชื่อเต็มของ SRT คือ Shortest Remaining Time หรือเวลาที่เหลือน้อยที่สุด เรียกอีกอย่างว่าการจัดตารางเวลาแบบ SJF (Self-Jest Framework) ในวิธีการนี้ กระบวนการจะถูกจัดสรรให้กับงานที่ใกล้จะเสร็จสมบูรณ์ที่สุด วิธีการนี้จะป้องกันไม่ให้กระบวนการที่พร้อมทำงานใหม่กว่ามาขัดขวางการทำงานของกระบวนการที่เก่ากว่า

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

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

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

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

การจัดลำดับความสำคัญของงานยังช่วยให้ระบบปฏิบัติการสามารถกำหนดลำดับความสำคัญได้ กระบวนการที่มีลำดับความสำคัญสูงกว่าจะถูกดำเนินการก่อน ในขณะที่งานที่มีลำดับความสำคัญเท่ากันจะถูกดำเนินการตามลำดับแบบวนรอบหรือแบบมาก่อนได้ก่อน (FCFS) ลำดับความสำคัญสามารถกำหนดได้จากความต้องการหน่วยความจำ ความต้องการเวลา และปัจจัยอื่นๆ

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

คำถามที่พบบ่อย