Process Concept

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.

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, such as:
  • 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

OS creates a new PCB for every new process.

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.

Linked-List Free Implementation

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

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

1. first_child
2. left_sibling
3. right_sibling
4. parent

This improves time efficiency, though space efficiency remains the same.

• Adding a new child process uses about the same amount of memory as linked-list.

TODO Diagram Linked List

Process States and Transitions

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

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 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.

Example:

1. Save state of old process
2. Load state of new process

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

TODO Diagram detailing context switch

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.

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.

TODO Queuing diagram

• Note how processes must always go through the ready queue, preventing hogging the CPU.

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) \to (must be fast)

Long-Term Scheduler (Job Scheduler)

Selects which processes should be brought into the ready queue.

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

Processes can be described as either:

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

These must be mixed to avoid starving the other.

TODO PlantUML of XXI doodle in my papers

Medium-Term Scheduler

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

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

TODO Not everything is wiped from memory, so what exactly is wiped?

TODO Medium term scheduler diagram

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 identified and managed via procss identifier (PID).

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() system call: 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 return PID of the child.
  • In the child process, return value is 0.
• exec() can be used after fork to replace process’ 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

pid = wait(&status)

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

• This can lead to cascading termination.
• Termination is initiated by the OS.

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

• The parent process may wait for termination of a child process by using the wait() system call.

Two Scenarios:

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

Interprocess Communication

Background

Concurrently executing process within a system may be:

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

Purpose:

• Information Sharing: Several applicatiosn 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

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 syncronization the programmer’s problem.

Virtual CPUs

Structuring an application as processes allows for independence from:

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