What is Semaphore in OS - dining philosophers problem

By:   Last Updated: in: ,

Operating System: Q1.What is Semaphore in OS? Q2.Explain classic problems of Synchronization? Or How can Semaphore be used to enforce mutual exclusion? Dining philosophers problem? (Operating System all notes) [ Topic= What is Semaphore in OS ]

What-is-Semaphore-in-OS

Q1. What is Semaphore in OS?

Ans. A semaphore is a variable. There are two types of semaphores:
(a) Binary semaphores.
(b) Counting semaphores.

Binary semaphore has two methods associated with it (up, down/lock, unlock). Binary semaphorès can take only 2 values (0/1). They are used to acquire locks. When a resource is available, the process in charge set the semaphore to 1 else 0.
Counting semaphore may have value to be greater than one, typically used to allocate resources from a pool of identical resources.
[ Topic= What is Semaphore in OS ]
[ Topic= What is Semaphore in OS ]
[ Topic= What is Semaphore in OS ]

Q2. Explain classic problems of Synchronization? Or How can a Semaphore be used to enforce mutual exclusion? Dining philosophers problem?

Ans. Semaphore in OS is used to solve the critical section problem. A semaphore (s) is an integer value. Semaphore is a variable that has an integer value upon which the following three operations are defined :
1. A semaphore may be initialized to a non-negative value.
2. The wait operation decrements the semaphore value. If the value becomes negative, then the process of executing the wait is blocked.
3. The signal operation increments the semaphore value. If the value is not positive, then a process blocked by a wait operation is unblocked.

Pseudo Code for Wait
Wait (s)
{
While (S ≤ 0)
S = S - 1
}
Pseudo Code for Signal
Signal (s)
{
S = S + 1
}

Semaphores are executed atomically. There is no guarantee that no two processes can execute wait and signal operations on the same semaphore at the same time. This situation is a critical section problem and can be solved in either of two ways.

A binary semaphore is a semaphore with an integer value that can range only between 0 and 1. In principle, it should be easier to implement the binary semaphore. In this, the queue is used to hold processes waiting on the semaphore. The process that has been blocked the longest is released from the queue.

Semaphores are not provided by hardware. But they have several attractive properties:
1. Semaphores are machine-independent.
2. Semaphores are simple to implement.
3. Correctness is easy to determine.
4. Can have many different critical sections with different semaphores.
5. Semaphore acquire many resources simultaneously.

To implement semaphores under this definition, the semaphore is defined as a type of the struct
{
int value;
struct process * list;
} semaphore;
The wait () operation can now be defined as:
wait (semaphore * s)
{
s → value --;
if (s → value < 0) {
add this process to s → list;
block [];
}
• The signal () semaphore operation can now be defined as
signal (semaphore *s) {
S → value + +;
if (s → value < = 0) {
remove a process P from s → list;
wakeup (P);
}
}
[ Topic= What is Semaphore in OS ]

1. The Bounded-Buffer Problem: (What is Semaphore in OS)

This is a generalization of the producer-consumer problem wherein access is controlled to a shared group of buffers of a limited size.

In this solution, the two counting semaphores "full" and "empty" keep track of the current number of full and empty buffers respectively (and initialized to 0 and N respectively.) The binary semaphore mutex controls access to the critical section. The producer and consumer processes are nearly identical. One can think of the producer as producing full buffers and the consumer producing empty buffers.
Do {
.......
//produce an item in nextp
Wait (empty);
Wait (mutex);
.......
//add nextp to buffer
.......
Signal (mutex);
Signal(full);
} while (TRUE);
The structure of the producer process
Do {
Wait (full);
Wait (mutex);
.......
//Remove an item from buffer to nextc
.......
Signal (mutex);
Signal (empty);
.......
//consume the item in nextc
.......
} while (TRUE);
The structure of the consumer process
[ Topic= What is Semaphore in OS ]

2.The Readers-Writers Problem: (What is Semaphore in OS)

In the readers-writers problem, there are some processes (termed readers) who only read the shared data, and never change it, and there are other processes (termed writers) who may change the data in addition to or instead of reading it.

There is no limit to how many readers can access the data simultaneously, but when a writer accesses the data, it needs exclusive access. There are several variations to the readers-writers problem, most centered around relative priorities of readers versus writers.

(i) The First Readers :

Writers problem gives priority to readers. In this problem, if a reader wants access to the data and there is not already a writer accessing it, then access is granted to the reader. A solution to this problem can lead to starvation of the writers, as there could always be more readers coming along to access the data.

(A steady stream of readers will jump ahead of waiting writers as long as there is currently already another reader accessing the data because the writer is forced to wait until the data is idle, which may never happen if there are enough readers.)

(ii) The Second Readers:

Writers problem gives priority to the writers. In this problem, when a writer wants access to the data it jumps to the head of the queue. All waiting readers are blocked, and the writer gets access to the data as soon as it becomes available. In this solution, the readers may be starved by a steady stream of writers.
[ Topic= What is Semaphore in OS ]

3. The Dining Philosophers Problem:

The dining philosophers problem is a classic synchronization problem involving the allocation of limited resources amongst a group of processes in a deadlock-free and starvation-free manner:

(a) Consider five philosophers sitting around a table, in which there are five chopsticks evenly distributed and an endless bowl of rice in the center, as shown in the diagram. (There is exactly one chopstick between each pair of dining philosophers.)
(b) These philosophers spend their lives alternating between two activities: eating and thinking.
(c) When it is time for a philosopher to eat, it must first acquire two chopsticks - one from their left and one from their right.
(d) When a philosopher thinks, it puts down both chopsticks in their original locations.
Dining-Philosophers-Diagram




[ Topic= What is Semaphore in OS ]
[ Topic= What is Semaphore in OS ]
[ Topic= What is Semaphore in OS ]



Join us on Facebook, Instagram, and Twitter to get the latest study material. You can also ask us any questions.
Facebook = @allbcaweb
(click on it or search "allbcaweb" on Facebook)
Instagram = @allbcaweb
(click on it or search "allbcaweb" on Instagram)
Twitter = @allbcaweb
(click on it or search "allbcaweb" on Twitter)
Email= allbca.com@gmail.com
Send us your query anytime about Semaphore in OS!

[ Topic= What is Semaphore in OS ]

External Links:-

1. What is Semaphore in OS - (click here)
2. What is Semaphore in OS - (click here)

[ Topic= What is Semaphore in OS ]
[ Topic= What is Semaphore in OS ]

No comments:
Write comment