Semaphores and CPU Scheduling

The assignment is about implementing a semaphore abstract class and solving problems related to buffer management using semaphores, as well as CPU scheduling using the EDF (Earliest Deadline First) and RMS (Rate Monotonic Scheduling) algorithms.

1. Please complete the following pseudocode to implement the semaphore abstract.
public class Semaphore {
// A private variable to set the buffer
Private int value;
void init(int val)
{
//initialize value if val>0
}
public void Wait()
{
repeat
wait();
until value is 0
decrement the value
}
void signal()
{
If value is 0
Notify();
End if
Increment value;
}
}
2. Write the Pseudocode for the following problems: ssignalpose there are three threads A,
B and C. A keeps producing an item into a buffer B1 of size M, B keeps taking an item
from B1, and put into another buffer B2 of size N. C keeps consuming an item from
buffer B2. Please write the pseudocode for Thread A,B,C
a. Using the semaphores class defined above to synchronize them.
b. Using the Monitor abstract to synchronize them.
A) Initialize Buffer b1 with buffer size M.
semaphore mutex = 1; // Controls access to critical section
semaphore empty = M; // counts number of empty buffer slots
semaphore full = 0; // counts number of full buffer
slots
semaphore mutex1 = 1;
semaphore empty1 = N;
semaphore full1 = 0;

Thread A:
while (TRUE) { // loop forever
make_new(object); // create a new widget to put in buffer
wait(&empty); // decrement the empty semaphore
wait(&mutex); // enter critical section
put_item(object); // put widget in buffer
signal(&mutex); // leave critical section
signal(&full); // increment the full semaphore
}
Thread B:
while (TRUE) { // loop forever
wait(&full); // decrement the full semaphore
wait(&mutex); // enter critical section
remove_item(object);
signal(&mutex); // leave critical section
signal(&empty); // increment the empty semaphore
wait(&empty1); // decrement the empty semaphore
wait(&mutex1); // enter critical section
put_item(object); // put widget in buffer
signal(&mutex1); // leave critical section
signal(&full1); // increment the full semaphore
}
while (TRUE) { // loop forever
make_new(object); // create a new widget to put in buffer
}
Thread C:
while (TRUE) { // loop forever
wait(&full1); // decrement the full semaphore
wait(&mutex1); // enter critical section
remove_item(object); // take a widget from the buffer
signal(&mutex1); // leave critical section
signal(&empty1); // increment the empty semaphore
consume_item(widget); // consume the item
}
B)
monitor ThreeThreads
condition full, empty,full1,empty1;
int count,count1;
ThreadA enter();
{
if (count == M) wait(full); // if buffer is full, block
put_item(widget); // put item in buffer
count = count + 1; // increment count of full slots
if (count == 1) signal(empty); // if buffer was empty, wake Thread B
}

ThreadB remove();
{
if (count == 0) wait(empty); // if buffer is empty, block
remove_item(widget); // remove item from buffer
if (count1 == N) wait(full1); // if buffer is full, block
put_item(widget); // put item in buffer
count1 = count1 + 1; // increment count of full slots
if (count == 1) signal(empty); // if buffer was empty, wake Thread B
count = count - 1; // decrement count of full slots
if (count == M-1) signal(full); // if buffer was full, wake Thread A
}
ThreadC remove();
{
if (count1 == 0) wait(empty); // if buffer is empty, block
remove_item(widget); // remove item from buffer
count1 = count1 - 1; // decrement count of full slots
if (count1 == N-1) signal(full); // if buffer was full, wake producer
}
count = 0;
count1=0;
end monitor;
3. CPU scheduling (You shall use the simulator provided on blackboard with CPU
scheduling lecture notes) (40%)
Process Arrive
time
Execution time (C) Period (T)
P0 0 2 8
P1 0 1 6
P2 0 1 3
a. Consider the above periodic process set. What is the total utilization of the given
process set? What is the hyperperiod? Please draw the Gantt Charts to illustrate
the schedule in hyperperiod using EDF and RMS respectively.

Utilization of the given set :-
Utilization of P0(U0)= C0/T0 = 2/8= 0.25
Utilization of P1(U1)= C1/T1 = 1/6= 0.167
Utilization of P2(U2)= C2/T2 = 1/3= 0.33
Total utilization of given set U= U0+U1+U2
=0.25+0.167+0.33
=0.75
Hyperperiod:-
Hyperperiod(LCM)=(8,6,3)
=24
EDF(Earlist deadline first):-
Utilization(U)= (2/8)+(1/6)+(1/3)
=(6+4+8)/24
=0.75
We know that :- U=Ci/Ti (i=1 to n)<=1
0.75<=1(true)
The utilization is very high. However, no deadline miss in the hyperperiod.
Gantt Chart(EDF)

RMS(rate monotonic scheduling):-
 this scheduling to schedule periodic tasks.
 A higher priority process will preempt a lower priority. (P2>P1>P0)
 Check whether it is possible to schedule the proesses, so that all of them meet their deadline.
 U=Ci/Ti (i=1 to n)<= N(21/N-1) (N= number of processes)
So that:-
0.75<=3(21/3-1)
0.75<=3(1.26-1)
0.75<=3(0.26)
0.75<=0.78(true)
Gantt Chart(RMS)