(e) Consider two processes time-sharing a CPU. Assume that each of these process
ID: 3590658 • Letter: #
Question
(e) Consider two processes time-sharing a CPU. Assume that each of these processes executes exactly n instructions during a CPU quantum. Assume that the processes consist of 10n instructions each and that they both become ready to run at the same time. None of the instructions results in a trap. Furthermore, none of the instructions causes a jump (i.e., the instructions are simply executed one after the other). Ignore instructions executed by the OS and the arrival of any interrupts other than How (i) How many unique interleavings are possible if the CPU scheduler were Round Robin many if it were Lottery and the processes were to have equal CPU weights?Explanation / Answer
Solution :-
Given that two processes has 10n instructions and each process executes n instructions in a cpu quantum. Both processes arrive same time.
(1) If the scheduler uses round robin scheduling scheme then each process has a time quantum of cpu burst in which process can execute n instructions. Each process has 10n instructions, so both processes requires 10 time quantum of cpu bursts.
There are 19 context switches to execute the both processes completely. Let first process is P1 and other is P2. So P1 has first quantum and executes the n instructions in first CPU burst. Then P1 is preempted and P2 has it's turn. Process P2 executes n instructions in the time quantum. When P1 leaves cpu and cpu is allocated to P2 then it is called context switch.
There are 10 time quantum required for P1 and 10 for orocess P2, total 20 time quantum for both processes to execute completely. There is a context switch between time quantums. So for 20 quantums there are 19 context switches or we can say there is 19 possible interleavings.
Therefore, there is 19 possible interleavings.
(2) If cpu scheduler uses a lottery system to allocate the CPU to the processes, then the order in which processes execute depends completely on the result of the lottery. If P1 wins the lottery then cpu is allocated to P1. There is no time quantum so P1 releases the cpu after complete execution of 10n instructions. Then context switch occurs and P1 releases the cpu and allocated to P2. Then P2 executes the 10n instructions in a single burst. So there is only one context switch. The same thing happens when P2 wins the lottery and gets the cpu first allocated.
Therefore, there is only 2 possible interleavings if the cpu scheduler uses the lottery to execute the processes.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.