ใบงานที่ 4 การจัดเวลาซีพียูCPU Scheduling

ใบงานที่ 4 การจัดเวลาซีพียู CPU Scheduling

นาย ไชยวัฒน์ เริงกะชีวิต เลขที่ 2

รหัส 6031280002

• การจัดเวลาซีพียู
• การจัดคิวในระยะสั้น
• การจัดคิวในระยะยาวระบบหลายโปรเซสเซอร์
• การทำงานของระบบหลายโปรเซสเซอร์

การจัดเวลาซีพียู  (CPU Scheduling)

• การจัดเวลา CPU เป็นหลักการทำงานหนึ่งของ OS ที่ทำให้คอมพิวเตอร์มีความสามารถในการรันโปรแกรมได้หลาย ๆ โปรแกรมในเวลาเดียวกัน

• เหตุการณ์ที่ซีพียูเปลี่ยนจากการทำงานหนึ่งไปยังอีกงานหนึ่งเรียกว่า การเปลี่ยนสถานะ (context switching)

ข้อพิจารณาในการจัดเวลา

• การใช้สอยซีพียู (CPU Utilization)
• ทรูพุต (Throughput)
• เวลาทั้งหมด (Turnaround Time)
• เวลารอคอย (Waiting Time)
• เวลาตอบสนอง (Response Time)

  การใช้สอยซีพียู(CPU Utilization) : การใช้ประโยชน์จากซีพียูอย่างสูงสุด โดยทำให้ซีพียูมีงานทำมากที่สุดเท่าที่จะทำได้  ซีพียูควรจะถูกใช้อยู่ระหว่าง 40-90 %

  ทรูพุต (Throughput) : จำนวนงานที่เสร็จต่อหน่วยเวลา

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

  เวลารอคอย (Waiting Time) : ช่วงเวลาที่งานใดงานหนึ่งต้องรอการทำงานของตัวจัดเวลา โดยไม่รวมเวลาของการใช้ซีพียู และเวลาของการติดต่ออินพุต/เอาต์พุต ส่วนใหญ่ก็คือเวลาที่งานต้องคอยอยู่ในคิว (Ready Queue)

  เวลาตอบสนอง (Response Time) : คือเวลาที่วัดระหว่างเวลาที่มีการร้องขอการกระทำใด  ๆ  ต่อระบบแล้วมีการตอบรับกลับออกมา (ความเร็วของเวลาตอบสนองจึงมักจะขึ้นอยู่กับอุปกรณ์อินพุต/เอาต์พุต)

การจัดคิวระยะสั้น(Short-term scheduling)

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

การจัดคิวระยะสั้นมีดังนี้

• การจัดคิวแบบ FCFS
• การจัดคิวแบบ RR
• การจัดคิวแบบลำดับความสำคัญ
• การจัดคิวแบบ SJN
• การจัดคิวแบบ SRT
• การจัดคิวแบบหลายระดับ

  ข้อดีคือ : การจัดคิวทำได้ง่ายไม่ยุ่งยากซับซ้อนตัวอย่างการจัดคิวเมื่อมี 3 โปรเซส ( A,B,C) ต้องการใช้ CPU

ปัญหาสำหรับการจัดคิวแบบ SJF คือ : ตัวจัดคิวระยะสั้นไม่ทราบว่าแต่ละโปรเซสต้องการใช้เวลาเท่าใด
  วิธีแก้คือ
   ให้แต่ละโปรเซสกำหนดเวลาที่ต้องการในการใช้ CPU มาด้วยให้ OS สร้างโปรเซสเพื่อคำนวณเวลาโดยประมาณของแต่ละโปรเซสที่ต้องการใช้ CPU

  คำถาม
  ถ้าเป็นการจัดคิวแบบ FCFS เวลาเฉลี่ยในการรอและเวลาเฉลี่ยในการทำงานเสร็จเท่ากับเท่าใด
  ถ้าเป็นการจัดคิวแบบ SJFเวลาเฉลี่ยในการรอและเวลาเฉลี่ยในการทำงานเสร็จเท่ากับเท่าใด

  คำตอบ
  เวลาเฉลี่ยในการรอและเวลาเฉลี่ยในการทำงานเสร็จในการทำงานและแบบ

Priority
    เวลาเฉลี่ยในการรอ =6.75
    เวลาเฉลี่ยในการทำงานเสร็จ =11.25
FCFS
    เวลาเฉลี่ยในการรอ =8.5
    เวลาเฉลี่ยในการทำงานเสร็จ =13
SJF
    เวลาเฉลี่ยในการรอ =3
    เวลาเฉลี่ยในการทำงานเสร็จ =7.5

การจัดคิวแบบวนรอบ (Round-Robin : RR)

  ใช้กับระบบงานคอมพิวเตอร์แบบแบ่งเวลา โดยมีลักษณะการจัดคิวเป็นแบบ FCFS แต่ให้มีกรรมวิธีของการให้สิทธิในการครอบครอง CPU ของแต่ละโปรเซส คือ “แต่ละโปรเซสที่เข้ามาในระบบจะถูกจำกัดเวลาการเข้าไปใช้ CPU เท่า ๆ กัน ” ซึ่งเรียกช่วงเวลานี้ว่า เวลาควันตัม (Quantum Time)

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

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

 

 

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

การจัดคิวแบบหลายระดับ

 

  การจัดคิวดังที่กล่าวมาแล้วทั้งสิ้นเป็นการจัดคิวภายในคิวเพียง 1 คิว เรียกว่าการจัดคิวแบบ 1 ระดับดังรูป







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

 

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

ระบบหลายโปรเซสเซอร์
(Multi-processor System)

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

• คำสั่งเดี่ยวและข้อมูลเดี่ยว ( Single Instruction Single Data : SISD )
• คำสั่งเดี่ยวและหลายชุดข้อมูล ( Single Instruction Multiple Data : SIMD )
• หลายชุดคำสั่งและข้อมูลเดี่ยว ( Multiple Instruction Single Data : MISD )
• หลายชุดคำสั่งและหลายชุดข้อมูล ( Multiple Instruction Multiple Data : MIMD ) 

คำสั่งเดี่ยวและข้อมูลเดี่ยว
( Single Instruction Single Data : SISD )

  คอมพิวเตอร์ที่ใช้งานทั่วไปในปัจจุบันจะเป็นประเภท SISDระบบคอมพิวเตอร์ประเภทนี้มีโปรเซสเซอร์อยู่เพียงตัวเดียว
  การทำงานของโปรเซสเซอร์ในระบบนี้จะทำงานได้ทีละ 1 คำสั่งและรับข้อมูลได้ 1 ชุด
P (Processor) แทนโปรเซสเซอร์ I (Instruction) แทนคำสั่ง D (Data) แทนข้อมูล และ O (Output) แทนผลลัพธ์

 

คำสั่งเดี่ยวและหลายชุดข้อมูล
( Single Instruction Multiple Data : SIMD )

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

 SIMD มีประโยชน์ต่องานทางด้านการคำนวณที่ต้องการคำนวณแบบเดียวกันกับข้อมูลหลาย ๆ ชุดเช่น การบวกเมตริกซ์ เช่น

 
 





 

หลายชุดคำสั่งและข้อมูลเดี่ยว
(Multiple Instruction Single Data : MISD ) 

  การทำงานของระบบนี้เป็นการทำงานของโปรเซสเซอร์หลายตัวพร้อมกัน หรือที่เรียกว่าทำงานขนานกัน (parallel processing)
  โดยโปรเซสเซอร์ทุกตัวจะมีคำสั่งของตนเอง แต่ทุกตัวจะใช้ข้อมูลชุดเดียวกัน

 

  เมื่อโปรเซสเซอร์ตัวแรกทำงานเสร็จ ผลลัพธ์ที่ได้จะเป็นข้อมูลของโปรเซสเซอร์ตัวต่อไป เช่นถ้าในระบบ MISD หาค่าจากสมการนี้ y = 2*X2+4 โดยที่ x มีค่าระหว่าง 1 ถึง 5

จากตัวอย่างพบว่ามี 3 คำสั่ง
หาค่า X ยกกำลัง 2
คูณผลลัพธ์จากข้อแรก ด้วย 2
เพิ่มค่าผลลัพธ์ที่ได้จากข้อ 2 ด้วย 4 

หลายชุดคำสั่งและหลายชุดข้อมูล
(Multiple Instruction Multiple Data : MIMD )

  การทำงานของระบบนี้เป็นการทำงานของโปรเซสเซอร์หลายตัวพร้อมกันและโปรเซสเซอร์แต่ละตัวจะมีคำสั่งและข้อมูลเป็นของตนเอง

  ดังนั้นในการทำงานแต่ละโปรเซสเซอร์จะเป็นอิสระจากกัน
ตัวอย่างระบบคอมพิวเตอร์ประเภท MIMD ที่เห็นได้ชัดเจนคือระบบเครือข่ายคอมพิวเตอร์ (Computer Network)

อ้างอิง

www.chantra.sru.ac.th

แบบฝึกหัดท้ายบท

 

1.จงอธิบายข้อดีของรูปแบบการทำงานแบบ SJF

ตอบ SJF จะให้ค่าเฉลี่ยของการคอยได้ต่ำที่สุด เพราะมีการเลื่อนโปรเซสที่มีเวลาใช้ CPU น้อยสุดมาไว้หน้าคิว

2. จงอธิบายข้อดีข้อเสียของรูปแบบการทำงานแบบ RR

ข้อดี การสร้างระบบการทำงานแบวนรอบ เราจะทำคิวที่พร้อมทำงาน (Ready Queue) เป็นแบบมาก่อนได้ก่อนไว้สำหรับเก็บโปรเซสต่างๆ โปรเซสที่เข้ามาใหม่จะถูกนำมาต่อไว้ที่หางของคิว ตัวจัดเวลาจะเลือกเอาโปรเซสที่อยู่ตรงหัวคิวออกมา แล้วกำหนดให้ไทม์เมอร์หยุดการให้เวลาซีพียูหลังจากนั้น 1 ควันตัม แล้วนำโปรเซสออกไปต่อที่หางคิว ถ้าหากว่าโปรแกรมยังไม่สิ้นสุดการทำงาน
ข้อเสีย เวลาเฉลี่ยของการคอยในกรรมวิธีของวนรอบจะค่อนข้างนาน ให้ลองพิจารณาตัวอย่างของการเอ็กซิคิวต์โปรเซส 3 โปรเซส ดังต่อไปนี้ในแบบวนรอบ โดยที่โปรเซสทั้ง 3 เข้ามาถึงระบบพร้อมๆ กัน

3. จงอธิบายข้อเสียของรูปแบบการทำงานแบบลำดับความสำคัญ

ตอบ ถ้าข้อมูลที่มีความสำคัญน้อยจะได้ทำงานที่หลังซึ่งทำให้เกิดความล้าช้าได้

4. การจัดคิวรูปแบบใดมีการใช้เวลาควันตัม

ตอบ การจัดเวลาแบบวนรอบ (RR : Round – Robin Scheduling)5. Short-term 

5.scheduler ทำหน้าที่อย่างไร

ตอบ จัดลำดับงาน (process) ที่ยูสเซอร์ต้องการใช้งานหลาย ๆ งานพร้อมกันบนเครื่องคอมพิวเตอร์นั้น ให้ CPU สามารทำงานได้อย่างมีประสิทธิภาพ

6. ตัวจัดคิวระยะสั้นกับระยะยาวแตกต่างกันอย่างไร

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

7. การบวกเมตริกซ์ ใช้รูปแบบ processor แบบใด

ตอบ parallel processing

8. ลักษณะการจัดคิวแบบใดมีค่าเฉลี่ยในการรอน้อยที่สุด

ตอบ การจัดคิวแบบงานสั้นทำก่อน (Short-Job-first : SJF)

9. ระยะเวลาที่โปรเซสทำงานเสร็จมีหลักการคำนวณอย่างไร

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

10. ตัวส่ง Dispatcher ทำหน้าที่อย่างไร

ตอบ  Dispatcher ซึ่งเป็นโมดูลที่ทำหน้าที่ควบคุมการครอบครองเวลา cpu ของ process ฟังก์ชันนี้ประกอบด้วย
• การย้าย Context
• การย้ายไป user mode
• กระโดดไปยังตำแหน่งที่เหมาะสมของโปรแกรม เพื่อที่จะเริ่มรันโปรแกรมนั้นใหม่อีกครั้ง

Dispatcher นี้ควรมีการทำงานที่เร็วที่สุดเท่าที่จะทำได้ เพราะว่ามันจะต้องทำงานทุกครั้งที่มีการย้าย process ซึ่งเวลาที่ถูกใช้ไปกับการทำเช่นนี้เราเรียกว่า Dispatch Latency