A counting semaphore can have any arbitrary integral value. A process using such

Question

A counting semaphore can have any arbitrary integral value. A process using such semaphore does not block until a down() invoked by the process on the semaphore makes the value negative. A negative value of the counting semaphore indicates that many processes blocked on the semaphore. An up() on the semaphore will wakeup a blocked process if the value is still negative. Describe how such a counting semaphore can be implemented using only binary semaphores and ordinary machine instructions. You may also use simple integer variables and list data structure.

Explanation / Answer

Solution:

Associated with each counting semaphore are two binary semaphores, mutex_s ,used for mutual exclusion, and delay_s , used for blocking.

semaphore mutex_s = 1;
semaphore delay_s = 0;

Also associated with each counting semaphore is a counter that holds the number of ups minus the number of downs, and a list of processes blocked on that semaphore.

int s = N;   // counter is initialized with N

To implement down(), a process first gains exclusive access to the semaphores, counter, and list by doing a down on mutex_s . It then decrements the counter. If it is zero or more, it just does an up() on mutex_s and exits. If mutex_s is negative, the process is put on the list of blocked processes. Then an upis done on mutex_s and a down is done on delay_s to block the process. To implement up, first mutex_s is downed to get mutual exclusion, and then the counter is incremented. If it is more than zero, no one was blocked, so all that needs to be done is to up mutex_s. If, however, the counter is now negative or zero, some process must be removed from the list. Finally, an up is done on delay_s and mutex_s in that order.

Implementation of down:

process the mutex_s first down to get exclusive access counter, linked list, and the counter i.e. (s) minus 1. If counter is greater than or equal to 0, the up can be directly on the M; Otherwise, up records in the list, and then on the B down to block this process as:

p(s) = down //implementation of down
down(mutex_s);
s--;

if (s<0)
up(mutex_s)
down(delay_s)
up(mutex_s)

Implementation of up:

process in mutex_s first down, plus 1 count to counter, if it is greater than 0, the up can be directly on the mutex_s; otherwise, counter is less than or equal to 0, a process list is removed, and then the delay_s, mutex_s and up is performed as:

V(s) = up //implementation of up
down(mutex_s)
s++
if (s<=0)
up(delay_s)
up(mutex_s)

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.