In the context of process scheduling, does the operating system intervene after each time slice/quantum ends? For example if the computer was idle and 4 tasks arrived : t1, t2, t3 and t4, and they got scheduled using first-come-first-serve, we would normally consider t1, t2, t3, t4 to be in the CPU but isn't this a simplification? Because it we t1, OS, t2, OS, t3 OS t4 is what would actually happen? If it's true the OS intervenes after each time slice (aka quantum) isn't this very inefficient?

up vote 1 down vote accepted

Not necessarily. Typically the scheduler will lower the dynamic priority of a task after its quantum expires, but if it is still the highest priority task, then it gets another. In general though, yes, when the task has run long enough, the OS takes over and switches to another. Why should that be inefficient?

  • Because (correct me I'm wrong) most tasks take several turns in the CPU so that's x times times the OS needs to do some calculation for each task, which there's lots of. For example there's 5 tasks and on average each takes 4 time slices to complete, so that's about 4x5 times the OS intervenes. I may be wrong, I guess this is just how I imagined it. – Celeritas Dec 5 '13 at 4:35
  • 1
    @Celeritas, only one task can be running on a given cpu and the time it takes to adjust the priority of the task and check to see if there's a higher priority one is very small ( like 10,000 or 100,000+ times less ) compared to the length of the quantum. – psusi Dec 5 '13 at 19:38
  • right so if the quantum is ridiculously short then things may start to be less efficient from all the swapping in and out of tasks and checking their priorities? – Celeritas Dec 6 '13 at 1:09
  • @Celeritas, there isn't any swapping and quanta aren't ridiculously short ;) – psusi Dec 6 '13 at 2:36

I believe that in modern operating systems the time-slices are variable length. The scheduler is invoked after servicing every interrupt (keyboard, mouse, touchscreen, network, disk-transfer finished, ...) as well as the timer interrupts.

Roughly speaking, the scheduler is designed to estimate the moving average of the times between a process's blocking system calls. Before the scheduler gives control to process X it sets up a timer that will interrupt at a time just slightly longer than process X's moving average. If the scheduler is doing a good job of guessing the time to the next blocking system call, then a large fraction of processes will actually voluntarily release the CPU by doing a blocking system call.

The goal is to get interactive processes to do a little bit of computation, make a blocking system call to request some data from a slow device, and then get rescheduled as soon as the data is returned. If the scheduler has to decide between scheduling between two processes, then all other things being equal, it will favor the process that is making blocking system calls more frequently. This tends to maximize the number of simultaneous blocking i/o requests, which improves overall system throughput.

  • what is a blocking call? – Celeritas Dec 6 '13 at 1:10
  • The scheduler isn't invoked after servicing every interrupt; that would have too much overhead. There also isn't any guessing about time between blocking calls; the scheduler just does a quick check to see if the quantum has expired on each timer interrupt. – psusi Dec 6 '13 at 2:39
  • @Celeritas, blocking means the task goes to sleep while it waits for something, like disk IO, allowing other tasks to be run instead. – psusi Dec 6 '13 at 2:40
  • @psusi so what's the difference between sleeping and blocking? Or is there no such word as sleeping and people say "blocking"? – Celeritas Dec 6 '13 at 4:50
  • @Celeritas, sleeping is the state the task is in and blocking is what a system call does when it puts the task to sleep. – psusi Dec 6 '13 at 14:35

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.