Message Primitives and Process States - Case 2

Message Primitives and Process States - Case 1

Process scheduling in Minix

The diagram above shows the state transitions for any process in Minix. A running process can become blocked when it makes a system call (which translates into the INT assembly instruction, also known as a software interrupt). Once blocked, it has to become ready before it can be run again. The scheduling algorithm only picks ready processes for execution.

The kernel maintains 16 queues of runnable processes. These queues are numbered 0 (highest priority queue) to 15 (lowest priority queue). Different processes have different priorities and the priority of a process may change during its execution. The changed priority is reflected in the fact that the process is moved to a different scheduling queue.

The clock and system tasks in Layer 1 of Minix have the highest priority. The device drivers in Layer 2 get lower priority but they are all not equal. Server processes (process manager, file system etc.) get lower priority than device drivers. User processes get lower priority than the server processes. Refer to this post for more on these layers.

Scheduling is round robin in each queue. If a running process uses up its quantum, it is moved to the tail of its queue and given a new quantum (Transition 4 in the diagram above). When a blocked process is awakened it is put at the head of its queue if it had any part of its quantum left when it blocked (Transition 2 in the diagram above). But it does not get a new quantum. It gets only as much quantum as it was left with when it blocked.

Whenever a running process becomes blocked or a runnable or running process is killed by a signal, it is removed from the scheduling queues. What this means is that the scheduling queues contain only ready or runnable processes.

Given this structure, the rule is very simple: Find the highest priority queue that is not empty and pick and continue running the process that is at the head of that queue.

So here is the chain of events at a high level: Process A is running -> Hardware and software interrupts occur -> interrupt handling code runs -> messages or notifications are sent or received -> the message processing results in process state transitions which causes changes to the scheduling queues in the kernel -> so Process B gets selected for execution.

We have discussed in detail how context switching happens and how the scheduling logic works. It is clear that the state transitions in the above diagram really drive the context switching. But what really causes these state transitions? The answer lies in the messaging layer of Minix. That is the final missing piece of the puzzle and I will discuss it with another diagram in an upcoming post.

Comments welcome.

Minix Context Switching Detail

Download and view this PDF file.

I have shown both hardware and software interrupt workflows here. Since the diagram is large and complex, it may have some errors due to oversight. Comments/corrections welcome.

Context Switching

I think I now understand exactly how context switching happens in Minix. I am working on a detailed diagram which I will upload once I am done.

Minix Interrupt Handling

Context Switching - The illusion of multiple processes executing simultaneously

In a single processor system, at any instant, only one process is executing - be it a system process (part of the OS) or a user process. The illusion of multiple processes running simultaneously is achieved by constantly switching from process to process. Now, when does a context switch happen in minix? What causes the CPU to suspend execution of one process and resume another? There are three ways in which this can happen:

1. Hardware interrupt (one of the devices in the computer sends a signal to the interrupt controller which in turn sends an interrupt signal to the INT pin of the CPU)

2. Software interrupt (i. e. system call made by the executing process)

3. The 'quantum' of time assigned to the executing process has been used up, so this process is pre-emptively suspended and another one is picked for execution. (This is really a special case of hardware interrupt where the interrupting device is the clock.)

In upcoming posts, I will first explain interrupt processing and context switching and then give more details on scheduling of processes.