I am a computer science student and I have an exam tomorrow on operating systems. I have the exam questions of past years and there is one scenario in a question. There are two tasks in the ready-to-run (I don’t what’s its name) queue. And the scheduling algorithm is Shortest Time to Completion First (STCF). And two semaphores, S1 and S2. Lets call the task one T1 and task two T2. Here is the scenario:
T1
{
down(S1);
// other codes
up(S1);
}
T2
{
down(S1);
down(S2);
//Other code...
up(S2);
up(S1);
}
T1 task comes to ready-to-run queue at time of 0th second and it takes 10 seconds to be completed. T2 comes to read-to-run queue at time of 3rd second and it takes 3 seconds to be completed.
Here is where I stuck. The T1 executes for 3 seconds, after that it will get preempted, since T2 comes and its time to completion is lesser. T2 will waits for the S1 semaphore to be upped to proceed further. What will processor do in this situation? Will it switch to T1 or it keeps try to process T2 since its completion time is lesser, and as a result deadlock?
Assuming you are using a half-decent scheduler, then if a task tries to claim a semaphore that is not available, then that task gets put into a “blocked” or “waiting” state and will not be considered “ready to run” until the semaphore it is waiting for becomes available. Then the scheduler checks again the “ready to run” queue and selects a task from those in the queue to execute.
So, in your example, when T2 hits semaphore S1 it becomes blocked. At that point only T1 is “ready to run”, so that task will be scheduled as it has the lowest time to completion among the tasks that could make progress when executed.
When T1 releases semaphore S1 (ups it), the scheduler will put T2 back in the “ready to run” queue and decides again which task to execute.