main

Chapter 3 - Processes

The process is the unit of work in a modern time-sharing system. A system consists of a collection of processes: operating system processes executing system code and user processes executing user code.

Potentially, all these processes can execute concurrently, with the CPU multiplexed among them. By switching the CPU between processes, the operating system can make the computer more productive.

A batch system executes jobs. A time-shared system has user programs or tasks.

All these activities are similar so we call them processes.

The Process

A process is more than the program code, also known as the text section. It also includes the current activity, represented by a value of the program counter and the contents of the processor’s registers.

A process also includes the process stack, which contains temporary data (such as function params, return addresses, and local variables) and a data section which contains global variables.

A process may also include a heap, which is memory that is dynamically allocated during process run time.

 max |-------|
     | Stack |
     |-------|
     |   |   |
     |   |   |
     |   V   |
     |       |
     |       |
     |   A   |
     |   |   |
     |   |   |
     |-------|
     | heap  |
     |-------|
     | data  |
     |-------|
     | text  |
   0 |-------|

A program is not a process. A program is a file containing instructions stored on disk like an executable file.

A process is an active entityt with a program counter specifying the next instruction to execute and a set of associated resources.

A program becomes a process when an executable file is loaded into memory.

Process State

As a process executes, it changes state. The state of a process is defined in part by the current activity of that process. It may be in one of the following states:

  • New: The process is being created
  • Running: Instructions are being executed
  • Waiting: The process is waiting for some event to occur (such as an I/O completion or reception of a signal)
  • Ready: The process is waiting to be assigned to a processor
  • Terminated: The process has finished execution.
-------                                   --------------
| new |-- admitted                    |-->| terminated |
-------      |       -- interrupt -   |   --------------
             V       |            |   | exit
          ---------  |        -----------
          | ready |<-|   |--->| running |
          ---------      |    -----------
              A  |-- scheduler    |
              |      dispatch     |
I/O complete  |                   | I/O wait
              |                   |
              |    -----------    |
              -----| waiting |<---|
                   -----------

Process Control Block

Each process is represented in the operating system by a process control block (PCB) – also called a task control block. It serves as the repository for any information that may vary from process to process.

  • Process state: The state may be new, ready, running, waiting, halted etc.
  • Program counter: The counter indicates the address of the next instruction to be executed for this process.
  • CPU registers: The registers vary in number and type, depending on the computer architecture.
    • include accumulators, index registers, stack pointers, and general purpose registers, plus any conditional code information.
  • CPU-scheduling information: This information includes a process priority, pointers to scheduling queues, and any other scheduling parameters.
  • Memory-management information: includes value of the base and limit registers and the page tables, or the segment tables, depending on the memory system used by the operating system.
  • Account information: includes the amount of CPU and real time used, time limits, account numbers, job or process numbers etc.
  • I/O status info: includes the list of I/O devices allocated to the process, a lit of open files, and so on.
Process Control Block

    ----------------------
    | process state      |
    ----------------------
    | process number     |
    ----------------------
    | program counter    |
    ----------------------
    |                    |
    |                    |
    |     registers      |
    |                    |
    |                    |
    ----------------------
    | memory limits      |
    ----------------------
    | list of open files |
    ----------------------
    |                    |
    | ...                |
    |                    |
    ----------------------

On Linux this is represented in struct task_struct in <linux/sched.h>.

Threads

The process model discussed so far has implied that a process is a program that performs a single thread of execution.

Processes can have multiple threads of execution and thus to perform more than one task at a time. This is beneficial on multicore systems, where multiple threads can run in parallel.

On systems that supports threads, the PCB is expanded to include information for each thread.

Process Scheduling

Multiprogramming: have some process running at all times to maximize CPU usage. Time sharing: switch the CPU among processes so frequently that users can interact with each program while it is running.

The process scheduler selects an available process for program execution on the CPU. A single-processor system, there will never be more than one running process. The rest will have to wait until the CPU is free.

Scheduling Queues

As processes enter the system, they are put into a job queue, which consists of all processes in the system. The processes that are residing in main memory and are ready and waiting to execute are kept in the ready queue. This queue is usually stored as a linked list. The doubly-linked list contains process control block nodes/structs. Each PCB points to the next PCB in the ready queue.

The list of processes waiting for a particular I/O device is called a device queue. Each device has its own device queue.

A new process is initially put in the ready queue. It waits there until it is selected for execution, or dispatched. Once the process is allocated the CPU and is executing, one of the several events could occur:

  • The process could issue an I/O request and then be placed in an I/O queue.
  • The process could create a new child process and wait for the child’s termination.
  • The process could be removed forcibly from the CPU, as a result of an interrupt and be put back in the ready queue.

Schedulers

A process migrates among the various scheduling queues throughout its lifetime. The operating system must select, processes from these queues in some fashion. The selection process is carried out by the appropriate scheduler.