Transcript OperatingSystems-Lecture14

Operating System Concepts and Techniques
Lecture 14
Interprocess communication-3
M. Naghibzadeh
Reference
M. Naghibzadeh, Operating System Concepts and Techniques, irst ed., iUniverse Inc., 2011.
To order: www.iUniverse.com, www.barnesandnoble.com, or www.amazon.com
Main program to spawn producer and
consumer processes
void main (void)
{
int pid;
pid = fork();
if (pid != 0) producer();
else consumer();
}
2
Semaphore adv/disadv
Advantages


A general solution for binary and integer
constraints
No busy-wait; if a process wants to use an
unavailable resource it sleeps in the queue of
waiting processes for that resource
Disadvantages

Somewhat difficult to use, but remember, OS
designers are highly skilled
3
Dijkstra’s P and V
Dijkstra first implemented down and up methods as
follows
P(s)
s = s-1;
if s < 0 wait (s);
V(s)
s = s+1;
if s ≤ 0 signal(s);
It is simple, symmetric, and it knows how many
processes are waiting for the resource
With down and up we do not know how many
processes are waiting for the resource
4
Monitor Based IPC
Monitor concept is for simplifying the
implementation of ME
Primitives are:


Wait
Signal
On condition variables wait and signal
may be executed
Only one process could be inside
monitor at any time  ME
5
Sample monitor
class insert_remove : public monitor
{ private:
condition available, occupied;
int count;
public:
insert (struct buffer_slot &entity);
{ if (count == BC) wait (&available);
insert_entity(&entity);
count = count +1;
if (count ==1) signal(&occupied) }
remove (struct buffer_slot &entity)
{ if (count == 0) wait (&cooupied);
remove_entity(&entity);
count = count - 1;
if (count = BC-1) signal(&available); }
Insert_remove (condition available=BC, condition occupied=0,
int count=0);
}
insert_remove IR;
6
Producer-Consumer
class producer_consumer
{
private:
struct buffer_slot entity;
public:
producer()
{
while (true) {
produce_entity (&entity);
IR.insert (&entity) ; }
}
consumer()
{
while (true) {
IR.remove(&entity);
consume_entity(&entity);
}
}
producer_consumer (struct buffer_slot entity =””);
}
7
Message-Based IPC method
Message is mainly used for information
interchange between in distributed systems,
however, it can be used within standalone
computers
There are two main system calls, send and
receive; usually with the following format


send (source, destination, message)
receive (source, destination, message)
8
Blocking/Non-blocking
Sending/receiving could be blocking or non-blocking;
we are interested in non-blocking send and blocking
receive




Blocking send: The execution of the sender process is suspended until
the message is delivered and the receiver informs the sender of the
matter
Nonblocking send: The sender executes the send and continues its
execution; The sender will not become aware of whether or not the
message was actually delivered
Blocking receive: The receiver(s) executes a receive and waits until
the message is fully received before proceeding
Non-blocking receive: The receiver executes a receive and continues
its execution; if the message is available it is received, otherwise, when
the message is received the kernel will send an interrupt to the
corresponding receiver process informing it of the receipt of message
9
How to enforce mutual exclusion
Suppose we have a common mailbox with one
message in it
Whichever process grabs the message is allowed to
use the critical resource
After the execution of its critical section, the process
sends back the message to the mailbox
Proper send and receive statements for this purpose
would be:


receive (mailbox, message)
send (mailbox, message)
10
The producer procedure
The following is the initialization and the
producer
#define true 1
#define BC 1000
// Buffer capacity
void producer (void)
{
struct buffer_slot entity;
message msg1, msg2;
while (true) {
produce_an_entity(&entity);
receive (consumer, producer, &msg1); //Wait for consumer’s message
receive (mailbox,&msg2);
//Get permission to use the entity-queue
insert_the_entity(&entity);
//Put entity in queue
send (mailbox, &msg2);
//Free the resource, i.e., queue
send (producer, consumer,&msg1);
//One slot is filled
}
}
11
The consumer procedure
void consumer (void)
{
struct buffer_slot entity;
message msg1, msg2;
for (i=0; i<BC; i++) send (consumer, producer, &msg1); //BC slots are free
while (true) {
receive (producer, consumer, &msg1); //Wait until there is an entity
receive (mailbox, &msg2);
remove_the_entity(&entity);
send (maibox, msg2);
send (consumer, producer,msg1);
consume_the_entity(&entity);
}
}
12
Main program to spawn producer and
consumer processes
void main (void)
{
int pid;
message msg2;
send (mailbox, &msg2);
pid = fork();
if (pid != 0) producer();
else consumer();
}
13
Summary
The semaphore method does not suffer from busywait; it is not restricted to two processes; it can be
used in multiprocessor environments.
The message-based method is borrowed from
distributed operating systems, but it works on
centralized systems, as well
Depending on the types of send and receive, there
are four possible combinations
Non-blocking send and blocking receive fits our need
to solve problems like producer-consumer
In message passing solutions, message loss could
pose a problem
14
Find out
Whether a process can wake itself up after sleeping
due to the execution of wait(&s)
If it is logical to execute wait (&mutex) before wait
(&available) in the producer-consumer problem
The correspondence between P and V on to down and
up, respectively
How can we modify down and up to count the
number of processes sleeping in the queue of a
resource
What would happen if we used non-blocking receive
for the implementation of producer consumer
15
Any questions?
16