Please enable JavaScript.
Coggle requires JavaScript to display documents.
บทที่ 6 กำหนดการใช้ซีพียู - Coggle Diagram
บทที่ 6 กำหนดการใช้ซีพียู
บทที่ 6 กำหนดการใช้ซีพียู
ตัวจัดการเวลาซีพียู
เมื่อใดก็ตามที่ซีพียูว่าง ระบบปฏิบัติการจะต้องเข้ามาเลือกโพรเซสตัวใดตัวหนึ่งที่คอยอยู่ในคิวเข้ามาใช้งานซีพียู การเลือกโพรเซสเพื่อเข้ามาใช้ซีพียูนี้ จะถูกจัดการด้วยส่วนที่เรียกว่า ตัวจัดการช่วงสั้น หรือตัวจัดการเวลาซีพียู จะเลือกโพรเซสที่อยู่ในหน่วยความจำที่พร้อมทำงานมากที่สุด ไม่จำเป็นต้องเป็นแบบมาก่อนได้ก่อนเสมอไป อาจจะเป็นไปตามลำดับสำคัญ โครงร่างต้นไม้ หรืออาจจะเป็นลิงค์ลิสต์ก็ได้
การให้สิทธิการจัดการเวลา
การตัดสินใจของซีพียูในการเลือกโพรเซสใดๆทำงาน ขึ้นอยู่กับสถานการณ์
ทั้ง 4 สถานการณ์นั้นจะต้องมีการตัดสินใจทำอะไรอย่างใดอย่างหนึ่ง โดยไม่สามารถหลีกเลี่ยงได้
เมื่อมีการเปลี่ยนสถานะของโพรเซสจากสถานะคอย เป็นสถานะพร้อม
เมื่อมีการเปลี่ยนสถานะของโพรเซสจากสถานะรันไปเป็นสถานะคอย
เมื่อโพรเซสเสร็จสิ้นหรือสิ้นสุดการดำเนินการ
เมื่อมีการเปลี่ยนสถานะของโพรเซสจากรัน เป็นสถานะพร้อม
การจัดเวลาซีพียูจะเป็นแบบไม่ให้สิทธิ์ก่อน นอกนั้นจะเรียกว่าให้สิทธิ์ก่อนภายใต้การทำงานแบบไม่ให้สิทธิก่อนนี้ โพรเซสจะครอบครองเวลาซีพียูไปจนกว่าจะเสร็จ หรือเปลี่ยนสถานะตัวเองเป็นสถานะคอย
ตัวส่งต่อ
Dispatcher เป็นโมดูลที่ทำหน้าที่ควบคุมการครอบครองซีพียูของโพรเซส ลักษณะของ Dispatcher คือการทำ Context switching โมดูลนี้ประกอบด้วยฟังก์ชัน
การย้าย User mode
กระโดดไปยังตำแหน่งที่เหมาะสมของโปรแกรม เพื่อที่จะเริ่มรันโปรแกรมนั้นใหม่อีกครั้ง
การย้าย Context
อัลกอริทึมของการจัดการเวลา
First-Come,First-Served(FCFS) Scheduling
กำหนดให้โพรเซสที่ร้องขอซีพียูก่อนเป็นโพรเซสที่ได้รับซีพียูก่อน เมื่อโฑรเซสอยู่ในสถานะพร้อมที่ทำงาน โพรเซสนั้นจะถูกนำเข้าไปต่อท้ายคิวพร้อม เมื่อซีพียูว่าระบบปฏิบัติการจะเรียกกำหนดการซีพียู เพื่อพิจารณามอบซีพียูให้แก่โพรเซสที่อยู่ในคิวพร้อม
สูตรในการคำนวณหาเวลาครบวงงาน
T=∑ni=1 Ti x 1/n เมื่อ Ti = Fi - Ai
Ti หมายถึง เวลาครบวงงานขงแต่ละโพรเซส (Turnaround time)
Fi หมายถึง เวลาที่แต่ละโพรเซสทำงานเสร็จสิ้น (Finish time)
Ai หมายถึง เวลาที่แต่ละโพรเซสเข้ามาในระบบ (Arrival time)
n หมายถึง จำนวนของโพรเซสที่เข้ามาในระบบ
T หมายถึง เวลาครบวงงานเฉลี่ยน (Average Turnaround time)
ตัวอย่าง
ระบบคอมพิวเตอร์มี 3 โพรเซสที่ต้องการเข้าใช้งานซีพียู คือ P1,P2 และ P3 เมื่อ
1.โพรเซส P1 เข้าระบบเมื่อเวลา 8.00 และต้องการใช้ซีพียู 2 หน่วยเวลา
2.โพรเซส P2 เข้าระบบเมื่อเวลา 8.10 และต้องการใช้ซีพียู 1 หน่วยเวลา
3.โพรเซส P3 เข้าระบบเมื่อเวลา 8.25 และต้องการใช้ซีพียู 0.25 หน่วยเวลา
1 more item...
Shortest-Job-First(SJF) Scheduling
อัลกอริทึมนี้จะให้งานสั้นทำก่อน จะพยายามลดค่าเฉลี่ยของเวลาครบวงงาน และค่าเฉลี่ยเวลารอ โดยกำหนดให้โพรเซสที่ต้องการใช้ซีพียูเป็นระยะเวลาน้อยได้เข้าใช้ซีพียูก่อนโพรเซสที่ต้องการใช้ซีพียูเป็นระยะเวลานาน อัลกอริทึมนี้สามารถทำงานได้ทั้งแบบ Preemptive และ Non-Preemptive process
ตัวอย่าง
ระบบคอมพิวเตอร์มี 3 โพรเซสที่ต้องการเข้าไปใช้งานซีพียู คือ
โพรเซส P1 เข้าระบบเมื่อเวลา 0.0 และต้องการใช้ซีพียู 8 หน่วยเวลา
โพรเซส P2เข้าระบบเมื่อเวลา 0.4 และต้องการใช้ซีพียู 4 หน่วยเวลา
โพรเซส P3 เข้าระบบเมื่อเวลา 1.0 และต้องการใช้ซีพียู 1 หน่วยเวลา
Non-Preemptive
ระบบจะยังคงให้โพรเซสเดิมทำงานต่อไปจนกว่าจะเสร็จสิ้นการทำงานของโพรเซสนั้น
P1 เริ่มทำงาน ณ เวลา 0.0 โดยมีค่า Finish Time = 8.0 หน่วยเวลา และค่า Turnaround Time = 8.0 หน่วยเวลา
P3 ต้องรอ P1 ทำงานให้เสร็จก่อนถึงจะเริ่มทำงาน ณ เวลา 8.0 เนื่องจาก P3 มีเวลาที่ใช้ซีพียูน้อยกว่า P2 จึงได้ทำงานก่อน P2 โดยมีค่า Finish Time = 9.0 หน่วยเวลา และค่า Turnaround Time = 8.0 หน่วยเวลา
P2 ต้องรอ P3 ทำงานให้เสร็จก่อนจึงจะเริ่มทำงาน ณ เวลา 9.0 เนื่องจาก P2 มีเวลาที่ใช้ซีพียูมากกว่า P3 จึงได้ทำงานต่อจาก P3 โดยมีค่า Finish Time = 13.0 หน่วยเวลา และค่า Turnaround Time = 12.0 หน่วยเวลา
เวลาครบวงงานเฉลี่ย = 28.6/3 =9.53 หน่วยเวลา
Preemptive
ขณะที่โพรเซสหนึ่งกำลังทำงานและมีโพรเซสใหม่เข้ามาในคิวพร้อม และโพรเซสใหม่ต้องการใช้ซีพียูเป็นเวลาน้อยกว่าโพรเซสที่กำลังทำงาน โพรเซสที่กำลังทำงานจะถูกขัดจังหวะ และคืนค่าให้แก่ระบบ เพื่อจะมอบซีพียูให้กับโพรเซสใหม่ที่ใช้เวลาน้อยกว่าได้เข้าไปทำงานที่ซีพียูก่อนหน้า
ณ เวลา 0.0 P1 เริ่มทำงาน
ณ เวลา 0.4 P2 เข้ามาขัดจังหวะเนี่องจาก P2 ใช้ซีพียูเป็นเวลาที่น้อยกว่า P1 (P1 เวลาที่เหลือ 7.6) ทำไปเรื่อยๆจน
ณ เวลา 1.0 P3 เข้ามาขัดจังหวะเนื่องจาก P3 ใช้ซีพียูเป็นเวลาน้อยกว่า P2 (P2 เวลาที่เหลือ 3.4) ทำไปจนเสร็จ
ณ เวลา 2.0 P2 เข้ามาทำงานต่อเนื่องจากเวลาที่เหลืออยู่น้อยกว่า P1 และทำต่อไปจนเสร็จ
ณ เวลา 5.4 P1 เข้ามาทำงานต่อจาก P2 และทำไปจนเสร็จ
สรุปการทำงาน
P1 มีค่า Finish Time = 13.0 และมีค่า Turnaround Time = 12.6
P2 มีค่า Finish Time = 5.4 และมีค่า Turnaround Time = 4.4
P3 มีค่า Finish Time = 2.0 และมีค่า Turnaround Time = 1.0
เวลาครบวงงานเฉลี่ย =19/3 = 6.33 หน่วยเวลา
Shortest-remaining-time-first
แนวคิดเวลาที่มาถึงโพรเซสที่แตกต่างกัน และวิเคราะห์การจัดลำดับใช้ซีพียูงานสั้นก่อนในแบบ Preemptive
P1 มีค่า Arrival Time =0 Burst Time = 8
P2 มีค่า Arrival Time =1 Burst Time = 4
P3 มีค่า Arrival Time =2 Burst Time = 9
P4 มีค่า Arrival Time =3 Burst Time = 5
การจัดอันลำใช้ซีพียูแบบงานสั้นไปก่อนในแบบ Preemptive สามารถแสดงได้ด้วย Gantt Chart
0--
P1
--1--
P2
--5--
P4
--10--
P1
--17--
P3
--26
ค่าเฉลี่ยของเวลาที่ใช้ในการรอ คือ = [(10-1)+(1-1)+(17-2)+(5-3)]/4 = 6.5 msec
ลำดับความสำคัญ (Priority Scheduling)
เป็นวิธีจัดลำดับการใช้ซีพียูโดยกำหนดลำดับความสำคัญให้แต่ละโพรเซส โดยระบบจะต้องกำหนดให้ตัวเลขที่มีค่าน้อยที่สุดแสเงลำดับความสำคัญน้อยที่สุด ให้ตัวเลขที่มีค่ามากที่สุดแสดงถึงลำดับความสำคัญมากสุด
โดยการทำงานจะเริ่มจากโพรเซสที่มีค่าความสำคัญมาที่สุดไปจนถึงน้อยที่สุด การทำงานของอัลกอริทึมนี้สามารถทำงานได้ทั้งแบบ Preemptive และ Non-Preemptive
Preemptive
โพรเซสที่มีลำดับความสำคัญต่ำกว่าถูกโพรเซสที่มีลำดับความสำคัญสูงกว่าแย่งชิงซีพียูไปใช้งาน ทำให้โพรเซสที่มีลำดับความสำคัญต่ำดว่าไม่มีโอกาสเข้าไปใช้ซีพียู และทำให้เกิดปัญหาการอดตาย
วิธีวนรอบ(Round-Robin Scheduling:RR)
ถูกออกแบบมาเพื่อใช้สำหรับระบบแบ่งเวลา โดยมีการทำงานเหมือนอัลกอริทึมแบบมาก่อนบริการก่อน แต่กำหนดโพรเซสใช้ซีพียูในเวลาที่จำกัด เรียกว่า เวลาควอนตัม(Quantum time) หรือ การแบ่งเวลา(time slice)
ในการทำงาน ตัวจัดลำดับการใช้ซีพียูจะเลือกโพรเซสจากต้นคิวพร้อมเข้าไปทำงานเป็นเวลา 1 เวลาควอนตัม ภายในระยะเวลาที่กำหนดถ้าโพรเซสไหนสามารถทำงานเสร็จ ก็จะคือซีพียูให้กับระบบแต่ถ้าไม่สามารถทำให้เสร็จภายในเวลา 1 เวลาควอนตัม โพรเซสก็จะถูกขัดจังหวะและนำไปต่อท้ายคิวพร้อม
การจัดตารางการทำงานสำหรับหลายหน่วยประมวลผล
ถ้าหน่วยประมวลผลมีหลายแบบ วิธีการจัดตารางก็จะถูกจำกัดมาก แต่ละหน่วยประมวลผลก็จะมีแถวคอยเป็นของตนเองเพราะโพรเซสต่างๆย่อมมีลักษณะเฉพาะที่จะทำงานได้ในหน่วยประมวลผลแบบหนึ่งเดียว
ถ้าหน่วยประมวลผลเป็นแบบเดียวกันหมด สามารถเฉลี่ยแบ่งงานกันทำได้ดีขึ้น โดยอาจให้มีแถวคอยแยกแต่ละหน่วยประมวลผล แต่วิธีนี้อาจทำให้หน่วยประมวลผลบางตัวว่างงาน ในขณะที่บางตัวทำงานหนัก ดังนั้นจึงควรใช้แถวคอยร่วมแถวเดียวกันให้ทุกๆโพรเซสเข้าแถวคอยแถวเดียวกันหมด เมื่อมีหน่วยประมวลผลใดว่างก็จะรับงานไปจากแถวคอยนี้
การจัดแถวคอยร่วม แบ่งได้ 2 วิธี
ให้หน่วยประมวลผลแต่ละตัวจัดตารางการทำงานเอง โดยเลือกแถวคอยเดียวกัน
ปัญหาหลักของวิธีนี้
คือ การที่หน่วยประมวลผลใช้ข้อมูลร่วมกัน ย่อมต้องการประประสานงานที่ดี เพื่อป้องกันปัญหาเขตวิกฤติ จำเป็นต้องทำให้แน่ใจว่าจะไม่มีหน่วยประมวลผลใดเลือกโพรเซศซ้ำกัน
กำหนดให้หน่วยประมวลผลหนึ่งมีหน้าที่จัดตารางการทำงานโดยเฉพาะ คอยจัดตารางการทำงานให้ทุกๆหน่วยที่เหลือ วิธีนี้เรียกว่า
วิธีเจ้านายและทาส
การประเมินอัลกอริทึม
การกำหนดโมเดล
วิธีนี้ทำโดยการกำหนดกลุ่มงานทดสอบขึ้นมาหนึ่งกลุ่ม แล้วคำนวณค่าคุณสมบัติของวิธีการจัดตารางแต่ละแบบ ผลลัพธ์ที่ได้สามารถเปรียบเทียบเป็นตัวเลขได้โดยตรง แต่มีข้อเสียคือ ผลลัพธ์ที่ได้อาจเป็นเฉพาะกรณีตามกลุ่มงานที่กำหนดขึ้นเท่านั้น วิธีนี้เหมาะเพียงการอธิบายการจัดตารางแบบต่างๆ เพื่อเป็นโมเดลการใช้งานที่เหมาะสม
ตัวอย่างเช่น กำหนดกลุ่มงานดังนี้
P1 Brust Time = 10
P2 Brust Time = 29
P3 Brust Time = 3
P4 Brust Time = 7
P5 Brust Time = 12
ให้ทั้ง 5 โพรเซสมาถึงระบบในเวลาเดียวกัน ที่เวลา 0 ตามลำดับ พิจารณาใช้วิธีการจัดตารางการทำงาน 3 แบบ คือ FCFS,SJF,RR(Quantum time = 10) แล้วคำนวณหาเวลารอคอยเฉลี่ยต่ำสุด
SJF
0--
P3
--3--
P4
--10--
P1
--20--
P5
--32--
P2
--61
เวลารอคอยเฉลี่ย = 13 มิลลิวินาที
RR(Quantum time = 10 )
0--
P1
--10--
P2
--20--
P3
--23--
P4
--30--
P5
--40--
P2
--50--
P5
--52--
P2
--61
เวลารอคอยเฉลี่ย = 23 มิลลิวินาที
FCFS
0--
P1
--10--
P2
--39--
P3
--42--
P4
--49--
P5
--61
เวลารอคอยเฉลี่ย = 28 มิลลิวินาที
การวิเคราะห์แถว
ผู้ให้บริการแต่ละตัวมีแถวคอยของตนเอง หน่วยประมวลผลกลาง(ผุ้ให้บริการประมวลผล) มีแถวพร้อมของตนเองอุปกรณ์รับส่งข้อมูลแต่ละตัว(บริการรับส่งข้อมูล) ก็มีแถวคอยอุปกรณ์ของตน
การจำลองสถานการณ์
เพื่อให้ได้ผลลัพธ์ถูกต้องใกล้เคียงมากขึ้น เราอาจจำลองเหตุการณ์จริงขึ้น โดยเขียนโปรแกรมตัวแบบของระบบคอมพิวเตอร์ และจำลองอุปกรณ์ต่างๆในระบบด้วยโครงสร้างข้อมูลที่เหมาะสม
การปฏิบัติจริง
วิธีนี้มีปัญหาสำคัญ คือ
ค่าใช้จ่ายสูงมาก
ไม่เพียงพอแต่ค่าใช้จ่ายในการเขียนโปรแกรมและแก้ไขระบบปฏิบัติการเท่านั้น แต่ยังมีผลกระทบต่อผู้ใช้โดยตรง นอกจากนี้การเปรียบเทียบวิธีต่างๆด้วยวิธะีนี้อาจได้ผลที่ไม่ถูกต้อง เราอาจกำหนดตัวแปรในระบบให้ผู้ควบคุมระบบสามารถแก้ไขวิธีจัดตารางได้ตลอดเวลา
เกณฑ์การวิเคราะห์ประสิทธิภาพ
มีเวลาครบวงงานน้อยที่สุด
เป็นเวลาต่อรอบงาน คือเป็นเวลาที่ผู้ใช้ต้องรอ โดยเริ่มตั้งแต่นำโพรเซสเข้าสู่ระบบจนได้รับผลลัพธ์หรือเอาต์พุตที่ต้องการกลับมา สิ่งที่ควรให้ความสำคัญคือแม้ว่าการใช้งานประมวลผลกลางสูง แต่ถ้าผู้ใช้ระบบต้องรอนาน อาจทำให้เกิดความล่าช้าต่อความต้องการของผู้ใช้งาน
มีเวลารอน้อยที่สุด
คือเวลาขอโพรเซสที่ถูกรอใน Ready queue
มีปริมาณงานมากที่สุด
ปริมาณงานต่อหน่วยเวลา เกณฑ์นี้เกี่ยวพันกับการใช้งานหน่วยประมวลผลกลาง ทั้งนี้ปริมาณงานที่ผ่านเข้ามาในระบบมาก หน่วยประมวลผลกลางจะถูกใช้งานมากตามปริมาณ
มีเวลาตอบสนองน้อย
เวลาที่มีการร้องขอข้อมูลหรือการส่งงงานเข้าไปในระบบและได้การตอบสนองกลับมาครั้งแรก(ไม่ใช่ผลลัพธ์)
มีการใช้งานหน่วยประมวลผลกลาง
จำเป็นให้หน่วยประมวลผลกลางถูกใช้งานให้มากที่สุด โดยปกติควรจะมีการใช้งานร้อยละ 40 ถึงร้อยละ 90 ทั้งนี้ขึ้นอยู่กับปริมาณงานในระบบ
คิวหลายระดับ
ถูกสร้างขึ้นจากแนวความคิดที่ว่า โพรเซสสามารถถูกแบ่งออกเป็นกลุ่มๆได้หลายกลุ่ม โพรเซสแต่ละกลุ่มจะมีเวลาการตอบสนองที่แตกต่าง จึงต้องการการจัดลำดับที่แตกต่างกันด้วย
การจัดตารางการทำงานแบบจัดลำดับหลายชึ้นแบบเลื่อนขั้นได้
โพรเซสที่เข้าสู่ระบบจะถูกกำหนดแถวที่แน่นอนตลอดเวลาการทำงาน โดยอาจเปลี่ยนแถวได้อีกเลย ซึ่งวิธีดังกล่าวไม่ยืดหยุ่นนัก การจัดตารางการทำงานแบบจัดลำดับหลายชั้นแบบเลื่อนชั้นได้นี้ จัมีวิธีการในการทำงานที่แก้ข้อเสียดังกล่าว
โพรเซสใดใช้เวลาในการทำงานกับหน่วยประมวลผลกลางนานเกินไป โพรเซสนั้นจะถูกย้ายลงไปในแถวที่มีค่าศักดิ์ต่ำกว่าแถวเดิม วิธีนี้จะทำให้โพรเซสที่เน้นการรับส่งข้อมูล และโพรเซสได้โต้ตอบถูกจัดอยู่ในแถวพร้อมที่มีศักดิ์สูงขึ้น
ถูกกำหนดโดยพารามิเตอร์ดังนี้
วิธีที่จะใช้ในการพิจารณาเพื่อที่จะยกระดับให้โพรเซสที่มีค่าศักดิ์สูงขึ้น
วิธีที่จะใช้ในการพิจารณาเพื่อที่จะลดระดับให้โพรเซสที่มีค่าศักดิ์น้อยลง
ขั้นตอนวิธีในการจัดตารางการทำงานของแต่ละแถว
วิธีที่จะใช้ในการพิจารณาว่า เมื่อโพรเซสเข้ามาในระบบ ควรจะให้อยู่ในแถวใด
จำนวนแถวพร้อม
การจัดตารางการทำงานแบบตอบสนองฉับพลัน
Hard Real-Time System
ต้องการเวลาที่คงที่แน่นอนตายตัว โดยทั่วไปโพรเซสจะได้รับเวลาจำนวนหนึ่งเพื่อนำไปทำงานให้เสร็จ ตัวจัดตารางการทำงานจะให้สิทธิโพรเซส เพื่อรับประกันว่าโพรเซสจะทำงานเสร็จตามเวลา หรือไม่ปฏิเสธการร้องขอของโพรเซสนั้น ถ้ามั่นใจว่าจะทำงานไม่เสร็จได้ตามเวลา การทำงานแบบนี้ถูกเรียกว่า
การจองทรัพยากร
Soft Real-Time System
ทำงานได้โดยไม่ต้องมีเวลามาจำกัด คือจะมีโพรเซสอยู่โพรเซสหนึ่งมีลำดับความสำคัญสูงกว่าโพรเซสอื่น การทำงานแบบ Soft Real-Time System อาจจะไม่เหมาะสมกับ Time sharing เพราะเกิดการล่าช้าหรือปัญหาการอดตาย แต่เหมาะกับระบบทั่วๆไป ที่สนับสนุนด้านมัลติมีเดีย กราฟฟิก เป็นต้น
เพื่อที่จะลดเวลาในการหยุดโพรเซสหนึ่งเพื่อให้อีกโพรเซสหนึ่งทำงาน ต้องอนุญาตให้โปรแกรมเรียกระบบที่สามารถแทรกกลางคันได้คือ
การแทรกโปรแกรม
การแทรกโปรแกรม คือ การเรียกระบบที่ทำงานในระยะยาวและเรียกจุดแทรกกลางคัน เพื่อตรวจสอบว่าโพรเซสที่มีลำดับความสำคัญสูงต้องได้ทำงานก่อน เมื่อโพรเซสดังกล่าวเสร็จงานโพรเซสที่ถูกขัดจังหวะจึงจะทำงานต่อ
ระยะที่เกิดการขัดแย้ง
เกิดการแทรกกลางคันของโพรเซสที่กำลังทำงานใน Kernel
โพรเซสที่มีลำดับความสำคัญต่ำปลดปล่อยทรัพยากรให้โพรเซสที่มีลำดับสำคัญสูง
หลักความต้องต้องการพื้นฐาน
ความต้องการที่จะให้ซีพียูมีการทำงานตลอดเวลา เพื่อให้มีการใช้ซีพียูอย่างเต็มที่และเต็มประสิทธิภาพ
ช่วงเวลาอินพุต/เอาต์พุต และช่วงเวลาใช้ซีพียู
ความสำคัญของการจัดเวลาของซีพียู ขึ้นอยู่กับคุณลักษณะการทำงานของโพรเซสโดยทั่วไปการทำงานของโพรเซสจะไปกอบไปด้วยเวลาที่ใช้ซีพียู และเวลาที่คอยอุปกรณ์อินพุต/เอารต์พุต ในขณะที่มีการทำงานโพรเซสจะมีการสลับการทำงานระหว่า 2 ช่วงเวลาเท่านั้น และจเกิดไม่พร้อมกัน
การทำงานมันเริ่มจาก การใช้ซีพียู และตามด้วยรออินพุต/เอาต์พุต เมื่อจบการรอคอยก็จะตามมาด้วยเวลาขอซีพียู สลับกันไปเรื่อยๆ จนกว่าจะทำงานเสร็จ