Wednesday, January 14, 2009

CPU Scheduling

Resource: what OS's manage things that process needs/uses (CPU, disk, memory, anything valuable..., Resource make up system, OS must manage them)

Resource manager: 1. allow more than one user to use resource (visualization, multiplexing), 2. protect applications from each others (protection), 3. provide efficient/fair access to resource (performance).

Preemptive: take resource away, use for something else and give back later (CPU)

Non-preemptive: once given away, cannot really take back (disk block, terminal)

Given resource and demands, how to manage it?

Allocation vs. Scheduling:
Allocation: which process gets which resource? Like space sharing -- divide up resource, give some to each when resources not easily preemptive. e.g. file space.
Scheduling: how long process keeps resource with best order. Like time sharing -- more resources can be requested than available. Resource must be preemptive. e.g. CPU scheduling

could have both space and time sharing of memory, CPU in parallel system

Dispatcher: is low level mechanism, is the module that gives control of the CPU to the process selected by the short-term scheduler. This function involves: switching context, switching to user mode, jumping to the proper location in the user program to restart that program.

Scheduler: higher level policy, decide which to run

FCFS (first-come, first-served) scheduling algorithm: simplest, can implement with FIFO queue. Why bad? wait/turnaround time depends on order. Unfair to later jobs (slow truck in front of fast cars)

SJF (shortest-job-first): should minimize wait/turnaround time. But not often practical: how to know job length?

STCF (shortest Time to Complete First) = SJF with preemption. SJF is fine if all jobs are in system, but some jobs arrive later.

RR (round-robin): more practical. Run for time slice, then back of FIFO Queue. Preemptive if still running at the end. Details: keep ready queue as a FIFO queue of processes. New process are added to the tail. The CPU scheduler picks the 1st process from the ready queue, sets a timer to interrupt after 1 time slice (usually 10-100 ms), and dispatches the process. If the process have a CPU burst less than 1 time slice, the process will release CPU voluntarily. The scheduler will proceed to the next process. If CPU burst is longer than 1 time slice, the time will go off and will cause an interrupt to the operating system. A context switch will be executed and the process will be put at the tail. The CPU schedule then select the next process.
Adv.: it is fair, low average wait if job lengths vary widely, low response, if N  jobs and time slice is T ms, longest wait is (N-1)*T, average is (N-1)*T/2
Disadv.: poor when jobs nearly identical. Performance depends on length of time slice. If it it too high, it = FCFS. If it is too low, context switch happens too much.   

No comments:

Post a Comment