Year: 2023-2024
Fall Semester
Operating Systems
Dr. Wafaa Samy
Operating System Concepts – 10th Edition
Silberschatz, Galvin and Gagne ©2018 3.1 Modified by Dr. Wafaa Samy
Chapter 3: Processes (Part 3)
Operating System Concepts – 10th Edition
Silberschatz, Galvin and Gagne ©2018 Modified by Dr. Wafaa Samy
IPC in Message-Passing Systems (Cont.)
Operating System Concepts – 10th Edition
Silberschatz, Galvin and Gagne ©2018 3.3 Modified by Dr. Wafaa Samy
2. Synchronization
Communication between processes takes place through calls to send() and
receive() primitives. There are different design options for implementing each
primitive.
Message passing may be either blocking or non-blocking, also known as
synchronous and asynchronous.
Blocking is considered synchronous:
• Blocking send -- the sender process is blocked until the message is
received by the receiving process or by the mailbox.
• Blocking receive -- the receiver is blocked until a message is available.
Non-blocking is considered asynchronous:
• Non-blocking send -- the sender process sends the message and
continue (i.e. resumes operation).
• Non-blocking receive -- the receiver receives: a valid message, or a
Null message.
Different combinations of send() and receive() are possible:
• If both send and receive are blocking, we have a rendezvous between
the sender and the receiver.
Operating System Concepts – 10th Edition
Silberschatz, Galvin and Gagne ©2018 3.4 Modified by Dr. Wafaa Samy
Producer-Consumer: Message Passing
The solution to the producer–consumer problem becomes trivial when we
use blocking send() and receive() statements.
• The producer merely invokes the blocking send() call and waits until
the message is delivered to either the receiver or the mailbox.
• Likewise, when the consumer invokes blocking receive() call, it blocks
until a message is available.
Producer
message next_produced;
while (true) {
/* produce an item in next_produced */
send(next_produced);
}
Consumer
message next_consumed;
while (true) {
receive(next_consumed)
/* consume the item in next_consumed */
}
Operating System Concepts – 10th Edition
Silberschatz, Galvin and Gagne ©2018 3.5 Modified by Dr. Wafaa Samy
3. Buffering
Queue of messages attached to the link.
• Whether communication is direct or indirect, messages exchanged by
communicating processes reside in a temporary queue.
Queues can be Implemented in one of three ways:
1. Zero capacity – no messages are queued on a link. Sender must wait
for receiver (rendezvous).
The queue has a maximum length of zero; thus, the link cannot have any
messages waiting in it.
In this case, the sender must block until the recipient receives the message.
The zero-capacity is referred to as a message system with no buffering.
2. Bounded capacity – the queue has finite length of n messages, sender
must wait if link is full. The link’s capacity is finite.
If the queue is not full when a new message is sent, the message is placed in
the queue, and the sender can continue execution without waiting.
If the link is full, the sender must block until space is available in the queue.
3. Unbounded capacity – the queue has infinite length, sender never
waits. The sender never blocks.
Operating System Concepts – 10th Edition
Silberschatz, Galvin and Gagne ©2018 3.6 Modified by Dr. Wafaa Samy
Example of IPC Systems
(Pipes)
Operating System Concepts – 10th Edition
Silberschatz, Galvin and Gagne ©2018 3.7 Modified by Dr. Wafaa Samy
Pipes
A pipe acts as a channel allowing two processes to communicate.
• Pipes were one of the first IPC mechanisms in early UNIX systems.
In implementing a pipe, four issues must be considered:
1. Is communication unidirectional or bidirectional?
2. If case of two-way communication (i.e. bidirectional), is it half
duplex (data can travel only one way at a time) or full duplex (data
can travel in both directions at the same time)?
3. Must a relationship (such as parent–child) exist between the
communicating processes?
4. Can the pipes communicate over a network, or must the
communicating processes reside on the same machine?
Two common types of pipes used on both UNIX and Windows systems:
1. Ordinary pipes – can not be accessed from outside the process that
created it. Typically, a parent process creates a pipe and uses it to
communicate with a child process that it created.
2. Named pipes – can be accessed without a parent-child relationship.
Operating System Concepts – 10th Edition
Silberschatz, Galvin and Gagne ©2018 3.8 Modified by Dr. Wafaa Samy
Ordinary Pipes
Ordinary Pipes allow communication in standard producer-consumer style.
• Producer writes to one end of the pipe (the write-end).
• Consumer reads from the other end (the read-end).
Ordinary pipes are therefore unidirectional, allowing only one-way
communication.
• If two-way communication is required, two pipes must be used, with each
pipe sending data in a different direction.
Require parent-child relationship between communicating processes.
In Unix:
• fd[0] is the read end of the
pipe.
• fd[1] is the write end.
Ordinary pipes on Windows are termed anonymous pipes, and they
behave similarly to their UNIX counter parts: they are unidirectional and
employ parent–child relationships between the communicating processes.
Operating System Concepts – 10th Edition
Silberschatz, Galvin and Gagne ©2018 3.9 Modified by Dr. Wafaa Samy
Named Pipes
Named Pipes are more powerful than ordinary pipes.
Communication is bidirectional.
No parent-child relationship is necessary between the
communicating processes.
Once a named pipe is established, several processes can use the
named pipe for communication.
Both UNIX and Windows systems support named pipes, although
the details of implementation differ greatly.
Operating System Concepts – 10th Edition
Silberschatz, Galvin and Gagne ©2018 3.10 Modified by Dr. Wafaa Samy
PIPES IN PRACTICE
Pipes are used in the UNIX command-line environment for situations
in which the output of one command serves as input to another.
For example:
• The UNIX ls command produces a directory listing.
• The command less manages output by displaying only one screen
of output at a time where the user may use certain keys to move
forward or backward in the file.
• Setting up a pipe between the ls and less commands (which are
running as individual processes) allows the output of ls to be
delivered as the input to less, enabling the user to display a large
directory listing a screen at a time.
A pipe can be constructed on the command line using the | character.
The complete command is ls | less
The ls command serves as the producer, and its output is
consumed by the less command.
Operating System Concepts – 10th Edition
Silberschatz, Galvin and Gagne ©2018 3.11 Modified by Dr. Wafaa Samy
Communication in Client-Server Systems
Sockets.
Remote Procedure Calls.
Operating System Concepts – 10th Edition
Silberschatz, Galvin and Gagne ©2018 3.12 Modified by Dr. Wafaa Samy
Sockets
A pair of processes communicating over a network employs a pair of
sockets — one for each process.
A socket is defined as an endpoint for communication.
• A socket is identified by a concatenation of IP address with a port number (i.e.
a number to differentiate network services on a host).
All ports below 1024 are well known and are used to implement standard
services.
• Example: The socket 161.25.19.8:1625 refers to port 1625 on host
161.25.19.8
Communication consists between a pair of sockets.
In general, sockets use a client–server architecture.
• The server waits for incoming client requests by listening to a specified port.
• Once a request is received, the server accepts a connection from the client
socket to complete the connection.
Operating System Concepts – 10th Edition
Silberschatz, Galvin and Gagne ©2018 3.13 Modified by Dr. Wafaa Samy
Socket Communication
Example:
• If a client on host X with IP address
146.86.5.20 wishes to establish a
connection with a web server (which is
listening on port 80) at address
161.25.19.8, host X may be assigned port client
1625.
When a client process initiates a
request for a connection, it is web server
assigned a port (i.e. greater than
1024) by its host computer. All connections must be unique.
Therefore, if another process also
• The connection will consist of a pair of on host X wished to establish
sockets: (146.86.5.20:1625) on host X another connection with the same
and (161.25.19.8:80) on the web server. web server, it would be assigned a
• The packets traveling between the hosts port number greater than 1024 and
are delivered to the appropriate process not equal to 1625. This ensures
based on the destination port number. that all connections consist of a
unique pair of sockets.
Operating System Concepts – 10th Edition
Silberschatz, Galvin and Gagne ©2018 3.14 Modified by Dr. Wafaa Samy
Sockets in Java
Three types of sockets
• Connection-oriented (TCP)
• Connectionless (UDP)
• MulticastSocket class–
data can be sent to multiple
recipients.
Consider this “Date” server in
Java:
Operating System Concepts – 10th Edition
Silberschatz, Galvin and Gagne ©2018 3.15 Modified by Dr. Wafaa Samy
Sockets in Java
The equivalent Date client
Operating System Concepts – 10th Edition
Silberschatz, Galvin and Gagne ©2018 3.16 Modified by Dr. Wafaa Samy
Chapter 5: CPU Scheduling (Part 1)
Operating System Concepts – 10th Edition
Silberschatz, Galvin and Gagne ©2018 Modified by Dr. Wafaa Samy
Outline
Basic Concepts
Scheduling Criteria
Scheduling Algorithms
Multi-Processor Scheduling
Algorithm Evaluation
Operating System Concepts – 10th Edition
Silberschatz, Galvin and Gagne ©2018 5.18 Modified by Dr. Wafaa Samy
Basic Concepts
Operating System Concepts – 10th Edition
Silberschatz, Galvin and Gagne ©2018 5.19 Modified by Dr. Wafaa Samy
Basic Concepts
In a system with a single CPU core:
• Only one process can run at a time.
• Other processes must wait until the CPU’s core is free and can be rescheduled.
The objective of multiprogramming is to have some process running at all
times, to maximize CPU utilization.
A process is executed until it must wait (for the completion of I/O request).
• In a non-multiprogrammed system, the CPU then just sits idle.
All this waiting time is wasted; no useful work is accomplished.
• With a multiprogramming system, we try to use this time productively. Every
time one process has to wait, another process can take over use of the CPU.
Several processes are kept in memory at one time.
When one process has to wait, the operating system takes the CPU away
from that process and gives the CPU to another process.
This pattern continues. Every time one process has to wait, another
process can take over use of the CPU.
On a multicore system, this concept of keeping the CPU busy is extended to
all processing cores on the system.
Operating System Concepts – 10th Edition
Silberschatz, Galvin and Gagne ©2018 5.20 Modified by Dr. Wafaa Samy
CPU–I/O Burst Cycle
Maximum CPU utilization obtained with
multiprogramming.
The success of CPU scheduling depends on
an observed property of processes.
CPU–I/O Burst Cycle: Process execution
consists of a cycle of CPU execution and I/O
wait.
Process execution begins with a CPU burst
followed by I/O burst, which is followed by
another CPU burst, then another I/O burst,
and so on.
Eventually, the final CPU burst ends with a
system request to terminate execution.
CPU burst distribution is of main concern.
Alternating sequence of
Operating System Concepts – 10th Edition
CPU and I/O bursts.
Silberschatz, Galvin and Gagne ©2018 5.21 Modified by Dr. Wafaa Samy
Histogram of CPU-burst Times
The durations of CPU bursts have been
measured extensively.
• Although they vary greatly from process
to process and from computer to
computer, they tend to have a frequency
curve similar to that shown in figure.
The curve is generally characterized with
a large number of short CPU bursts and
a small number of long CPU bursts.
• An I/O-bound program typically has
many short CPU bursts.
• A CPU-bound program might have a
few long CPU bursts.
This distribution can be important when
implementing a CPU-scheduling
algorithm. Large number of short bursts
Small number of longer bursts
Operating System Concepts – 10th Edition
Silberschatz, Galvin and Gagne ©2018 5.22 Modified by Dr. Wafaa Samy
CPU Scheduler
The CPU scheduler selects from among the processes in
ready queue, and allocates a CPU core to one of them.
• Queue may be ordered in various ways.
A ready queue can be implemented as a first-in and first-out
(FIFO) queue, a priority queue, a tree, or simply an unordered
linked list.
• The records in the queues are generally process control
blocks (PCBs) of the processes.
Operating System Concepts – 10th Edition
Silberschatz, Galvin and Gagne ©2018 5.23 Modified by Dr. Wafaa Samy
Operating System Concepts – 10th Edition
Silberschatz, Galvin and Gagne ©2018 5.24 Modified by Dr. Wafaa Samy
