Process Communication and Synchronization

Process Communication and Synchronization

Principle of Concurrency

Inter process Communication

There should be well structured way of communication between process without using interrupts. Such communication is known as Inter process communication (IPC)

---

Issues related to IPC

a) How one process can pass information to another?
b) Making sure two or more process do not get into each other’s way while critical selection.
c) Proper sequencing when dependencies are present.

---

Q) Why process need to be synchronized? [2]

- Sharing system resources by the processes such that cosurrent access to shared sata can be handled efficiently.
- Maintains data consistency.

---

Q) Why do you need pipe () function? [3]

- Pipe () function is created before farking one or more child processes.
- It OS used for communication between parent or child processes, or between two sibling processes.
- Pipe, is a undirectedly data channel used for IPC.

---

Critical Region

- Critical section is the part of the program in which it access the shared memory.

- The conditions to avoid race conditions are: -
a) No two processes may be simultaneously inside critical sections.
b) No assumptions may be made about speed and no. of CPUs.
c) No process running outside critical region may block other processes.
d) No process shoud have to wait forecer to enter critical region.

---

Race Condition

The situation in which two or more processes are reading or writing from a shared storage and the final result depends on the timing of the processes to run is called race condition.

For eg. Consider an example of print spooler when a process wants to print a file, it writes filename in a spooler directory. A process, printer daemon, periodically checks if there is file to be printed and if yes, it prints them and removes name form directory. Assume spooler directory with large no. of slats each capable of holding a filename and there are two shared variables (out  points next file to be printed, in  points next free slot).

Consider slots 1 to 6 are full and simultaneously proves A and B decide to queue file for printing.
- Process A reads in and stores ‘7’ as next free slot.
- A clock interrupt occurs and CPU decides to switch to process B.
- Process B reads in and also gets ‘7’, stores filename in slot 7 and updates in to be ‘8’
- Process A runs again and find ‘7’ as next free slot, writes filename in slot 7 erasing filename put by process B and computes next free slot as B.
- Printer daemon will continue printing.
- Process b will never get an output.

---

Mutual Exclusion

Mutual exclusion is the way of making sure that if one process is in its critical region, the other processes will be excluded from entering into their critical region.

---

3.5.1 Disabling Interrupts

- Each process disable all interrupts just after entering its critical region and re-enable them just before leaving it.
- No clock interrupts occur, resulting in no process switching.
- It is useful within OS but not for user processes.
- If user process did not re-enable the interrupts, the system collapsed.
- In multiprocessor system, even one processor interrupt is disabled, the other processors can access the shared memory.

---

3.5.2 Lock Variables

- Lock is a single, shared variable which is initially 0.
- When a process wants to enter its critical region, it tests the cock variable.
- If lock is 0, the process sets it to 1 and enters critical region.
- If lock is 1, the process waits until it becomes 0.
- Flow: one process reads lock begins which also finds lock to be 0 and set it to 1. This results in two process in critical regions simultaneously.

---

3.5.3 Strict Alteration

-The integer variable ‘turn’ which is initially 0 keeps track of ehich process will enter the critical region.
-Initially process 0 inspects turn, finds it 0 and enters critical region. Also, process 1 finds turn to be 0 and continuously test turn in a loop until becames1.
-When process 0 leaves critical region, it sets turn to 1, allowing process to enter critical region.

i.e While (TRUE)
{
while (turn! = 0)
critical_region ();
turn = 2;
non_critical_region ();
}

While (TRUE)
{
while (turn! = 1)
critical_region ();
turn = 0;
non_critical_region ();
}

- It violates the condition that a process should not be blocked by another process not in critical region.
For eg:
Suppose process 1 finishes critical region setting turn to 0. Again, process continues critical region and finishes setting turn to 1. Now, process) can not enter critical region even if process 1 is in non-critical region.

---

3.5.4 Peterson’s Solution

#define FALAE 0
#define TRUE 1
#define N 2 /*no of processes */

Int turn;
Int interested [N]; /* all values initially 0*/

Void enter_region (int process)
{
int other; /*no. of other process*/
other = 1- processes;
interested [process] = TRUE;
turn = process;
while ( turn = = process && interested [other] = = TRUE)
}

Void leave region (int process)
{
Interested [process] = FALSE;
}

---

3.5.5 TSL (Test and Set Lock) Instruction

tsl register, lock // copy lock to register and set lock to
cmp register, # 0
jne enter_region
ret
leave_region:
move lock, #0
ret

---

3.5.6 Sleep and Wakeup

- SLEEP is a system call that causes the caller to block until another process wakes it up.
- WAKEUP is a call that awake the process in sleep.
- It saves the CPU time.

---

Semaphore and Mutex

- Semaphore is variable used to count the number of wakeups saved for future use.
- A value of 0 indicates no wakeups were saved and positive value indicates one or more wakeups are pending.
- It has two operations: DOWN and up
- DOWN operation checks if the value is greater than 0 and if so, it decrements the value and continues. If value is 0, the process is put to sleep.
- UP operation increments the value of semaphore. If one or more process were sleeping is allowed to complete previous DOWN operation.
- The mutex is a semaphore used for mutual exclusion.

---

Q) can semaphores be used in distributed system? [3]

- Distributed system have multiple CPU’s, each with private memory connected by LAN.
- Semaphores are designed to solve mutual exclusion on one or more CPU’s that have access to common memory.
- It is too low level information exchange between machines is not possible.

---

Message Passing

- It is a method of IPC that uses system calls SEND and RECEIVE.
- Messages can be lost by the network. So, acknowledgement system should be used.

---

Monitors

- A monitor is a collection of procedures, variables and data structures that are all grouped together in a special kind of module or package.
- Processes may call procedures in a monitor but they can not directly access monitor’s internal data structures from procedures declared outside the monitor.
- Only one process can be active in a monitor at any instant.
- Condition variable used for blocking with operations WAIT and SIGNAL.

---

Producer Consumer Problem

Two processes share a common fixed size buffer. The producer process puts information into the buffer and the consumer process sakes out the information. Problem arises when producer wants to put new item in full buffer or consumer wants to get item form empty buffer.

---

Using semaphores

#define N 100 /* no. of slots in buffer */
Typedef int semaphore; /* semaphore as special int */
Semaphore mutex = 1; /* control access to critical region */
Semaphore empty = N; /* no. of empty slots */
Semaphore full = 0; /* no. of full sots */

Void producer (void)
{
Int item;
While (TRUE){
producer_item(& item); /* generate item to put in buffer */
down (& empty); /* decrement empty count */
down (& mutex); /* enter critical region */
enter_item (item); /* put item in buffer */
up (& mutex) ; /* leave critical region */
up (& full); /* increment count of full slots */
}
}

void consumer (void)
{
Int item;
While (TRUE) {
down (& full);
down (& mutex);
remove_item (2 item);
up (& mutex);
up (& empty);
consume_item (item);
}
}

---

Using monitors

Monitor Producer Consumer
condition full, empty;
integer count;

procedure enter;
begin
it counts = N then wait (full);
enter_item;
count: = count +1;
if count = 1 then signal (empty);
end;

procedure remove;
begin
if count = 0 then wait (empty);
remove_item;
count: = count - 1;
if count = N - 1 then signal (full)
end;
end monitor;

procedure producer;
begin
while true do
begin
produce_item;
producer Consumer enter;
end;
end;

procedure consumer;
begin
while true do
begin
ProducerConsumer. remove;
Consume_item;
end;
end;

---

Using message passing

#define N 100

void producer (void)
{ int item;
Message m;
While (TRUE) {
produce_item (& item);
receive (consumer, & m); /*wait for empty to arrive */
build_message (&m, item); /* construct message to send*/
send (consumer, &m); /* send item to consumer */
}
}

void consumer (void)
{ int item, ; ;
Message m;
for ( i = 0; i < N; i++)
send (producer, &m) ; /* send N emptile*/
while (TRUE){
receive (producer, &m);
extract_item (&m, & item);
send (producer &m);
consume_item (item);
}

---

Dining Philosopher Problem

Problem Statement

Five philosophers are seated around a circular table. Each one has a plates spaghetti. The spaghetti is so slipper that a philosopher needs two forks to eat it. Between each pair of plates is one fork. The life of philosopher consists of alternate periods of eationf and thinking. When philosopher gets hungry, she tries to acquire her left and right fork, one at a time, in either order. If successful to get two forks, she eats for a while, then puts down the forks ans continue to think.

The problem is deadlock and starvation.

---

Solution using semaphores

#define N 5 /*no. of philosophers*/
#define LEFT ( i-1)%N /* no of i’s left neighbor*/
#define RIGHT (i=1) %N
#define THIKING 0
#define HUNGRY 1
#define EATING 2
Typedef int semaphore;
int state [N]; /* array to keep track of everyone’s state*/
semaphore mutex = 1;
semaphore s[N]; /* one semaphore per philosopher*/

void philosopher (int i)
{
While (TRUE){
Think ();
take_forks (i);
eat ();
put_forks (i);
}
}

void take_forks (int i)
{
down (& mutex);
state [i] = HUNGRY;
test (i) ;
up (& mutex);
down (& s [i]);
}

void put_fork (int i)
{ down (& mutex);
state [i] = THINKING;
test (LEFT)
test (RIGHT);
up (& mutex);
}

Void test (int i)
{
If (state [i] = = HUNGRY && state [LEFT] ! = EATING && state [RIGHT] ! = EATING);
{ state [i] =EATING;
Up (& s [i]);
}

 

   -by SURAJ AWAL