1- Which of the following scheduling algorithms could result in starvation? Why?
ID: 3635992 • Letter: 1
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?
Explanation / Answer
1.
The following algorithms results to starvation:
Shortest Job First.
Priority
Explanation:
For Shortest Job First
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 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.
4.
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.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.