Scheduling Overheads

Question

Consider three processes that require 10, 20, 30 units and arrive at time 0, 2, 4. The number of scheduling overheads needed using S.R.T.F. scheduling is 

I think answer is 1 at time t = 10

Comments

at t=10 P1 completed and P2 started to execute , and at t=30 , p2 completed and P3 started to execute , so if we ignore the switch when P1 acquired the cpu and when P3 leave the cpu then it's 2 time when  switching happened...

---

at t=30 there won't be scheduler involved as only left process is P3. Dispatcher just performs the context switch.

---

Shivam you raised an interesting point.

you mean to say that as we have asked "scheduling overhead" so you're saying 1 because at t=30 no scheduling needed because only one process left...so short term scheduler will have to make no choice and just involvement of dispatcher for context switch and mode switch...

But i have some points.

1) How do your system know that it's last process to execute so better i don't waste my time in making scheduling decision.? of course our question is just an example to teach SRTF . practically scheduling only ends when you give shutdown command..

2) even if you somehow do something and your scheduler always now can know when the last process will come then , isn't this is an overhead to check that it's our last process so no need to schedule..?

i never heard the term 'scheduling overhead' but i think it would mean  time when your cpu is idle..so context switch will be included in that way...

---

Then this also applies at time t=0 how our system knows that only one process has arrived

---

i already said we're ignoring the game before P1 and after P3.

at t=0 Short term scheduler decides that P1 is the bet process according to SRTF and then dispatcher allocate cpu to it. in that kind of questions we consider that before this there was no process (idle cpu) so no switching overhead...

---

@Rupendra Choudhary

@Shivam Chauhan

Can you give the definition of Scheduling overhead according to you.

---

time that is consumed by scheduler to make scheduling decision is supposed to be overhead as CPU is idle during this time.but scheduling is not just to decide 'whose turn this time' but also to allocate cpu...so the time in b/w when p1 relinquished cpu and time when p2 acquired cpu is an overhead that i would say is scheduling overhead...i never heard this term before so i might wrong...

---

I think Scheduling overhead is the overhead on Short Term Scheduler, because Short Term scheduler have to make decision that which process should be schedule, ONLY THIS MUCH.

Now, the scheduled process allocated to CPU by dispatcher.

Coming to the question, IT is using SRTF algorithm, So after 1 time unit, STS have to make decision, that whether the process scheduled onto the CPU have less burst time or the processes in the ready queue.

So, this should be more than a single digit no.

---

According to me, Scheduling overhead means the number of times scheduling algorithm runs to determine which process to run. It is an overhead in multiprogramming OS because we have processes to run but then also we need to determine which process to run.

S.R.T.F. is Preemptive algorithm

at t=0  Only one process so OS finds no need to run scheduling algorithm

at t=2 P2 arrives so OS checks if remaining burst time of P1 > Burst time of P2 

No, so need to run scheduling algo

at t=4 P3 arrives so  OS checks if remaining burst time of P1 > Burst time of P3 

No, so need to run scheduling algo

at t=10 we need to run scheduling algorithm between P2 and P3 to determine which process to run 

at t=30 Only one process so OS finds no need to run scheduling algorithm

Therefore only one scheduling overhead.

---

in that way answer would be 4 , as t=2 there is P1 and now P2 arrived so decide who has shortest remaining burst , at t=4 again there is new process P3 so here again short term scheduler have to decide the best choice and at t=10 decide b/w P2 and P3 ,and then t=30 decide again ...so overall 4 times scheduler have to make decision..

---

Consider three process A, B, C:-

SRTF table:-

Time	Ready Queue	Running
0	-	A
1	-	A
2	A, B	A
3	A, B	A
4	A, B, C	A
....	....	....
9	A, B, C	A
10	B,C	B
11	B,C	B
....	......	.......
29	B,C	B
30	-	C
59	-	C

Scheduling overhead = 29 - 2 + 1 = 28.

This is the schedule table for SRTF not SJF.

In SJF, Short term Scheduler have make decision at once when T = 10 {process A has completed at t =9 that's why at t = 10 STS has to make decision} processes in the ready queue = B, C. As a result B gets the CPU

 And, after that no need of scheduling as after t = 10 there is only 1 process in the ready queue.

@Shivam Chauhan

I think answer is 1 at time t = 10

I think it is true for SJF not for SRTF.

let me know what is wrong here. 

---

@Shubhanshu in this case SRTF is behaving as SJF as there is no  preemption involved anywhere

---

Even though SRTF is reduced to SJF, But since here the scheduling algorithm is SRTF, so every time STS has to decide whether running process is having minimum burst or the processes having in the ready queue.

---

hello shubhanshu and shivam.

but in that strategy i have one doubt.

how will OS know that there is new process that also want to execute, it can only happen when OS checks ready queue , after every single time unit(1 time unit)and see if there is new process in ready queue or not..as you are saying at t=0 , no scheduling work , that can only happen when OS know that no process in ready queue , and then how does at t=2 OS knows that this time i have to execute some scheduling decision making algo to know which is best to execute...

---

@Shubhanshu 

Suppose we have processes P1, P2, P3 currently in ready queue (at t=0) and we run scheduling algorithm to determine process with minimum next CPU burst (say, P1 is selected). Now suppose at t=t₁ a new process P4 arrives. WE NEED  MAXIMUM CPU UTILIZATION. COMMON SENSE APPLIES

If we apply scheduling algorithm on all four processes and determine next process and get among P1 or P4 to run.  Overhead

OR

Since We already know if P1 is running now then it must have minimum CPU burst among P1, P2, P3

so just check left CPU burst with P4 burst time and determine the next process.

Answer 1

Scheduling overhead means The time taken by dispatcher to move the process from ready state to running state.

So here it will be 3.