The Process Concept

What is a Process?

Process: Instance of a program being executed.

• The OS itself is organized as a collection of processes.
• The OS tracks a process with a process control block (PCB)

Parts of a Process:

• Text Section: Program code
• Current activity (e.g., program counter, processor registers)
• Stack: Contains temporary data
  • Function parameters, return addresses, local variables.
• Data Section: Contains global vars
  • Static vars
• Heap: Contains memory dynamically allocated at runtime.

Program v.s. Process: Programs are passive entities, stored on the disk. Processes are active entities.

The Need for Processes (Virtual CPUs)

Structuring an application as processes allows for independence from:

1. Number of CPUs, and
2. Type of CPU

Process Management

Process Control Block

Process Control Block (PCB): The concrete representation of a process.

• aka: Task Control Block
• Independent data structure that holds information on a process
• OS creates a new PCB for every new process.

PCB Contents

• Current instruction address
• Registers
• CPU Scheduling info (priorities, scheduling queue pointers)
• Memory-management info (memory used)
• Accounting info (CPU used, clock time elapsed, time limits)
• I/O status information (open files, etc.)
• Program being executed

Organizing PCBs

Two ways to efficiently organize PCBs:

1. Array of Structures: PCBs marked as free or allocated, and stored which eliminates need for dynamic memory management.
   • Drawback: Wasted memory (a large, but sparsely-populated array)
2. Array of Pointers: Pointers point to dynamically-allocated PCBs.
   • Wastes little space and can grow.
   • Drawback: Overhead of dynamic memory management to allocate and free PCBs.

Linux PCB Implementation (Linked-List Free)

Linux solves this by adding two more fields for “left and right sibling”, resulting in:

1. parent: Points to process’s parent (same as before)
2. first_child: Points to process’s first child
3. younger_sibling (left sibling): Points to sibling of process, created immediately following this process.
4. older_sibling (right sibling): Points to sibling of process, created immediately prior to this process.

Why? — Linked-list introduces a lot of performance issues and dynamic memory management issues.

• This implementation improves time efficiency and doesn’t need dynamic memory management (and space efficiency remains the same).

Process States and Transitions

Process States

Typical Process States:

• New: Process being created
• Running: Instructions are being executed
• Blocked/Waiting: Process is waiting for some event to occur
• Ready: Process is waiting to be assigned to a processor
• Terminated: Process has finished execution
• suspended: TODO

void main()
{
  printf("Hello world");
}

Context Switch

Context Switch: When CPU transfers control from one process to another.

• May be triggered by OS for scheduling reasons or caused by current process’s inability to continue.
• Context-switching adds overhead.
  • The more complex the OS and PCB, the longer this delay is.

CPU State: All intermediate values held in any CPU registers and hardware flags at the time of interruption.

Note: The PCB contains an up-to-date copy of CPU state only when a process’s state is ready or blocked!

Process Scheduling

Process Scheduler: Selects among available processes for next execution on CPU.

• Maintains scheduling queues of processes.

Why? — Process schedulers exist to aid the goals of:

1. Multiprogramming: Have some process running at all times to maximize CPU utilization.
2. Timesharing: Switch the CPU among processes frequently so that users can interact with each program while it’s running.

Scheduling Queues

Types of Queues

• Job Queue: Set of all processes in the system
• Ready queue: set of all processes residing in main memory, ready to execute
• Device queues: Set of processes waiting for an I/O device

Processes migrate among the various queues.

Schedulers

Short-Term Scheduler (CPU Scheduler)

Selects which process should be executed next and allocates CPU.

• Sometimes the only scheduler on a system.
• Invoked frequently (ms), so must be fast

Long-Term Scheduler (Job Scheduler)

Selects which processes should be brought into the ready queue.

• Invoked infrequently (secs/mins), so can be slow
• Controls degree of multiprogramming (# of processes in memory).
• Strives for good process mix.

More on Process Mix:

Processes can be described as either:

• I/O-Bound: Spends more time doing I/O than computation, lots of short CPU bursts; or
• CPU-Bound: Spends more time doing computations, few but very long CPU bursts.

These must be mixed to avoid starving the other.

Medium-Term Scheduler

Suspends process from main memory to achieve higher degrees of multiprogramming.

• Swapping out (remove partially-executed process from memory) \to do stuff, space opens eventually \to swap in (continue execution)

More on Swapping Out — When a process is swapped out, its entire memory image (Text, Data, Stack, and Heap sections) is moved from main memory (RAM) to a backing store (like a disk).

• The PCB, however, is retained. Its state is just updated to “Suspended.”

When swapping back in, the memory image is loaded back into RAM (not necessarily in the same location), and the process eventually becomes Ready again.

Process Operations

There are other operations as well.

Process Creation

Parent process creates a child process, which can create other processes, forming a tree of processes.

• Generally, processes are identified and managed via a process identifier (PID).

Resource Sharing Options

1. Parent and children share all resources.
2. Children share subset of parent’s resources.
3. Parent and child share no resources.

fork() and exec() System Calls

fork(): Copies variables and registers from parent to child.

• Child processes have their own PCB.
• Only difference between child and parent is the value returned by fork.
  • In the parent process, fork returns PID of the child.
  • In the child process, return value is 0.

exec(): Can be used after fork to replace process’s memory space with a new program.

pid = fork();

if (pid < 0) {
  // Error
  return 1;
} else if (pid == 0) {
  // Child process
  execlp("/bin/ls","ls",NULL);
} else {
  // Parent process
  wait(NULL);
  printf("Child complete");
}
return 0;

Process Termination

Design Choice — Can children live without their parents?

Some OSes don’t allow children to exist if their parent is terminated.

• If this design choice is made, it can lead to cascading termination.
• Termination would be initiated by the OS.

wait() System Call

pid = wait(&status)

wait(): Returns status information and PID of process.

• The parent process can wait for termination of a child by using wait().

Zombie and Orphan Processes

Two Scenarios:

1. Zombie: No parent waiting (did not invoke wait)
2. Orphan: Parent terminated without invoking wait

Interprocess Communication

Background and Purpose

Concurrently executing processes within a system may be:

1. Independent: Cannot affect or be affected by another process, or
2. Cooperating: Can affect or be affected by the execution of another process.

Why do IPC?

• Information Sharing: Several applications may be interested in the same piece of info (e.g., clipboard)
• Computation Speedup: Some tasks could be split into subtasks to be executed in parallel (for computers with multiple cores)
• Modularity: We may want to construct the system in a modular fashion and divide system functions into separate processes or threads.

IPC Models

Two models of IPC:

1. Shared Memory
2. Message Passing

Shared Memory v. Message Passing:

• Message passing is more complex and slower. Good for small messages.
• Shared memory makes data synchronization the programmer’s problem.

Example: Producer-Consumer Problem

Producer makes info used by the consumer

• e.g., compiler \to assembler \to etc.

Shared Memory is a solution to the producer-consumer problem.

Naive Producer:

item next_produced;

while(true) {
    while (((in + 1) % BUFFER_SIZE == out)
        ; /* do nothing */
    
    buffer[in] = next_produced;
    in = (in + 1) % BUFFER_SIZE;
}

Naive Consumer:

item next_consumed;

while (true) {
    while (in == out)
        ; /* do nothing */
    
    next_consumed = buffer[out];
    out = (out + 1) % BUFFER_SIZE

    /* consume the item in next_consumed */
}

This code uses the following:

• in: points to next free position in array
• out: points to first full position in array
• buffer empty when in == out
• buffer full when (in + 1) % BUFFER_SIZE == out

This code doesn’t synchronize the producer and consumer, so if the consumer tries to consume an item that hasn’t been produced, it’ll fail. We’ll discuss process synchronization in a future chapter, as this has just been a short sample.

Message Passing

Message System: Processes communicate without sharing variables.

IPC provides two operations:

• Send
• Receive

Synchronization (Blocking v. Non-Blocking)

Synchronization: Message passing may blocking or non-blocking.

1. Blocking (Sync)

• Blocking send: Sender blocked until message received
• Blocking receive: Receiver blocked until message available

2. Non-Blocking (Async)

• Non-blocking send: Sender sends message and continues.
• Non-blocking receive: Receiver gets a valid or null message.