ใบงานที่ 4 การจัดการเวลาCPU

โดยนายพลวัต เทพศร รหัสนักศึกษา6031280058

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

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

ในการประมวลผลหลายโปรแกรม

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

-อรรถประโยชน์ของซีพียู(CPU Utilization)คือการใช้ประโยชน์จากซีพียูอย่างสูงสุด

-ปริมางานงาน(Throughput)ที่กำลังถูกทำเสร็จซึ่งสามารถที่จะวัดออกมาได้เป็นจำนวนงานที่เสร็จต่อหน่วยเวลา

-เวลาทั้งหมด(Turnaround Time)คือช่วงเวลาทั้งหมดที่ใช้ในการทำงานใดงานหนึ่งตั้งแต่เริ่มต้นเข้าไปในระบบจนงานถูกทำ

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

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

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

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

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

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

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

1. First-Come, First-Served Scheduling : FCFS (มาถึงก่อนได้รับบริการก่อน)
วิธีนี้เป็นวิธีที่ง่ายที่สุดในการจัดลำดับการทำงานของ process บน CPU โดยใช้หลักเกณฑ์ง่าย ๆ ว่า process ไหนที่ร้องขอใช้งาน CPU และเข้ารออยู่ใน ready queue (process ที่อยู่ในหน่วยความจำหลัก) ก่อนก็จะได้รับสิทธ์ในการเข้าใช้งาน CPU ก่อน เมื่อ process แรกทำงานเสร็จ process ที่มาถึงในลำดับถัดไปก็จะได้สิทธ์ในการทำงานบน CPU เป็นลำดับถัดไป ตัวอย่างข้างล่าแสดงถึงลำดับการมาถึงของ process และ burst บอกเวลาที่ใช้ในการทำงานบน CPU ตามลำดับ
Process          Burst
P1                  24
P2                    3
P3                    3
จากข้อมูลด้านบนเราสามารถคำนวณเวลาทั้งหมดที่ต้องใช้ไปเพื่อให้การทำงานของแต่ละ process เสร็จสมบูรณ์ (turn around time) และเวลาที่ใช้ในการรอของแต่ละ process (waiting time)ได้ดังนี้
จากในรูปเวลาเฉลี่ยที่ต้องในการทำงานให้เสร็จสิ้นของ process ทั้งหมดคือ 27 และเวลาเฉลี่ยที่ต้องใช้ในการรอของ process ทั้งหมดคือ 17  ข้อเสียของวิธีนี้ก็คือ เวลาที่จะต้องรอคอยในการเข้าทำงานบน CPU ของ process ที่มาถึงในลำดับท้าย ๆ นั้นจะนานมาก  และเวลาเฉลี่ยที่ต้องใช้ในการรอคอยก็สูงมากเช่นเดียวกัน FCFS จึงไม่เหมาะกับระบบที่เป็น time-sharing พึงสังเกตุว่า FCFS เป็นการจัดลำดับการทำงานแบบ nonpreemptive

2. Shortest-Job-First Scheduling : SJF ให้งานที่ใช้เวลาน้อยที่สุดได้ทำงานก่อน
วิธีนี้ ถ้ามี process ที่มาถึง ready queue พร้อม ๆ กัน จะต้องจัดให้ process ที่มีเวลาในการทำงานน้อยกว่าได้ทำงานก่อน แต่ถ้ามีสอง process ที่มีเวลาในการทำงานเท่ากัน จะใช้วิธี FCFS หรือให้สิทธิ์ process ที่มาถึงก่อนได้ทำงานก่อน ตัวอย่างข้างล่าแสดงถึงลำดับการมาถึงของ process และ burst บอกเวลาที่ใช้ในการทำงานบน CPU ตามลำดับ

Process        Burst
P1                    6
P2                    8
P3                    7
P4                    3
จากข้อมูลด้านบนเราสามารถคำนวณเวลาทั้งหมดที่ต้องใช้ไปเพื่อให้การทำงานของแต่ละ process เสร็จสมบูรณ์ (turn around time) และเวลาที่ใช้ในการรอของแต่ละ process (waiting time)ได้ดังนี้
ผลจากการคำนวณเวลาเฉลี่ยที่ต้องในการทำงานให้เสร็จสิ้นของ process ทั้งหมดคือ 13 และเวลาเฉลี่ยที่ต้องใช้ในการรอของ process ทั้งหมดคือ 7 ซึ่งจะเห็นได้ว่าวิธี SJF ใช้เวลาในการทำงานและเวลาในการรอน้อยกว่าวิธี FCFS มาก  ความจริงแล้ว SJF น่าจะเป็นวิธีการจัดลำดับการทำงานที่ให้ผลที่ดีที่สุด แต่เป็นที่น่าเสียดายที่วิธี SJF ไม่สามารถนำมาใช้งานจริงได้ เนื่องจากเราไม่มีทางรู้ล่วงหน้าได้ว่าเวลาที่แต่ละ process จะใช้งาน CPU นั้นจริง ๆ แล้วมีค่าเท่าไหร่
วิธี SJF สามารถเป็นได้ทั้ง preemptive และ nonpreemptive ถ้าทุก process มาถึง ready queue พร้อม ๆ กัน ก็จะมีการทำงานเป็นแบบ nonpreemptive  แต่ถ้า process มาถึงต่างเวลากัน process ที่มาถึงทีหลังแต่มีเวลาในการทำงานน้อยกว่า process ที่กำลังทำงานอยู่ในขณะนั้น สามารถเข้าแทรก หรือ preempt process ที่กำลังทำงานอยู่ได้ ดังตัวอย่่างต่อไปนี้

Process             Arrival Time              Burst Time
P1                              0                                   8
P2                              1                                   4
P3                              2                                   9
P4                              3                                   5
จะเห็นว่าเวลาที่มาถึงของแต่ละ process (arrival time) ไม่เท่ากัน เราสามารถคำนวณเวลาทั้งหมดที่ต้องใช้ไปเพื่อให้การทำงานของแต่ละ process เสร็จสมบูรณ์ (turn around time) และเวลาที่ใช้ในการรอของแต่ละ process (waiting time)ได้ดังนี้

ผลการคำนวณสำหรับ SJF ที่มีการ preemptive นั้น เวลาเฉลี่ยที่ต้องในการทำงานให้เสร็จสิ้นของ process ทั้งหมดคือ 8.75 และเวลาเฉลี่ยที่ต้องใช้ในการรอของ process ทั้งหมดคือ 6.50
3. Priority Scheduling ให้ process ที่มีความสำคัญมากกว่าได้ทำงานก่อน
วิธีนี้จะต้องมีการกำหนดลำดับความสำคัญให้แก่ process ที่จะเข้ามาทำงานบน CPU ก่อนว่า process ใดความสำคัญมาก process ใดมีความสำคัญน้อย แล้ว CPU scheduler ก็จะจัดให้ process ที่มีความสำคัญมากที่สุดได้ทำงานก่อนและ process ที่มีความสำคัญน้อยกว่าได้เข้ามาทำงานต่อไปตามลำดับ ตัวอย่างข้างล่าแสดงถึง process ที่มาถึงพร้อมกัน  เวลาในการทำงาน(burst)  และระดับความสำคัญ (Priority) ที่ใช้ในการทำงานบน CPU ตามลำดับ
Process                   Burst Time                 Priority
P1                                  10                                3
P2                                    1                                1
P3                                    2                                4
P4                                    1                                5
P5                                    5                                2
จะเห็นว่าแต่ละ process มี priority ที่ไม่เท่ากัน โดยตัวเลขที่ต่ำกว่าแสดงถึง priority ที่สูงกว่า (1 มี priority สูงสุดและ 5 มี priority ต่ำสุด) เราสามารถคำนวณเวลาทั้งหมดที่ต้องใช้ไปเพื่อให้การทำงานของแต่ละ process เสร็จสมบูรณ์ (turn around time) และเวลาที่ใช้ในการรอของแต่ละ process (waiting time)ได้ดังนี้

ผลการคำนวณสำหรับวิธี priority จะมีค่าเฉลี่ยของ turnaround time เท่ากับ 12 และค่าเฉลี่ยของ waiting time เท่ากับ 8.20  วิธี priority สามารถเป็นได้ทั้งแบบ preemptive และ nonpreemptive ถ้าทุก process มาถึง ready queue พร้อม ๆ กัน ก็จะมีการทำงานเป็นแบบ nonpreemptive ตามตัวอย่างข้างบน แต่ถ้า process มาถึงต่างเวลากัน process ที่มาถึงทีหลังแต่มี priorityในการทำงานสูงกว่า process ที่กำลังทำงานอยู่ในขณะนั้น สามารถเข้าแทรก หรือ preempt process ที่กำลังทำงานอยู่ได้ ดังตัวอย่่างต่อไปนี้

Process	Arrival	Burst	Priority
P1	3	10	3
P2	2	1	1
P3	1	2	4
P4	4	1	5
P5	0	5	2

จะเห็นว่าแต่ละ process นอกจากมี priority ที่ไม่เท่ากันแล้ว ยังมีเวลาที่มาถึง (arival) ไม่เท่ากันอีกด้วย เราสามารถคำนวณเวลาทั้งหมดที่ต้องใช้ไปเพื่อให้การทำงานของแต่ละ process เสร็จสมบูรณ์ (turn around time) และเวลาที่ใช้ในการรอของแต่ละ process (waiting time)ได้ดังนี้

ผลการคำนวณสำหรับวิธี priority แบบที่ process เดินทางมาถึงไม่พร้อมกัน จะมีค่าเฉลี่ยของ turnaround time เท่ากับ 10.4 และค่าเฉลี่ยของ waiting time เท่ากับ 6.60
4. Round-Robin Scheduling สลับให้แต่ละ process ได้ทำงานคนละหนึ่งช่วงเวลา
วิธีนี้ถูกออกแบบมาเพื่อใช้กับระบบที่ต้องรองรับรับผู้ใช้จำนวนมากเช่นระบบ time sharing โดยแต่ละ process จะสลับกันเข้าทำงานบน CPU ในระยะเวลาสั้น ๆ เท่า ๆ กันจนกว่างานของแต่ละ process จะเสร็จสมบูรณ์  ซึ่งช่วงเวลาที่กำหนดให้แต่ละ process เข้าทำงานได้จะเรียกว่า time quantum หรือ time slice ซึ่งโดยปรกติจะมีค่าตั้ง 10 ถึง 100 milliseconds  ในกรณีที่ burst time ของ process น้อยกว่า time quantum เมื่อ process ทำงานเสร็จสิ้น CPU scheduler ก็จะจัดให้ process ที่อยู่ในลำดับเข้าทำงานต่อทันทีโดยไม่ต้องให้ครบเวลาตาม time quantum ที่ได้กำหนดไว้ ตัวอย่างข้างล่าแสดงถึง process ที่มาถึงพร้อม ๆ กันในวินาทีที่ 0 และ burst บอกเวลาที่ใช้ในการทำงานบน CPU ตามลำดับ โดยกำหนดให้มี time quantum = 4
Process               Burst Time
P1                               24
P2                                 3
P3                                 3

ผลการคำนวณสำหรับวิธี round robin จะมีค่าเฉลี่ยของ turnaround time เท่ากับ 12 และค่าเฉลี่ยของ waiting time เท่ากับ 5.66  วิธี round robin เป็นแบบ preemptive เท่านั้น  ไม่ว่า process จะมาถึง ready queue พร้อม ๆ กัน หรือ process มาถึงต่างเวลากัน ส่วนตัวอย่างในกรณีที่ process มาถึงไม่พร้อมกัน เราจะแก้โจทย์เดิมโดยเพิ่มเวลาที่มาถึงของแต่ละ process เข้าไปด้วย ซึ่งจะมีการคำนวณดังนี้

ผลการคำนวณสำหรับวิธี round robin แบบที่ process เดินทางมาถึงไม่พร้อมกัน จะมีค่าเฉลี่ยของ turnaround time เท่ากับ 12 และค่าเฉลี่ยของ waiting time เท่ากับ 3.33
พึงสังเกตุว่า ถ้าเรากำหนดให้ค่าของ time quantum มีค่าสูงมากจนเกิน วิธี round robin ก็จะมีค่าเท่ากับวิธี FCFS

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

ระบบหลายโปรเซสเซอร์ (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.csnon04.blogspot.com
www.thaiall.com
www.pedcharatn.exteen.com/20080819/5-cpu