Processes

°
c Department of Computing, Imperial College London Operating Systems II 58/396
 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

Disk I/O
Alarm condition
Keyboard
Clock

Interrupt Time

°
c Department of Computing, Imperial College London Operating Systems II 59/396
 Avoid I/O Delays
An I/O action is normally started by sending information to a
special address in the machine’s memory (DMA); the result of the
action is reported in another address.
After initiating an I/O action, the CPU can repeatedly check the
reply address to see if the execution went well: but this is a
busy-wait solution, which wastes CPU-cycles.
It is better to have the CPU start another action, and have the I/O
device interrupt the CPU when the I/O action has finished, after
which the CPU can continue the initial program.
The requires a concept of halt and restart of program execution:
we need to store the state of a program, so that we can start it
later as if it was not halted at all

°
c Department of Computing, Imperial College London Operating Systems II 60/396
 Processes
An abstraction of a running program, characterised by
code,
input,
output, and
state.
Used in situations where a program can get blocked (waiting for
I/O, e.g.) and another gets the CPU instead; the blocked process
can get restarted at a later, therefore, all information concerning
the process, needed to restart safely, should be stored.
For each process, all this data is stored in a process descriptor,
or process control block (PCB), that is kept in the process table

°
c Department of Computing, Imperial College London Operating Systems II 61/396
 Process States
Exit .
.
Running ...... Terminated
initiate I/O; ......
send message; ­ JJ.J
­ time slice expired
down on semaphore ­ J J pre-empted
­ J J
Picked by J
....­...­ scheduler JJ .J
J .
.....
..... .......
Waiting ... Ready New
I/O complete; Enable
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
 Process Switches
Events (or interrupts) cause process switches. For example, an
I/O completion interrupt will cause the OS to switch to an I/O
process

The way an OS switches between processes cannot be

pre-determined, since the events which cause the switches
are not deterministic
The interleaving of instructions, executed by a processor, from
a set of processes is non-deterministic

°
c Department of Computing, Imperial College London Operating Systems II 63/396
 Scheduler
The part of the OS that decided which of the runnable processes
is to run first. Some criteria for the scheduling algorithm are:
Fairness : Each process gets its fair share of CPU.
Efficiency : Keep CPU busy 100 percent of the time.
Response time : Minimize for interactive users.
Turnaround : Minimize the time users must wait for output.
Throughput : Maximize the number of jobs processed.
Some of these criteria are in conflict

°
c Department of Computing, Imperial College London Operating Systems II 64/396
 Scheduler (2)
It basically changes the state of a process; it picks a process from
the Ready Queue and makes it the Running Process
PCB PCB PCB
Ready Queue
.....
.. ¾
.....
.. ¾
.....
..
runnable runnable runnable

next À next À nil

PCB
.....
Running Process ..
running (normally the
head of the
nil Ready Queue)

°
c Department of Computing, Imperial College London Operating Systems II 65/396
 Scheduler’s Task
The scheduler

allocates processes to processors.

selects highest priority ready process (from head of Ready
Queue) and moves it to the running state, i.e., allows it to start
executing on the processor.
gets invoked after every entry to the kernel.

Current process continues unless:

Kernel call moved it into waiting state (e.g.

down(semaphore)).
Error trap occurred (e.g. memory protection violation).
Time slice expired.
A higher priority process is made ready.

°
c Department of Computing, Imperial College London Operating Systems II 66/396
 Scheduling Strategies
Different strategies exist in selecting the next running process:

Preemptive scheduling: time-slices.

Run to completion: non-preemptive.
Round Robin: last run process to tail of queue.
Priority scheduling: new priority = 1 / (fraction of time-slice
used).
Multiple queues.
Shortest job first.
Guaranteed scheduling: allotted time = 1 / (# procs).
Lottery scheduling.
Real time scheduling.
Two level scheduling: process on disk or in RAM.

°
c Department of Computing, Imperial College London Operating Systems II 67/396
 Scheduler Lay-out
void Scheduler (){
if (current->state != running ||
current->priority < ready_queue->priority)
{ /* choose new process */
if (current->state == running) {
current->state = ready;
schedule(current);
/* add current to ready_q in priority order */}
current = ready_q;
ready_q = ready_q->next;

©
}
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
 Low Level Scheduling
Natural Break / Run to completion : Process runs until it
completes or suspends itself by:
performing a call to the kernel e.g. down(semaphore) or
receive(message); it then typically waits for interrupt to
occur, and a message from the device handler to arrive.
cause error trap, and then the control switches to an
exception handler.
process completes and leaves system; the current process is
resumed after interrupt.

°
c Department of Computing, Imperial College London Operating Systems II 69/396
 Round Robin Process Queue
Runnable process inserted at end of ready queue

' $
Suspend

º º
Running Process Suspended Queue
...... ...... ......
suspend º
. . .....
' %
running suspend suspend ...
nil next ¸ next ¸ nil ¸
.......
Schedule Á
Interrupt Á Á$
º
...... º
...... ......
º
.. .. ......
&
runnable runnable runnable ..

...... next ¸ next ¸ nil ¸

Complete
Ready Queue

°
c Department of Computing, Imperial College London Operating Systems II 70/396
 R.R.Q. with Timeslice
Process runs until it suspends itself or time quantum expires.
' $
Suspend

º º
Running Process Suspended Queue
...... ...... .......
º
.. .. ......
' %
running suspend suspend suspend ..

nil next ¸ next ¸ nil ¸

......
"
Time quantum Á
Interrupt Á Á$
º º
expired
...... ...... .......
runnable º
.. .. ......
&
runnable runnable .
....... Schedule next ¸ next ¸ nil ¸
Complete
Ready Queue
Small quantum: more overhead; large quantum: poor response

°
c Department of Computing, Imperial College London Operating Systems II 71/396
 Concurrent Processes
Activation of one or more processes at the same time

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

P3
P2
P1
Time

°
c Department of Computing, Imperial College London Operating Systems II 72/396
 Concurrent Processes (2)
Real Concurrency : Multiple hardware processors; usually
less processors than processes

ÂP4
¶P3
ÁP2
µP1

Time

°
c Department of Computing, Imperial College London Operating Systems II 73/396
 Process Interactions
Shared Objects.
Write Write
User A ..... ........ User B
.. Data

Mutual exclusion in critical section

Synchronisation of Action. Same time or defined order
Producer ...... ...... Consumer
.. Bounded Buffer ..

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
 Concurrent Programming
A combination of notations, language constructs, system facilities
and techniques for:
expressing potential parallelism
solving the resulting synchronisation and communication
problems.
Note: The techniques are independent of whether concurrency is
real (supported by parallel hardware) or apparent (supported by
software)

°
c Department of Computing, Imperial College London Operating Systems II 75/396
 Why?
For expressiveness and elegance of solutions to practical
problems, and for efficiency:
Provides programming abstractions for dealing with "real
world" parallelism as occurs for
Operating Systems
Real-Time Systems
Leads to efficient implementations through interleaving on
uni-processors and real parallel execution on multi-processors

°
c Department of Computing, Imperial College London Operating Systems II 76/396
 Concurrency Issues
The main issues in managing concurrency safely are:

How to express correctly that two programs run concurrently.

How to make sure that processes synchronise their actions in
the right way (perhaps by formulating constraints on ordering
of events).
How to let processes communicate (use shared data or
messages).

Synchronisation and communication are interdependent

°
c Department of Computing, Imperial College London Operating Systems II 77/396
 Concurrency Levels
In general, concurrency can be provided at 3 levels:
Operating System : The OS can support multi-programming
like for example, in Unix, VMS, VM/370, Mach. All these
systems use the concept of processes to model
multi-programming. A process gets identified by, e.g., its code,
data, stack, and state (the value of the Program Counter and
the registers; details follow).
High Level language tasks : Several high level programming
languages exist that allow explicit concurrency. They are
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
 Concurrency Levels (2)
Threads : Those are a kind of lightweight process, and can
exist within a context with full-scale processes. It is a unit of
CPU utilisation, and is identified by the PC, registers, and
stack. Protection is not supplied by the kernel and threads
may share code and data with other threads in process. They
are light, because the switching overhead is minimal
(switching discussed later)
On systems that recognize threads, switching is performed by
the kernel; otherwise, scheduling code is added to the process
that contains the threads

°
c Department of Computing, Imperial College London Operating Systems II 79/396
 Shared vs Non-shared
Shared Data : Used in multiprocessor systems that have
shared memory. Access to the shared data is controlled by
synchronisation primitives (like, for example, semaphores,
monitors), and processes communicate through the shared
data.
Non-shared Data : Used in distributed systems that are, for
example, interconnected by networks. The communication
primitives deal with synchronisation, and communication is
established through message passing or remote procedure
call.

°
c Department of Computing, Imperial College London Operating Systems II 80/396
 Expressing Concurrent Execution
The overall design for a system with processes can be:
Static : The number of processes is fixed and known at compile
time
Dynamic : Processes can be created at any time, and their
number is determined by a program.
Nested : Processes can be defined within processes.
Flat : Processes are defined at outermost level of program; each
program is at execution time exactly one process.
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 81/396
 Dynamic Process Creation
Fork and Join (Unix). fork creates a process (child) identical
to parent, by allocating a new PCB, that is identical to the
parent’s PCB; to create a different process the child must call
exec(ute), which will replace the code and reset the registers.
For process synchronisation, to join, a process can call
waitpid. Concurrency and synchronisation are mixed.
Create Process is a call to the OS.
Pid := create (file name)
The result of this call is that the OS allocates storage space
and a process ID, and loads code from file store
Use other mechanisms to synchronise with process.

°
c Department of Computing, Imperial College London Operating Systems II 82/396
 Linux Process Creation
System call fork creates a new child process by making a
copy of the parent process image. The child process will
inherit the resources of the parent process and will be
executed concurrently with the parent process.
For the parent process fork returns the process ID of the
child process.
For the child process fork returns 0
System call exit terminates a process implicitly or explicitly:
System call exit returns an exit status to the parent
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 83/396
 Use of fork and exec
A command interpreter could do:

while (TRUE) { /* repeat forever */

read_command (command,parameters)
if (fork () != 0) /* fork off child process */
waitpid(-1, &status, 0); /* Parent code */
else /* Child code */
execve (command, parameters, 0);
/* execute command */
}
...... P1 ...... waitpid ......
.. fork .. ..
......
P2 .... ..... waitpid
exec .... fork ...
.......
P3
exec
°
c Department of Computing, Imperial College London Operating Systems II 84/396
 Static Process Creation
OS configuration time : Processes are created as part of
initialisation of the Kernel, are written as procedures that are
loaded with Kernel. This is used in real-time embedded
systems, where the (limited) resources are pre-defined.
create(pid,procedure,stack,priority)
Compile Time : At language level. This is a mechanism for
creating instances of processes from pre-declared types.
Process creation is done at initialisation time; fixed number.
Examples: Concurrent Pascal, Modula

°
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