Non - Determinism
Operating Systems and Real-Time systems are non-deterministic
in that they must respond to events (I/O) which occur in an
unpredictable order, and at any time
Processes Disk I/O
Alarm condition
Keyboard
Clock
Interrupt Time
c Department of Computing, Imperial College London Operating Systems II 58/396
c Department of Computing, Imperial College London Operating Systems II 59/396
Avoid I/O Delays Processes
An I/O action is normally started by sending information to a An abstraction of a running program, characterised by
special address in the machine’s memory (DMA); the result of the code,
action is reported in another address.
input,
After initiating an I/O action, the CPU can repeatedly check the output, and
reply address to see if the execution went well: but this is a
busy-wait solution, which wastes CPU-cycles. state.
Used in situations where a program can get blocked (waiting for
It is better to have the CPU start another action, and have the I/O
I/O, e.g.) and another gets the CPU instead; the blocked process
device interrupt the CPU when the I/O action has finished, after
can get restarted at a later, therefore, all information concerning
which the CPU can continue the initial program.
the process, needed to restart safely, should be stored.
The requires a concept of halt and restart of program execution: For each process, all this data is stored in a process descriptor,
we need to store the state of a program, so that we can start it or process control block (PCB), that is kept in the process table
later as if it was not halted at all
c Department of Computing, Imperial College London Operating Systems II 60/396
c Department of Computing, Imperial College London Operating Systems II 61/396
Process States Process Switches
Exit .
.
Running ...... Terminated Events (or interrupts) cause process switches. For example, an
initiate I/O; I/O completion interrupt will cause the OS to switch to an I/O
send message; ......
JJJ process
down on semaphore J time slice expired
J pre-empted
J The way an OS switches between processes cannot be
Picked by J JJ
....... scheduler JJ .J ...... pre-determined, since the events which cause the switches
are not deterministic
..... ........
Waiting .. Ready New The interleaving of instructions, executed by a processor, from
I/O complete; Enable a set of processes is non-deterministic
message arrived; semaphore signalled
New : the process is being created.
Running : executing on a processor.
Ready : runnable and waiting for processor.
Waiting : blocked or waiting for an event.
Terminated : process is being deleted.
c Department of Computing, Imperial College London Operating Systems II 62/396
c Department of Computing, Imperial College London Operating Systems II 63/396
Scheduler Scheduler (2)
The part of the OS that decided which of the runnable processes It basically changes the state of a process; it picks a process from
is to run first. Some criteria for the scheduling algorithm are: the Ready Queue and makes it the Running Process
Fairness : Each process gets its fair share of CPU. PCB PCB PCB
...... ......
......
Efficiency : Keep CPU busy 100 percent of the time.
Ready Queue .. .. ..
runnable runnable runnable
Response time : Minimize for interactive users.
next next nil
Turnaround : Minimize the time users must wait for output.
Throughput : Maximize the number of jobs processed.
PCB
Some of these criteria are in conflict ......
Running Process ..
running (normally the
head of the
nil Ready Queue)
c Department of Computing, Imperial College London Operating Systems II 64/396
c Department of Computing, Imperial College London Operating Systems II 65/396
Scheduler’s Task Scheduling Strategies
The scheduler Different strategies exist in selecting the next running process:
allocates processes to processors. Preemptive scheduling: time-slices.
selects highest priority ready process (from head of Ready Run to completion: non-preemptive.
Queue) and moves it to the running state, i.e., allows it to start Round Robin: last run process to tail of queue.
executing on the processor. Priority scheduling: new priority = 1 / (fraction of time-slice
gets invoked after every entry to the kernel. used).
Multiple queues.
Current process continues unless:
Shortest job first.
Kernel call moved it into waiting state (e.g. Guaranteed scheduling: allotted time = 1 / (# procs).
down(semaphore)). Lottery scheduling.
Error trap occurred (e.g. memory protection violation). Real time scheduling.
Time slice expired. Two level scheduling: process on disk or in RAM.
A higher priority process is made ready.
c Department of Computing, Imperial College London Operating Systems II 66/396
c Department of Computing, Imperial College London Operating Systems II 67/396
Scheduler Lay-out Low Level Scheduling
void Scheduler (){
if (current->state != running ||
Natural Break / Run to completion : Process runs until it
current->priority < ready_queue->priority)
completes or suspends itself by:
{ /* choose new process */ performing a call to the kernel e.g. down(semaphore) or
if (current->state == running) { receive(message); it then typically waits for interrupt to
current->state = ready; occur, and a message from the device handler to arrive.
schedule(current); cause error trap, and then the control switches to an
/* add current to ready_q in priority order */} exception handler.
current = ready_q; process completes and leaves system; the current process is
ready_q = ready_q->next; resumed after interrupt.
}
load registers from PCB or stack;
Assembler
Put PC and PSW on stack; Level
return from interrupt; /* load PC and PSW from stack */
}
c Department of Computing, Imperial College London Operating Systems II 68/396
c Department of Computing, Imperial College London Operating Systems II 69/396
Round Robin Process Queue R.R.Q. with Timeslice
Process runs until it suspends itself or time quantum expires.
Runnable process inserted at end of ready queue
'
Suspend $
'
Suspend $ Running Process Suspended Queue
......
......
.......
Running Process Suspended Queue .. .. ......
.....
.....
....... running suspend suspend suspend
..
... ... ..... ' %
running suspend suspend suspend ...
' % nil next next nil
nil next next nil ......
....... Time quantum
" Interrupt
$
Interrupt expired
Schedule $ ......
......
......
.. .. ......
.....
.....
....... runnable runnable runnable
..
... ... ...... &
runnable runnable runnable
..
& ...... Schedule next next nil
....... next next nil Complete
Ready Queue
Complete
Ready Queue Small quantum: more overhead; large quantum: poor response
c Department of Computing, Imperial College London Operating Systems II 70/396
c Department of Computing, Imperial College London Operating Systems II 71/396
Concurrent Processes Concurrent Processes (2)
Activation of one or more processes at the same time Real Concurrency : Multiple hardware processors; usually
less processors than processes
Apparent Concurrency : A single hardware processor which
is switched between processes by interleaving
Over a period of time this gives the illusion of concurrent
execution. Also called pseudo concurrency P4
P3
P2
P3
P1
P2
Time
P1
Time
c Department of Computing, Imperial College London Operating Systems II 72/396
c Department of Computing, Imperial College London Operating Systems II 73/396
Process Interactions Concurrent Programming
Shared Objects. A combination of notations, language constructs, system facilities
Write Write and techniques for:
User A ...... ....... User B expressing potential parallelism
.. Data
solving the resulting synchronisation and communication
Mutual exclusion in critical section problems.
Synchronisation of Action. Same time or defined order Note: The techniques are independent of whether concurrency is
Producer ..... ..... Consumer real (supported by parallel hardware) or apparent (supported by
.. Bounded Buffer ..
software)
Exchange of Information (printing / mail)
Mutual exclusion
Shared memory
Distribution
To safely use shared objects, synchronisation is necessary.
c Department of Computing, Imperial College London Operating Systems II 74/396
c Department of Computing, Imperial College London Operating Systems II 75/396
Why? Concurrency Issues
For expressiveness and elegance of solutions to practical The main issues in managing concurrency safely are:
problems, and for efficiency:
How to express correctly that two programs run concurrently.
Provides programming abstractions for dealing with "real
world" parallelism as occurs for How to make sure that processes synchronise their actions in
Operating Systems the right way (perhaps by formulating constraints on ordering
of events).
Real-Time Systems
How to let processes communicate (use shared data or
Leads to efficient implementations through interleaving on
messages).
uni-processors and real parallel execution on multi-processors
Synchronisation and communication are interdependent
c Department of Computing, Imperial College London Operating Systems II 76/396
c Department of Computing, Imperial College London Operating Systems II 77/396
Concurrency Levels Concurrency Levels (2)
In general, concurrency can be provided at 3 levels: Threads : Those are a kind of lightweight process, and can
Operating System : The OS can support multi-programming exist within a context with full-scale processes. It is a unit of
like for example, in Unix, VMS, VM/370, Mach. All these CPU utilisation, and is identified by the PC, registers, and
systems use the concept of processes to model stack. Protection is not supplied by the kernel and threads
multi-programming. A process gets identified by, e.g., its code, may share code and data with other threads in process. They
data, stack, and state (the value of the Program Counter and are light, because the switching overhead is minimal
the registers; details follow). (switching discussed later)
On systems that recognize threads, switching is performed by
High Level language tasks : Several high level programming the kernel; otherwise, scheduling code is added to the process
languages exist that allow explicit concurrency. They are that contains the threads
typically used for implementing parallel applications, real-time
systems and OS. Examples are: Ada, Regis, CSP, Monitors
package in Modula 2.
c Department of Computing, Imperial College London Operating Systems II 78/396
c Department of Computing, Imperial College London Operating Systems II 79/396
Shared vs Non-shared Expressing Concurrent Execution
Shared Data : Used in multiprocessor systems that have The overall design for a system with processes can be:
shared memory. Access to the shared data is controlled by Static : The number of processes is fixed and known at compile
synchronisation primitives (like, for example, semaphores, time
monitors), and processes communicate through the shared
data. Dynamic : Processes can be created at any time, and their
number is determined by a program.
Non-shared Data : Used in distributed systems that are, for
example, interconnected by networks. The communication Nested : Processes can be defined within processes.
primitives deal with synchronisation, and communication is Flat : Processes are defined at outermost level of program; each
established through message passing or remote procedure program is at execution time exactly one process.
call.
Coarse grained : This expresses that processes are on the
average large, and are relatively few.
Fine Grained : This expresses that processes are on the
average light weight, and many simple processes can exist
that contain only a few statements.
c Department of Computing, Imperial College London Operating Systems II 80/396
c Department of Computing, Imperial College London Operating Systems II 81/396
Dynamic Process Creation Linux Process Creation
Fork and Join (Unix). fork creates a process (child) identical System call fork creates a new child process by making a
to parent, by allocating a new PCB, that is identical to the copy of the parent process image. The child process will
parent’s PCB; to create a different process the child must call inherit the resources of the parent process and will be
exec(ute), which will replace the code and reset the registers. executed concurrently with the parent process.
For process synchronisation, to join, a process can call For the parent process fork returns the process ID of the
waitpid. Concurrency and synchronisation are mixed. child process.
Create Process is a call to the OS. For the child process fork returns 0
Pid := create (file name) System call exit terminates a process implicitly or explicitly:
The result of this call is that the OS allocates storage space System call exit returns an exit status to the parent
and a process ID, and loads code from file store process.
Use other mechanisms to synchronise with process. System call exit does not yet free the resources of the
process.
Parent and child processes are executing concurrently
c Department of Computing, Imperial College London Operating Systems II 82/396
c Department of Computing, Imperial College London Operating Systems II 83/396
Use of fork and exec Static Process Creation
A command interpreter could do: OS configuration time : Processes are created as part of
initialisation of the Kernel, are written as procedures that are
while (TRUE) { /* repeat forever */ loaded with Kernel. This is used in real-time embedded
read_command (command,parameters) systems, where the (limited) resources are pre-defined.
if (fork () != 0) /* fork off child process */
waitpid(-1, &status, 0); /* Parent code */
create(pid,procedure,stack,priority)
else /* Child code */ Compile Time : At language level. This is a mechanism for
execve (command, parameters, 0); creating instances of processes from pre-declared types.
/* execute command */ Process creation is done at initialisation time; fixed number.
} Examples: Concurrent Pascal, Modula
..... P1 ..... waitpid ...
... fork ... .....
.......
P2 .... ..... waitpid
exec .... fork ... .
......
P3
exec
c Department of Computing, Imperial College London Operating Systems II 84/396
c Department of Computing, Imperial College London Operating Systems II 85/396
Process Termination
Normal completion : Process completes execution of body
Suicide : Explicit termination instruction within the process’
code (present e.g. in ADA)
Abnormal exit : The process has run into an error or an
unhandled exception
Aborted : The process stops because another process has
overruled its execution (killed from terminal)
Never : Many real-time processes run in endless loop and never
terminate unless error occurs
c Department of Computing, Imperial College London Operating Systems II 86/396