prepared by Yoav Zimmerman and Noah Hadfield-Manell
CSS styling based on Eric Bollen's Fall 2010, Lecture 2 Scribe Notes.
There are several metrics used to describe the efficiency of a scheduling algorithm used by an OS to order the execution of waiting processes.
The first three are time periods whose max values, average values, and variance (standard deviation) should be minimized for optimal runtime. These time periods each start when a given process is queued up for execution; they are as follows:
The other two metrics also evaluate runtime and should be maximized:
The final value that factors into the efficiency of a scheduling algorithm is context switching time. This quantity (as indicated by its name) is the time taken by an OS to switch from one process to another and can be viewed--for our purposes--as a constant value regardless of the processes. Since the processor is idle during a context switch, utilization and throughput are directly and adversely affected by each context switch.
To better understand these concepts, consider an assembly line of the Ford Motor Company. For the discussion of OS scheduling in these notes, we will assume (for simplicity's sake) that our OS has access to one CPU. Similarly, in this example, the auto factory has only one assembly line that must be used for all of its models.
Order Start Done
Arrives Building Building
| | |
v v<--runtime-->v
t----------------------+-------------+---+--------->
<--wait time-->| Model S |///| Model A
+-------------+---+--------->
<--response time-->^ <->
| ^
1st car |
rolls off +---Time spent rearranging
the line assembly line to produce
Model A's (context switch)
<------turnaround time------->
At time 0, the factory workers get orders for 10 Model S cars and and 10 Model A's. The factory owner decides to begin production on the Model S's first.
When a processor uses FCFS, it selects the next process to execute based on which process has been waiting the longest.
When a processor uses SJF, it selects the next process to execute based on which waiting process has the shortest runtime.
A processor receives processes A,B,C,D in that order. The processor's context switch time is x.
FCFS SJF
AAAAA|//|BB|//|CCCCCCCCC|//|DDDD AAAAA|//|BB|//|DDDD|//|CCCCCCCCC
t +----+//+--+//+---------+//+----+----> +----+//+--+//+----+//+---------+----->
| |//| |//| |//| | |//| |//| |//|
v v v v v
0 5+x 7+2x 16+3x 20+3x
Process Runtime Arrival time Time of first response FCFS wait time SJF wait time
A 5 0 1 0 0
B 2 1 1 4+x 4+x
C 9 2 3 5+2x 9+3x
D 4 3 3 13+3x 4+2x
FCFS SJF
utilization = 20/(20+3x) utilization = same as FCFS
throughput = 4/(20+3x) throughput = same as FCFS
avg wait = 5.5 + 1.5x avg wait = 4.25 + 1.5x
avg turnaround = avg wait + avg runtime = 10.5 + 1.5x avg turnaround = 9.25 + 1.5x
avg response = avg wait + avg time of 1st response = 7.5 + 1.5x avg response = 5.25 + 1.5x
While SJF has shorter average wait, turnaround, and response times, it introduces the problem of
When a scheduler operates with preemption, it is allowed to switch processes mid-execution of a process. This will often reduce average wait time but also reduce throughput and utilization due to an increased number of context switches.
Round Robin is a scheduling policy that uses FCFS with preemption.
This is how the above example would be scheduled using round robin (| represents context switch):
A|B|A|C|B|D|A|C|D|A|C|D|A|C|D|CCCCC utilization = 20/(20+15x) avg wait time = 1 + 2.5x
Priority Scheduling is a scheduling technique in which each process is assigned a priority value. In Linux, priority is defined as niceness to avoid confusion about whether low or high priority numbers should come first. Linux processes may be assigned a niceness by the bash command nice as follows:
$ nice sort # adds 10 niceness to sort $ nice -9 sort # adds 9 niceness to sort $ nice --9 sort # subtracts 9 niceness (only allowed by root user)
The linux OS then decides which process should run next through a complicated function involving niceness, total CPU time the process will take, time since last run, and more factors.
To create a successful priority scheduling scheme, system architects usually have to tune the priority function "just right". The process usually goes as following:
Realtime schedulers fall into either of two categories: Hard or Soft.
For some systems, the best effort of a scheduler is not good enough. For example, the scheduler controlling a nuclear power plant cannot afford to make any mistakes; if a process that regulates the temperature of it's cores becomes starved then the plant may experience a meltdown!
Hard Realtime Schedulers are schedulers that cannot miss a deadline. They often have the following properties:
Unlike a hard realtime scheduler, a Soft Realtime Scheduler can afford to make mistakes sometimes. Most systems, including the most popular operating systems Windows, OS X, and Linux, are soft realtime schedulers. Although a perfect schedule is preferred, jobs in these systems can be canceled without too much cost, providing flexibility for the scheduler.
The problem of synchronization in multithreaded applications is often regarded by computer scientists as the single biggest problem with multithreaded applications. The culprit? Race conditions.
When the behavior of two threads running concurrently depends on the true order they run in, you are faced with a race condition. These are notoriously difficult to debug because they are rare, intermittent, and hard to catch automatically. Race conditions are undefined behavior, so there is no way to guarantee a program output. Even if your multithreaded program is running as expected, there may be a race condition hidden in it that could cause unexpected bugs in the future. Race conditions are sometimes hidden in codebases for years before a bug emerges; in fact, there are likely many race conditions still hidden in many major software programs you use right now!
As multithreaded developers, we need to be able to avoid race conditions while still fulfilling the following properties
Consider the following two snippets of code used in Bank's codebase to handle user deposits and withdrawls
bool deposit(int deposit) {
if (deposit < 0)
return false;
if (deposit > INT_MAX)
return false;
balance += deposit;
return true;
}
bool withdraw(int withd) {
if (withd < 0 || width > balance)
return false;
if (withd > INT_MAX)
return false;
balance -= withd;
return true;
}
Although the snippets look bulletproofed in every way (checking for negative inputs, integer overflow, etc), they are still susceptible to race conditions if run concurrently in seperate threads! This is an example of why race conditions are so difficult to catch. As a multithreaded programmer, you must always be wary of how the statements you are writing may be affected by a multithreaded context.
One common solution for the problem of synchronization is locking, in which the system only allows an object of memory to be accessed by one thread at once. If a thread tries to access an object that is currently locked, it blocks execution until the lock is released.
Locking faces some issues quickly. Here are some functions the bank may need, and the problems caused through an implementation using locking.
In addition the issues with concurrent memory access, a multithreaded programmer must also consider order of execution. Consider the following execution model of two threads T1 and T2. T1 executes actions A1-4 and T2 executes actions A5-8.
+--+ +--+ +--+ +--+ T1 |A1|--+ +--->|A6|----+ +---------->|A3|--+ +----->|A8| +--+ | | +--+ | | +--+ | | +--+ +---|--+ +--|--+ +--|--+ +--+ | | +--+ | | +--+ | | +--+ T2 |A5|----+ +-->|A2|-----+ +---->|A7|--------+ +----->|A4| +--+ +--+ +--+ +--+ Order of execution above (1): A1 A5 A6 A2 A7 A3 A8 A4 Another valid order of execution (2): A5 A1 A2 A6 A3 A7 A4 A8
Within the threads T1 and T2, A1-4 and A5-8 will be executed in order respectively. But the entire order of execution of A1-8 is undefined and depends on the CPU and compiler of the system. Therefore, a valid change in order of thread execution (such as 1 to 2 above) should not affect the observable behavior. We would like observable behavior to have two properties in a synchronization problem