Process

OS manages user-level and kernel-level processes, which includes creating, managing, scheduling and terminating.

A program in execution. An active entity. Program becomes active when it is loaded into memory. Instructions of a process are executed in sequence. Multiple processes can be associated with a single program.

A process contains:

• Text section
  The program code.
• Program counter
• CPU registers, holding current working values
• Data section
  Global/static variables.
• Stack
  Function calls, return addresses, local variables.
• Heap
  Dynamically allocated memory.

Multithreaded processes have 1 program counter per thread.

Program

A passive entity stored on disk. Aka. executable file.

System Program

Programs that provide services to the user and the OS. Shipped with the OS. Not part of the kernel.

Context

Complete set of information about a process, that is required to pause, and later resume it exactly where it left off.

A process’s context splits into 3 categories.

Memory Context

The process’s address space.

Includes the address space layout of the process’s text, data, heap, and stack segments.

Hardware Context

CPU state captured at the last context switch.

Includes:

• Program counter
  Address of the next instruction to execute.
• Stack pointer
  Address of the top of the process’s stack.
• Register contents
  Values of the CPU’s registers at the time of the last context switch.

OS Context

What the kernel tracks about the process beyond its memory and CPU state.

Includes:

• Process ID, state
  Unique identifier and current state of the process.
• Parent process ID
  Identifier of the process that created this process.
• Open files
  File descriptors for files currently in use by the process.
• Scheduler information
  Priority, queue pointers, and other data used by the scheduler.
• I/O devices
  Devices allocated to the process.
• Signal handlers
  Routines registered to handle specific signals.
• Accounting information
  CPU time used, memory usage, I/O operations.

Process Control Block

Aka. PCB, task control block. Representation of a process’ context.

The kernel maintains 1 PCB per process, conceptually organized as a process table.

Design issues:

• Scalability
  How many concurrent processes the table can support.
• Efficiency
  Access must be efficient with minimum space wastage.

In Linux, a PCB is named task_struct and defined as follows:

struct task_struct {
    pid t_pid; /* process identifier */
    long state; /* state of the process */
    unsigned int time_slice; /* scheduling information */
    struct task_struct *parent;/* this process’s parent */
    struct list_head children; /* this process’s children */
    struct files_struct *files;/* list of open files */
    struct mm_struct *mm; /* address space of this process */
}

sizeof(struct task_struct) is usually 3 to 4 KB on 64-bit systems. It varies by kernel version, architecture, and enabled debug config options.

Context Switching

The technique of saving the current process’s context and loading another process’s context. Required for multitasking. Introduces overhead.

Process States

Most OS model a process’s lifecycle using 5 states: new, ready, running, waiting, terminated. A process occupies exactly 1 state at a time.

Some OS add suspended states (suspended-ready, suspended-waiting) for medium-term scheduling, when a process is swapped out of main memory to disk to free space.

Stopped, zombie, and orphan are UNIX-specific special cases.

New

When a process is being created. Resources are allocated and the process is prepared to be admitted to the ready queue.

Ready

When a process is loaded into memory and ready to run.

Running

When a process’s instructions are being executed on a CPU.

Waiting

Aka. blocked. When a process is waiting for an event or a resource. Waits in an event-specific queue until the condition is satisfied.

Terminated

When a process has finished execution or been killed. Its resources are reclaimed and a cleanup is performed.

Stopped

When a process is suspended by a SIGSTOP signal. Resumed by a SIGCONT signal.

Zombie

When process is in terminated state, but its exit status has not yet been collected by its parent.

Once the parent collects the exit code (using wait() or waitpid()), the process entry is completely deleted.

Orphan

When a parent process terminates before its child process. The orphaned child is adopted by the init process (PID 1).

init periodically calls wait() on its adopted children, reaping any that are zombies. This is what cleans up a zombie whose original parent exited without collecting its exit status.

Process Scheduling

The procedure of choosing which process runs next. Handled by process scheduler. Maintains scheduling queues of processes.

Ready Queue

For processes waiting to run.

Wait Queues

For processes waiting on events (I/O).

Processes move across these queues continuously.

Process Creation

Parent–Child Model

A parent creates a child, forms a process tree. Parent and child may or may not share all or a subset of resources. Parent and child may run concurrently; or parent may wait for child to complete.

The root of the tree is init (PID 1), started directly by the kernel at boot. Every other process descends from it.

In UNIX:

• fork()
  Duplicates current process. Returns 0 to child, child’s PID to parent.
• exec()
  Loads new program into process
• wait()
  Parent waits for child to finish, retrieves exit status

Process Termination

Mobile OS often have to terminate processes to reclaim system resources such as memory. From most to least important:

• Foreground process
• Visible process
• Service process
• Background process
• Empty process

Normal Termination

When a process finishes, it calls exit() to terminate itself. Its exit status is read using wait() by the parent.

Abnormal Termination

Parent may kill the child via abort(). Possible reasons for killing:

• Child exceeded resources
• Child’s task is unnecessary
• Parent itself is exiting

On some systems, the OS would kill the entire subtree when parent dies, which is called cascading termination.