Programming System
Process Scheduling
Tutorial class by Philippe Décogné
26/10/2002 (dd/mm/yy)
Five jobs A, B, C, D, and E arrive at a computer center in that order, and essentially at the same time. Those jobs don't request I/O services. Their execution times are 10, 6, 2, 4, and 8 seconds resp.
Response time
This is the time from the submission of a request until the response begins to be received.
For a batch job, it is the same as the turnaround time: i.e. actual execution time + time spent in waiting for resources, including the processor.
For an interactive job, it may be smaller, as the process can produce some output to the user before completion.
FIFO scheduling policy
The processes are executed in their order of arrival time.
Mean response time: (10 + 16 + 18 + 22 + 30) / 5 = 19.2 s
SJF scheduling policy
The process with shortest execution time is executed first.
Mean response time: (2 + 6 + 12 + 20 + 30) / 5 = 14 s
Jobs with priorities
The process with higher priority is executed first.
Mean response time: (4 + 6 + 16 + 24 + 30) / 5 = 16 s
PS scheduling policy
The process with higher priority is executed first for the given quantum time, then the others in their order of priority for the given quantum time. Thereafter the same scheme is applied until all processes are terminated.
Without priority
Mean response time: (30 + 22 + 6 + 16 + 28) / 5 = 20.4 s
With priority: P(A) = 3, P(B) = 5, P(C) = 2, P(D) = 1, P(E) = 4
Mean response time: (30 + 24 + 4 + 12 + 28) / 5 = 19.6 s
For each of the following process state transitions tell if the transition is possible. Indicate an action that may cause each valid transition.
Process states
New
Process created to execute a program. It can be created by the system to control a batch job, when a user logs in, to provide a service (printing for example), or by another process (fork).
A new process is not already in the ready processes queue (it has not already been loaded into main memory).
A process may not be loaded immediately into the ready processes queue if the system limit for currently running processes has been reached.
Ready
Process ready to be executed as soon as the processor dispatches it.
Running
Process that is currently being executed.
Blocked
Process that cannot execute until some event occurs (for example waiting for an I/O device). The process is in main memory.
Ready/Suspend
The process is swapped out into secondary memory and will be ready to execute as soon as it is loaded in main memory.
The process may be suspended by the system in case it seems not to run correctly (utility or background process), by the user when debugging or to use special resources, when it is a periodic process waiting for its next instance, by its parent to modify or synchronize it with other children.
Blocked/Suspend
Blocked process that has been moved out of the main memory onto the disk into a so called suspend queue to make place to a new process or another blocked process (process swapping).
The process is in secondary memory and is waiting for the event which originates the blocked state (Event wait).
Exit
Process that has been released from the pool of executables processes by the operating system (halt or abort).
Transition between states
New ->Ready
There is enough room in main memory to load the new process. The process enters the Ready state.
New ->Ready/Suspend
A new process cannot be admitted to the Ready state immediately, as the system should build some allocation tables and allocate address space for the new process. If there is not enough room in the main memory to hold those resources, the process enters the Ready/Suspend state before the Ready state.
Ready/Suspend -> Ready
Either there is no Ready processes in main memory, or there is a higher-priority process in the suspend queue than those in the ready queue. The process then enters the Ready state.
Ready -> Ready/Suspend
Either there is no other way to free some memory in main memory to load another process, or a blocked process has a higher priority and is about to enter the ready state. The process enters the Suspend state.
Ready-> Running
The system chooses a process following its scheduling policy, the priorities on queues, etc.
Running-> Ready
A process can move from the Running state to the Ready state based on the time quantum allocated to each process (Timeout), if it is preempted, or if it releases control of the processor.
Running -> Blocked
The process is waiting for a resource. It enters the Blocked state.
Blocked -> Blocked/Suspend
As the processor runs much faster than any devices, it happens most of the time that all processes in main memory are in the Blocked state waiting for I/O. In this case, the system moves all or parts of the blocked processes into a so called suspend queue on disk (secondary memory). This way the processor can choose a process already in this list or admit a new process (swap).
Blocked/Suspend-> Blocked
There is a process in the Blocked/Suspend queue with higher priority than those in the Ready/Suspend queue (in secondary memory) and this process is about to acquire the resource it was waiting for - thus it has entered the Blocked/Suspend state. In this case, the process is loaded in main memory, hence it enters the Blocked state.
Blocked/Suspend -> Ready/Suspend
The process is in secondary memory. The event which originated the Blocked state - therefore the Suspend state - had occurred.
Blocked -> Ready
The process is in main memory. The event which originated the Blocked state has occurred.
Running-> Exit
The process is terminating either normally, or on fatal error, or on signal (sigkill), or its parent terminates. The system frees its resources (if possible).
Solving the problem
For the processes in the following table draw a diagram showing their execution within a priority scheduling policy. Higher priority has higher value.
| Process | Arrival time | Cycle | Priority |
|---|---|---|---|
| A | 0.0000 | 4 | 3 |
| B | 1.0001 | 3 | 4 |
| C | 2.0001 | 4 | 6 |
| D | 3.0001 | 5 | 5 |
Order of execution
Without any priority/preemption, processes are executed in their order of arrival time.
With priority applied, in case of two processes arriving at the same time, the one with higher priority is executed before the other.
With preemption, as soon as a process with higher priority arrives, the ones with lower priorities are suspended and the former executes. Then the others are resumed and executed the same way.
Preempted
Not preempted
Consider a LINUX single-processor system, where processes share a disc as unique resource (other than the processor obviously). This resource is in exclusive access and not requirable, i.e. a disc request from a process should terminate before another disc request could occur.
Process states are: Running, Waiting for I/O, Waiting for processor. Actually, the blocked state is divided into two states: waiting for disc, waiting for the end of the operation. I/O requests are managed FIFO.
Within this system consider four processes P1, P2, P3, and P4 under the following scheme:
The SCHED_FIFO class processes have always higher priority than the SCHED_RR class processes.
The four processes are described above (priority at start time is indicated between curly braces):
| P1 (100) | P2 (99) | P3 (99) | P4 (98) |
| Computing 40 ms | Computing 30 ms | Computing 40 ms | Computing 80 ms |
| Reading disc 50 ms | Reading disc 80 ms | Reading disc 40 ms | |
| Computing 30 ms | Computing 80 ms | Computing 10 ms | |
| Reading disc 40 ms | Reading disc 20 ms | ||
| Computing 20 ms | Computing 10 ms |
Draw the chronogram for the four processes on a diagram showing each process states.
Priorities
P1 and P2 have a higher priority level than P3 and P4.
Reading disc is performed without preemption for P1, P2, P3 and P4, i.e. once the disc is allocated to a process, the operation is not interrupted.
Computing is performed with preemption for P1 and P2, i.e. P1 may acquire the processor for computing, though it is computing for P2.
For P3 and P4 computing, the processor is allocated for 10 ms, then given to the job with highest priority (either P1, P2, or P3).
States
I/O states match disc read.
Waiting states match waiting for disc to perform reading from disc.
Ready states indicate that the process is waiting for the processor to perform computing.
Running states match the processor use to perform computing.
Caption
Fixed priorities
For computing the processor chooses the process which asks for computing and has the highest priority; this process enters the Running state. The processor performs the operation as long as needed for processes P1 and P2. It may interrupt P2, whenever P1 asks for computing. For processes P3 and P4, the processor gives them 10 ms time, except when any other process asks for computing. A process waiting for computing enters the Ready state.
For reading from disc the processor chooses the process with highest priority which asks for the disc and gives it as much time as needed. If during this time another process asks for the disc, that process enters the Waiting state.
Variant with variable priorities
Say the priority of a process is changed each time that process leaves the Waiting state as follows:
New priority = New priority - (processor time used by the process / 10)
Caption
The diagram changes as following:
The new priority for P2 does not change anything, as P1 has a higher priority than P2, and P3 and P4 have always a lower priority than P1 and P2.
On the contrary, the new priority for P1, whose priority becomes less than P2's, allows the processor to compute for 80 ms without interruption for P2. P1 enters the Ready state for 40 ms, then is given access to the processor for 20 ms computing, meanwhile P2 reads disc for 20 ms.
The new priority for P3, whose priority becomes less than P4's, allows the processor to choose P4 before P3 for 10 ms computing just before the last computing for P3.
Consider a configuration with three jobs {Tp1, Tp2, Tp3} defined as follows :
- Tp1 : (r0 = 0, C = 1, R = 3, P = 3)
- Tp2 : (r0 = 0, C = 1, R = 4, P = 4)
- Tp3 : (r0 = 0, C = 2, R = 3, P = 6)
Draw a diagram showing the series obtained for the configuration with RM, ID, and ED scheduling.
Scheduling type
Here we have to deal with real time scheduling of three tasks with same arrival time (r0) 0.
Execution times C for the first two tasks are the same and equals one time unit. Third task's execution time is two time units.
Deadline R, or maximum time for executing a task, is the same for job Tp1 and Tp3. That means that the beginning of a task may be shifted provided that its end occurs before (or at) the end of deadline for that task.
The periods, time between two instances of the same task, are different for each task.
Let us draw a diagram with all possible settings for each task within its period:
RM scheduling
Scheme
Rate Monotonic scheduling is a scheduling where the highest-priority task is the one with the shortest period. It is named after the diagram obtained by plotting the priority of the tasks as a function of their rates (inverse of period). The resulting graphics is a monotonic function, i.e. for any x and y pertaining to the definition domain of the function the following is true :
x <= y => f(x) <= f(y) - increasing function
o:
x <= y => f(x) >= f(y) - decreasing function
Application
The highest-priority task is Tp1 (P = 3), then Tp2 (P = 4), then Tp1 (P = 6). That leads to the following scheduling:
Caption
délai critique: deadline
We can observe that the deadline may be reached for tasks Tp1 and Tp2, but not for task Tp3, which has its second execution time unit located after its deadline.
This scheduling does not meet the requirements for the given configuration.
ID scheduling
Scheme
Inverse deadline scheduling is a scheduling where the highest-priority task is the one with shortest deadline. It is so called as, in this scheduling, the priorities are inverse function of deadlines.
Application
The highest-priority task is Tp1 (R = 3), then Tp3 (R = 3), then Tp2 (R = 4). That gives the following scheduling:
Caption
délai critique: deadline
We can see that, during the second cycle for Tp2, the task cannot be scheduled within its period.
This scheduling does not meet the requirements for the given configuration.
ED scheduling
Scheme
Earliest Deadline scheduling is a scheduling where the highest-priority task is the one with the shortest dynamic deadline, i.e. the shortest current delay before the deadline. It is so called as, in this scheduling, the tasks' priorities are function of the earliest deadlines.
Application
Caption
délai critique: deadline
At the beginning the highest-priority task is Tp1 with 3 time units for deadline (TUD), then Tp3 with 2 TUD, then Tp2 with 1 TUD. Again Tp1 is the highest-priority task with 2 TUD and Tp2 with 3 TUD. Again Tp1 is the highest-priority task with 3 TUD, then Tp3 with 2 TUD. At last Tp1 is the highest-priority task with 3 TUD, then Tp2 with 2 TUD.
This scheduling conforms the requirements for the given configuration.
