ใบงานที่3การจัดเวลาซีพียู (CPU Scheduling)
จัดทำโดย นายอนุชิต หุ่นออนไพร รหัสนักศึกษา 6031280067
การจัดเวลาซีพียู (CPU Scheduling)
การจัดเวลาซีพียู (cpu Scheduling) เป็นหลักการทำงานหนึ่งของระบบปฏิบัติการที่ทำให้คอมพิวเตอร์มีความสามารถในการรันโปรแกรมหลายๆ โปรแกรมในเวลาเดียวกัน ซึ่งการแบ่งเวลาการเข้าใช้ซีพียูให้กับโปรเซสที่อาจถูกส่งมาหลายๆ โปรเซสพร้อมๆกัน ในขณะที่ซีพียูอาจมีจำนวนน้อยกว่าโปรเซส หรืออาจมีซีพียูเพียงตัวเดียว จะทำให้คอมพิวเตอร์สามารถทำงานได้ปริมาณงานที่มากขึ้นกว่าการที่ให้ซีพียูทำงานให้เสร็จทีละโปรเซส ในบทนี้ เราจะมาพูดถึงอัลกอริทึมพื้นฐานของการจัดเวลาซีพียูนี้ โดยจะพูดถึงวิธีการหลักๆ ที่แต่ละอัลกอริทึมมีแตกต่างกัน ข้อดีข้อเสีย และความเหมาะสมต่อระบบงานแบบต่างๆ เพื่อการเลือกใช้อย่างถูกต้อง
3.1 หลักความต้องการพื้นฐาน
จุดประสงค์ของการรันโปรแกรมหลายโปรแกรมคือ ความต้องการที่จะให้ซีพียูมีการทำงานตลอดเวลาเพื่อให้มีการใช้ซีพียูอย่างเต็มที่ และเต็มประสิทธิภาพ ซึ่งระบบคอมพิวเตอร์มีซีพียูตัวเดียว ในเวลาใดเวลาหนึ่งซีพียูจะทำงานได้เพียงงานเดียวเท่านั้น ถ้ามีหลายโปรแกรมหรือหลายงาน งานที่เหลือก็ต้องคอยจนกว่า จะมีการจัดการให้เข้าไปใช้ซีพียู
ความคิดและหลักการของการทำงานกับหลายโปรแกรมในขั้นพิ้นฐานนั้นค่อนข้างที่จะไม่ซับซ้อน แต่ละโปรแกรมจะถูกรันจนกระทั่งถึงจุดที่มันจะต้องคอยอะไรซักอย่างเพื่อใช้สำหรับการทำงานช่วงต่อไป ส่วนมากการคอยเหล่านี้ก็คือการทำงานที่เกี่ยวข้องกับอินพุต/เอาต์พุตนั้นเอง ในระบบคอมพิวเตอร์ที่มีความสามารถรันโปรแกรมได้ทีละโปรแกรม การทำงานของระบบก็จะไม่ซับซ้อน ซีพียูจะหยุดการทำงานในระหว่างที่คอยอินพุต/เอาต์พุตนี้ ซึ่งการคอยเหล่านี้เป็นการเสียเวลาโดยเปล่าประโยชน์ เพราะซีพียูไม่ได้ทำงานเลย
ส่วนหลักในการรันหลายโปรแกรม เราพยายามใช้เวลาเวลาที่ซีพียูต้องคอยนี้ทำงานอย่างอื่นต่อไป ดังนั้นเมื่อใดก็ตามที่ซีพียูต้องคอย และยังมีโปรแกรมในหน่วยความจำหลายโปรแกรมที่คอยการใช้ซีพียูอยู่ เราจะจัดให้ซีพียู ทำงานในโปรแกรมเหล่านั้นทันที ซึ่งระบบจะจัดการนำเอาโปรแกรมที่คอยอินพุต/เอาต์พุต ออกไปก่อน เพื่อที่จะให้โปรแกรมอื่นที่คอยใช้ซีพียูนี้ สามารถเข้ามาได้ ถ้าทำงานในแบบนี้ไปเรื่อยๆ ซีพียูก็จะได้มีงานเกือบตลอดเวลากับโปรแกรมหลายๆ โปรแกรมที่อยู่ในระบบ
การจัดเวลาให้กับซีพียูแบบนี้ เป็นหลักความต้องการพื้นฐานของระบบปฏิบัติการในคอมพิวเตอร์ ทรัพยากรที่คอมพิวเตอร์มีอยู่ในเครื่องๆหนึ่ง จะถูกจัดสรรการใช้ก่อนการนำไปให้โปรแกรมใดๆ ซีพียูเองก็ถือได้ว่าเป็นทรัพยากรของระบบคอมพิวเตอร์ชนิดหนึ่งที่มีความสำคัญมากที่สุด โดยซีพียูนี่เอง ที่จะเป็นศุนย์กลางของการสร้างระบบปฏิบัติการที่มีความสามารถในการรันหลายโปรแกรม
ข้อพิจารณาในการจัดเวลา
การใช้สอยซีพียู(CPU Utilization) : การใช้ประโยชน์จากซีพียูอย่างสูงสุด โดยทำให้ซีพียูมีงานทำมากที่สุดเท่าที่จะทำได้ ซีพียูควรจะถูกใช้อยู่ระหว่าง 40-90 %
การจัดคิวระยะสั้น(Short-term scheduling)
- การจัดคิวแบบมาก่อนได้ก่อน(First-come-first-served : FCFS) … ต่อ
- 1. แบบมาก่อนได้ก่อน (First- Come- First-Served Scheduling: FCFS) เป็นวิธีการจัดการที่มีความเข้าใจง่าย กล่าวคือโปรเซสใดก็ตามที่มีการร้อนขอซีพียูก่อนก็สามารถครอบครองเวลาซีพียูได้ก่อน โดยเป็นไปตามลำดับเวลาของการเข้ามาในลำดับคิวข้อดีของการจัดคิวแบบ FCFS นั้นเป็นอัลกอริทึมที่ง่าย ไม่ยุ่งยากซับซ้อน
รูปที่ 1 การกำหนดเวลาแบบ FCFเวลารอคอย (waiting time) P1=O, P2=24, P3=27เวลารอคอยโดยเฉลี่ย ( Average waiting time) = ( 0+ 24+27)/3 =17วินาที
จากผลลัพธ์เวลารอคอยโดยเฉลี่ยของวิธี FCFS ดังกล่าว เป็นจุดเสียของการจัดลำดับคิวแบบFCFS เป็นP2P3P10 24 27 30เวลารอคอย (Waiting time) P1=6, P2=0, P3=3เวลารอคอยโดยเฉลี่ย (Average waiting time) = (6+0+3)/3=3 ในกรณีที่สองนี้จะเห็นว่ามีเวลารอคอยที่ลดลงมาก ซึ่งวิธีนี้คงไม่สามารถควบคุมปรับให้ตรงตามความต้องการข้างต้นได้ เพราะหากบังเอิญโปรเซสต้น ๆ มีเวลาในการทำงานน้อยก็ทำให้เกิดเวลารอคอยน้อย แต่ถ้าหากว่าโปรเซสต้น ๆ มีระยะเวลาในการรันที่ยาวนานจะทำให้โปรเซสที่ใช้เวลารันงานน้อยในอันดับท้ายๆ มีเวลารอคอยที่นาน จึงมีผลให้เกิดภาวะอดตาย(Starvation) - อย่างมาก เช่น ในโปรเซสที่ P2 ต้องการใช้เวลาในการทำงานเพียง 3 วินาที แต่ก็ต้องรอให้โปรเซส P1 ทำงานจนเสร็จสิ้นเสียก่อน ซึ่งต้องใช้เวลารอนานถึง 24 วินาที และโปรเซส P3 ต้องรอนานถึง 27 วินาที หากในกรณีที่มีโปรเซสเข้ามาเป็นลำดับใหม่ดังนี้คือ P2, P3 และ P1 ก็จะได้
จากตัวอย่างจะพบว่าการจัดคิวแบบ FCFS เป็นผลเสียอย่างมากกับโปรเซส B คือ โปรเซส B ต้องการเวลาในการทำงานเพียง 1 วินาที แต่ต้องรอให้โปรเซส A ซึ่งเข้ามาก่อนทำงานเสร็จ
เวลาเฉลี่ยในการรอ = (15+16)/3 = 10.33 วินาที
ทำให้การทำงานของโปรเซส B นั้นใช้เวลา 16 วินาทีจึงจะเสร็จสิ้น
เทียบเวลาในการทำงานคือ 1/16*100 = 6 %
สำหรับเวลาในการรอคือ 100-6 = 94 % ซึ่งจะเห็นว่าโปรเซส B ต้องเสียเวลารอนานมาก
การจัดคิวแบบงานสั้นทำก่อน(Short-Job-first : SJF)
จากปัญหาของการจัดคิวแบบมาก่อนได้ก่อน จึงทำให้เกิดแนวคิดที่จะคัดเลือกโปรเซสที่ต้องการเวลาในการทำงานน้อยที่สุดเข้ามาใช้ CPU ก่อนเพื่อทำให้ โปรเซสที่ต้องการเวลาในการทำงานจบออกไปได้เร็วขึ้น และจำนวนโปรเซสที่รออยู่ในคิวก็จะมีจำนวนลดลง
แต่ถ้ามีโปรเซสหลายตัวที่มีความต้องการเวลาในการทำงานเท่ากัน ก็จะใช้หลักการแบบมาก่อนได้ก่อนมาใช้ในการคัดเลือก
ตัวอย่างการจัดคิวเมื่อมี 4 โปรเซส (A,B,C,D) ต้องการใช้ CPU โดยมีลำดับการเข้ามาในคิวเป็น A,B,C,D
จากการทดลองพบว่า SJF จะให้ค่าเฉลี่ยของการคอยได้ต่ำที่สุด เพราะมีการเลื่อนโปรเซสที่มีเวลาใช้ CPU น้อยสุดมาไว้หน้าคิว
ปัญหาสำหรับการจัดคิวแบบ SJF คือ ตัวจัดคิวระยะสั้นไม่ทราบว่าแต่ละโปรเซสต้องการใช้เวลาเท่าใด
วิธีแก้คือ
ให้แต่ละโปรเซสกำหนดเวลาที่ต้องการในการใช้ CPU มาด้วยให้ OS สร้างโปรเซสเพื่อคำนวณเวลาโดยประมาณของแต่ละโปรเซสที่ต้องการใช้ CPU
การจัดคิวแบบตามลำดับความสำคัญ (Priority Queue)
วิธีนี้จะมีการจัดลำดับความสำคัญให้กับแต่ละโปรเซสที่ต้องการใช้ CPU
โปรเซสที่อยู่ ณ. ต้นคิวก็จะเป็นโปรเซสที่มีความ สำคัญมากที่สุด และลดลงเรื่อย ๆ
โปรเซสที่อยู่ท้ายคิวคือโปรเซสที่มีความสำคัญต่ำสุด
ถ้ามีโปรเซสใหม่เข้ามาในคิว ก็จะมีการแซงคิวได้ถ้าโปรเซสที่เข้ามาใหม่มีลำดับความสำคัญสูงกว่าโปรเซสที่กำลังบรรจุอยู่ในคิว
การจัดคิวแบบงานที่เหลือเวลาน้อยทำก่อน (Shortest-remaining-first : SRJ)
วิธีการนี้จะคล้ายกับแบบ SJF แต่ SRJ จะนำเอาโปรเซสที่เหลือเวลาในการใช้ CPU น้อยที่สุดมาอยู่ที่ต้นคิวเพื่อเข้าไปใช้งาน CPU ก่อน
วิธีการนี้จะทำให้ทั้งโปรเซสที่ต้องการเวลาในการใช้ CPU น้อย และโปรเซสที่ต้องการเวลาในการใช้ CPU มากแต่ใกล้จะจบสามารถออกจากระบบได้เร็วขึ้น
วิธีการนี้นอกจากจะต้องทราบเวลาที่ต้องการใช้ CPU แล้วยังต้องมีการบันทึกเวลาที่โปรเซสทำงานไปแล้วด้วย
การจัดคิวแบบวนรอบ (Round-Robin : RR)
ใช้กับระบบงานคอมพิวเตอร์แบบแบ่งเวลา โดยมีลักษณะการจัดคิวเป็นแบบ FCFS แต่ให้มีกรรมวิธีของการให้สิทธิในการครอบครอง CPU ของแต่ละโปรเซส คือ “แต่ละโปรเซสที่เข้ามาในระบบจะถูกจำกัดเวลาการเข้าไปใช้ CPU เท่า ๆ กัน ” ซึ่งเรียกช่วงเวลานี้ว่า เวลาควันตัม (Quantum Time)
ตัวจัดเวลาระยะสั้นจะมีการให้ CPU กับโปรเซสที่อยู่ในคิวแบบวนรอบ โดยมีกฏเกณฑ์ว่า ถ้าโปรเซสใดไม่สามารถกระทำได้สำเร็จภายใน 1 ควันตัม โปรเซสจะต้องถูกนำกลับไปไว้ในคิวเช่นเดิม
สถานภาพต่าง ๆ ของโปรเซสที่ยังทำไม่เสร็จจะถูกบันทึกไว้ เมื่อถึงโอกาสได้ครอบรอง CPU อีก ก็จะได้เริ่มต้นรันต่อจากครั้งที่แล้วโดยไม่ต้องเริ่มใหม่ทั้งหมด
การจัดคิวแบบวนรอบ
จากตัวอย่างจะเห็นว่าการทำงานแบบ RR จะเป็นประโยชน์ต่อโปรเซส B หรือโปรเซสที่ต้องการเวลาในการใช้ CPU น้อยแต่เข้าคิวมาทีหลัง
ในทางตรงกันข้ามจะเกิดผลเสียต่อโปรเซส A หรือโปรเซสที่ต้องการเวลาในการใช้ CPU มากประสิทธิภาพของการวนรอบขึ้นอยู่กับการกำหนดขนาดของควันตัมเป็นอย่างยิ่ง
ถ้าขนาดของควันตัมใหญ่หรือนานเกินไป ประสิทธิภาพของการวนรอบก็จะใกล้เคียงกับแบบมาก่อนได้ก่อน
ถ้าขนาดของควันตัมเล็กเกินไป ระยะเวลาที่ใช้ในการทำงานของระบบ (throughput) ก็จะช้าลง
การจัดคิวแบบหลายระดับ
- การจัดคิวแบบหลายระดับนั้น แต่ละคิวไม่จำเป็นเป็นต้องเป็นประเภทเดียวกัน
- การคัดเลือกโปรเซสนั้นจะคัดเลือกจากคิวที่ 1 ก่อนจนกระทั่งโปรเซสภายในคิวที่ 1 ทำงานเสร็จทั้งหมด แล้วจึงคัดเลือกโปรเซสในคิวลำดับถัดไป
- โปรเซสที่มีความสำคัญมาก มักจะอยู่ในคิวระดับแรก โปรเซสที่มีลำดับความสำคัญน้อยลงไปก็จะอยู่ในคิวระดับหลัง
- โปรเซสประเภทเดียวกันมักอยู่ในคิวระดับเดียวกัน
การจัดคิวระยะสั้นเป็นการจัดคิวในระดับโปรเซส โดยมีตัวจัดคิวระยะสั้นทำหน้าที่คัดเลือกโปรเซสที่อยู่ในคิวที่มีสถานะพร้อม ส่งเข้าไปอยู่ในสถานะรัน
การจัดคิวระยะยาวเป็นการจัดคิวในระดับงาน ไม่ใช่ระดับโปรเซส
เมื่อผู้ใช้ส่งงานเข้ามาในระบบ งานเหล่านี้จะไปรออยู่ในคิวงานเมื่อระบบอยู่ในสภาพพร้อมที่จะรับโปรเซสใหม่ได้ เช่น มีหน่วยความจำเหลือมาก
อ้างอิง
http://csnon04.blogspot.com/2008/03/3_06.html
https://www.google.co.th/search?q=%E0%B8%81%E0%B8%B2%E0%B8%A3%E0%B8%88%E0%B8%B1%E0%B8%94%E0%B8%84%E0%B8%B4%E0%B8%A7%E0%B8%A3%E0%B8%B0%E0%B8%A2%E0%B8%B0%E0%B8%AA%E0%B8%B1%E0%B9%89%E0%B8%99%E2%80%8B&rlz=1C1CHZL_enTH769TH769&source=lnms&tbm=isch&sa=X&ved=0ahUKEwiV4sfnib3XAhVLC5AKHWLCDJAQ_AUICigB&biw=1366&bih=637#imgrc=yNplLsCGsj7eTM:
https://www.google.co.th/search?q=%E0%B8%81%E0%B8%B2%E0%B8%A3%E0%B8%88%E0%B8%B1%E0%B8%94%E0%B8%84%E0%B8%B4%E0%B8%A7%E0%B9%81%E0%B8%9A%E0%B8%9A%E0%B8%87%E0%B8%B2%E0%B8%99%E0%B8%AA%E0%B8%B1%E0%B9%89%E0%B8%99%E0%B8%97%E0%B8%B3%E0%B8%81%E0%B9%88%E0%B8%AD%E0%B8%99+%E2%80%8B+(Short-Job-first+:+SJF)+%E2%80%A6+%E0%B8%95%E0%B9%88%E0%B8%AD%E2%80%8B&source=lnms&tbm=isch&sa=X&ved=0ahUKEwiIxZqBjr3XAhXKo48KHVb4AL4Q_AUICigB&biw=1366&bih=588#imgrc=zhGX2GHixjL_GM:
https://www.google.co.th/search?q=%E0%B8%81%E0%B8%B2%E0%B8%A3%E0%B8%88%E0%B8%B1%E0%B8%94%E0%B8%84%E0%B8%B4%E0%B8%A7%E0%B9%81%E0%B8%9A%E0%B8%9A%E0%B8%95%E0%B8%B2%E0%B8%A1%E0%B8%A5%E0%B8%B3%E0%B8%94%E0%B8%B1%E0%B8%9A%E0%B8%84%E0%B8%A7%E0%B8%B2%E0%B8%A1%E0%B8%AA%E0%B8%B3%E0%B8%84%E0%B8%B1%E0%B8%8D+%E2%80%8B&source=lnms&tbm=isch&sa=X&ved=0ahUKEwjAmPXDjr3XAhURT48KHb-OC_8Q_AUICigB&biw=1366&bih=588#imgrc=gKNfqeuJW9puWM:
ความคิดเห็น
แสดงความคิดเห็น