Processes, Jobs, Signals, Scheduling and Automation

process identity

A Linux process has a PID and parent PID plus real, effective and saved user and group identities that determine ownership and permission checks.

process state

A process may be running, interruptibly sleeping, uninterruptibly sleeping, stopped or a zombie awaiting collection by its parent.

foreground and background jobs

A foreground job owns terminal input and receives terminal-generated signals

signal

A signal is an asynchronous notification delivered to a process; most signals can be handled or blocked, while SIGKILL and SIGSTOP cannot.

kill and termination

kill sends a signal rather than directly destroying a process

nice value

A nice value influences CPU scheduling priority for ordinary processes

cron

A daemon and schedule format for recurring commands, executed with a restricted noninteractive environment.

at command

at schedules commands for one future time, stores the submitted environment and command text and executes them later through the at daemon.

systemd service

A systemd service unit declares how a daemon starts, stops, restarts, orders against dependencies.

automation idempotence

Idempotent automation converges a host to the requested state and can be repeated without accumulating duplicate users, lines, mounts, jobs or deployments.

CPU Scheduling

What is CPU Scheduling?

CPU Scheduling selects which process in the Ready queue gets the CPU next.

Why scheduling?

• CPU can only run one process at a time
• Multiple processes compete for CPU
• OS must decide who runs next

Scheduling Queues

New Process → Job Queue
                 ↓
         Ready Queue (in RAM)
                 ↓
         CPU Scheduler picks one
                 ↓
         CPU executes process
                 ↓
     I/O request? → I/O Wait Queue → I/O done → Ready Queue
     Time slice?  → Preempted → Ready Queue
     Exit?        → Terminated

Scheduling Criteria (Performance Metrics)

Metric	Description	Optimize
CPU Utilization	Percentage of time CPU is busy	Maximize
Throughput	Number of processes completed per time unit	Maximize
Turnaround Time	Total time from submission to completion	Minimize
Waiting Time	Total time process spends in ready queue	Minimize
Response Time	Time from submission to first response	Minimize

Formulas:

Turnaround Time = Completion Time - Arrival Time
Waiting Time    = Turnaround Time - Burst Time
Response Time   = First CPU given - Arrival Time

Preemptive vs Non-Preemptive Scheduling

Type	Description
Non-Preemptive	Once CPU is given to a process, it keeps it until done or waiting for I/O
Preemptive	OS can forcibly take CPU from running process (time slice, priority)

Process States

Five-State Process Model

                    +--------+
                    |  NEW   |  ← Process created
                    +--------+
                         | admitted
                         ↓
              +------READY------+
              |    ←scheduler   |
              |   dispatch      |
              ↓                 |  interrupt / time slice
         +--------+             |
         |RUNNING |→→→→→→→→→→→→+
         +--------+
              |
              | Wait for I/O or event
              ↓
         +--------+
         |WAITING |  ← process blocked for I/O
         | (BLOCKED)|
         +--------+
              |
              | I/O or event complete
              ↓
         READY (returns to Ready queue)

RUNNING → TERMINATED (exit)

Process States Explained

State	Description	Transitions
New	Process is being created	→ Ready (after creation)
Ready	In memory, waiting for CPU	→ Running (scheduler dispatches)
Running	Actually being executed on CPU	→ Ready (time slice expires) / Waiting (I/O) / Terminated (exit)
Waiting (Blocked)	Waiting for I/O completion or event	→ Ready (I/O/event done)
Terminated	Process has finished execution	End state

Context Switch

When CPU switches from one process to another:

Process A running on CPU
    |
    | Interrupt / time expired
    ↓
Save CPU state of A → PCB_A
Load CPU state of B ← PCB_B
    |
    | Process B now running on CPU

Context switch overhead: Saving and restoring registers, cache flush — expensive!

Inter-Process Communication (IPC)

What is IPC?

IPC (Inter-Process Communication) mechanisms allow processes to communicate and synchronize.

Two Models of IPC

19.1 Shared Memory Model

• Processes share a common memory region
• Both processes can read and write to the shared memory
• Fast — no OS involvement after setup
• Risk: Need synchronization to avoid race conditions

Process A      Process B
    |               |
    +→ Shared ←+    |
       Memory         (both access same region)

APIs: shmget(), shmat(), shmdt(), shmctl() (POSIX)

19.2 Message Passing Model

• Processes communicate by sending and receiving messages
• OS manages the communication channel
• Slower than shared memory (OS involvement for every message)
• Safer — no shared state; no synchronization issues

Process A → [Message Queue/Pipe] → Process B
            (OS manages this)

APIs:

• Pipes — pipe() (anonymous) or named pipes (FIFO)
• Message Queues — msgget(), msgsnd(), msgrcv()
• Sockets — socket(), send(), recv()

Signals — kill(), signal()

IPC Mechanisms Comparison

Mechanism	Direction	Speed	Type
Pipe	Unidirectional	Fast	Related processes only
FIFO (Named Pipe)	Unidirectional	Fast	Any processes
Message Queue	Bidirectional	Medium	Any processes
Shared Memory	Bidirectional	Fastest	Any processes
Socket	Bidirectional	Medium	Same or different machines
Signal	Unidirectional	Fast	Simple notification

CPU Scheduling Algorithms

17.1 FCFS — First-Come, First-Served

• Non-preemptive
• Processes scheduled in arrival order
• Simple but can cause Convoy Effect (short jobs wait behind long jobs)

Example:

Process  Burst Time  Arrival Time
P1        24ms        0
P2         3ms        0
P3         3ms        0

Gantt Chart:    | P1 (0-24) | P2 (24-27) | P3 (27-30) |
Waiting Times:  P1=0, P2=24, P3=27
Average Waiting: (0+24+27)/3 = 17ms

17.2 SJF — Shortest Job First

• Non-preemptive (or preemptive = SRTF)
• Schedule process with shortest burst time next
• Optimal for minimizing average waiting time
• Problem: Requires knowing burst time in advance

SRTF (Shortest Remaining Time First): Preemptive version of SJF

Example:

Process  Burst Time  Arrival Time
P1        6ms        0
P2         8ms        0
P3         7ms        0
P4         3ms        0

Order: P4(3ms) → P1(6ms) → P3(7ms) → P2(8ms)
Average Waiting = (3+16+9+0)/4 = 7ms   (vs FCFS: 10.25ms)

17.3 Round Robin (RR)

• Preemptive
• Each process gets a fixed time quantum (time slice) — usually 10-100ms
• After time quantum expires, process is preempted and moved to back of ready queue
• Most common in time-sharing systems

Example (q=4ms):

Process  Burst Time
P1        24ms
P2         3ms
P3         3ms

Gantt: |P1(0-4)|P2(4-7)|P3(7-10)|P1(10-14)|P1(14-18)|P1(18-22)|P1(22-26)|P1(26-30)|

Tradeoff: Large quantum → behaves like FCFS; Small quantum → more context switches

17.4 Priority Scheduling

• Each process has a priority number (lower number = higher priority)
• Highest priority process runs first
• Preemptive or Non-preemptive
• Problem: Starvation — low priority processes may never run

Solution: Aging — gradually increase priority of waiting processes

17.5 Multilevel Queue Scheduling

Multiple queues for different process types:

• Foreground (interactive) — Round Robin

Background (batch) — FCFS

• Different queues have different priorities

17.6 Multilevel Feedback Queue

• Processes can move between queues based on behavior
• CPU-bound processes → lower priority queue
• I/O-bound processes → higher priority queue
• Most complex but most flexible

Algorithm Comparison

Algorithm	Preemptive	Avg Wait	Starvation	Overhead
FCFS	No	High	No	Low
SJF	No	Optimal	Yes (long jobs)	Medium
SRTF	Yes	Optimal	Yes	High
Round Robin	Yes	Medium	No	Medium
Priority	Both	Medium	Yes (low priority)	Low
Multilevel Feedback	Yes	Good	No (with aging)	High

Process Control Block (PCB)

What is a PCB?

The PCB (Process Control Block) is the data structure used by the OS to store all information about a process.

Also called: Task Control Block (TCB)

PCB Contents

Field	Description
Process ID (PID)	Unique identifier for the process
Process State	New, Ready, Running, Waiting, Terminated
Program Counter (PC)	Address of next instruction to execute
CPU Registers	Contents of all CPU registers (saved on context switch)
CPU Scheduling Info	Priority, scheduling queue pointers
Memory Management Info	Base register, limit register, page/segment tables
I/O Status Info	List of open files, I/O devices allocated
Accounting Info	CPU time used, elapsed time, job limits
Parent PID (PPID)	PID of parent process
User ID (UID)	Owner of the process

Process Synchronization

The Critical Section Problem

Critical Section: A code segment where a process accesses shared resources.

Requirements for a valid solution:

1. Mutual Exclusion — Only one process in critical section at a time
2. Progress — If no process is in critical section, one waiting should enter
3. Bounded Waiting — Process should not wait indefinitely (no starvation)

Race Condition

A race condition occurs when multiple processes access and manipulate shared data concurrently and the outcome depends on execution order.

Example:

Shared: count = 5

Process A reads count=5 → count++  → count=6
Process B reads count=5 → count++  → count=6

Expected: count=7, Got: count=6  ← RACE CONDITION!

Synchronization Solutions

20.1 Mutex (Mutual Exclusion Lock)

pthread_mutex_t lock;
pthread_mutex_lock(&lock);     // Acquire lock
// Critical section
pthread_mutex_unlock(&lock);   // Release lock

• Only one thread can hold mutex at a time
• Other threads block waiting for the lock

20.2 Semaphore

A semaphore is an integer variable with two atomic operations:

• wait(S) / P(S): S--; if S<0 then block
• signal(S) / V(S): S++; if S<=0 then wake up process

Binary Semaphore (Mutex): Value is 0 or 1 Counting Semaphore: Value is N (controls N resources)

semaphore S = 1;  // Binary semaphore

// Process 1:
wait(S);          // P: S=0; enter critical section
// Critical section
signal(S);        // V: S=1; release

// Process 2:
wait(S);          // P: S=-1; blocked until P1 signals

20.3 Monitors

• High-level synchronization construct (in Java, C#)
• Only one thread can execute inside monitor at a time
• Java: synchronized keyword implements monitor

synchronized(object) {
    // Critical section
}

Classic Synchronization Problems

Problem	Description
Producer-Consumer	Producer adds to buffer; consumer removes from buffer; need to coordinate
Readers-Writers	Multiple readers OK simultaneously; writers need exclusive access
Dining Philosophers	5 philosophers, 5 forks; each needs 2 forks; potential deadlock

Threads

What is a Thread?

A thread is the smallest unit of CPU execution — a lightweight process.

Process vs Thread:

Feature	Process	Thread
Definition	Program in execution	Lightweight sub-unit of a process
Memory	Own address space	Shares process address space
Creation cost	Expensive	Cheap
Communication	IPC required	Shared memory directly
Context switch	Heavy	Light
Failure	Isolated	Can crash other threads

Types of Threads

Type	Description
User-level threads	Managed by user-space library (not OS)
Kernel-level threads	Managed by OS kernel
Hybrid threads	Combination

Multi-threading Models

Model	Description	Example
Many-to-One	Many user threads → one kernel thread	Old Green threads
One-to-One	Each user thread = one kernel thread	Windows, Linux
Many-to-Many	Many user → many kernel threads	Solaris, HP-UX

Thread Benefits

• Faster creation than processes
• Faster context switching within same process

Shared memory enables easy data sharing

• Enables true parallelism on multi-core CPUs
• Responsive UI (one thread handles UI, another does background work)

Memory Management

Why Memory Management?

• Multiple processes must share memory
• Each process needs its own address space
• Protect one process's memory from another
• Efficiently allocate and deallocate memory

Memory Allocation Methods

22.1 Contiguous Memory Allocation

Fixed Partitioning:

• Memory divided into fixed-size partitions
• Each process gets one partition
• Problem: Internal Fragmentation — wasted space within partition if process is smaller

Dynamic Partitioning:

• Partitions created as needed, sized to process needs

Problem: External Fragmentation — free space scattered in small chunks

Fragmentation

Type	Description	Solution
Internal Fragmentation	Wasted space within an allocated partition (process smaller than partition)	Smaller fixed partitions or dynamic allocation
External Fragmentation	Enough total free memory exists but scattered in non-contiguous chunks	Compaction, Paging

External Fragmentation Example:

Memory: [P1: 40KB] [Free 10KB] [P2: 20KB] [Free 15KB] [P3: 30KB] [Free 8KB]
Total free: 33KB    But a 30KB process cannot fit (no single 30KB block)

Compaction: Move processes to consolidate free space → expensive!

Memory Allocation Algorithms

When a new process needs memory, which free block to allocate?

Algorithm	Description	Advantage	Disadvantage
First Fit	Allocate first block large enough	Fast	May leave large holes
Best Fit	Allocate smallest sufficient block	Least waste	Slow; creates tiny unusable fragments
Worst Fit	Allocate largest available block	Leaves larger remaining holes	Often worst overall
Next Fit	First fit starting from last allocation point	Fast	Less initial waste

Deadlocks

What is a Deadlock?

A deadlock is a situation where a set of processes is permanently blocked because each process is holding a resource and waiting for a resource held by another process.

Example:

Process A holds Resource 1, waiting for Resource 2
Process B holds Resource 2, waiting for Resource 1
→ DEADLOCK: Neither can proceed

Coffman's Four Necessary Conditions for Deadlock

Condition	Description
Mutual Exclusion	Resources cannot be shared (one process at a time)
Hold and Wait	Process holds resource while waiting for others
No Preemption	Resources cannot be forcibly taken; must be released voluntarily
Circular Wait	Circular chain: P1 waits P2's resource, P2 waits P3's, ..., Pn waits P1's

All four conditions must hold simultaneously for deadlock

Deadlock Handling Methods

1. Deadlock Prevention

Prevent one of the four necessary conditions:

• Eliminate Mutual Exclusion: Share resources (not always possible)
• Eliminate Hold and Wait: Process must request all resources at once (or release before requesting more)
• Allow Preemption: OS can forcibly take resources from waiting processes
• Eliminate Circular Wait: Order resources; processes must request in increasing order

2. Deadlock Avoidance

Dynamically analyze resource allocation to ensure system never enters deadlock state.

Banker's Algorithm:

• Like a bank approving loans — only approve if system stays "safe"
• Safe State: There exists a sequence in which all processes can complete
• If next allocation might lead to unsafe state → deny request

3. Deadlock Detection

Allow deadlock to occur, then detect and recover.

Detection: Draw Resource Allocation Graph (RAG)

• If RAG has a cycle → deadlock (for single-instance resources)

Recovery methods:

• Process termination — kill one or all deadlocked processes

Resource preemption — take resources from some processes

4. Deadlock Ignorance (Ostrich Algorithm)

Pretend deadlocks don't occur — "bury your head in sand".

• Used by most OS (Unix, Windows) for infrequent deadlocks
• Reboot the system if deadlock occurs