Question

1- Which of the following scheduling algorithms could result in starvation? Why? If any, show how can starvation problem be resolved.

a. First-come, first-served (FCFS)
b. Shortest job first (SJF)
c. Round robin (RR)
d. Priority?


2- Illustrate Peterson solution to critical section problem, showing how it satisfy the conditions of mutual exclusion, progress, and bounded waiting!

3- What is the meaning of the term busy waiting? What other kinds of waiting are there in an operating system? Can busy waiting be avoided altogether? Explain your answer.

4- Explain why interrupts are not appropriate for implementing synchronization primitives in multiprocessor systems.


5- Which of the following components of program state are shared across threads in a multithreaded process?
a. Register values
b. Heap memory
c. Global variables
d. Stack memory

6- Using pseudo C like code, illustrate two algorithms uses hardware synchronization.

7- Semaphores are used to overcome a drawback of hardware synchronization, what is this drawback, and how semaphores addresses this drawback?

Answer 1

1.

The following algorithms results to starvation:

Shortest Job First.

Priority

Explanation:

For Shortest Job First

• The occurrence of starvation in shortest job first is possible when the process of higher burst time will execute before the lower burst time process.
• The lower burst time process is there in the queue.
• Thus, in this case the higher burst time process feels the starvation.

The solution for the starvation is to avoid the scheduling of jobs when the job pool is full.

The pool must wait to be empty for the execution of further processes.

For Priority

• The processes with higher priority will execute first.
• Thus, the lower burst time process feels the starvation.

The solution of the starvation for priority is that the processes which are waiting for their execution from a long time, their priorities will be increased.

2.

The illustrated Peterson solution to the critical section problem is as follows:

Code for process a:

do {

flag[a] := TRUE;

turn := b;

while (flag [b] and turn = b) do no-op;

CS

flag [a] := FALSE;

RS }

while(1);

Code for process b:

do {

flag[b] := TRUE;

turn := a;

while (flag [a] and turn = i) do no-op;

CS

flag [b] := FALSE;

RS }

while(1);

where, CS = Critical section and `

RS = Remainder section

From the above illustrated Peterson solution, the following conditions are satisfied.

Mutual exclusion: From the above illustrated solution, at a time only one process will enter in the critical section.

Bounded waiting: After the execution of the process a it will set the flag as false.

Then only the process b will enter in the critical section.

Thus, the process is bounded.

Hence, the above illustration follows the property of bounded waiting.

Progress: If some another process wants to execute in its critical section, when no process is executing its critical section then the processes which are not in their remainder section will decide which process will enter in the critical section.

After the execution of the process in the critical section, they will set their flag as false.

After that some other process will execute.

Thus, the progress property is also satisfied.

3.

• The term busy waiting refers to the process waiting for the condition to be true.
• If a program is reached to an appropriate state, then there is a need of waking up the process which is slept before, to sustain the accompanying overhead.
• With this, the busy waiting can be avoided.

4.

• The processes will not execute in the processor where the interrupt is disable.
• But they can run on any different processor where the interrupt is not disabled,
• This is the limitation of interrupt.
• Thus, the interrupts are not appropriate.

5.

The components shared across are as follows:

Heap memory

Global memory

Explanation:

The heap memory belongs to the whole process and not to any single thread.

All threads of the process work on this memory, that’s why the memory is shared.

6.

The code for test-and-set with mutual exclusion is as follows:

boolean lock = false;

do {

while (TestAndSet(lock));

CS

lock = false;

RS

} while (TRUE);

The code for swap with mutual exclusion is as follows:

boolean lock;

do {

key = true;        

while (key == true)

Swap(lock,key);

CS

lock = false;

RS

} while (TRUE);

where, CS = Critical section and

RS = Remainder section

7.

With the help of semaphores, the critical section can be accessed by more than one thread.

Since, they are more flexible to manage the resources.

Thus, they are more useful to use.