1
$\begingroup$

When a computer OS supports multi-program, it needs to have a scheduling algorithm to handle which process will be run by the cpu.

If a process is in state 'blocked' waiting for IO, the scheduling causes another process to be taken by the cpu while the process in state 'blocked' is waiting for a response I/O. In this situation, when the process returns to state 'ready' and then runs, how does the cpu know which process to run and where it was stopped ?

$\endgroup$
  • $\begingroup$ What research have you done? Have you read about scheduling in undergraduate textbooks on operating systems? What didn't you understand about the way it was presented there? This topic is well explained in those standard resources -- there's not a lot of point in having us re-type that in. If you didn't understand it when you read it there, you probably won't understand it when we re-type in the same standard explanation. $\endgroup$ – D.W. Oct 23 '14 at 22:45
2
$\begingroup$

The scheduling algorithm is largely irrelevant. What is relevant is how the Operating System kernel saves information about requests it has made for which it is awaiting replies.

When we say that a process is in state "blocked" we don't really mean that there is a variable somewhere called state to which we have assigned the value running or blocked or waiting. Rather we have a bunch of different lists or queues in the system and we move the process from one queue to another queue to change the state. (Or more technically, we move a pointer to the data structure that represents the information about the process.) The information we record about a process includes all the information we need to resume running the process (the program counter to the last instruction it executed, plus the values of all its registers, plus pointers to its page table.)

There is one queue for all the processes that are ready-to-run. When the scheduler (whatever kind of scheduler it is) decides that it is time for a different program to run it moves the pointer to the currently running process on to the ready-to-run queue and then pulls some other process off the ready-to-run queue, and resumes that process (restore all its registers and then jump to the next instruction in the process.)

If a process makes an i/o request then it gets placed in a queue specific to that i/o device. (So there will be one queue for the keyboard, another for the mouse, another for the disk-drive and yet another for the wireless network.) When the process make the i/o request it gets moved to the correct queue for the kind of i/o it requested, the the operating system selects a different process from the ready-to-run queue.

When an i/o device sends the response to a request (for example, you press a key on the keyboard, which causes an interrupt, which causes the processor to jump to the keyboard interrupt handling routine) the resulting data will be put in an appropriate buffer and then the process that was blocked waiting for that data will be moved off of the keyboard queue and back on to the ready-to-run queue. The os will then return from the interrupt (to the process that was running at the time the interrupt occurred) and then some time later it will decide to schedule in another process (which might or might not be the process that just got the data from the keyboard.)

$\endgroup$
  • 1
    $\begingroup$ Very nice answer, but I think the scheduling matters. Would you care to elaborate on how the OS handles the case where multiple processes waiting for the same kind of IRQ. I think the case of multiple processes waiting for a keyboard action is not the same as the case of multiple processes waiting for a network byte via socket. I can surmise that they use buffer pointers for the data, but I am not certain. It will be nice to see an elaborated answer here. $\endgroup$ – InformedA Oct 24 '14 at 4:18
  • $\begingroup$ @InstructedA I think you are presuming that a process owns an interrupt when it is waiting on it, which is not true. At best, one could say the CPU itself owns the interrupt, and the kernel code is welcome to do as they see fit. On modern OSs, interrupts are always handled within the kernel at a level below the scheduler, and the interrupt handling code may elect to notify the scheduled programs in an interrupt specific manner. In old OSs, like DOS, there was no concept of multiple processes, so ISRs were simply handled by "the running program," treated as the only program. $\endgroup$ – Cort Ammon Oct 24 '15 at 18:03
  • $\begingroup$ I think there should be more to add to this answer particularly when there's networking involved. I mean, there's must be a way to associate a request/socket with it's owner process ID (or sth equivalent) since network requests are not necessarily to be responded/returned in same order you've sent them which means a simple FIFO queue that would work for "keyboard" device wouldn't work your networking device. $\endgroup$ – zgulser Nov 25 '18 at 12:19
2
$\begingroup$

First of all, different environments need different scheduling algorithms.

This is mainly because different operating systems have different objectives according the needs. Then, what the scheduler is going to optimize will not be the same for every case.

There are Real time systems, batch processing, interactive systems, etc. Let's consider interactive systems because these are the typical desktop computers and servers, offering services for various users. The main concerns for the scheduler is to "quickly" answer users querys.

In general, the scheduler tells the CPU wich process is next (the CPU is driven by the scheduler), and the details depends on the sheduler algorithm.

Consider the following simple and old scheduling algorithm, called Round-robin:

Each process is assigned with a pre-fixed quantum of time. There is a list of process. The CPU run process A, when the time is over (or A is blocked before time) it switch's to the next process B in the list. A is moved to the end of the list. The context of A is saved in the Process Control Block, so in the next turn for A the CPU knows where to continue because the IP register was saved in that context. In this case, is like all processes have the same priority. One key thing here is how much time is assigned to the quantum, it must be a reasonabe amount of time.

There are more complex algorithms, based in priority scheduling. In general, there are different classes of hierarchys, and each hierarchy may have his own queue of processes waiting to run. The CPU can start running process of the highest priority class, and when that class is empty it move downwards the hierarchy. The time of execution in this case can be a quantum, or the CPU can decrease priority of the current process in each clock interruption to avoid indefinite postponement of the other processes.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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