Preemptive Multitasking

Motivation: Concurrency of Many Processes

Imagine that we are designing CPU mechanism. The simplest algorithm is to let the CPU execute instructions one by one. This algorithm is ineffective because I/O instructions taken cared by storage devices are much slower than CPU instructions. If the CPU sees an I/O instruction, it will be stuck there until the instruction completes.

To boost performance, we can let the CPU do something else when seeing an I/O instruction. For example:

• CPU handles programA.

• CPU sees an I/O instruction in programA, for example, fprintf().

• While the I/O instruction is being executing by storage devices, CPU handles programB.

• Once the I/O instruction completes, CPU comes back to programA and continues the work.

However, it is not as simple as it seems to be: we have to save the context (registers values, of programA, otherwise the CPU won't be able to execut instructions in programA correctly when it comes back. This context includes register values, stack frame address, and etc. The context is stored in a data structure called PCB (process control block) and PCB together with the program itself is called a process.

Definition 1: A process is a running program.

Definition 2: Process = program + PCB.

Concurrency vs. Parallelism

Don't confuse concurrency with parallelism:

• Concurrency: On a single-core machine, the CPU runs processA => processB => processA => processB => ... , this is called concurrency.

• Parallelism: On a multiple-core machine coreA runs processA, coreB runs processB, coreC runs processC at the same time, this is called parallelism.

Process State

In a multitasking computer system, processes may occupy a variety of states. These distinct states may not be recognized as such by the kernel. However, they are a useful abstraction for the understanding of processes. The following typical process states are possible on computer systems of all kinds. In most of these states, processes are "stored" on main memory:

• Created

  • When a process is first created, it occupies the "created" or "new" state. In this state, the process awaits admission to the "ready" state. Admission will be approved or delayed by a long-term, or admission, scheduler. Typically in most desktop computer systems, this admission will be approved automatically. However, for real-time operating systems this admission may be delayed. In a realtime system, admitting too many processes to the "ready" state may lead to oversaturation and overcontention of the system's resources, leading to an inability to meet process deadlines.

• Ready

  • A "ready" or "waiting" process has been loaded into main memory and is awaiting execution on a CPU (to be context switched onto the CPU by the dispatcher, or short-term scheduler). There may be many "ready" processes at any one point of the system's execution—for example, in a one-processor system, only one process can be executing at any one time, and all other "concurrently executing" processes will be waiting for execution.

  • A ready queue or run queue is used in computer scheduling. Modern computers are capable of running many different programs or processes at the same time. However, the CPU is only capable of handling one process at a time. Processes that are ready for the CPU are kept in a queue for "ready" processes. Other processes that are waiting for an event to occur, such as loading information from a hard drive or waiting on an internet connection, are not in the ready queue.

• Running

  • A process moves into the running state when it is chosen for execution. The process's instructions are executed by one of the CPUs (or cores) of the system. There is at most one running process per CPU or core. A process can run in either of the two modes, namely kernel mode or user mode.

    • Kernel mode

      • Processes in kernel mode can access both: kernel and user addresses.

      • Kernel mode allows unrestricted access to hardware including execution of privileged instructions.

      • Various instructions (such as I/O instructions and halt instructions) are privileged and can be executed only in kernel mode.

      • A syscall from a user program leads to a switch to kernel mode.

    • User mode

      • Processes in user mode can access their own instructions and data but not kernel instructions and data (or those of other processes).

      • When the computer system is executing on behalf of a user application, the system is in user mode. However, when a user application requests a service from the operating system (via a syscall), the system must transition from user to kernel mode to fulfill the request.

      • User mode avoids various catastrophic failures:

        • There is an isolated virtual address space for each process in user mode.

        • User mode ensures isolated execution of each process so that it does not affect other processes as such.

        • No direct access to any hardware device is allowed.

• Blocked

  • A process transitions to a blocked state when it cannot carry on without an external change in state or event occurring. For example, a process may block on a call to an I/O device such as a printer, if the printer is not available. Processes also commonly block when they require user input, or require access to a critical section which must be executed atomically. Such critical sections are protected using a synchronization object such as a semaphore or mutex.

• Terminated

  • A process may be terminated, either from the "running" state by completing its execution or by explicitly being killed. In either of these cases, the process moves to the "terminated" state. The underlying program is no longer executing, but the process remains in the process table as a zombie process until its parent process calls the wait syscall to read its exit status, at which point the process is removed from the process table, finally ending the process's lifetime. If the parent fails to call wait, this continues to consume the process table entry (concretely the process identifier or PID), and causes a resource leak.

A running process is given a time slice which represents how much time the process can occupy the CPU. When the time slice is used up, the process changes state: running => ready. At this moment, the CPU would handle another process: ready => running.

PCB

A Process Control Block (PCB) is a data structure used by the OS to store all the information about a process. It is also known as a process descriptor. When a process is created (initialized or installed), the operating system creates a corresponding PCB. This specifies the process state (i.e. created, ready, running, blocked or terminated).

Ready Queue and Blocked Queue

Usually PCBs are stored in a linked list. When the PCBs of ready processes are linked together, it is called a ready queue; when the PCBs of blocked processes are linked together, it is called a blocked queue.

There is no such thing as "running queue" because the CPU is only capable of handling one process at a time.

Structure

In multitasking operating systems, the PCB stores data needed for correct and efficient process management. Pictorially:

PCB structure

Location

PCB must be kept in an area of memory protected from normal process access.

Reference

Process stateWikipedia

Process state - Wikipedia

Process control blockWikipedia

Process control block - Wikipedia

Introduction

Diagram of a Process Control Block (PCB)