PilotOS: Processes 2 (Process states and mutual exclusion)

The last article about processes had a concrete implementation in mind, with this article there is no implementation in PilotOS (yet). Therefore I will write some theory about processes, their states and mutual exclusion.

A process is a unit of execution or code, which can be executed. With this definition we don't care whether the code really can be executed now, it is enough, that the code is "ready" to be executed, so the code can be jumped to, has got some memory and could be executed in theory. In real operating systems there are several constraints about the point in time when a process can be executed. Therefore there are process states.

The state of a process determines in what state of an automaton the process is right now. A process can be executed only if it is in the main memory (see virtual memory, MMU, paging) und does not wait for other processes to finish. A process may be waiting for other processes if they want to use the same resource, which can only be used exclusively and the other process has allocated them.

Resources will be managed by the operating system. There as physical and logical resources, eg. for physical ones hard-drive or memory; a file may be logical. To ensure secure access to these resources there are means for mutual exclusion (mutex) in most operating systems. These are used to ensure, that there can only be one (or in general k) processes executing a critical section at one point in time. A critical section is code, which, when executed by several processes concurrently, may lead to harm, which can not be undone.

There are several design critia for the implementation of mutexes. For example livelyness, i.e. a process does not keep a resource an infinite amount of time. Security, i.e. something bad, that can not be undone, may never happen. And fairness, which can be definited differently, but we will use the following definition: no process will wait indefinitely. With these criteria one can implement a policy, which determines when and how waiting processes will be unblocked.

The blocking of a process can be done by the process itself (by sending the request to be blocked until a condition is fulfilled to the operating system), or by the operating system, while accessing a resource. For example it is sometimes necessary to wait for another process to finish a certain action, so they can work in synchron.

A first implementation of waiting could be a busy wait, i.e. a while-loop in the code, which tests the condition. Only if it is fulfilled, the following code can be executed (safely). But this method is really heavy on computing-time, because the scheduler has to schedule this process, and it will use its complete time-interval only for testing a variable.

It would be more reasonable to not schedule this task again, until the condition is met. For this we set the process state to "waiting" or "blocked", which indicates, that the process is waiting for some condition to be fulfilled. The condition must the saved also (for example as mutex-descriptor). In the moment this mutex will be cleared, the operating system may unblock every (or any one) of the processes waiting for that condition, be setting their state to "active".

That means we have the following three process states: "running", i.e. the process is executed by the CPU at this point in time; "active" - the process is waiting for the CPU but can be executed and "blocked, waiting" - the process is waiting for a mutex to be cleared.

A mutex can be cleared differently. In normal operating systems, there are semaphores, and also monitors. And it can be implemented with the help of a boolean-Variable. But with several processes it become non-trivial to implement a mutex. On entrance into the critical section the process must check if the variable is set (or the semaphore has reached a certain number). If so, then the process must wait.

If the variable is not set, the process may enter the critical section and has to set the variable with a second instruction. If it is preempted between these two instruction, then a second process may be allowed to enter the critical section and something bad may happen (see race conditions). Therefore most of the processes have an instruction, that sets a variable and returns if it was set, so no other process may enter the critical section.

Alternatively for the time, the process is in the critical section, it may disable the interrupts in the CPU. This in turn means, thet the process can not be interrupted by timer-interrupts, and therefore can not be interrupted by any process in general. If this method is used the programmer must be very aware, that his/her critical section must be as short as possible, because it would bring the system down to a crawl, because no ther process can be executed in the mean-time. In turn, the interrupts may only be disabled for the time-interval the variable is tested and set, and afterwards can be activated again.

Last edit: 22.05.2016 10:00