Processes
Tran, Van Hoai
Faculty of Computer Science & Engineering
HCMC University of Technology
E-mail: hoai@hcmut.edu.vn
(partly based on slides of Le Thanh Van)
1 / 71
Outline
1 Process concept
2 Process scheduling
3 Operations on processes
4 Interprocess communication
5 Communication in client-server model
2 / 71
Outline
1 Process concept
2 Process scheduling
3 Operations on processes
4 Interprocess communication
5 Communication in client-server model
3 / 71
What is a process ?
The textbook
A process is a program in execution
Oxford dictionary
A process is a series of actions or steps taken in order to
achieve a particular end
4 / 71
What is a process ?
The textbook
A process is a program in execution
Oxford dictionary
A process is a series of actions or steps taken in order to
achieve a particular end
process execution must progress in sequential fashion
job and process are used interchangeably
5 / 71
Process vs. Program
Process is not the same as “program”
6 / 71
Process vs. Program
Process is not the same as “program”
Program is a passive executable code on disk; process is an
active entity
7 / 71
Process vs. Program
Process is not the same as “program”
Program is a passive executable code on disk; process is an
active entity
A same program can be executed into multiple processes
(normally by mutiple users)
8 / 71
Process vs. Program
Process is not the same as “program”
Program is a passive executable code on disk; process is an
active entity
A same program can be executed into multiple processes
(normally by mutiple users)
Components of a process
program counter
stack
data section
9 / 71
Process vs. Program
Process is not the same as “program”
Program is a passive executable code on disk; process is an
active entity
A same program can be executed into multiple processes
(normally by mutiple users)
Components of a process
program counter
stack
data section
User and OS processes
jobs (batch system)
tasks (time-shared system)
process (generic)
10 / 71
Process vs. Program
Process is not the same as “program”
Program is a passive executable code on disk; process is an
active entity
A same program can be executed into multiple processes
(normally by mutiple users)
Components of a process
program counter
stack
data section
User and OS processes
jobs (batch system)
tasks (time-shared system)
process (generic)
J. Brisendine (writer)
Life is a process, not a thing
11 / 71
Process in memory
12 / 71
Process in memory
Temporary data
Dynamically allocated memory
Global variables
Program code
13 / 71
Process in execution
Conceptual model of
process execution
Process A Process B Process D
Process C
time
14 / 71
Process in execution
Conceptual model of Actual interleaved exe-
process execution cution of the processes
Process A
Process A Process B Process D Process B
Process D
Process A
Process C Process B
Process D
Process A
Process C
Process D
Process C
Process C
Process C
Process C
time
15 / 71
Process state
2-state process model
A process is either “running” or “not running”
dispatch
entry exit
not running Running
pause
16 / 71
Process state
2-state process model
A process is either “running” or “not running”
dispatch
entry exit
not running Running
pause
Queueing diagram
queue
enter dispatch exit
CPU
17 / 71
Process state
2-state process model
A process is either “running” or “not running”
dispatch
entry exit
not running Running
pause
Queueing diagram
queue
Weakness
enter dispatch exit
CPU
2-state model cannot deal with I/O operations.
18 / 71
Process state
As a process executes, it changes state
new: the process is being created
running: its instructions are being executed
waiting: the process is waiting for some event to occur
ready: the process is waiting to be assigned to CPU
terminated: the process has finished execution
19 / 71
Process state
As a process executes, it changes state
new: the process is being created
running: its instructions are being executed
waiting: the process is waiting for some event to occur
ready: the process is waiting to be assigned to CPU
terminated: the process has finished execution
20 / 71
Process control block (PCB)
Following information is for a process in operating system,
stored in process control block
Process state
Program counter
CPU registers
CPU scheduling information (e.g.,
process priority, pointers to scheduling
queues)
Memory management information
(e.g., base/limit registers, segment
tables)
Accounting information
I/O status information (e.g., open
files)
21 / 71
Process switching
PCBs are used for process switching in a mutiple tasking
operating system
22 / 71
Context switching
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
Ex.: UltraSPARC uses multiple register sets
23 / 71
Outline
1 Process concept
2 Process scheduling
3 Operations on processes
4 Interprocess communication
5 Communication in client-server model
24 / 71
Process scheduling queues
In 5-state process model, we need more than 1 queue to store
jobs
25 / 71
Process scheduling queues
In 5-state process model, we need more than 1 queue to store
jobs
Queue types:
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
26 / 71
Process queues as linked lists
27 / 71
Queueing diagram
28 / 71
Schedulers
Processes are selected from the queues for migration, under
some selection strategies managed by schedulers.
29 / 71
Schedulers
Processes are selected from the queues for migration, under
some selection strategies managed by schedulers.
Long-term scheduler (or job scheduler): selects which
processes should be brought into the ready queue
Frequency: only necessary when a process leaves
Efficiency depends strongly on I/O bound or CPU bound
30 / 71
Schedulers
Processes are selected from the queues for migration, under
some selection strategies managed by schedulers.
Long-term scheduler (or job scheduler): selects which
processes should be brought into the ready queue
Frequency: only necessary when a process leaves
Efficiency depends strongly on I/O bound or CPU bound
Short-term scheduler (or CPU scheduler): selects which
process should be executed next and allocates CPU
Frequency: at least once every 100 milliseconds (quantum
time)
Effciency depends strongly on process switching time
31 / 71
Schedulers
Processes are selected from the queues for migration, under
some selection strategies managed by schedulers.
Long-term scheduler (or job scheduler): selects which
processes should be brought into the ready queue
Frequency: only necessary when a process leaves
Efficiency depends strongly on I/O bound or CPU bound
Short-term scheduler (or CPU scheduler): selects which
process should be executed next and allocates CPU
Frequency: at least once every 100 milliseconds (quantum
time)
Effciency depends strongly on process switching time
Job scheduler is for batch systems
CPU scheduler is for time-sharing systems
32 / 71
Medium-term scheduler
Swaping is useful to release some resources (for other
ready processes)
Mobile OSs utilize swaping to save memory and power
33 / 71
Outline
1 Process concept
2 Process scheduling
3 Operations on processes
4 Interprocess communication
5 Communication in client-server model
34 / 71
Process tree
Process tree
Processes are organized in a form of tree
Process identifier
35 / 71
Process creation
Parent creates children processes
36 / 71
Process creation
Parent creates children processes
Resource sharing: 3 possibilities
Parent and children share all resources
Children share subset of parent’s resources
Parent and children share no resources
Execution: 2 possibilities
Parent and children execute concurrently
Parent waits until children terminate
Address-space: 2 possibilities
Children duplicate of the parent (program & data)
Children load new program
37 / 71
fork() system call
#include <sys/types.h>
#include <stdio.h>
#include <unistd.h>
Memory Memory
int main()
{
pid_t pid;
copy
/* fork a child */ Process Parent
pid = fork(); pid=xxx pid=xxx
fork()
if ( pid < 0 ){ /* error occurs */
fprintf( stderr, "Fork failed\n" );
return 1; Child
} else if ( pid == 0 ){ /* child process */ pid=0
execlp( "/bin/ls", "ls", NULL );
} else { /* parent process */
wait(NULL);
printf( "Child complete!\n" );
}
return 0;
}
38 / 71
Process termination
Process executes the last statement and asks OS to
decide it (exit())
Output data from child to parent (via wait())
Process’s resources are deallocated by OS
39 / 71
Process termination
Process executes the last statement and asks OS to
decide it (exit())
Output data from child to parent (via wait())
Process’s resources are deallocated by OS
Parent may terminate execution of children processes
(abort())
Child has exceeded allocated resources
Task assigned to child is no longer required
Parent is exiting
OS does not allow child to continue if its parent terminates ⇒
Cascading termination
Parent did not invoke wait() and instead terminated, thereby
leaving its child processes as orphans
40 / 71
Outline
1 Process concept
2 Process scheduling
3 Operations on processes
4 Interprocess communication
5 Communication in client-server model
41 / 71
Process relationship
Independent process: cannot affect or be affected by
others
Independent process does not share data
Cooperating process: can affect or be affected by others
Cooperating process does share data
Reasons for process cooperation
Information sharing
Computation speedup
Modularity
Convenience
42 / 71
Interprocess communication (IPC)
IPC
IPC is used to exchange
data and information
2 IPC models:
shared-memory and
message-passing
Shared-memory: fast
Message-passing: no conflict ; suitable for distributed
system; better performance on multiple core architecture
43 / 71
Shared-memory
All things for IPC are decided by processes in
communication themselves, not under OS’s control
Producer Consumer
item next_produced; item next_consumed;
while (true){ while (true){
while ((( in + 1 ) % BUFFER_SIZE ) == out ) while ( in == out )
; /* do nothing */ ; /* do nothing */
buffer[ in ] = next_produced; next_consumed = buffer[ out ];
in = ( in + 1 ) % BUFFER_SIZE; out = ( out + 1 ) % BUFFER_SIZE;
} }
At most BUFFER_SIZE-1 items in the buffer at the same
time
44 / 71
Message-passing
IPC facility provides at least 2 operations
send(message)
receive(message)
If P and Q wish to communicate, they need to
establish a communication link between them
exchange a message via send()/receive()
Methods to implement communication link
physical link: shared memory, hardware bus, network, ...
logical link: by following methods
Direct or indirect communication
Synchronous or asynchronous communication
Automatic or explicit buffering
45 / 71
Message-passing
Implementation questions
How are links establised ?
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 ?
46 / 71
Message-passing
Direct communication
Explicit name of sender and receiver must be given
send(P,message)
receive(Q,message)
Links are established automatically
A link is associated with exactly one pair of
communicating processes
The link may be unidirectional, but is usually
bi-directional
47 / 71
Message-passing
Direct communication
Explicit name of sender and receiver must be given
send(P,message)
receive(Q,message)
Links are established automatically
A link is associated with exactly one pair of
communicating processes
The link may be unidirectional, but is usually
bi-directional
Disadvantage
Direct communication has poor modularity
48 / 71
Message-passing
Indirect communication (1)
Messages are sent to or received from a mailbox or port
send(A,message)
receive(A,message)
A is a mailbox with unique identification
A link between 2 processes is established only if both
have a shared mailbox
A link may be associated with more than 2 processes
Between each pair, several different links may exist
49 / 71
Message-passing
Indirect communication (1)
P1 , P2 and P3 share a mailbox.
P1 sends a message
P2 and P3 receive
Who gets the message ?
50 / 71
Message-passing
Indirect communication (1)
P1 , P2 and P3 share a mailbox.
P1 sends a message
P2 and P3 receive
Who gets the message ?
It depends on which of the following methods is chosen
A link associated with 2 processes at most
Allowing one process to perform receive() at a time
An algorithm to choose which process to perform receive()
(e.g., round-robin)
51 / 71
Message-passing
Indirect communication (1)
P1 , P2 and P3 share a mailbox.
P1 sends a message
P2 and P3 receive
Who gets the message ?
It depends on which of the following methods is chosen
A link associated with 2 processes at most
Allowing one process to perform receive() at a time
An algorithm to choose which process to perform receive()
(e.g., round-robin)
A mailbox may be owned by a process or OS. If it owned
by OS, system calls must be provided to
1 Create a new mailbox
2 Send and receive messages through the mailbox
3 Delete a mailbox
52 / 71
Message-passing
Synchronization
send() and receive() can be blocking (synchronous) or
non-blocking (asynchronous)
53 / 71
Message-passing
Synchronization
send() and receive() can be blocking (synchronous) or
non-blocking (asynchronous)
(source: cfd-online.com)
54 / 71
Message-passing
Synchronization
send() and receive() can be blocking (synchronous) or
non-blocking (asynchronous)
(source: cfd-online.com) (source: cfd-online.com)
55 / 71
Message-passing
Buffering
Message queues attached to the link; implemented in one
of 3 ways
Zero capacity: 0 message; sender must wait for receiver
Bounded capacity: finite length of n; sender must wait if link
is full
Unbounded capacity: infinite length; sender never waits
56 / 71
Outline
1 Process concept
2 Process scheduling
3 Operations on processes
4 Interprocess communication
5 Communication in client-server model
57 / 71
Client-server communication
(source: wikipedia)
58 / 71
Client-server communication
(source: wikipedia)
Sockets
Remote Procedure Calls
Remote Method Invocation (Java)
Pipes
59 / 71
Socket
Socket is an endpoint, consisting of
IP address
port
Socket
161.25.19.8:1625
refers to port 1625
on host 161.25.19.8
60 / 71
Socket
Socket is an endpoint, consisting of
IP address
port
161.25.19.8
Socket Server 1
161.25.19.8:1625 Client 2
refers to port 1625 Client 1 Server 2
on host 161.25.19.8
Server 3 Client 3
1625
22
80
61 / 71
Socket communication
62 / 71
Socket communication
Socket is low-level form of communication in which data is
transferred in unstructured stream.
63 / 71
Remote procedure call (RPC)
Remote procedure call (RPC) abstracts procedure calls
between processes on networked systems
Messages exchanged in RPC are well-structured (function
name, parameters)
Stubs: client-side proxy for the actual procedure on the
server
separate stub for each separate remote procedure
stub locates port on server and marshalls parameters into a
package (by a mechanism of External Data Representation
(XDR))
The server-side stub receives this message, unpacks the
marshalled parameters, and peforms the procedure on the
server
64 / 71
Execution of RPC
65 / 71
Execution of RPC
RPC is useful to implement services for distributed systems
66 / 71
Remote method invocation
A Java mechanism and quite similar to RPC
RMI allows a Java program on one machine to invoke a
method on a remote object
67 / 71
Pipe
Pipe is one of very first IPC mechanisms in early UNIX
Ordinary pipe is unidirectional
Pipes can be treated as a special type of file
read end write end
68 / 71
Anonymous pipe
#include <sys/types.h>
#include <stdio.h>
#include <string.h> if ( pid > 0 ){
#include <unistd.h> /* close unused end of pipe */
close( fd[READ_END] );
#define BUFFER_SIZE 25
#define READ_END 0 /* write to the pipe */
#define WRITE_END 1 write( fd[WRITE_END], write_msg,
strlen(write_msg) + 1 );
int main(void)
{ /* close the write end */
char write_msg[BUFFER_SIZE] = "Greetings"; close( fd[WRITE_END] );
char read_msg[BUFFER_SIZE]; }
int fd[2]; else {
pid_t pid; /* close unused end of pipe */
close( fd[WRITE_END] );
/* create the pipe */
if ( pipe( fd ) == 1 ){ /* write to the pipe */
fprintf( stderr, "Pipe failed!\n" ); read( fd[READ_END], read_msg, BUFFER_SIZE );
return 1;
} /* close the read end */
close( fd[READ_END] );
/* fork a child process */ }
pid = fork();
if ( pid < 0 ){ return 0;
fprintf( stderr, "Fork failed!\n" ); }
return 1;
}
69 / 71
Homeworks
1 Read materials on Thread: textbook, slides (Le Thanh
Van)
2 There is quiz in April 1, 2021) on Process & Thread
70 / 71
Homeworks
1 Read materials on Thread: textbook, slides (Le Thanh
Van)
2 There is quiz in April 1, 2021) on Process & Thread
3 Quiz grade (of students in 2017)
Histogram of grade$X7
10
8
Frequency
6
4
2
0
4 5 6 7 8 9 10
grade$X7
71 / 71
