Operating Systems Course Outline

5. Process Scheduling

Process Scheduling goal

to have CPU utilized all the time. Several processes are in memory, scheduler decides which should get the CPU.

CPU Burst Cycle

Large number of short burst of CPU use, small number of longer bursts. I/O bound processes tend to have more and shorter bursts.

short-term scheduler

when CPU is Idle (or at other times too), this scheduler selects a process to run from the ready queue. Ready queue need not be a fifo.

When does ST Scheduler act?

1. A Process becomes idle(wait for child, or I/O) 2.Process halted by a signal/interrupt 3. When a processes stops waiting and become ready again 4. when a process terminates.

Non-Preemptive or cooperative Scheduling

Scheduler act only in cases 1 and 4 above. When a process gets CPU it keeps it for as long as it wants (Windows 3.x)

Preemptive Scheduling

Scheduler acts in all 4 cases. More complex and creates a critical area problem . Also what if Kernel is in the middle of a request from a process when the process is preempted? Linux waits for the kernel to finish, but this is not good for some aplications (real-time). Also need to prevent an interrupt occuring in the middle of another interrupt. Can cause data corrupting. therefore interrupts usually block other interrupts.

Dispatcher

Gives CPU to process selected by scheduler. needs to switch context, switch to user mode, jumpt to program counter location.

Dispatch Latency

time it take to stop one process and start another.

Measures of Scheduling Algoritms - how to gauge an algorithm

CPU Utilization
percent of time CPU is active
Throughput
how many processes are completed per hour.
Turnaround time
How long a given process takes to complete (on a busy system)
Waiting Time
total Time spent in ready queue (perhaps the best measure since cpu time is not determined by the scheduler.)
Response time
time it takes from process start to when first output starts to be printed. This measure is independent of the output device's speed.

We may want to optimize the average values for these gauges or the maxes or mins . We may also want to minimize the variance so we can have a predictable response time.

Scheduling Algorithms

Gantt Chart

bar chart use for comparing algorithms. Process in order are represented showing burst time by length.

__________________________________
| P1                  | P2  | P3  |
----------------------------------
0                     14    17    20

Average Wait time is (0+14+17)/3 = 10.3

First-Come, First-Served

Easy to implement, FIFO. But the order that processes arrive can strongly affect average wait time. Drawback also if there is one CPU bound Process, it may force other I/O bound processes to wait for it each time, convoy effect. Preempting based on time slice can help alleviate this, though this algorithm is usually considered to be non-preemptive.

Shortest Job First (SJF)

Should really be called shortest next-CPU-burst first Need to know the length of the next CPU burst of each process, then assign the shortest to the top of the queue (use fcfs to break ties). Gantt chart show this to have optimal average wait time, but can cause a long process to "starve". Also How to comute next cpu burst? We could try to predict it based on past behavior. Compute an exponential average.

Let t_n be the length of the nth CPU burst, and let τ_n+1 be our predicted value for the next cpu burst. Then, for α, 0 ≤α≤1, define

τ_n+1 = α t_n + (1- α)τ_n

τ_n stores past history, t_n contains the most recent CPU burst history . Changing the value we assign to α changes the relative weight recent and distant history has. If we preempt a process when a shorter one arrives we call this a shortest remaining time first algorithm.

Draw a Gantt chart for the following:

Process	Arrival Time	CPU Burst Time
P1	0	7
P2	1	2
P3	3	11
P4	4	4

Gantt Chart

Priority Scheduling

High priority jobs go first. Priority can either be internal determined (based on memory requirements, CPU need, etc.) or determined by something outside the OS. Can be preemptive. Probelm is that low priority process are kept waiting indefinately. "starvation" or "blocking". "Aging" solves this problem.

Round-Robin

Each process gets a "time slice" of CPU use in FCFS fashion, but is preempted at end of time slice (eg. 20 ms). If process CPU burst < time slice, then the OS will move to next job sooner. We want the time slice to be significantly larger than the time required to do a context switch. If the time slice is too large then we end up with a FCFS algorithm. Ideally, at least 80% of the CPU bursts should be smaller than the time slice.

Multi-Level Queue

Foreground processes (interactive) and background processes have different response time requirements. Each process is assigned perminently to one queue (i.e. interactive queue or batch queue). Each queue has its own scheduling algorithm and the combining of the queues is also according to some algorithm. Interactive queue might get priority and may be a round robin. The background queue might be a FCFS.

Multi-Level Feedback Queue

Like Multi-level queue but can move from lower to higher priority queues and the reverse. Long CPU burst process or CPU bound processes are set to lower priority. Older processes can also have their priority raised. (Prevents starvation). Example, have three queues. Queue 1 gives process 10 ms.If it does not finish, it is moved to queue 2. Only when queue 1 is empty is queue allowed to run. It gives processes 20ms. If process does not finish, moved to queue 3 with 40 ms. Queue 3 is only run once queue 2 is empty. Thus short CPU processes run faster. We can also add aging so that old processes go back to queue 1 (or 2). Complex.

Multiprocessor Scheduling

Asymetric: processors are set up in a master slave manner. Symmetric Multiprocessing (SMP): Either private or shared ready queues. If shared, need to prevent both processors from selecting the same process to be run. If private, OS must populate each queue in a balanced fashion.

CPU Cache

by way of reminder, the CPU has its own cache which is faster than RAM. Recent data is kept in cache. When a context switch occurs, the cache is not necessarily switched out. Thus the OS must seperate cache data between processes.

processor affinity

Once a process has been chosen for one processor, it is best to keep the process assigned to that processor. Otherwise the OS would need to copy out data from one CPU cache to the other. Processor affinity can be hard or soft(flexible)

load balancing

required on SMP systems that have private queues. push migration a seperate routine checks periodicaly for imbalances and redistributes. pull migration an idle processor checks other processor queues and takes its process. Can be implemented together. LB is contrary to idea of processor affinity.

Multicore Processor

Many CPUs on a single chip, each with its own registers and cache.

Memory Stall

processor waiting for memory to be accesses so it can perform.

Multi-threaded

two or more processes are loaded into each cpu (each has its own registers, cache may be shared) processor alternates among the processes while waiting for a memory stall. May be combined with multicore. Multi-threading requires a second level of process scheduling, i.e. when to switch among processes in the CPU and which one to activate.

hard-ware thread

logical (virtual) processor

Virtualization and scheduling

Often a host system has many guest OSs. If the Guest OS alocated 100 ms to each process, it may actually take longer than 100ms to get those virtual 100ms because other guests are demanding CPU. Or put another way, you may have to slow down how many hardware cycles per second a guest has so that the host can handle all the interrupts of all its guest. In virtualization, you don't have the CPU speed you think you have.

Question for thought. When a process is switched out because of I/O when it is ready, where does it go in the queue, back to the top or to the end?

interrupt handling: During an interrupt, the OS will usually block (mask) that same interrupt. Accepting two of the same interrupts (interrupting as interrupt) can cause a vicious circle which the OS may never get out of.
Real-time OS: Application's process priority level may exceed that of a system process. App can run in Kernel mode (in order to save the overhead of having to switch between user and kernel mode) and it can block (mask) OS interrupts. Typically, real-time software requires guaranteed CPU time for its process and guaranteed response time for an interrupt. The OS may also deny other processes the ability to interrupt the real-time process. The OS may use a multi-level scheduling queue to provide these guarantees. In general, a real-time OS will sacrifice throughput for responsiveness and guaranteed resource allocation.
vxworks: a popular embedded real time OS, but more and more popular to use a Linux on an embedded system, but Linux cannot provide hard real time because cannot guarantee fixed cpu allocation.
soft real time: timing important but time failure will not cause everything to be worthless. ex. VOIP,
hard real time: time failure causes system to be useless,worthless. Ex. Missile System, GSM needs to transmit in strict time frames so as not to conflict with other phones in the cell, and needs guaranteed CPU to calculate what to send.
interrupts on VMWare client: should be slowed down or turned off because otherwise host is spending all time supplying the interrupts and client (guest) will run slow. When you set up a VMWare machine you set its disk size and memory. these should be less than host, even if you plan to run only one guest.