การจัดการเวลา CPU
การจัดเวลาซีพียู (CPU Scheduling) เป็นหลักการทำงานหนึ่งของระบบปฏิบัติการที่ทำให้คอมพิวเตอร์มีความสามารถในการรันโปรแกรมหลายๆ โปรแกรมในเวลาเดียวกัน ซึ่งการแบ่งเวลาการเข้าใช้ซีพียูให้กับโปรเซสที่อาจถูกส่งมาหลายๆ โปรเซสพร้อมๆกัน ในขณะที่ซีพียูอาจมีจำนวนน้อยกว่าโปรเซส หรืออาจมีซีพียูเพียงตัวเดียว จะทำให้คอมพิวเตอร์สามารถทำงานได้ปริมาณงานที่มากขึ้นกว่าการที่ให้ซีพียูทำงานให้เสร็จทีละโปรเซส ในบทนี้ เราจะมาพูดถึงอัลกอริทึมพื้นฐานของการจัดเวลาซีพียูนี้ โดยจะพูดถึงวิธีการหลักๆ ที่แต่ละอัลกอริทึมมีแตกต่างกัน ข้อดีข้อเสีย และความเหมาะสมต่อระบบงานแบบต่างๆ เพื่อการเลือกใช้อย่างถูกต้อง
1. Scheduling Criteria
1.1 การใช้ประโยชน์หน่วยประมวลผลกลาง (CPU utilization)
1.2 ประมาณงาน (Throughput)
1.3 เวลาโดยรวม (Turnaround time)
1.4 เวลาคอย (Waiting time)
1.5 เวลาตอบสนอง (Response time)
2. Scheduling Algorithms
หน้าที่ของตัวจัดคิวคือ คัดเลือกโปรเซสซึ่งรออยู่ในสถานะพร้อมที่เหมาะสมที่สุดให้เข้าไปอยู่ในสถานะรัน (ได้ครอบครองซีพียู) โดยแท้จริงแล้วการส่งโปรเซสที่ถูกเลือกแล้วให้เข้าไปอยู่ในสถานะรัน เป็นหน้าที่ของโปรเซสของ OS ที่ชื่อตัวส่ง (dispatcher) ในแง่การทำงานแล้วตัวจัดคิวจะเป็นผู้คัดเลือกโปรเซสและเรียกให้ตัวส่งส่งโปรเซสที่ถูกเลือกแล้วเข้าไปในสถานะรันเป็นความรับผิดชอบของตัวจัดคิว
2.1 การจัดเวลาแบบมาก่อนได้ก่อน (FCFS : First-come First-served Scheduling)
การจัดคิวแบบ FCFS (first-come-first-served) วิธีการคัดเลือกแบบ FCFS นี้เป็นวิธีที่ง่ายที่สุด คือ โปรเซสไหนเข้ามารอในคิวก่อนจะได้ครอบครองซีพียูก่อน ตามลำดับเวลาของการเข้ามาอยู่ในคิว คือ “มาก่อนได้ก่อน” โปรเซสที่ได้ครอบครองซีพียูจะทำงานไปจนเสร็จ ไม่มีระยะเวลาควอนตัมซึ่งจำกัดเวลาการครอบครองซีพียู แต่ถ้าโปรเซสมีการเรียกใช้งานอุปกรณ์อินพุต-เอาต์พุต หรือรอเหตุการณ์บางอย่าง โปรเซสนั้นต้องปลดปล่อยซีพียู และออกจากสถานะรันไปอยู่ในสถานะติดขัด เมื่อใดที่งานเสร็จสิ้นลงหรือเกิดเหตุการณ์ที่กำลังรออยู่ โปรเซสนั้นจึงค่อยกลับเข้าไปอยู่ต่อท้ายคิวของสถานะพร้อมใหม่อีกครั้ง
เราอาจแสดงการเปลี่ยนสถานะของโปรเซสโดยใช้การจัดคิวแบบ FCFS ซึ่งจะเห็นว่าแตกต่างกับรูปแสดงการเปลี่ยนสถานะของโปรเซสที่เคยกล่าวมาคือ ไม่มีการเปลี่ยนสถานะของโปรเซสจากสถานะรันมายังสถานะพร้อมโดยตรง
2.2 การจัดเวลาแบบงานสั้นทำก่อน (SJF : Short-Job-First Scheduling)
การจัดคิวแบบ SJN (shortest job next) การคัดเลือกโปรเซสด้วยวิธีนี้ จะคัดเลือกเอาโปรเซสที่ต้องการเวลาในการทำงานน้อยที่สุด ทำให้โปรเซสที่ต้องการเวลาในการทำงานน้อยจบออกไปได้เร็วขึ้น จำนวนโปรเซสในระบบที่รออยู่ในคิวมีก็จะมีจำนวนลดลง และทำให้เวลาโดยเฉลี่ยในการทำงาน 1 งานเสร็จหรือเวลาครบงาน (turnaround time) น้อยลงแต่การจัดคิวแบบนี้เป็นผลเสียต่อโปรเซสที่ต้องการเวลาในการทำงานนาน
2.3 การจัดเวลาตามลำดับความสำคัญ (Priority Scheduling)
การจัดคิวแบบลำดับความสำคัญ (priority queue) คิวแบบลำดับความสำคัญมีลักษณะแตกต่างกับคิวธรรมดา ภายในคิวจะมีการจัดเรียงลำดับของโปรเซสต่าง ๆ ตามลำดับความสำคัญของโปรเซสนั้น โปรเซสที่อยู่ต้นคิวจะมีลำดับความสำคัญมากที่สุด และลดลงเรื่อย ๆ โปรเซสที่อยู่ท้ายคิวคือโปรเซสที่มีลำดับความสำคัญต่ำสุด การคัดเลือกโปรเซสจะเอาโปรเซสที่อยู่ต้นคิว (มีลำดับความสำคัญสูงสุด) เข้าไปครอบครองซีพียูก่อน ดังนั้นถึงแม้ว่าโปรเซสที่เข้าคิวทีหลังแต่มีลำดับความสำคัญสูงกว่าก็อาจได้เข้าไปครอบครองซีพียูก่อน โปรเซส E เข้าคิวเป็นโปรเซสหลังสุด แต่จะได้ครอบครองซีพียูก่อนโปรเซส C และ D
2.4 การจัดเวลาแบบวนรอบ (RR : Round-Robin Scheduling)
การจัดคิวแบบ RR (round-robin) การจัดคิวแบบ RR อาจเรียกว่าเป็นการจัดคิวแบบมีการวนรอบ ลักษณะการคัดเลือก โปรเซสในคิวจะเป็นแบบ FCFS คือ “มาก่อนได้ก่อน” แต่ต่างกันนิดหน่อยตรงที่การครอบครองซีพียูของโปรเซสในสถานะรันจะถูกจำกัดเวลาไว้ด้วยระยะเวลาควอนตัม ทำให้โปรเซสที่ต้องการเวลาในการทำงานนานจะต้องเปลี่ยนสถานะหมุนระหว่างสถานะพร้อมและสถานะรัน
การจัดคิวแบบ RR สามารถแก้ปัญหาการคอยนานของโปรเซสที่ต้องการเวลาทำงานน้อย ๆ ได้ลองกลับไปพิจารณาเหตุการณ์สมมติซึ่งกล่าวไว้ในหัวข้อที่แล้ว ถ้าระบบกำหนดเวลาควอนตัมเป็น 1 วินาที โปรเซส A ต้องมีการวนรอบเปลี่ยนสถานะระหว่างสถานะรันและสถานะพร้อม 15 ครั้ง โปรเซส B 1 ครั้ง โปรเซส C 10 ครั้ง เมื่อโปรเซส A เข้าไปอยู่ในสถานะรันครั้งแรกและกลับออกมา โปรเซส B จะได้ครอบครองซีพียูได้และ ทำงานเสร็จโปรเซส B จบและออกจากระบบไปเลยเหลือเพียง 2 โปรเซสที่อยู่ในคิวของสถานะพร้อม โปรเซสถัดไปที่จัดได้ครอบครองซีพียูคือ C โปรเซส C และ A จะสลับกันครอบครองซีพียูกันโปรเซสละ 1 วินาที จนกระทั่งโปรเซส C จบ เหลือโปรเซส A เพียงโปรเซสเดียว เป็นแผนภาพแสดงการสลับกันทำงานของโปรเซสทั้ง 3 และเป็นผลที่เกิดขึ้นจากการจัดคิวแบบ RR
2.5 การจัดเวลาแบบคิวหลายระดับ (Multilevel Queue Scheduling)
เพื่อให้การจัดคิวเป็นไปอย่างมีประสิทธิภาพ จึงมีการนำหลาย ๆ เทคนิคมาประยุกต์เข้าด้วยกัน เป็นการจัดคำแบบวนรอบ ที่คำนึงถึงความสำคัญของงาน ทำให้งานที่มีความสำคัญเหมือนกันอยู่ในคิวเดียวกัน และให้งานสำคัญน้อย ๆ อยู่ในคิวที่สำคัญน้อยเช่นกัน
3. การประเมินอัลกอริทึม (Algorithm Evaluation)
จากที่ได้ศึกษาอัลกอริทึมทั้ง 5 แบบ สำหรับการจัดเวลาซีพียูมาแล้ว ก็ต้องเลือกอัลกอริทึมที่จะใช้งาน สำหรับเลือกงานเข้าประมวลผล มีหลาย ๆ วิธีในการพิจารณาอัลกอริทึม ที่ต้องคำนึงถึง CPU utilization, Response time และ Throughput เพื่อให้ได้ผลออกมาดีที่สุด
หลักเกณฑ์การพิจารณาอัลกอริทึมเข้าประมวลผล
1. ให้ใช้ซีพียูสูงสุด โดยช่วงเวลาตอบสนองต่ำสุด
2. ให้มีเวลารวม หรือวนรอบที่เหมาะสม กับเวลาที่ต้องใช้ประมวลผลทั้งหมด
3.1 วิธีกำหนดโมเดล (Deterministic modeling)
วิธีนี้มีข้อจำกัดมากเกินไปสำหรับการนำมาใช้ในปัจจุบัน เพราะวิธีนี้จะเป็นวิธีที่ง่าย ได้ตัวเลขออกมาแน่นอน จากตัวอย่างข้อมูลจำนวนหนึ่งที่ป้อนเข้าไป แต่ผลลัพธ์ไม่มีความน่าเชื่อถือมากพอ เพราะในสถานการณ์จริงจะมีข้อมูลที่ซับซ้อนกว่ามาก เช่นเลือกอัลกอริทึมมาพิจารณา 3 แบบ คือ FCFS, SJF และ RR ซึ่งผลของการพิจารณาแต่ละอัลกอริทึมจะออกเป็นตัวเลขให้เลือก การเลือกเป็นสิ่งที่ตัดสินใจได้ง่าย แต่ไม่อาจไม่เหมาะที่จะใช้งานจริง
3.2 วิธีจัดเมเดลของคิว (Queueing models)
วิธีนี้มีปัญหาการคำนวณค่าเฉลี่ยของการกระจายในระบบที่มีความซับซ้อน เมื่อพิจารณาในระบบเครือข่ายที่แบ่งกลุ่มงานออกเป็นสถานี หรือสายการผลิตที่มีคิวของตนเอง ถ้าทราบเวลาที่ให้บริการของแต่ละสายการผลิต และรู้เวลาที่แต่ละงานเข้าคิว ก็จะหาค่าต่าง ๆ ได้ตามต้องการ วิธีนี้เรียกว่า queueing network analysis
จากตัวอย่างข้างต้นอาจใช้สูตร al = at * w (ค่าเฉลี่ยความยาวของคิว = ค่าเฉลี่ยของงานใหม่เข้ามา * ค่าเฉลี่ยการรอคอย) เช่น เวลาเฉลี่ยในคิวคือ 10 วินาที ถ้างานใหม่ต้องรอเข้าคิวประมาณ 2 วินาที และแต่ละงานต้องคอยเข้าหน่วยประมวลผล 5 วินาที
3.3 วิธีจำลองสถานการณ์ (Simulations)
วิธีนี้จะพัฒนาโปรแกรมคอมพิวเตอร์ขึ้นมา เสมือนเป็นหุ่นจำลอง พร้อมกำหนดสภาพแวดล้อม และตัวแปรคำนวณเวลาให้อยู่ในการควบคุม โดยเวลาของสถานการณ์กำหนดได้ 2 แบบคือ แบบสุ่ม หรือแบบข้อมูลจริง นอกจากนั้นยังต้องมี trace tape เก็บข้อมูลในช่วงเวลาต่าง ๆ และนำมาเปรียบเทียบ สำหรับวิธีการนี้ต้องอาศัยเวลา และค่าใช้จ่าย เพื่อให้ได้ผลลัพธ์ที่เที่ยงตรง
3.4 วิธีติดตั้งจริง (Implementation)
วิธีนี้ไม่นิยมปฏิบัติ แม้แบบจำลองจะไม่มีทางเหมือนจริง จึงมีแนวคิดว่าเขียนขึ้นมาใช้จริงเพื่อให้ได้ข้อมูลจริง แต่วิธีนี้ต้องลงทุนสูงมาก นอกจากต้องเขียนโปรแกรมของอัลกอริทึมแต่ละตัว ยังต้องใช้เวลา และแรงงานเปลี่ยนการทำงานของโปรแกรม การจัดการระบบเพื่อให้รองรับอัลกอริทึมแบบต่าง ๆที่จะนำมาทดลอง ซึ่งแต่ละอัลกอริทึมอาจต้องการฮาร์ดแวร์ที่พิเศษ และคอมพิวเตอร์ก็มิได้เปลี่ยนอุปกรณ์กันได้ง่าย
ไม่มีความคิดเห็น:
แสดงความคิดเห็น