Week 10 AOS: Interprocess Communication and Process Scheduling (Content)

What is IPC?

Mechanism for processes to share information without direct memory access. (Processes are isolated.)

Two main IPC issues

Avoid race conditions; ensure correct sequencing. (Safety + ordering.)

Definition of race condition

Outcome depends on unpredictable timing of processes. (Shared data conflict.)

Definition of critical region

Section of code accessing shared data. (Needs protection.)

Definition of mutual exclusion

Only one process may enter critical region at a time. (Prevents races.)

Four requirements for solving critical section problem

Mutual exclusion; no assumptions about speed/CPUs; progress; bounded waiting. (Correctness conditions.)

Busy waiting

Process repeatedly checks a condition while consuming CPU. (Inefficient.)

Lock variable idea

Shared lock=0 means free; lock=1 means busy. (Fails due to race on lock.)

Strict alternation

Processes alternate turns entering critical region. (Mutual exclusion but violates progress.)

Peterson’s solution

Uses flag[i] and turn to ensure mutual exclusion + progress. (Classic software solution.)

TSL instruction

Atomic test-and-set hardware instruction for locking. (Prevents races.)

XCHG instruction

Atomic swap used for locking on x86. (Hardware mutual exclusion.)

Problems with busy waiting

Wastes CPU; priority inversion. (Inefficient + unfair.)

Priority inversion

Low-priority task blocks high-priority task by holding resource. (Inversion of priorities.)

Sleep and wakeup

Sleep blocks a process; wakeup unblocks it. (Avoids busy waiting.)

Producer-consumer problem

Producer fills buffer; consumer empties it. (Needs synchronization.)

Semaphore definition

Integer with atomic up/down operations. (Synchronization primitive.)

Semaphore operations

down() waits/decrements; up() increments/wakes. (Atomic.)

Semaphores in producer-consumer

full, empty, mutex. (Synchronization + mutual exclusion.)

Mutex definition

Binary lock for mutual exclusion. (Protects shared resources.)

Mutex vs semaphore

Mutex = lock; semaphore = counter. (Different semantics.)

Monitors

Language-level construct with implicit locking + condition variables. (Safer abstraction.)

Message passing

send/receive communication without shared memory. (Distributed-friendly.)

Deadlock definition

Processes wait forever for each other. (Circular wait.)

Livelock definition

Processes keep reacting without progress. (Active but stuck.)

Starvation definition

Process never gets CPU time. (Unfair scheduling.)

CPU-bound vs I/O-bound

CPU-bound = long bursts; I/O-bound = short bursts. (Scheduler behaviour.)

Cooperative vs preemptive scheduling

Cooperative = voluntary yield; preemptive = forced context switch. (Scheduling style.)

Batch vs interactive vs real-time scheduling

Batch = throughput; interactive = responsiveness; real-time = deadlines. (Different goals.)

Scheduling goals

Fairness, policy enforcement, balance. (General.)

CPU scheduling criteria

Utilization, throughput, turnaround, waiting, response time. (Metrics.)

FCFS

Non-preemptive, simple, long waiting times possible. (Queue order.)

SJF

Shortest job first; optimal average waiting time. (Non-preemptive.)

Round robin

Fixed quantum; preemptive; good responsiveness. (Interactive systems.)

Quantum size trade-off

Too small = overhead; too large = poor response. (Balance needed.)

Priority scheduling

CPU given to highest priority (lowest number). (Can cause starvation.)