Transcript Module 4: Processes

Chapter 4
Processes
os4
1
Outline
Process Concept
Process Scheduling
Operations on Processes
Cooperating Processes
Interprocess Communication
Communication in Client-Server
Systems
os4
2
Process Concept (1)
Process (job): a program in execution (informally).


the unit of work in most systems
A system consists of a collection of processes (system
processes and user processes) executing concurrently,
with CPU multiplexed among them
A process is more than the program code (known
as the text section). It also includes: (more formal
definition)

current activity (program counter, content of registers)

stack containing temporary data (e.g., parameters)
data section containing global variables

a set of associated resources.

os4
3
Process Concept (2)
program counter: next instruction to be executed
A program is a passive entity but a process is an
active entity
Two processes may be associated with the same
program, they are considered as separate
execution sequences.

They have the same text section, but their data section
will vary.
e.g., several users may running the copies of the mail/editor
program.
A process may spawn many processes as it runs.
os4
4
Process State
Process state





new: the process is being created
running: instructions are being executed
waiting: the process is waiting for some event to
occur (such as an I/O completion or reception of a
signal)
ready: The process is waiting to be assigned to a
processor
terminated: The process has finished execution
Only one process is running on any processor at
any instant. However, many processes may be
ready or waiting.
os4
5
Diagram of Process State
new
admitted
terminated
interrupt
exit
ready
I/O or
event completion
running
scheduler dispatch
I/O or event wait
waiting
os4
6
Process Control Block (PCB)
Each process control block (task
control block) represents a
process. It includes







process state (N, R, T, W, Run)
program counter
CPU registers
CPU scheduling information (e.g.,
priority)
memory-management information
(e.g., base/limit register)
accounting information
I/O status information
os4
to next PCB
process
state
pointer
process number
program counter
registers
memory limits
list of open files
...
7
CPU Switching
process P0
executing
executing
operating system
process P1
interrupt or system call
.
.
.
.
.
.
.
.
.
.
.
.
.
. idle
.
.
.
.
.
.
.
.
save state into PCB0
.
.
.
reload state from PCB1
interrupt or system call
save state into PCB1
.
.
.
.
.
.
.
.
. idle
.
.
executing
.
.
.
.
. idle
.
reload state from PCB0
os4
8
Threads
Thread

Sometimes is called a lightweight process: is a
basic unit of CPU utilization; it comprises a thread
ID, a program counter, a register set, and a stack.
 It shares with other threads belonging to the
same process its code section, data section, and
other OS resources, such as open files and signals.
 A web browser might have one thread display
images or text while another thread retrieves data
from the network.
 Modern OS has extend the process concept to
allow a process to have multiple threads of
execution.
os4
9
Process Scheduling
Objective of multiprogramming: CPU runs
process at all times to maximize CPU
utilization.
Objective of time sharing: switch CPU
frequently such that users can interact
with each program while it is running.
For a uni-processor system, there is only
one running process. The rest should
wait until CPU free and is rescheduled.
os4
10
Scheduling Queues
Scheduling queues


job queue: containing all processes
ready queue
 usually, stored as a linked list

device queues: each containing processes
waiting for it
Queuing diagram: a common
representation for process scheduling



rectangle: queue
circle: server for a queue
arrow: flow
os4
11
ready
queue
mag tape
unit
1
disk
unit
0
head
tail
PCB7
PCB2
registers
registers
PCB3
PCB14
PCB8
registers
registers
registers
head
tail
head
tail
PCB6
terminal
unit
0
head
tail
registers
Ready queue and various I/O device queues
os4
12
Queuing-diagram Representation
of Process Scheduling
CPU
ready queue
I/O
I/O queue
I/O request
each device
has one
time slice expired
Child
terminates
child
executes
fork a child
interrupt
occurs
wait for an INT
os4
13
Schedulers (1)
Long-term Scheduler (job Scheduler): selecting
processes from the job pool and loads them into
memory for execution.
 Execute less frequently (e.g., once several
minutes)
 Control the degree of multiprogramming
 Select a good process mix of I/O-bound
processes and CPU-bound processes
 Some system, such as time-sharing system, do
not have. Their multiprogramming degree are
controlled by hardware limitation (e.g., # of
terminals) or on the self-adjusting nature of
users.
os4
14
Schedulers (2):
Short-term scheduler
(CPU scheduler)
selecting one of the ready processes, and
allocates the CPU to it.


Execute quite frequently (e.g., once per 100ms)
must be very fast
e.g., if it takes 10 ms, then 10/(100+10) percent of
CPU is wasted.
long-term
end
short-term
CPU
ready queue
I/O
I/O queue(s)
os4
15
Schedulers (3):
Medium-term Scheduler
(Swapping)
 swap out: removing processes from memory to reduce
the degree of multiprogramming.
 swap in: reintroducing swap-out processes into memory
 for improving process mix or for memory not enough
medium-term
swap in
swap out
partially executed
swapped-out processes
ready queue
CPU
I/O waiting
I/O
os4
16
Schedulers (4)
context switch: saving the state of the old
process and loading the saved state of the
new process.


This is a pure overhead
switch time (about 1~1000 ms) depends on
 memory speed
 number of registers
 existence of special instructions
e.g., a single instruction to save/load all registers
 hardware support
e.g., multiple sets of registers
os4
17
Operation on Processes:
Creation and Termination
Process creation


A parent process creates children processes
via a system call (such as fork in UNIX)
A child process may obtain resource by
1. ask new ones from OS, or
2. use a subset of its parent’s
J: prevent system
overloading
(by too many
sub-processes)
P1
P2
P4
P3
P4
P5
process graph (a tree)
os4
18

Two possibilities of execution
 parent execute concurrently
 parent waits until some/all children terminate.

Two possibilities of the address space of the
new process
 The child process is a duplicate of the parent
process. (communication via sharing variables)
 The child process has a program loaded into it.
(communication via message passing)
e.g., UNIX : both (fork, execve)
DEC VMS: load
Windows/NT: both
os4
19
Process termination

two termination system calls
 exit (parent can use wait to get the output)
 abort: usually only the parent can abort a
child (except OS). The reasons may be:
the child has exceeded its usage of some
resources
 the assigned task is no longer required
 the parent is exiting, and OS does not allow its
children to continue
cascading termination (initiated by OS):
a terminated process causes all its children
(and their children in turn) to terminate.

os4
20
Cooperating Processes
Two type of processes

independent process: not affect or be affected
by others

cooperating processes
 reasons:




information sharing (a shared file)
computation speedup (CPUs, I/O channels)
modularity (construct a system in a modular fashion)
convenience (A user can performs several tasks at one
time (editing, printing, compiling))
 need communication/synchronization mechanisms
os4
21
An Example: The producer-consumer
problem


producer produces items (into buffer) for
consumer
e.g., print program  printer driver
compiler  assembler  loader
unbounded-buffer problem
 producer: no wait
 consumer: wait when buffer is empty

bounded-buffer problem
 producer: wait when buffer is full
 consumer: wait when buffer is empty
os4
22

A shared-memory solution for synchronization

implement the buffer as a circular array
var




buffer: array[1..n] of item;
in, out: 0..n-1; (initialized to 0)
next free: in
first full: out
empty: in=out
at most n-1 items
out
in
os4
23
Shared-memory solution for the
producer-consumer problem
Import java.util.*;
Public class BoundedBuffer
{
public BoundedBuffer () {
// Buffer in initially empty
count = 0; in = 0; out = 0;
buffer = new Object[BUFFER_SIZE];
// producer calls this method
public void enter (Object item) { // in next slice}
// consumer calls this method
public Object remove() { // in next slice}
public static final int NAP_TIME = 5;
private static final int BUFFER_SIZE = 5;
private
private
private
private
}
volatile int count;
volatile int in;
//points to the next free position
volatile int out; //points to the next free position
Object [] buffer;
os4
24
public Object remove () {
Object item;
public void enter(Object item) {
while (count == BUFFER_SIZE)
; // do nothing
while (count == 0)
; // do nothing
// add an item to the buffer
++count;
buffer[in] = item;
in = (in + 1) % BUFFER_SIZE;
if (count == BUFFER_SIZE)
system.out.println(“Producer
Entered “ + item + “ Buffer FULL”);
else
system.out.println(“Producer
Entered “ + item + “ Buffer Size” +
count);
}
enter()
os4
// remove an item from the buffer
- -count;
item == buffer[out];
out = (out + 1) % BUFFER_SIZE;
if (count == 0)
system.out.println(“Consumer
Consumed “ + item + “ Buffer
EMPTY”);
else
system.out.println(“Consumer
Consumed “ + item + “ Buffer
Size” + count);
return item;
}
remove()
25
Inter-process Communication (IPC)
Two ways for communication


shared-memory (e.g., thread facility)
IPC (e.g., message-passing system)
An IPC provides a mechanism to allow processes
to communicate and to synchronize their actions
without sharing the same address space.
An IPC is particularly useful in a distributed
environment where communicating processes
may reside on different computers connected
with a network.
chat on WWW.
An IPC facility provides at least two operations:
send(message)
os4
26
receive(message)
Several methods for logically implementing a
link and the send/receive operations:





Naming
Direct or indirect communication
Symmetric or asymmetric communication
Automatic or explicit buffering
Send by copy or send by reference
Fixed-sized or variable-sized messages
Buffering
os4
27
Naming: direct communication
Use process identities (symmetry in
addressing)
send(P, message) receive(
identity Q, message)
Asymmetry (receiving from any process)
send(P, message) receive(id, message)
Properties



from whom
A link is established automatically between every
pair of processes.
A link is associated with exactly two processes.
Between each pair of processes, there exists
exactly one link.
os4
28

The link may be unidirectional, but is usually
bidirectional.
Example: a solution to the producer-consumer
The producer process
The consumer process
problem
repeat
...
produce an item in nextp
...
send(consumer,nextp);
until false;
repeat
receive(producer,nextc);
...
consume the item in nextc
...
until false;
L: limited modularity: if the name of a
process is changed, all old names should be
found. It is not easy for
os4 separate compilation.
29
Naming: indirect communication
Use mailboxes (or called ports, each has a
unique id).
send(A, message)
receive(A, message)
Properties of such a link:



A link is established between every pair of
processes only if they have a shared mailbox.
A link may be associated with more than two
processes.
Between each pair of communicating processes,
there may be a number of different links, each
corresponding to one mailbox.
os4
30

The link may be either unidirectional or bidirectional.
One Problem: Which process, P2 or P3, will
receive the message sent by P1?
P2
send
P1
(1)
mailbox A



(2)
P3
Solutions:
receive
receive
Allow a link to be associated with at most two
processes.
At most one process at a time to execute a receive
operation.
The OS arbitrarily selects one (not both).
os4
31
Synchronization
Message passing may be either blocking or
nonblocking – and also as synchronous and
asynchronous.




Blocking send: SP is blocked until the message is
received by RP or by the mailbox.
Nonblocking send: SP sends the message and
resumes operation.
Blocking receive: RP is blocked until the message
is available.
Nonblocking receive: RP receives a valid message
or a null.
os4
32
Buffering
Capacity of a link: the number of messages
that can reside (queued) temporarily.
No buffering
Three ways for implementation:

zero capacity: queue length = 0.
 The sender must wait until the recipient receives the
message.
 This synchronization is called a rendezvous.

bounded capacity: queue length = n.
 Sender should wait if queue is full.

Automatic buffering
unbounded capacity.
 The sender is never delayed.
os4
33
In nonzero-capacity cases, two processes
communicate asynchronously.
For asynchronous communication, one way to
make sure (or to wait) that the receiver has
received the sent message is as follows.
process P (sender)
send(Q, message)
receive (Q, message)
process Q (receiver)
receive(P, message)
send(P,acknowledgement")
os4
34
Production-Consumer
Example – Mailbox for message passing
The buffer is
implemented using
the java.util.Vector
class (unbounded
capacity)
Note: both the
send() and receive()
are nonblocking
A multi-thread
version is discussed
in Chapter 5.
import java.util.*;
public class MessageQueue
{ public MessageQueue() {
queue = new Vector (); }
//This implements a nonblocking send
public void send(Object item) {
queue.addElement(item); }
//This implements a nonblocking receive
public void receive() {
object item;
if (queue.size() == 0)
return null;
else { item = queue.firstElelemt();
queue.removeElementAt(0);
return item;
}
}
os4private Vector queue;
35
MessageQueue mailBox;
MessageQueue mailBox;
While (true) {
Date message = new
Date();
mailBox.send (message);
}
While (true) {
Date message = (Date)
mailBox.receive ();
if (message != null)
//consume the
message
}
The producer process
The consumer process
os4
36
An Example: Mach
Developed at Carnegie Mellon University
Most communications are carried out by
messages. Message are sent to and received
from mailboxes, called ports.
Even system calls are made by messages.
When each task is created, two special
mailboxes – the Kernel mailbox and the Notify
mailbox – are also created.

The Kernel mailbox is used by the kernel to
communication with the task. The kernel sends
notification of event occurrences to the Notify port.
os4
37
Three system calls using message transfer



msg_send: sends a message to a mailbox
msg_receive
msg_rpc: Remote Procedure Calls (PRCs)
port_allocate: creates a new mailbox and allocates
space for its queue of messages. The task that creates
the mailbox is that mailbox’s owner.
Messages are copied into mailbox. Multiple messages
from the same sender are queued in FIFO order.
If the mailbox is full, the sending thread has 4 options:




Wait indefinitely until there is a room in the mailbox.
Wait at most n milliseconds.
Do not wait at all, but rather return immediately.
Temporarily cache a message.
os4
38
The receive operation must specify from which
mailbox or mailbox set to receive a message.
port_status: returns # of messages in a given
mailbox.
If no message is waiting to be received, the
receiving thread may wait, wait at most n
milliseconds, or not wait.
The Mach message system attempts to avoid
double copy operations by using virtual-memory
management techniques. Mach maps the
address space containing the sender’s message
into the receiver’s address space.
os4
39
os4
40
Process Control Block (PCB)
Information associated with each process.
Process state
Program counter
CPU registers
CPU scheduling information
Memory-management information
Accounting information
I/O status information
os4
41
Process Control Block (PCB)
os4
42
CPU Switch From Process to
Process
os4
43
Process Scheduling Queues
Job queue – set of all processes in the system.
Ready queue – set of all processes residing in
main memory, ready and waiting to execute.
Device queues – set of processes waiting for
an I/O device.
Process migration between the various
queues.
os4
44
Device Queues
os4
45
Representation of Process
Scheduling
os4
46
Schedulers
Long-term scheduler (or job scheduler) –
selects which processes should be brought
into the ready queue.
Short-term scheduler (or CPU scheduler) –
selects which process should be executed
next and allocates CPU.
os4
47
Addition of Medium Term
Scheduling
os4
48
Schedulers (Cont.)
Short-term scheduler is invoked very
frequently (milliseconds)  (must be fast).
Long-term scheduler is invoked very
infrequently (seconds, minutes)  (may be
slow).
The long-term scheduler controls the degree
of multiprogramming.
Processes can be described as either:


I/O-bound process – spends more time doing I/O
than computations, many short CPU bursts.
CPU-bound process – spends more time doing
os4 long CPU bursts.
49
computations; few very
Context Switch
When CPU switches to another process, the
system must save the state of the old process
and load the saved state for the new process.
Context-switch time is overhead; the system
does no useful work while switching.
Time dependent on hardware support.
os4
50
Process Creation
Parent process create children processes,
which, in turn create other processes,
forming a tree of processes.
Resource sharing



Parent and children share all resources.
Children share subset of parent’s resources.
Parent and child share no resources.
Execution


Parent and children execute concurrently.
Parent waits until children terminate.
os4
51
Process Creation (Cont.)
Address space


Child duplicate of parent.
Child has a program loaded into it.
UNIX examples


fork system call creates new process
exec system call used after a fork to
replace the process’ memory space with a
new program.
os4
52
System
os4
53
Process Termination
Process executes last statement and asks the
operating system to decide it (exit).


Output data from child to parent (via wait).
Process’ resources are deallocated by operating
system.
Parent may terminate execution of children
processes (abort).



Child has exceeded allocated resources.
Task assigned to child is no longer required.
Parent is exiting.
 Operating system does not allow child to continue if its
parent terminates.
os4
 Cascading termination.
54
Cooperating Processes
Independent process cannot affect or be
affected by the execution of another process.
Cooperating process can affect or be affected
by the execution of another process
Advantages of process cooperation




Information sharing
Computation speed-up
Modularity
Convenience
os4
55
Producer-Consumer Problem
Paradigm for cooperating processes,
producer process produces information
that is consumed by a consumer
process.


unbounded-buffer places no practical limit
on the size of the buffer.
bounded-buffer assumes that there is a
fixed buffer size.
os4
56
Solution
Shared data
#define BUFFER_SIZE 10
Typedef struct {
...
} item;
item buffer[BUFFER_SIZE];
int in = 0;
int out = 0;
Solution is correct, but can only use
BUFFER_SIZE-1 elements
os4
57
Bounded-Buffer – Producer
Process
item nextProduced;
while (1) {
while (((in + 1) % BUFFER_SIZE) == out)
; /* do nothing */
buffer[in] = nextProduced;
in = (in + 1) % BUFFER_SIZE;
}
os4
58
Bounded-Buffer – Consumer
Process
item nextConsumed;
while (1) {
while (in == out)
; /* do nothing */
nextConsumed = buffer[out];
out = (out + 1) % BUFFER_SIZE;
}
os4
59
Interprocess Communication
(IPC)
Mechanism for processes to communicate
and to synchronize their actions.
Message system – processes communicate
with each other without resorting to shared
variables.
IPC facility provides two operations:


send(message) – message size fixed or variable
receive(message)
If P and Q wish to communicate, they need
to:


establish a communication link between them
os4
exchange messages via send/receive
60
Implementation Questions
How are links established?
Can a link be associated with more than two
processes?
How many links can there be between every
pair of communicating processes?
What is the capacity of a link?
Is the size of a message that the link can
accommodate fixed or variable?
Is a link unidirectional or bi-directional?
os4
61
Direct Communication
Processes must name each other explicitly:


send (P, message) – send a message to process P
receive(Q, message) – receive a message from
process Q
Properties of communication link




Links are established automatically.
A link is associated with exactly one pair of
communicating processes.
Between each pair there exists exactly one link.
The link may be unidirectional, but is usually bidirectional.
os4
62
Indirect
Communication
Messages
are directed and received from
mailboxes (also referred to as ports).


Each mailbox has a unique id.
Processes can communicate only if they
share a mailbox.
Properties of communication link




Link established only if processes share a
common mailbox
A link may be associated with many
processes.
Each pair of processes may share several
communication links.
Link may be unidirectional or bi-directional.
os4
63
Indirect Communication
Operations



create a new mailbox
send and receive messages through mailbox
destroy a mailbox
Primitives are defined as:
send(A, message) – send a message to
mailbox A
receive(A, message) – receive a message
from mailbox A
os4
64
Indirect Communication
Mailbox sharing



P1, P2, and P3 share mailbox A.
P1, sends; P2 and P3 receive.
Who gets the message?
Solutions



Allow a link to be associated with at most two
processes.
Allow only one process at a time to execute a
receive operation.
Allow the system to select arbitrarily the receiver.
Sender is notified who the receiver was.
os4
65
Synchronization
Message passing may be either blocking
or non-blocking.
Blocking is considered synchronous
Non-blocking is considered
asynchronous
send and receive primitives may be
either blocking or non-blocking.
os4
66
Buffering
Queue of messages attached to the link;
implemented in one of three ways.
1. Zero capacity – 0 messages
Sender must wait for receiver (rendezvous).
2. Bounded capacity – finite length of n
messages
Sender must wait if link full.
3. Unbounded capacity – infinite length
Sender never waits.
os4
67
Client-Server Communication
Sockets
Remote Procedure Calls
Remote Method Invocation (Java)
os4
68
Sockets
A socket is defined as an endpoint for
communication.
Concatenation of IP address and port
The socket 161.25.19.8:1625 refers
to port 1625 on host 161.25.19.8
Communication consists between a pair
of sockets.
os4
69
Socket Communication
os4
70
Remote Procedure Calls
Remote procedure call (RPC) abstracts
procedure calls between processes on
networked systems.
Stubs – client-side proxy for the actual
procedure on the server.
The client-side stub locates the server and
marshalls the parameters.
The server-side stub receives this message,
unpacks the marshalled parameters, and
peforms the procedure on the server.
os4
71
Execution of RPC
os4
72
Remote Method Invocation
Remote Method Invocation (RMI) is a
Java mechanism similar to RPCs.
RMI allows a Java program on one
machine to invoke a method on a
remote object.
os4
73
Marshalling Parameters
os4
74