Transcript บทที่ 4

บทที่ 4
Processor Management
(single processor with single-threaded process)
ประเด็นเกี่ยวกับ Single processing
•
•
•
•
•
มี processor เดียว (single core)
ทำงำนได้ ทีละคำสัง่ (ระดับภำษำเครื่ อง)
มีหลำยงำนที่รันอยูพ่ ร้ อมกัน (multitasking)
กำรที่ OS รันอยูก่ ็ต้องใช้ CPU เหมือนกัน
ให้ ทกุ กลุม่ ปรึกษำกัน และนำเสนอแนวคิดว่ำ ถ้ ำมีสงิ่ ของอยูช่ ิ ้นหนึ่ง ไม่
สำมำรถแบ่งแยกได้ ไม่สำมำรถใช้ ร่วมกันได้ แต่มีผ้ ตู ้ องกำรใช้ หลำยคน จะมี
วิธีแบ่งอย่ำงไร จึงจะได้ ใช้ ทกุ คน
– ทุกกลุม่ เสนอแนวคิด
– ปรับปรุงเป็ นกำรจัดสรร CPU
– เปรี ยบเทียบข้ อแตกต่ำงกับกำรจัดสรร memory
Process state
(การเรี ยกชื่อ state ต่างๆอาจต่างกันไปตามผูแ้ ต่งหนังสื อ น.ศ.ไม่จาต้องเรี ยกตาม
อาจารย์ แต่ตอ้ งอธิ บายความหมายได้ถูกต้อง)
• เมื่อมีกำรเริ่ มต้ น process ใหม่ process ยังไม่พร้ อมจะทำงำนทันที
ต้ องผ่ำนกระบวนกำรบำงอย่ำงเสียก่อน (เช่นเตรี ยมทรัพยำกรและข้ อมูล)
• เมื่อ process พร้ อมจะทำงำน ก็อำจไม่สำมำรถทำงำนได้ ทนั ที เพรำะ
CPU ไม่วำ่ ง (แล้ วทำยังไงดี กลับไปเริ่ มต้ นใหม่ดีไหม ?กลุม่ ... ตอบ)
• เมื่อ process ได้ เริ่ มทำงำน (ได้ ใช้ CPU แล้ ว) ควรให้ ทำงำนไปจนจบ
หรื อไม่ (กลุม่ ... ตอบ)
• ถ้ ำ process ทำคำสัง่ I/O เช่นรับข้ อมูลจำก keyboard ต้ องรอ
จนกว่ำจะได้ ข้อมูล จึงจะทำคำสัง่ ต่อไปได้ process ดังกล่ำวควรจะ
ครอบครอง CPU ต่อหรื อไม่ ถ้ ำไม่ควรทำอย่ำงไร (กลุม่ ... ตอบ)
Job and Process Status
Admitted
Hold
Finished
Interrupt
Ready
Exit
Running
Scheduler dispatch
I/O or event
completion
Waiting
I/O or event
wait
Handled by Process
Scheduler
4
Handled by Job Scheduler
เมื่อ CPU ว่าง process ใดที่จะได้รัน
• จำกแผนภำพมีเพียงเส้ นจำก ready เท่ำนันที
้ ่มำยัง running
• Process ที่อยูใ่ นสถำนะ ready เท่ำนันจึ
้ งจะมีสทิ ธิได้ รัน
• Process ในสถำนะ ready มีอยู่ process เดียวหรื อเปล่ำ ?
– จำกแผนภำพเส้ นที่มำ ready มี 3 เส้ น มีโอกำสที่จะมำจำกทัง้ 3 ทำง
– ในแต่ละเส้ นทำง มีโอกำสที่จะมีหลำย process เข้ ำมำขณะ CPU ไม่
ว่ำง
• เมื่อมีหลำย process อยูใ่ นสถำนะ ready จะเลือก process
ใดมำรัน
– ให้ ทกุ กลุม่ ปรึกษำและเสนอควำมเห็น
เมื่อมีการเปลี่ยน process ทางาน
• ถ้ ำ process ที่กำลังครอบครอง CPU ทำงำนเสร็ จสิ ้น CPU ก็จะว่ำงให้
process อื่นมำทำงำนได้ โดยไม่มีปัญหำใดๆ
• แต่ถ้ำ process ที่ครอบครอง CPU ยังทำงำนไม่จบ จำเป็ นต้ องกลับมำ
ใช้ CPU ใหม่ หำกเอำ process ดังกล่ำวออกไปอยูส่ ถำนะอื่นเฉยๆย่อม
มีปัญหำ เพรำะเมื่อกลับมำทำงำนต่อ จะต้ องกลับมำทำงำนต่อทีค่ ำสัง่
ต่อเนื่องจำกเดิม ข้ อมูลที่อยูร่ ะหว่ำงประมวลผลโดย CPU ก็จะต้ อง
เหมือนเดิม
• ดังนันจ
้ ำเป็ นต้ องเก็บข้ อมูลไว้ เพื่อที่จะกลับมำทำงำนต่อได้ ถกู ต้ อง
• ข้ อมูลสำคัญที่ต้องเก็บไว้ ได้ แก่ program counter, register
content และอื่นๆ ซึง่ จะเก็บไว้ ใน PCB ซึง่ จะถูกนำกลับมำไว้ ในที่เดิม
เมื่อ process กลับมำทำงำนอีกครัง้
• กระบวนกำรนี ้เรี ยกว่ำ Context Switching
Process Control Block (PCB)
• Process Control Block (PCB) -- data structure
that contains basic info about the job
– Process identification
– Process status (HOLD, READY, RUNNING,
WAITING)
– Process state (process status word, register
contents, main memory info, resources, process
priority)
– Accounting (CPU time, total amount of time, I/O
operations, number input records read, etc.)
Understanding Operating
Systems
7
PCBs and Queuing
• PCB of job created when Job Scheduler accepts it
– updated as job goes from beginning to termination.
• Queues use PCBs to track jobs.
– PCBs, not jobs, are linked to form queues.
– E.g., PCBs for every ready job are linked on READY
queue; all PCBs for jobs just entering system are linked
on HOLD queue.
– Queues must be managed by process scheduling
policies and algorithms.
Understanding Operating
Systems
8
Process Scheduling Algorithms
•
•
•
•
•
•
First Come First Served (FCFS)
Shortest Job Next (SJN)
Priority Scheduling
Shortest Remaining Time (SRT)
Round Robin
Multiple Level Queues
Understanding Operating
Systems
9
First Come First Served (FCFS)
• Non-preemptive.
• Handles jobs according to their arrival time -the earlier they arrive, the sooner they’re
served.
• Simple algorithm to implement -- uses a FIFO
queue.
• Good for batch systems; not so good for
interactive ones.
• Turnaround time is unpredictable.
Understanding Operating
Systems
10
FCFS Example
Process
A
B
C
CPU Burst (Turnaround Time)
15 milliseconds
2 milliseconds
1 millisecond
• If they arrive in order of A, B, and C.
What does the time line look like?
What’s the average turnaround time?
Understanding Operating
Systems
11
Shortest Job Next (SJN)
• Non-preemptive.
• Handles jobs based on length of their CPU cycle time.
– Use lengths to schedule process with shortest time.
• Optimal – gives minimum average waiting time for a
given set of processes.
– optimal only when all of jobs are available at same time
and the CPU estimates are available and accurate.
• Doesn’t work in interactive systems because users
don’t estimate in advance CPU time required to run
their jobs.
Understanding Operating
Systems
12
Priority Scheduling
• Non-preemptive.
• Gives preferential treatment to important jobs.
– Programs with highest priority are processed first.
– Aren’t interrupted until CPU cycles are completed or a
natural wait occurs.
• If 2+ jobs with equal priority are in READY queue,
processor is allocated to one that arrived first (first
come first served within priority).
• Many different methods of assigning priorities by
system administrator or by Processor Manager.
Understanding Operating
Systems
13
Shortest Remaining Time (SRT)
• Preemptive version of the SJN algorithm.
• Processor allocated to job closest to completion.
– This job can be preempted if a newer job in READY
queue has a “time to completion” that's shorter.
• Can’t be implemented in interactive system -requires advance knowledge of CPU time
required to finish each job.
• SRT involves more overhead than SJN.
– OS monitors CPU time for all jobs in READY queue and
performs “context switching”.
Understanding Operating
Systems
14
Round Robin
• Preemptive.
• Used extensively in interactive systems because
it’s easy to implement.
• Isn’t based on job characteristics but on a
predetermined slice of time that’s given to each
job.
– Ensures CPU is equally shared among all active
processes and isn’t monopolized by any one job.
• Time slice is called a time quantum
– size crucial to system performance (100 ms to 1-2
secs)
Understanding Operating
Systems
15
If Job’s CPU Cycle < Time Quantum
• If job’s last CPU cycle & job is finished, then all
resources allocated to it are released &
completed job is returned to user.
• If CPU cycle was interrupted by I/O request, then
info about the job is saved in its PCB & it is linked
at end of the appropriate I/O queue.
– Later, when I/O request has been satisfied, it is
returned to end of READY queue to await allocation of
CPU.
Understanding Operating
Systems
16
Time Slices Should Be ...
• Long enough to allow 80 % of CPU cycles to
run to completion.
• At least 100 times longer than time required
to perform one context switch.
• Flexible -- depends on the system.
Understanding Operating
Systems
17
Multiple Level Queues
• Not a separate scheduling algorithm.
• Works in conjunction with several other schemes
where jobs can be grouped according to a common
characteristic.
• Examples:
– Priority-based system with different queues for each priority level.
– Put all CPU-bound jobs in 1 queue and all I/O-bound jobs in another.
Alternately select jobs from each queue to keep system balanced.
– Put batch jobs “background queue” & interactive jobs in a “foreground
queue”; treat foreground queue more favorably than background queue.
Understanding Operating
Systems
18
Policies To Service Multi-level Queues
• No movement between queues.
• Move jobs from queue to queue.
• Move jobs from queue to queue and
increasing time quantums for “lower” queues.
• Give special treatment to jobs that have been
in system for a long time (aging).
Understanding Operating
Systems
19
ผลของแต่ละ algorithm
• จะเห็นว่ำแต่ละ algorithm ก็มีข้อดีข้อเสียแตกต่ำงกันไป ผลกระทบต่อ
process แต่ละแบบก็แตกต่ำงกันด้ วย
• ดังนันกำรเลื
้
อกใช้ algorithm ใด จะเป็ น preemptive หรื อ nonpreemptive กำรตังค่
้ ำเวลำของ time quantum ย่อมขึ ้นอยูก่ บั นโยบำย
ในกำรออกแบบ OS ว่ำต้ องกำรออกแบบ OS ให้ เป็ นแบบใด เหมำะกับงำนแบบใด
โดยเฉพำะหรื อไม่
–
–
–
–
–
–
CPU-bound jobs
I/O-bound jobs
Interactive jobs
Background jobs
Real time jobs
Transactions Processing jobs
Process Scheduling Policy
 Maximize throughput by
running as many jobs as
possible in a given amount
of time.
 Maximize CPU efficiency by
keeping CPU busy 100 % of
time.
 Ensure fairness for all jobs
by giving everyone an equal
amount of CPU and I/O
time.
 Minimize response time by
quickly turning around
interactive requests.
 Minimize turnaround time
by moving entire jobs in/out
of system quickly.
 Minimize waiting time by
moving jobs out of READY
queue as quickly as
possible.
21
Interrupts
• There are instances when a job claims CPU for a
very long time before issuing an I/O request.
– builds up READY queue & empties I/O queues.
– Creates an unacceptable imbalance in the system.
• Process Scheduler uses a timing mechanism to
periodically interrupts running processes when a
predetermined slice of time has expired.
– suspends all activity on the currently running job and
reschedules it into the READY queue.
Understanding Operating
Systems
22
Cache Memory
• Cache memory -- quickly accessible memory that’s
designed to alleviate speed differences between a
very fast CPU and slower main memory.
• Stores copy of frequently used data in an easily
accessible memory area instead of main memory.
CPU
Main Memory
Cache
Controller
Hit
Cache Memory
Miss
23
Types of Interrupts
• Page interrupts to accommodate job requests.
• Time quantum expiration.
• I/O interrupts when issue READ or WRITE
command.
• Internal interrupts (synchronous interrupts) result
from arithmetic operation or job instruction
currently being processed.
• Illegal arithmetic operations (e.g., divide by 0).
• Illegal job instructions (e.g., attempts to access
protected storage locations).
Understanding Operating
Systems
24
Interrupt Handler
• Describe & store type of interrupt (passed to user as error
message).
• Save state of interrupted process (value of program
counter, mode specification, and contents of all
registers).
• Process the interrupt
–
–
–
–
Send error message & state of interrupted process to user.
Halt program execution
Release any resources allocated to job are released
Job exits the system.
• Processor resumes normal operation.
Understanding Operating
Systems
25