CA216 Operating Systems Concepts and Mechanisms

Process

Has its own memory space and is when the program is executed.

Thread

Shares memory with other threads in the same process.

Use-case for fork() + exec()

A shell launching a command: fork to create a new process, then exec to load the command.

kill

Sends a signal to a process.

strace

Traces system calls and signals made by a program.

Amdahl's Law formula

S = 1 / ((1 - P) + P / N), where P = parallel fraction, N = processors.

Semaphore

A signaling mechanism to control access to shared resources.

Busy waiting/spinlock

A process constantly checks a condition.

Deadlock conditions

Mutual exclusion, Hold and wait, No preemption, Circular wait.

Prevention vs Avoidance Deadlock

Prevention: Break one of the four conditions; Avoidance: Use safe states (e.g., Banker's algorithm).

IPC mechanisms in Linux

Pipes, Shared Memory, Message Queues, Semaphores.

Paging

Process address space is broken down into blocks of same size. Size of process can be measured by number of pages.

TLB (Translation Lookaside Buffer)

special memory cache that holds translations

Impacts of large vs small page sizes

Small: more overhead from page tables; Large: internal fragmentation.

Wildcard Expansion

The shell expands the wildcard and passes the result to the program, not the string '*'.

Adding Directory to PATH

export PATH=$PATH:$HOME/bin

wait() Function

It makes the parent process wait until the child process finishes.

What is execlp() Behavior

It replaces the current process image; code after it won't run if it succeeds.

Process Lifecycle Transition

It was interrupted, usually by a scheduler for time-sharing.

Thread Race Condition

Lack of atomic operations or synchronization.

Fixing Race Conditions in C

Use atomic_int or mutexes for shared variable updates.

Dining Philosophers Problem

It introduces asymmetry, preventing circular wait.

Inode

A data structure that stores information about a file except its name.

Internal Fragmentation

Wasted space within allocated memory blocks due to allocation rounding.

Process Control Block (PCB)

It contains process information like PID, registers, scheduling info, memory info, etc.

Heap Usage Reporting

Heap size is dynamic and allocated at runtime.

Direct Memory Access (DMA)

Hardware feature allowing devices to access memory without CPU involvement.

Conditions for Deadlock

Mutual exclusion, Hold and wait, No preemption, Circular wait.

Amdahl's Law

Limits on performance gain from parallelization due to serial portions of code.

Safe State in Resource Allocation

The system can avoid deadlock by safely allocating resources in some order.

Difference Between Process and Thread

A process is an independent program with its own memory space and resources. A thread is a lightweight unit of execution within a process, sharing the process's memory and resources.

What is fork()

Creates a new child process by duplicating the parent process.

Process Control Block (PCB) Definition

The PCB is a data structure in the OS that stores information about a process, including process ID, state, CPU registers, memory info, and open files.

Linux Process Life-Cycle States

New , Ready , Running, Waiting, Terminated.

Initialized Data

Global/static variables with initial values, e.g., int b=2.

Uninitialized Data

Global/static variables without values

Heap

Dynamic memory allocation

Stack

Local variables and function calls.

Paging

Divides virtual memory into fixed-size pages and physical memory into frames, with a page table mapping virtual addresses to physical addresses.

Page Table

Maps virtual addresses (page number + offset) to physical addresses.

Swapping

Moves pages to disk when memory is full.

Internal Fragmentation

Occurs when allocated memory is larger than needed, wasting space within the block.

Translation Lookaside Buffer (TLB)

A cache that stores recent page table mappings to speed up virtual-to-physical address translation.

Difference between Paging and Swapping

Paging divides memory into pages for efficient allocation; swapping moves entire processes or pages to disk when memory is full.

Amdahl's Law

Calculates parallel program speedup: Speedup = 1 / (s + (1-s)/N), where s is the serial proportion and N is the number of processors.

Preemptive Scheduling

Allows the OS to interrupt and switch processes.

Non-Preemptive Scheduling

Runs a process to completion or until it yields.

Shortest-Remaining-Time-First (SRTF) Scheduling

A preemptive scheduler that prioritizes the process with the shortest remaining burst time.

Processor Affinity

Assigns a process to a specific CPU to improve cache performance by reducing cache misses.

Critical Section Problem

Code accessing shared resources that requires mutual exclusion to prevent race conditions.

Race Condition

Occurs when multiple processes/threads access shared resources concurrently, leading to unpredictable outcomes.

Test_and_Set

An atomic instruction for synchronization that sets a boolean and returns its old value atomically.

Compare_and_Swap

An atomic instruction that updates a value if it matches an expected value.

Deadlock

It occurs when processes hold resources and wait for others, forming a cycle.

Deadlock Example

Two processes each hold one resource and request the other.

Deadlock Prevention

Prevention eliminates one of the four deadlock conditions (e.g., break circular wait by resource ordering).

Deadlock Avoidance (Banker’s Algorithm)

The Banker's Algorithm is a deadlock avoidance method that checks if granting a resource request keeps the system in a safe state by dynamically checking resource allocation, ensuring no deadlock occurs.

OS Recovery from Deadlock

Terminate one or more processes, roll back a process to release resources, preempt resources, or restart the system.

Dining Philosophers Problem

Five philosophers alternate between thinking and eating, needing two forks (shared resources).

Dining Philosophers Solution

Use semaphores or resource ordering.

Inode

An inode is a filesystem structure storing file metadata (permissions, owner, size, timestamps) and pointers to data blocks, but not the file name.

pstree Command

pstree displays a tree of processes, showing parent-child relationships.

Direct Memory Access (DMA)

DMA allows devices to transfer data to/from memory without CPU involvement, improving performance over programmed I/O.

Dynamically Linked Library (DLL)

A DDL is loaded at runtime, shared among programs.

Busy Waiting/Spinlock

When a process repeatedly checks a condition, wasting CPU.

Bootstrap Program

Loads at power-up, initializes hardware, and loads the OS kernel.

Cache locality

Assigning a process to a specific CPU to leverage cache locality, improving performance.

Dividing by zero

An interrupt is generated, and the OS terminates the program, preventing system crashes.

Foreground process

A process currently open, visible on the display, and has keyboard or other I/O directed to it.

Kernel mode

Allows all instructions to be executed, with only the kernel running, providing full control over system resources.

Context switch

It is when the OS saves the state of a running process via its PCB and loads another process's state to run, enabling multitasking.

Multi-threaded program performance

Overhead from thread creation/management and synchronisation can slow performance.

What is Compaction in memory management

It rearranges memory to consolidate free space into a single large block, reducing external fragmentation.

Cache memory

It is small, fast memory between the processor and main memory, storing frequently accessed data to speed up CPU operations.

External fragmentation

It occurs when free memory is scattered in small blocks, insufficient for new processes despite total free space being adequate.

Unequal-sized partitions

Fit different-sized processes better, cuts down on wasted memory space and makes memory use more efficient than equal-sized partitions.

Linux size command and heap size

size command reports static sections at compile time, heap is dynamically allocated at runtime

Round Robin scheduling

Preemptive scheduling that assigns each process a time quantum in a cyclic order, ensuring no process is permanently overlooked, though delays may occur with many processes.

What is Starvation in scheduling

It occurs when a runnable process is indefinitely overlooked by the scheduler despite being able to proceed.

Livelock

When threads continuously attempt an action that fails, preventing progress, unlike a deadlock where threads are blocked.

Monitor

A synchronisation construct that ensures mutual exclusion for shared resources, allowing only one thread to execute its critical section at a time.

Atomic operation

An indivisible instruction that completes without interruption, ensuring no race conditions.

circular wait condition for deadlock

Occurs when a set of processes form a cycle, each holding a resource and waiting for the next process's resource.

resource-allocation graph for deadlock

A system is deadlocked if a cycle exists in the resource-allocation graph with only assignment edges.

sequential vs. random access in file systems

Sequential access reads/writes data in order. Random access allows direct access to any data part.

benefits and drawbacks of single vs. multiple file copies

Single copy: Saves space, ensures consistency; drawback: contention delays. Multiple copies: Faster access, fault tolerance; drawback: inconsistency if not synchronized.

strace command

System calls and signals made by a program, useful for debugging or monitoring. Example: open(), read()

pipe in operating systems

A logical conduit for inter-process communication, allowing data to flow from one process's output to another's input.

asynchronous thread

Created by a parent thread, which resumes execution, allowing both to run concurrently and independently.

logical address

A virtual address generated by the CPU, mapped to a physical address by the MMU.

shared memory and message passing

Shared memory allows processes to communicate via a common memory region. Message passing sends data via OS-mediated messages.

privileged instructions

Restricted to kernel mode, managing critical operations like interrupts or I/O. They can be attempted from user mode

dispatcher in an operating system

The OS component that selects and switches to the next process to run, performing the context switch.

What is unbounded buffer

It has no practical size limit, allowing producers to add items without waiting for space.

New state

Process is initialized. Moves to Ready when resources are allocated.

Ready state

Process is waiting for CPU. Moves to Running when scheduled.

Running state

Process is executing. Moves to Ready if pre-empted. Moves to Waiting if it needs I/O or an event. Moves to Terminated if it completes

Waiting state

Process awaits an event. Moves to Ready when the event occurs.

Termination state

Process has finished but its parent hasn’t reaped it. Fully exits after parent calls wait().

Text

Stores the program’s executable code