Operating System Notes
1. Introduction
Application software: performs specific tasks for the user
System software: operates and controls the computer system and provides a platform to run an application software.
Operating system: program (collection of system softwares) that acts as an interface between the user and hardware.
Why do we need OS ?
Without an OS, we would have bulky and complex apps which would need to have the complex hardware interaction code in the codebase of the app itself. There would be exploitation of resources between apps. There would be no memory protection as well.
OS tries to maximize CPU utilization, lessen process starvation and cause higher priority job execution.
Goals of OS
- Easy-to-use environment to the user to execute programs in a convenient and efficient manner
- Arbitration: Efficient resource management
- Modularity
- Abstraction: Hides the underlying complexity of the hardware
- Easy debugging
- Isolation and protection for the execution of application programs
user -> application programs -> opertaing system -> computer hardwareFunctions of OS/Kernel
i. Process management: scheduling processes and threads on CPUs, creating and deleting user and system processes, suspending and resuming processes, providing mechanisms for process synchronzation or process communication
ii. Memory management: allocating and deallocating memory space as per need, tracking memory being used and by what process
iii. File systems management: creating and deleting files and directories, mapping files into secondary storage, backup support onto a stable storage media
iv. I/O management: to manage and control I/O operations and devices, buffering (data copy between two devices within one job, eg: youtube video buffering), caching, spooling (within differing speed jobs, eg: print spooling, mail spooling)
v. Protection and security
Types of OS
i. Single process operating system: only one process executes at a time from the ready queue.
ii. Batch processing operating system: a user prepares his jobs using punch cards and then submits them to the computer operator who sorts the jobs into batches with similar requirements. The operator then submits the batches to the processor one by one. All the jobs of one batch are executed together.
Drawbacks: priorites can’t be set if a job comes with higher priority, may lead to starvation as a batch may take more time to complete, CPU may become idle during I/O operations, decreased throughput of the system
iii. Multiprogramming operating system: multiple jobs (code and data) are kept in main memory so that the CPU always has one to execute incase some job gets busy with I/O. For a single CPU, this increases CPU utilization. Context switching happens for processes when the current process goes to wait state. CPU idle time is reduced.
The CPU switches to a different program only when the current program pauses to wait for an external input or output (I/O) action, like reading a file or waiting for a printer.
iv. Multitasking operating system: it is a logical extension of multiprogramming. With a single CPU, we are able to run more than one task simultaneously. Context switching and time sharing is used. This increases responsiveness and CPU idle time is further reduced.
The CPU uses time-sharing, giving each task a tiny fraction of time called a “time slice” or “quantum”. It cycles through tasks so fast that they appear to run at the exact same time.
v. Multiprocessing operating system: uses more than 1 CPU in a single computer. This increases reliability because if 1 CPU fails, the other can work. Better throughput. Lesser process starvation.
vi. Distributed operating system (loosely coupled systems): handles jobs that are executed by multiple processors networked to each other. The OS manages many bunches of resources (more than one CPUs, memory and GPUs) to form loosely connected autonomous interconnected computer nodes. The advanatges include resource sharing, computation speed up and reliability.
vii. Real time OS: used for real-time error free computations within tight-time boundaries. Processing of the program must be done in the defined constraints or the system will fail. They are categorized into hard and soft real time systems. They are used in air traffic control system, robots etc.
2. Multi-Tasking vs Multi-Threading
Program: an executable file which contains a certain set of instructions written to complete the specific job or operation on the computer. It is a complied code that is stored in the disk, ready to be executed. It is passive and is not allocated any resources.
Process: program under execution that resides in the computer’s primary memory (RAM). It is active and dynamic. The OS allocates resources to the process for its execution.
Thread (light-weight process): an independent path of execution within a process used to achieve parallelism by dividing a process’s task. Ex: multiple tabs in a browser.
Each thread has its own program counter. The OS schedules these threads depending on the thread scheduling algorithm. A single CPU system doesn't gain from multi-threading technique as threads have to context switch for that single CPU.
Multi-Tasking: The execution of more than one task simultaneously. There is a single CPU that has more than one process being context switched. The OS provides isolation and memory protection to each program that the CPU is executing.
Multi-Threading: The division of a process into sub-tasks called as threads that have their own path of execution. There can be more than or equal to one CPU where the threads are context switched. There is no isolation and memory protection. Resources (user address space, files, signals and signal handlers) are shared among the threads of that process. Each thread has its own stack, thread id, CPU state information (control and status registers, stack pointers) and scheduling information (thread state, priority etc.)
Thread Scheduling: Even though threads are executing within the runtime, all threads are assigned processor time slices by the operating system. Threads are executed based on their priority.
Thread Context Switching: OS saves the current state of the thread and switches to another thread of the same process. This is a fast switching where the CPUs cache state is preserved. The switching of memory address space doesn’t happen while the program counter, register and stack are included in the switch.
Process Context Switching: OS saves the current state of the process and switches to another process by restoring its state. Memory address space is switched. The switching is slower and the CPU’s cache state is flushed.
Benefits of Threads: Improved response time, faster context switches, effective utilization of multiprocessor systems, enhanced throughput of the system, economical and effective resource sharing and utilization.
Types of threads based on level
- User level threads: threads that are managed at the user level. They are implemented as dependent threads. All user-level threads of a process can run on one processor only and only one thread runs at a time. Blocking one user-level thread of a process blocks the entire process. These threads have less context. Scheduling of user-level threads is done by the thread libraries. No hardware support is required. Implementation is easy and simple.
- Kernel level threads: threads that are managed at the kernel level. They are implemented as independent threads. The kernel-level threads of a process can run on different processors concurrently in a multiprocessor environment. Blocking one kernel-level thread of a process does not affect the other threads of the process. These threads have more context. Scheduling of kernel-level threads is done by the operating system. Hardware support is required. Implementation is complicated and difficult.
Multithreading Models
a. Many-to-One: Many user level threads are mapped to single kernel-level thread.
b. One-to-One: Each user level thread is mapped to single kernel-level thread.
c. Many-to-Many: Many user level threads are mapped to multiple kernel-level threads. It allows the OS to create a sufficient number of kernel threads.
Thread Libraries: Thread libraries provide programmer with API for creating and managing threads. There are two primary ways of implementing thread libraries: in user space and kernel level supported by OS. Ex: pthread libraries, java thread, green threads.
Disadvantages of multithreading
- Blocking: Blocking one user-level thread of a process blocks the entire process. If the kernel thread is single threaded, then blocking the kernel thread will block the whole process. Consequently, CPU may remain idle during this period.
- Security: Since, there is an extensive sharing among threads, there is a potential problem of security.
- Maintaining Thread Control Block (TCB) is considered as overhead for the system.
Concurrency: It is the execution of multiple instruction sequences at the same time when there are several process threads running in parallel.
3. Components of OS
Kernel: core component of the OS that directly interacts with the hardware and performs the most crucial tasks. It is also the very first part of OS to load on start-up.
User space: this is where the application softwares run that dont have privileged access to the underlying hardware. It interacts with the kernel via CLI or GUI.
Shell/Command Interpreter: part of the OS that receives commands from the users and gets them executed.
Types of Kernels
i. Monolithic kernel: All functions are in the kernel itself which makes it bulky in size and requires a high memory to run. It is less reliable since if one module crashes the whole kernel is down. Provides high performance as communication is fast. Eg: Linux, Unix, MS-DOS
ii. Micro kernel: Only major functions (memory management and process management) are in the kernel. File management and I/O management are in user space. It is smaller in size and more reliable and stable. Performance is slow. There is an overhead in switching between user mode and kernel mode. Eg: L4 Linux, Symbian OS, MINIX
iii. Hybrid kernel: Combined approach that takes advantage of both worlds. File management happens in the user space and the rest happens in the kernel. This has the speed and design of monolithic and modularity and stability of the micro kernel. Inter process communication (IPC) happens with less overheads.
iv. Nano/Exo kernels
Dual Mode Operations
A processor supports two modes of instruction execution to provide protection and security to the user application programs and the operating system from unauthorized users.
Mode bit 0 Kernel mode (Privileged mode): A process running in kernel mode has direct access to the hardware and full access to the machine instruction set. The OS runs in kernel mode. I/O operations, context-switching, clearing the memory map, communicating with other programs are some examples of privileged instructions.
Mode bit 1 User mode (Non - privileged mode): A process running in the user mode has no access to the hardware and limited access to the machine instruction set. Reading the time of the clock, reading the status of processor, generate trap are examples of non-privileged instructions.
Communication happens between the user mode and the kernel mode using Inter Process Communication (IPC).
System Call
User application programs interact with the kernel using system calls to request a service from the kernel for which it doesn’t have permission to perform. The transition from user mode to kernel mode is done by software interrupts.
Types of System Calls
a. Process control: end, abort, load, execute, create process, terminate process, get process attributes, set process attributes, wait for time, wait event, signal event, allocate and free memory
b. File management: create file, delete file, open, close, read, write, reposition, get file attributes, set file attributes
c. Device management: request device, release device, read, write, reposition, get device attributes, set device attributes, logically attach or detach devices
d. Information maintenance: get time or date, set time or date, get system data, set system data, get process, file, or device attributes, set process, file, or device attributes
e. Communication management: create, delete communication connection, send, receive messages, transfer status information, attach or detach remote devices
Examples of Unix System Calls
i. Process control: fork(), exit(), wait()
- Fork(): system call used to create child processes. It returns 0 to the newly created child processes and returns the process id to the parent process on successful creation of the child process and negative value to the parent process on the unsuccessful creation of the child process. For a program with ’n’ fork() system calls, the number of child processes created is (2^n)-1.
ii. File management: open(), read(), write(), close(), chmod(), umask(), chown()
iii. Device management: ioctl(), read(), write()
iv. Information management: getpid(), alarm(), sleep()
v. Communication: pipe(), shmget(), mmap()
4. What happens when you power on a computer?
- Power-on and firmware initialization (BIOS/UEFI): The moment you press the power button, the CPU starts executing instructions stored in firmware on the motherboard — either legacy BIOS (Basic input-output system chip) or the more modern UEFI (Unified extensible firmware interface). This firmware runs a POST (Power-On Self-Test), which checks that essential hardware (CPU, RAM, keyboard, storage controllers) is present and functioning. If something’s broken, you’ll usually hear beep codes or see an error before the OS even loads.
- Locating a bootable device: The firmware checks its configured boot order (SSD, HDD, USB, network, etc.) and looks for a valid bootloader on one of these devices. UEFI systems typically read this from an EFI System Partition. BIOS systems read the Master Boot Record (MBR) on the disk.
- Bootloader execution: The bootloader is a small program whose only job is to load the operating system’s kernel into memory. Windows uses the Windows Boot Manager, Linux commonly uses GRUB and macOS uses its own boot loader tied to the Secure Boot chain. If there are multiple OSes installed, this is where you’d see a menu to choose between them.
- Kernel initialization: The bootloader hands control to the OS kernel, which is the core of the operating system. The kernel: Initializes memory management, detects and loads drivers for hardware (disk controllers, graphics, network cards, etc.), sets up process scheduling and interrupt handling, mounts the root filesystem.
- System and service startup: Once the kernel is running, it starts the first user-space process:
- Linux:
systemd(or olderinit) starts background services (networking, logging, display manager, etc.) in a dependency order - Windows:
wininit.exeand the Session Manager, which brings up core Windows services - macOS:
launchd, which manages all system and user services
6. User session and login: The OS starts a login manager or login screen. Once you authenticate, it loads your user session — desktop environment, taskbar, background apps, and whatever startup programs are configured to launch automatically.
7. Steady state: At this point, the OS is fully running: it’s managing memory, scheduling processes across CPU cores, handling file I/O, and responding to your input through the desktop environment.
5. Storage Devices
Primary memory: comprises of register, cache and main memory.
A register is the smallest unit of storage (instruction, storage address, any such data) and it is part of the CPU itself. They are used to quickly accept, store and transfer data and instructions that can be used immediately by the CPU.
Cache temporarily stores frequently used instructions and data for quicker processing by the CPU.
The main memory is the RAM.
Secondary memory: comprises of electronic disk, magnetic disk, optical disk, magnetic tapes etc. It is the secondary media on which computer can store data and programs.
Comparison:
- Cost: primary storage (with registers being the most expensive) costs more than secondary storage.
- Access speed: primary storage (registers > cache> main memory) has higher access speed than secondary memory.
- Storage size: secondary memory has more space than primary memory
- Volatility: Primary memory is volatile while secondary memory is non-volatile.
6. Process
A program is a compiled code (set of instructions and data) that is ready to execute. A program under execution is a process.
Architecture of Process
A process comprises of:
- Process attributes (PCB)
- Stack: load variables, function arguments and return values
- Heap: dynamically allocated variables
- Data: global and static data
- Text: compiled code loaded from the disk
The context of a process includes the process attributes and runtime stack information. The user address space includes dynamic data, static data and the code section.
Attributes of Process
An attribute of a process allows identify a process uniquely. All processes are being tracked by the OS using a table like data structure called Process Table. Each entry in this table is a Process Control Block (PCB). A PCB is a double linked list data structure that stores info/attributes of a process. The PCBs of all the processes are stored in the main memory.
PCB Structure
- Process ID: unique identifier
- Program counter (PC): next instruction address of the program
- Process state: stores process state
- Priority: decides when a process gets CPU time
- Registers: when the time slice of a running process expires, the current value of the process specific registers would be stored in the PCB and the process is swapped out. When the process is scheduled to run again, the register value is read from the PCB and written to the CPU registers.
- List of open files
- List of open devices
Process States ( 7 State Model )
As a process executes, it changes state across its lifetime. When the process is present in the ready, run or wait state, it resides in the main memory. When present in suspend ready or suspend block state, it resides in the secondary memory.
- New: when the OS is about to pick the program and convert it into process or when the process is being created.
- Ready: the process is in the memory, waiting in the ready queue to be assigned to a processor.
- Running: CPU is executing the instructions of the process.
- Blocked/Waiting: The process cannot continue because it is waiting for an event such as I/O completion, user input, or access to a locked resource. Once the event is complete, it moves back to the ready state.
- Terminated: when the process has finished execution. The PCB entry is removed from the process table and frees all resources allocated to it.
- Suspend Ready: A ready process that has been swapped out of main memory and placed in secondary storage due to memory shortage. When brought back to main memory, it returns to the ready state.
- Suspend Block: A blocked process that has been swapped out of main memory and placed in secondary storage due to memory shortage. When brought back to main memory, it returns to the blocked state.
Process Queues
a. Job Queue: when a process is in a new state, it is present in the secondary memory. Job scheduler/ Long term scheduler (LTS) picks process from the pool and loads them into the memory for execution.
b. Ready Queue: processes are in ready state in the main memory. CPU scheduler/ Short term scheduler picks the process from ready queue and dispatches it to CPU.
c. Waiting Queue: processes in wait state.
Schedulers
- Long term scheduler: It is responsible for creation and bringing of new processes into the main memory, ie, the new to ready state transition. It controls the degree of multi-programming (the number of processes in the memory). It should generate a good mix of CPU and I/O bound processes for efficient resource utilization.
- Medium term scheduler: It is responsible for carrying out swapping, ie. ready to suspend ready, suspend ready to ready, block to suspend block and suspend block to block.
Swap-out: suspending the process from the main to secondary memory
Swap-in: resuming the process by bringing it from secondary to main
- Short term scheduler: It is responsible for selecting a process from the ready state to be executed, ie. ready to run state transition.
Dispatcher
The dispatcher is responsible for loading the job selected by the short term scheduler onto the CPU. It performs context switching.
Context-Switching
Context switching refers to saving the context of the process which was being executed by the CPU and loading the context of the new process that is being scheduled to be executed by the CPU. When this happens, the kernel saves the context of the old process in its PCB and loads the saved context of the new process scheduled to run. It is a pure overhead as the system does no useful work while switching. The speed of switching varies from machine to machine depending on the memory speed, number of registers to be copied etc.
Swapping
Time sharing systems have a medium term scheduler (MTS) that removes processes temporarily out of main memory to disk and makes the memory available to other processes. At a later point, the system swaps back the process from disk to main memory. Removing processes from the memory reduces the degree of multi-programming. Swapping is necessary to improve process mix and free up memory upon overcommitment.
Orphan Process
The process whose parent process has been terminated (crashes) and the child is still running. It gets adopted by the init process, which is the first process of OS.
Example: You run a background script from a terminal, then close the terminal before the script finishes. That script becomes an orphan and gets adopted by init.
Zombie Process
A process that has finished executing but still has an entry in the process table because its parent hasn’t yet read its exit status.
A zombie consumes almost no resources, just a slot in the process table but if a parent process is buggy and never calls wait(), zombies can accumulate. Enough of them can exhaust the process table, preventing new processes from being created (a form of resource leak).
Normally, the parent calls wait() and the zombie disappears immediately. This is called reaping the zombie process. If the parent itself dies without reaping its zombie children, those zombies become orphans too and get re-parented to init/systemd, which periodically calls wait() on its adopted children specifically to clear them out.
7. Process Scheduling
Process scheduling is the basis of multi-programming OS. Many processes are kept in memory at a time. When a process must wait or time quantum expires, the OS takes the CPU away from that process and gives the CPU to another process.
Process scheduling includes long-term scheduler (Job scheduler), medium-term scheduler and short-term scheduler (CPU scheduling).
8. CPU Scheduling
Whenever the CPU becomes idle, the STS selects one process from the ready queue to be executed.
Non-preemptive scheduling: Once CPU has been allocated to a process, the process keeps the CPU until it releases CPU either by terminating or by switching to wait-state. This may cause starvation as process with long burst time may starve a less burst time process. Low CPU utilization happens here.
Preemptive scheduling: CPU is taken away from a process after time quantum expires along with terminating or switching to wait-state. There are less chances of starvation and high CPU utilization.
Starvation: A situation where a process waits indefinitely for a resource (usually the CPU) because other processes keep getting prioritized ahead of it. Most commonly seen in Priority Scheduling. If high-priority processes keep arriving, a low-priority process might never get scheduled. It just sits in the ready queue forever, “starved” of CPU time.
Aging: Gradually increasing the priority of processes the longer they wait. Eventually even a low-priority process’s priority becomes high enough to guarantee it runs.
Convoy Effect: Convoy Effect is a situation where many processes, who need to use a resource for a short time, are blocked by one process holding that resource for a long time. It will have major effect on average WT of different processes. This causes poor resource management.
Scheduling Criteria
CPU scheduling will occur when:
- A new process arrives into the Ready state.
- A process undergoes Wait → Ready state transition.
- A process undergoes Run → Wait state transition for an I/O request.
- A process undergoes Run → Ready state transition every q second where q is the time slice.
- The priority of a ready process is higher than the priority of a running process.
Goals of CPU Scheduling
- maximize CPU utilization and throughput (number of processes completed per unit time) of the system
- minimize response time, turnaround time and waiting time of the processes
Process Times
i. Arrival Time (AT): The time at which the process arrives into the ready queue.
ii. Burst Time (BT): The time required by the process for its complete execution.
iii. Completion Time (CT): The time by which a process completes its execution post arrival.
iv. Turnaround Time (TAT): The time difference between completion and arrival times of a process. TAT = CT — AT.
v. Waiting Time (WT): The time spent waiting for the CPU to complete the execution. WT = TAT — BT.
vi. Response Time (RT): The time difference between the first response and arrival times of a process, ie. the time duration between process getting into ready queue and process getting CPU for the first time.
Scheduling Algorithms
i. First Come First Serve (FCFS): Whichever process comes first in the ready queue is given the CPU first. If two or more processes have the same arrival times, then the processes are assigned based on their process ids. It is free from starvation but it suffers from convoy effect.
ii. Shortest Job First (SJF): It is a non-preemptive algorithm where processes are assigned to the CPU based on the shortest burst time (should be known prior execution). Two or more processes having the same burst time are assigned CPU based on their arrival times. SJF behaves like FCFS if all the processes have the same burst time. There is a chance of starvation in SJF. It minimizes the average response time of the processes. This can suffer from convoy effect if the very first process that came in the ready state is having a large BT.
iii. Shortest Remaining Time First (SRTF): It is a preemptive algorithm where the processes are assigned CPU based on their shortest remaining burst times. SRTF behaves like SJF when all the processes have the same arrival time. It minimizes the average TAT and WT of the processes. If the shorter processes keep on arriving then the longer processes may starve. There are less chances of starvation. There is no convoy effect.
iv. Longest Remaining Time First (LRTF): It is a preemptive algorithm where the processes are assigned CPU based on their longest remaining burst times. It minimizes the average response time of the processes It favors CPU bound processes and is free from starvation.
v. Priority based Scheduling: Priority scheduling can either be pre-emptive or non-preemptive. In preemptive priority scheduling, a process is voluntarily preempted whenever a higher priority process arrives. In non-preemptive priority scheduling, the scheduler picks up the highest priority process. If all the processes have equal priority, then priority scheduling behaves as FCFS. SJF is a special case of general priority scheduling with priority inversely proportional to BT.
The lower priority jobs may face indefinite waiting leading to starvation. The solution to this is aging.
vi. Round Robin Scheduling (RR): It is a preemptive FCFS based on the concept of time quantum or time slice. If the time quantum is too small, then the number of context switches (overhead) will increase and the average response time will decrease. If the time quantum is too large, then the number of context switches (overhead) will decrease and the average response time will increase. If the time quantum is greater than the burst times of all the processes, RR scheduling behaves as FCFS. RR is designed for time sharing systems. There are low chances of starvation and no convoy effect.
vii. Highest Response Ratio Scheduling: It is a non preemptive algorithm where processes are assigned CPU based on their highest response ratio. It is free from starvation. It favors the shorter jobs and limits the waiting time of longer jobs.
Response Ratio = (WT + BT) / BT
viii. Multilevel Queue Scheduling (MLQ): The ready queue is divided into multiple queues depending upon priority. High priority processes will be placed in top-level ready queue and low priority process will be placed in bottom level ready queue. Only after completion of all the processes, from top level ready queue the further level ready queue processes will be
scheduled. Each queue has its own scheduling algorithm.
System processes created by the OS have higher priority than interactive processes (foreground processes) that need user input (I/O) than batch processes (background process) that runs silently with no user input required.
Scheduling among different sub-queues is implemented as fixed priority preemptive scheduling. If an interactive process comes & batch process is currently executing. Then, batch process will be preempted. Only after completion of all the processes from the top-level ready queue, the
ix. Multilevel feedback queue scheduling (MLFQ): Multiple sub-queues are present and the process move between them based on their BT. If a process uses too much CPU time, it will be moved to lower priority queue. This scheme leaves I/O bound and interactive processes in the higher-priority
queue. In addition, a process that waits too much in a lower-priority queue may be moved to a higher priority queue. This form of aging prevents starvation. This suffers from less starvation than MLQ and is flexible and configurable to match specific system design requirements.
9. Process Synchronization
Process synchronization techniques play a key role in maintaining consistency of shared data.
Processes can be categorized into being cooperative and independent. If the execution of one process affects or is affected by other process then those processes are said to be cooperative process. Otherwise, they are independent. Processes must be cooperative to be synchronized.
Critical Section (CS)
It is the segment of code where processes/threads access shared resources such as common variables and files and perform write operations on them. Ex: count = count + 1
Race condition
A race condition occurs when two or more threads can access shared data and try to change it at the same time. The result of the change in data is dependent on the thread scheduling algorithm. To avoid race condition, only one process is allowed to enter into the critical section.
Solutions to race condition: atomic operations on critical section code, mutual exclusion using locks and semaphores
A simple flag variable cannot be used to solve the problem of race condition.
Any solution to the critical section problem must satisfy three conditions:
i. Mutual Exclusion (ME): Only one process can be in the critical section at a time
ii. Progress: If no process is in the critical section, one of the waiting processes must be allowed in. The decision can’t be postponed indefinitely
iii. Bounded waiting: A process must not wait forever to enter its critical section. There’s a limit on how many times others can enter before it does.
An overview of solutions to the synchronization problem
i. Software type: Lock variables, Strict alternation or Decker’s algorithm, Petersons algorithm
ii. Hardware type: TSL (Test and Set Lock) instruction set
iii. OS type: Counting semaphore, Binary semaphore
iv. Programming language compiler support type: Monitors
Lock variable
A lock variable is a simple shared variable used to try to achieve mutual exclusion in software.
int lock = 0;
while (lock == 1)
; // wait
lock = 1; // acquire
// critical section
lock = 0; // releaseThis does not work. Checking lock and setting it are two separate steps, so two threads can both see lock == 0 before either sets it to 1, and both enter the critical section. It’s the standard example of why you need atomicity, and why Peterson’s solution or hardware support is needed.
Mutex
A mutex is a properly implemented lock. It looks similar from the outside (lock/unlock), but:
- Acquiring is atomic. It’s built on hardware instructions like test-and-set or compare-and-swap, so the check-and-set can’t be interleaved.
- Waiters sleep. The OS blocks waiting threads instead of making them spin.
- Ownership. The thread that locks it must unlock it.
If both processes try to enter at the same time, both set their flags, but turn can only hold one value because whichever process writes it last “loses” and waits. The other proceeds. When it leaves and sets its flag to false, the waiting process gets in. It satisfies the three requirements of a critical section solution.
A mutex has two operations:
- acquire (lock): take the mutex. If it’s already held by someone else, the caller blocks (waits) until it’s free.
- release (unlock): give the mutex back, allowing one waiting thread to proceed.
pthread_mutex_t m = PTHREAD_MUTEX_INITIALIZER;pthread_mutex_lock(&m);
// critical section: only one thread here at a time
counter++;
pthread_mutex_unlock(&m);Without a lock, two threads doing counter++ can interleave. Each reads the same old value, adds one, and writes back, so one increment is lost. This is a race condition. Wrapping the update in a lock makes it effectively atomic.
Mutexes rely on hardware atomic instructions such as test-and-set or compare-and-swap, plus help from the OS scheduler to put threads to sleep and wake them up. This is why they work reliably on modern hardware, unlike Peterson’s solution.
The disadvantages of mutex/locks
- Deadlocks: thread A holds lock 1 and waits for lock 2, while thread B holds lock 2 and waits for lock 1. Neither can proceed. A common fix is to always acquire locks in a consistent order.
- Debugging
- Contention: when a thread acquires a lock, the other threads will be busy waiting. If the thread that has acquired the lock dies, then all other threads will be in infinite waiting.
- Priority inversion: a low-priority thread holding a lock can block a high-priority one.
- Forgetting to unlock: especially on early returns or exceptions. Languages offer helpers (like C++ std::lock_guard or Python’s with lock:) to release automatically.
- Holding locks too long: this hurts performance by serializing work.
“Lock” is the general concept (anything that enforces exclusive access), and a mutex is the most common kind. A spinlock is also a lock, but one that busy-waits.
Strict Alternation
Processes take turns using a shared variable turn, which says whose turn it is to enter the critical section.
int turn = 0;
// Process 0
while (true) {
while (turn != 0)
; // busy wait
// critical section
turn = 1; // hand over to P1
// remainder section
}
// Process 1
while (true) {
while (turn != 1)
;
// critical section
turn = 0; // hand over to P0
// remainder section
}Mutual exclusion holds, because only the process whose number matches turn can enter. Progress fails. The processes are forced to alternate P0, P1, P0, P1. If P1 is slow or busy in its remainder section (or has terminated), P0 finishes its critical section, sets turn = 1, and then can never enter again, even though the critical section is free and P1 isn’t using it. A process outside its critical section is blocking another, which violates the progress requirement. Other drawbacks: busy waiting, and it forces the two processes to run at the same rate.
Dekker’s algorithm
Dekker's algorithm (credited to Th. J. Dekker, and often called the first correct software solution to mutual exclusion) keeps the turn idea but adds per-process flags, so a process only defers when the other one actually wants to enter.
bool wants[2] = {false, false};
int turn = 0;
// Process i (j = the other process)
wants[i] = true;
while (wants[j]) { // other also wants in
if (turn == j) { // and it's their turn
wants[i] = false; // back off
while (turn == j)
; // wait until it's my turn
wants[i] = true; // try again
}
}
// critical section
turn = j; // give priority to the other
wants[i] = false;
// remainder sectionHow it works:
i. Set your flag to say you want in.
ii. If the other process doesn’t want in, enter immediately (this is what fixes the progress problem).
iii. If both want in, turn breaks the tie: the process whose turn it is keeps its flag up and enters, while the other lowers its flag, waits for turn to change, and retries.
iv. On exit, pass turn to the other process and clear your flag.
Dekker’s satisfies mutual exclusion, progress, and bounded waiting.
Peterson’s solution
A software-based solution to the critical section problem for two processes, proposed by Gary Peterson in 1981. It guarantees mutual exclusion without needing any special hardware instructions or OS support, just plain shared variables.
Each process announces its interest in entering the critical section, then politely gives the other process priority. Two shared variables make this work:
- flag[2]: flag[i] = true means process i wants to enter the critical section.
- turn: indicates whose turn it is to enter if both want to.
Algorithm
For process P0 (with i = 0, j = 1):
do {
flag[i] = true; // I want to enter
turn = j; // but you go first, if you also want to
while (flag[j] && turn == j)
; // busy wait
// ---- critical section ----
flag[i] = false; // I'm done
// ---- remainder section ----
} while (true);P1 runs the same code with i = 1, j = 0.
If both processes try to enter at the same time, both set their flags, but turn can only hold one value because whichever process writes it last “loses” and waits. The other proceeds. When it leaves and sets its flag to false, the waiting process gets in. It satisfies the three requirements of a critical section solution.
Limitations
- Only works for two processes. Generalizations exist (such as the filter lock), but they are more complex.
- Busy waiting: the waiting process burns CPU cycles in a spin loop.
- Fails on modern hardware without memory barriers. Compilers and CPUs may reorder instructions (for example, reordering the write to turn and the read of flag[j]), which breaks the algorithm. Real systems rely on atomic instructions like test-and-set or compare-and-swap, and on mutexes and semaphores built on top of them.
Because of these limits, it is mainly taught as an elegant demonstration of how mutual exclusion can be achieved in software, rather than something used in production.
Test and Set Lock
It is a single hardware instruction (not a whole instruction set) that reads a memory location and sets it to 1 as one atomic, indivisible operation. This is the missing piece that made the naive lock variable fail: there, “check the lock” and “set the lock” were two separate steps that could be interleaved. TSL fuses them into one.
Conceptually, TSL REGISTER, LOCK does this atomically:
bool test_and_set(bool *lock) {
bool old = *lock; // read the old value
*lock = true; // set it to 1
return old; // return what it was before
}Because it is atomic, no other CPU or interrupt can slip in between the read and the write. On a multiprocessor, the hardware locks the memory bus (or the cache line) for the duration of the instruction, so other processors cannot touch that location in the middle of it.
Building a lock with it (a spinlock)
bool lock = false; // false = free, true = held
void acquire() {
while (test_and_set(&lock))
; // returns true -> someone holds it, keep spinning
}
void release() {
lock = false;
}How it works: If the lock is free (false), test_and_set returns false and sets it to true in the same step. The caller sees false, exits the loop, and now owns the lock.
If the lock is held (true), it returns true, so the caller keeps spinning. Setting it to true again changes nothing.
Only one thread can ever see false, which guarantees mutual exclusion.
The assembly-style version (as in Tanenbaum)
enter_region:
TSL REGISTER, LOCK ; copy LOCK to register and set LOCK to 1
CMP REGISTER, #0 ; was LOCK zero?
JNE enter_region ; if nonzero, lock was set, so loop
RET ; return, caller is in the critical section
leave_region:
MOVE LOCK, #0 ; store 0 in LOCK
RETProperties and drawbacks
- Mutual exclusion: guaranteed.
- Busy waiting: waiting threads spin and waste CPU, so this is a spinlock. It is fine for very short critical sections but poor for long ones.
- No bounded waiting: nothing orders the waiters, so an unlucky thread can keep losing the race and starve. (Variants add a waiting array to fix this.)
- Priority inversion: a high-priority process spinning for a lock held by a preempted low-priority process can spin forever on a single CPU.
- Cache traffic: every TSL is a write, so many spinning CPUs cause heavy bus contention. A common improvement is test-and-test-and-set: spin on a plain read (while (lock) ;) and only attempt TSL when the lock looks free.
Monitor
A monitor is a high-level synchronization construct that bundles shared data, the procedures that operate on it, and the synchronization needed to protect it, all into a single module. Instead of the programmer manually pairing lock/unlock calls (as with mutexes and semaphores), the language or runtime guarantees that only one thread can be active inside the monitor at a time. It was proposed by Hoare (1974) and Brinch Hansen (1973).
Think of a monitor as a room with a single door. Threads enter by calling one of its procedures. If someone is already inside, newcomers wait outside. When the occupant leaves (or waits), the next thread enters.
Mutual exclusion is automatic. You can’t forget to unlock, because you never lock explicitly.
monitor BoundedBuffer {
int buffer[N];
int count = 0;
condition notFull, notEmpty;
procedure insert(item) {
if (count == N) wait(notFull);
buffer[...] = item;
count++;
signal(notEmpty);
}
procedure remove() {
if (count == 0) wait(notEmpty);
item = buffer[...];
count--;
signal(notFull);
return item;
}
}No semaphores, no explicit mutex. The monitor handles exclusion, and condition variables handle waiting.
Parts of a monitor
- Shared data: private, only accessible through the monitor’s procedures.
Procedures: the only entry points; at most one thread executes in them at a time. - Entry queue: threads waiting to get in.
- Condition variables: let a thread inside the monitor wait for a condition (wait(c)) and let others wake it (signal(c)).
When a thread calls wait(c), it releases the monitor and sleeps on c’s queue, so another thread can enter. This is the same condition variable idea from earlier, and a monitor is essentially a mutex plus condition variables packaged together by the language.
Signal semantics: who runs after signal?
If thread A signals and wakes thread B, both can’t be inside at once. Two classic policies:
- Hoare style (signal-and-wait): the signaler immediately yields to the woken thread. The condition is guaranteed true when B resumes, so if is enough.
- Mesa style (signal-and-continue): the signaler keeps running, and B waits until it can re-enter. The condition may have changed by then, so B must recheck in a while loop. This is what real systems use (Java, pthreads, C#).
Monitors in real languages
Java: every object has a built-in monitor. synchronized methods/blocks provide exclusion, and wait(), notify(), notifyAll() act as the condition operations (one implicit condition per object).
C#: lock statement and Monitor.Wait/Pulse.
C/C++: no built-in monitors, but you can emulate them with a mutex plus condition variables (e.g., std::mutex and std::condition_variable).
class Counter {
private int count = 0;
public synchronized void increment() { count++; }
public synchronized int get() { return count; }
}Conditional variable
A condition variable is a synchronization primitive that lets a thread wait until some condition becomes true, without busy-waiting. It’s always used together with a mutex. Contention doesn’t happen here.
Suppose a consumer thread needs to wait until a queue is non-empty. Without a condition variable, you’d write:
while (true) {
lock(&m);
if (!queue_empty()) break;
unlock(&m); // spin: wasteful
}This burns CPU. A condition variable lets the thread sleep until another thread signals that the state has changed.
The operations
- wait(cv, mutex): atomically releases the mutex and puts the thread to sleep. When woken, it re-acquires the mutex before returning.
- signal(cv) (or notify_one): wakes up one waiting thread.
- broadcast(cv) (or notify_all): wakes up all waiting threads.
Typical usage (producer-consumer)
pthread_mutex_t m = PTHREAD_MUTEX_INITIALIZER;
pthread_cond_t cv = PTHREAD_COND_INITIALIZER;
// Consumer
pthread_mutex_lock(&m);
while (queue_empty()) { // always a while loop
pthread_cond_wait(&cv, &m); // releases m, sleeps, re-locks m
}
item = dequeue();
pthread_mutex_unlock(&m);
// Producer
pthread_mutex_lock(&m);
enqueue(item);
pthread_cond_signal(&cv); // wake a waiting consumer
pthread_mutex_unlock(&m);Semaphores
A semaphore is a synchronization primitive built around an integer counter that equals the number of resources. It controls access to shared resources by letting threads wait until the counter is positive and signal when they’re done. It was introduced by Edsger Dijkstra in 1965. Multiple threads can go and execute C.S concurrently. Allows multiple program threads to access the finite instance of resources whereas mutex allows multiple threads to access a single shared resource one at a time.
To overcome the need for busy waiting, we can modify the definition of
the wait () and signal () semaphore operations. When a process executes the wait () operation and finds that the semaphore value is not positive, it must wait. However, rather than engaging in busy waiting, the process car block itself. The block- operation places a process into a waiting queue associated with the semaphore, and the state of the process is switched to the Waiting state. Then control is transferred to the CPU scheduler, which selects another process to execute.
A process that is blocked, waiting on a semaphore S, should be restarted
when some other process executes a signal () operation. The process is
restarted by a wakeup () operation, which changes the process from the
waiting state to the ready state. The process is then placed in the ready
queue.
The two operations: Both are atomic
- wait (also P, down, acquire): if the counter is greater than 0, decrement it and continue. If it is 0, block until another thread increments it.
- signal (also V, up, release, post): increment the counter, waking one waiting thread if there is any.
wait(S): while (S <= 0) block; S--;
signal(S): S++; wake one waiter;Two kinds
- Counting semaphore: the counter can be any non-negative value. It models a pool of N identical resources, like 5 database connections or 10 buffer slots.
- Binary semaphore: the counter is only 0 or 1. It behaves much like a mutex, though without ownership (any thread can signal it).
Pitfalls
- Deadlock: swapping the order of wait(&empty) and wait(&mutex) in the producer can leave it holding the mutex while waiting for a slot, blocking consumers forever.
- Forgetting to signal: leaves waiters blocked indefinitely.
- No ownership: because any thread can signal, bugs like an accidental extra post silently break the invariant.
- Priority inversion: possible here too, and harder to mitigate than with mutexes because there is no owner to boost.
Condition variable vs. semaphore
A semaphore keeps a count, so a “signal” is remembered even if nobody is waiting yet. A condition variable has no memory: it is purely a wait/wake mechanism, and the actual condition lives in your own shared variables. Condition variables are more flexible for arbitrary conditions (for example, “buffer is full” or “all workers finished”), while semaphores are simpler for counting resources.
The Dining Philosophers Problem
A classic synchronization problem proposed by Edsger Dijkstra in 1965. It elegantly illustrates the challenges of deadlock, starvation, and mutual exclusion when multiple processes compete for shared resources.
The Setup: 5 philosophers sit around a circular table. 5 forks (chopsticks), one placed between each pair of philosophers. Each philosopher alternates between thinking and eating.To eat, a philosopher needs both the left and right fork. After eating, they put both forks down and go back to thinking.
The analogy is as follows. Philosophers are processes or threads. Forks are non-shareable resources (locks, devices, files). Eating refers to executing in critical section. Deadlock refers to circular wait on locks in multu-threaded programs. Starvation refers to a thread never acquiring all needed locks.
The Problem: A philosopher can only pick up one fork at a time, and a fork can only be held by one philosopher at a time. This creates a resource sharing conflict. Three challenges arise:
i. Deadlock: If every philosopher simultaneously picks up their left fork, each one is now waiting for their right fork, which is held by the neighbor to their right, who is also waiting. Everyone waits forever. Nothing ever proceeds.
P0 holds fork0, waiting for fork1
P1 holds fork1, waiting for fork2
P2 holds fork2, waiting for fork3
P3 holds fork3, waiting for fork4
P4 holds fork4, waiting for fork0
This is a circular wait. One of the four necessary conditions for deadlock.
ii. Starvation: Even if deadlock is avoided, a philosopher might never get to eat if their neighbours keep eating in turns, always holding one of the forks the middle philosopher needs.
iii. Mutual Exclusion: A fork cannot be used by two philosophers simultaneously. It’s a non-shareable resource.
Solution 1: Allow only 4 Philosophers at a Time
Introduce a room semaphore that allows at most 4 philosophers to sit and try to eat simultaneously. With only 4 philosophers competing for 5 forks, the pigeonhole principle guarantees at least one philosopher always has both forks available.
semaphore fork[5] = {1, 1, 1, 1, 1};
semaphore room = 4; // only 4 allowed to try eating at once
// Philosopher i
while (true) {
think();
wait(room); // enter the room
wait(fork[i]); // pick up left fork
wait(fork[(i+1) % 5]); // pick up right fork
eat();
signal(fork[(i+1) % 5]); // put down right fork
signal(fork[i]); // put down left fork
signal(room); // leave the room
}Solution 2: Asymmetric Solution (Odd/Even)
Make philosophers behave differently based on whether their number is odd or even. Even philosophers pick up left fork first, then right. Odd philosophers pick up right fork first, then left. Breaking the symmetry means not everyone grabs the same side simultaneously. Circular wait is impossible because at least two adjacent philosophers try in opposite orders.
// Philosopher i
while (true) {
think();
if (i % 2 == 0) {
wait(fork[i]); // left first
wait(fork[(i+1) % 5]); // then right
} else {
wait(fork[(i+1) % 5]); // right first
wait(fork[i]); // then left
}
eat();
signal(fork[i]);
signal(fork[(i+1) % 5]);
}Solution 3: Monitor Based
Get pranamya’s stories in your inbox
Join Medium for free to get updates from this writer.
Each philosopher has a state: THINKING, HUNGRY, or EATING. A philosopher can only eat if neither neighbour is eating. This is enforced using a monitor with condition variables. pickup() sets state to HUNGRY and calls test(); only transitions to EATING if both neighbours aren’t eating. If it can’t eat, it blocks on self[i].wait(). putdown() sets state back to THINKING, then calls test() on both neighbours, waking them up if they can now eat
monitor DiningPhilosophers {
enum {THINKING, HUNGRY, EATING} state[5];
condition self[5];
void pickup(int i) {
state[i] = HUNGRY;
test(i); // try to eat
if (state[i] != EATING)
self[i].wait(); // block if can't eat
}
void putdown(int i) {
state[i] = THINKING;
test((i + 4) % 5); // check left neighbour
test((i + 1) % 5); // check right neighbour
}
void test(int i) {
if (state[(i+4)%5] != EATING &&
state[i] == HUNGRY &&
state[(i+1)%5] != EATING) {
state[i] = EATING;
self[i].signal(); // wake up philosopher i
}
}
// initialization
initialization_code() {
for (int i = 0; i < 5; i++)
state[i] = THINKING;
}
}# Philosopher Process
DiningPhilosophers.pickup(i);
eat();
DiningPhilosophers.putdown(i);The Producer-Consumer Problem (Bounded Buffer Problem)
It is a classic synchronization problem that illustrates how multiple processes/threads can safely share a common, limited resource.
Problem: You have two types of processes sharing a fixed-size buffer:
- Producer: generates data and places it into the buffer
- Consumer: removes data from the buffer and processes it
The producer must not add data when the buffer is full. Otherwise data is lost due to buffer overflow. The consumer must not remove data when the buffer is empty. Otherwise it reads garbage and crashes. The producer and the consumer must not access the buffer at the same time. You get a race condition, corrupting the data structure.
Solution: Using three semaphores
- Mutex: Ensures mutual exclusion such that only one process touches the buffer at a time. Initial value = 1
- Empty: counts empty slots in the buffer. Initial value: N (buffer size)
- Full: counts filled slots in the buffer. Initial value: 0
#define BUFFER_SIZE 5
typedef struct {
// item type, e.g., int
} item;
item buffer[BUFFER_SIZE];
int in = 0; // next free position to produce into
int out = 0; // next position to consume from
semaphore mutex = 1; // binary semaphore for mutual exclusion
semaphore empty = BUFFER_SIZE; // counts empty slots
semaphore full = 0; // counts filled slotsThe buffer is treated as circular. In and out wrap around using modulo arithmetic.
Producer Process
item nextProduced;
while(true) {
// produce an item in nextProduced
wait(empty); // decrement empty slots (block if 0)
wait(mutex); // acquire exclusive access
// add item to buffer
buffer[in] = nextProduced;
in = (in + 1) % BUFFER_SIZE;
signal(mutex); // release exclusive access
signal(full); // increment filled slots
}Consumer Process
item nextConsumed;
while(true) {
wait(full); // decrement filled slots (block if 0)
wait(mutex); // acquire exclusive access
// remove item from buffer
nextConsumed = buffer[out];
out = (out + 1) % BUFFER_SIZE;
signal(mutex); // release exclusive access
signal(empty); // increment empty slots
// consume the item in nextConsumed
}Semaphore primitives
wait(S) {
while (S <= 0)
; // busy wait (in practice, process is blocked, not spun)
S--;
}
signal(S) {
S++;
}The wait(empty) and wait(full) happen before wait(mutex). If the mutex where to be acquired first and then blocked on empty or full, you’d be holding the lock while waiting, causing a deadlock. By checking buffer space before acquiring the lock, a blocked producer/consumer doesnt hold mutex hostage.
Walkthrough Example: Say buffer size = 5, currently 2 items in it.
- empty = 3, full = 2
- Producer wants to add an item: wait(empty) → empty becomes 2. Locks mutex, writes item, unlocks mutex. signal(full) → full becomes 3.
- Consumer wants to remove an item: wait(full) → full becomes 2. Locks mutex, reads item, unlocks mutex. signal(empty) → empty becomes 4.
If the buffer were completely full (empty = 0), any producer calling wait(empty) would block until a consumer signals it by removing an item, naturally pausing production without wasting CPU cycles on busy-waiting.
Real World Implementation: Printer Spooler Daemon
Reader Writer Problem
The readers-writers problem is a classic synchronization problem about a shared resource (a database, file, or data structure) accessed by two kinds of threads:
Readers: only read the data, so many of them can safely access it at the same time.
Writers: modify the data, so a writer needs exclusive access. No other reader or writer may be active while it writes.
Solution (readers-preference) with semaphores
sem_t rw_mutex; // init 1: exclusive access to the data
sem_t mutex; // init 1: protects read_count
int read_count = 0;
// Writer
sem_wait(&rw_mutex);
write_data();
sem_post(&rw_mutex);
// Reader
sem_wait(&mutex);
read_count++;
if (read_count == 1)
sem_wait(&rw_mutex); // first reader locks out writers
sem_post(&mutex);
read_data();
sem_wait(&mutex);
read_count--;
if (read_count == 0)
sem_post(&rw_mutex); // last reader lets writers in
sem_post(&mutex);The first reader in locks out writers, and the last reader out lets them back in. Readers in between enter freely.
The variants
- First readers-writers (readers-preference): no reader waits just because a writer is waiting. Problem: writer starvation. A steady stream of readers can keep writers out forever.
- Second readers-writers (writers-preference): once a writer is waiting, no new readers may start. Problem: reader starvation if writers keep arriving.
- Fair version: serve requests in arrival order (for example, with a queue or an extra “turnstile” semaphore that both readers and writers pass through). This avoids starvation of both, at some cost to concurrency.
10. Deadlock
A set of blocked processes each holding a resource and waiting to acquire a resource held by another process in the set. Resources are finite and we have several processes competing for it.
Example: Imagine two processes and two resources.
- Process P1 holds Resource R1 and needs Resource R2.
- Process P2 holds Resource R2 and needs Resource R1.
Both processes wait indefinitely. This is a deadlock.
System Model: Resource type R1, R2, … Rn include resources likes CPU cycles, memory space, files, locks, sockets, I/O devices etc. Each resource type Ri has Wi instances (CPU is a resource and a system can have 2 CPUs as instances). A process P can request, use or release a resource.
Necessary Conditions for Deadlock (All 4 must hold simultaneously)
i. Mutual exclusion: only one process can use a resource. Another process that requests to use the same resource must wait until it is released. Ex: A printer can be allocated to only one process at a time. If P1 is using the printer, P2 must wait.
ii. Hold and wait: a process must be holding one resource and waiting to acquire additional resources that are currently being held by other processes. Ex: P1 holds R1. P1 requests for R2. R2 is currenlty held by P2. P1 continues holding R1 while waiting for R2.
iii. No preemption: A resource cannot be forcibly taken away from a process. It must be released voluntarily by the process holding it. Ex: The OS cannot simply take a resource away from P1 while P1 is using it if that resource does not support safe preemption.
iv. Circular wait: A circular chain of processes exists in which each process waits for a resource held by the next process in the chain. Ex: P1 waits for a resource held by P2. P2 waits for a resource held by P3. P3 waits for a resource held by P1. This creates a circular dependency.
All four conditions are necessary for deadlock. If even one condition is eliminated, deadlock can be prevented.
Methods for Handling Deadlock
A. Deadlock Prevention: Deadlock prevention ensures that at least one of the four necessary conditions for deadlock can never hold.
- Prevent mutual exclusion: Make resources shareable wherever possible. Some resources, such as a mutex lock, inherently require exclusive access. Therefore, mutual exclusion cannot always be eliminated.
- Prevent hold and wait: can be unsatisfied through the following strategies — (i) A process should be assigned all the required resources before the start of its execution. This may lead to low device utilization. (ii) The process should release all the existing resources before making a new request. This may eventually lead to starvation. The disadvantage with this is that resources may remain allocated but unused, reducing resource utilization.
- Prevent No preemption: Suppose a process P1 is requesting for a resource R which is held by another process P2. If P2 is already in execution thenP1 has to wait; else, the resource R will be pre-empted from P2 and allocated to P1. Allow the operating system to take resources away from a process under suitable conditions.
- Prevent circular wait: Impose a fixed ordering on resource types. Every process must request resources in increasing order. Ex: Suppose the resource ordering is: R1 < R2 < R3. Processes must request resources in this order. A process holding R1 can request R2, but a process holding R2 cannot request R1. This prevents a circular chain of resource dependencies.
B. Deadlock Avoidance: Deadlock avoidance dynamically examines resource requests and grants a request only if doing so keeps the system in a safe state. Unlike prevention, avoidance does not necessarily eliminate any of the four necessary conditions. Instead, it carefully manages resource allocation.
Safe state: A system is in a safe state if there exists at least one sequence in which every process can obtain the resources it still needs, complete execution, and release its resources. This sequence is called a safe sequence. For ex: <P2, P1, P3> This means P2 can finish first, followed by P1, followed by P3, assuming each process’s remaining needs can be met as it runs.
An unsafe state does not necessarily mean the system is already deadlocked. It means deadlock cannot be ruled out using the safe-state guarantee.
Banker’s algorithm: The algorithm is called the Banker’s Algorithm because it resembles a bank deciding whether granting a loan will leave it able to satisfy its other commitments. It is used when there are multiple instances of resource types. Each process declares its maximum resource requirements in advance. The system checks whether granting a request preserves a safe state.
C. Deadlock Detection: Deadlock detection allows deadlocks to occur and periodically checks whether the system has entered a deadlocked state. Unlike prevention and avoidance, the system does not necessarily stop every unsafe resource allocation in advance.
Method 1 Wait-For Graph: A wait-for graph is commonly used for systems where each resource type has a single instance. In this graph each node represents a process. An edge Pi->Pj means process Pi is waiting for a resource held by process Pj. Consider P1->P2, P2->P3 and P3->P1. This creates a cycle. For a system with a single instance of each resource type, a cycle in the wait-for graph indicates deadlock. When resource types have multiple instances, a cycle in a resource-allocation graph does not necessarily imply deadlock.
Method 2 Detection Algorithm for Multiple Resource Instances: For multiple instances of resource types, a detection algorithm can use:
- Available: Number of available instances of each resource type.
- Allocation: Resources currently allocated to each process.
- Request: Resources each process is currently requesting.
The algorithm repeatedly checks whether a process’s outstanding request can be satisfied using the currently available resources.
If it can:
1. Assume the process finishes.
2. Add its allocated resources back to Available.
3. Continue checking other processes.
If some processes cannot be marked as finished after the algorithm terminates, those processes are deadlocked under the algorithm’s assumptions.
D. Deadlock Recovery: Once a deadlock has been detected, the system must take action to break it. A system can recover from deadlock through adoption of the following mechanisms:
- Process termination: Abort all deadlock process or abort one process at a time until deadlock cycle is eliminated.
- Resource preemption: The system takes a resource away from one process and gives it to another to break the deadlock. This involves three important issues:
1. Victim selection: Choose a process whose resources can be taken away with the lowest overall cost.
2. Rollback: If necessary, return the victim process to an earlier checkpoint and restart it later.
3. Starvation prevention: Ensure that the same process is not repeatedly selected as the victim. - Ostrich algorithm/Deadlock ignorance: Ignore the problem altogether and pretend that deadlocks never occur in system. Used by most OS including UNIX.
11. Memory Management
Memory management is the function of an operating system that manages the computer’s main memory (RAM). The task of the memory management unit is the efficient utilization of memory and minimize the internal and externalfragmentation. The operating system must:
1. Allocate memory to each process.
2. Track which memory regions are occupied and which are free.
3. Protect one process’s memory from unauthorized access by another.
4. Reclaim memory when a process terminates.
5. Use secondary storage when appropriate to support processes that cannot all fit in physical RAM.
Logical (virtual) Address: The address generated by the CPU when a program accesses memory. User can access the logical address of the process.
Physical address: The actual address of a location in RAM. User cannot access the physical address of the program.
The user program deals with logical addresses, it never sees the real physical address.
Memory Management Unit (MMU)
Hardware device that maps virtual to physical address. The value in the relocation register is added to every address generated by a user process at the time it is sent to memory.
Suppose you write a C program and want to execute it. What happens?
1. Compilation: The compiler converts source code into object code. The resulting object file may contain unresolved external references and relocation information.
2. Linking: The required libraries and object files are combined to create an executable or another suitable program image.
3. Loading: The loader prepares the executable for execution and establishes the required memory mappings.
4. Address binding: Program addresses are associated with memory addresses at the appropriate stage.
Loading: Loading refers to bringing the program from secondary to the main memory. The types of loading are:
- Absolute Loading: In absolute loading, the program contains absolute addresses, and the loader places it at the specified memory locations.
- Relocatable Loading: In relocating loading, the loader can place a program at a different memory location and adjust its relocatable address references accordingly.
- Dynamic Loading: In dynamic loading, a routine or module is loaded into memory only when it is needed during execution. Unused routines need not occupy memory. Memory can be used more efficiently, particularly for large programs.
Linking: Linking combines object files and resolves references to functions, variables, and libraries. There are two primary types of linking:
- Static Linking: In static linking, the required library code is incorporated into the executable during the linking stage.
Advantages: The required library code is bundled into the executable. There is no need to dynamically resolve those bundled library references at runtime. Deployment can be simpler when the relevant dependencies are included.
Disadvantages: Executable files can be larger. Multiple applications may contain separate copies of the same library code. Updating the library generally requires relinking the application to incorporate the update.
- Dynamic Linking: In dynamic linking, the program’s references to shared libraries are resolved using runtime linking mechanisms. The required library may be mapped into memory and linked when the program starts or when a particular library function is first needed, depending on the platform and linking configuration.
Advantages: Executables can be smaller. Multiple processes can share library code in physical memory. Library updates may be possible without rebuilding every application, provided compatibility is maintained.
Disadvantages: The required library must be available and compatible. Linking can introduce runtime overhead. Dependency or version problems can prevent a program from running correctly.
Address Binding: Address binding is the process of associating program addresses with actual memory addresses. There are three types:
- Compile-Time Binding: If the final memory location is known at compile time, the compiler can generate absolute code for that location. Changing the required location may require rebuilding the program.
- Load-Time Binding: If the final memory location is unknown at compile time, the compiler can generate relocatable code. The loader determines the actual placement and adjusts the relevant addresses when the program is loaded. Once binding is completed, moving the program generally requires another relocation operation or suitable hardware support.
- Execution-Time Binding: In execution-time binding, address translation takes place dynamically while the program executes. The process can be moved between physical memory locations without changing its logical addresses, provided the operating system and hardware support the required remapping.
Contiguous Memory Allocation
In contiguous memory allocation, each process occupies a single continuous block of physical memory. There are two major approaches:
Fixed Partitioning: Physical memory is divided into a fixed number of partitions. Each partition can hold one process at a time. Since the size of the partition cannot be varied according to the size of the process, the degree of multi programming is fixed and low.
Internal Fragmentation: Internal fragmentation occurs when allocated memory contains unused space that cannot be allocated separately.
External fragmentation: External fragmentation occurs when total free memory is sufficient, but it is divided into separate non-contiguous blocks.
Ex: Suppose a 100 MB region of memory is divided into four partitions of 25 MB each. P1 -> Process A 20 MB, P2 -> Process B 12 MB, P3 -> Process C 24 MB and P4 -> Free. For Process B, internal fragmentation amounts for 13 MB (25–12) which is wasted.
Variable Partitioning: Partitions are created dynamically according to the size of each process. However, repeated allocation and deallocation can leave many small free spaces between allocated blocks.
There is no internal fragmentation and no limit on the size of process. It has a better degree of multi-programming. However, it suffers from external fragmentation.
Defragmentation/Compaction: All the loaded partitions are brought together and the free partitions are made contiguous.
Example: Process A requires 15 MB. Process B requires 20 MB. Process C requires 10 MB. Suppose free memory consists of blocks 10 MB + 5 MB + 15 MB = 30 MB. Even though 30 MB is free in total, a process requesting 20 MB of continuous memory has no individual block that is large enough. The allocation fails due to external fragmentation.
Memory Allocation Algorithms
When using variable-sized contiguous memory allocation, the OS needs to decide which free block should be assigned to a process. Free holes in the memory are represented using free list (linked list data structure).
Consider these available memory blocks: 100, 500, 200, 300, 600 KB. A process requests 212 KB.
- First Fit: Select the first free block that is large enough. Checking from the beginning, Allocate 212 KB from the 500 KB block. Remaining free space: 500–212 = 288 KB. Usually quick because it stops at the first suitable block.
- Next Fit: It behaves similar to first fit except that it scans the memory after the ‘last allocation point’.
- Best Fit: Select the smallest free block that can accommodate the process. The smallest suitable block is 300 KB. Remaining free space: 300–212 = 88 KB. Minimizes the leftover space in the selected block for that particular allocation. Can create many small unusable free blocks, depending on the allocation pattern.
- Worst Fit: Select the largest available free block. The largest suitable block is 600 KB. Remaining free space: 600–212 = 388 KB. The idea is to leave a relatively large free block after allocation.
Do not assume Best Fit always produces the least overall fragmentation. Its selection rule minimizes the leftover in the chosen block for that allocation, but the long-term result depends on the sequence of requests and releases.
Non Contiguous Memory Allocation
Paging
Paging divides logical memory into fixed-sized pages and physical memory into equally sized frames. Page size = Frame size. Page size is uuallu determines by the processor architecture. Unlike contiguous allocation, a process’s pages can occupy different physical frames which are accessed using address translation.
Example: Suppose a process has 4 pages: P0, P1, P2 and P3. Physical memory has these available frames: F0, F1, F2, F3 and F4. The OS might allocate the pages as follows.
Page Table: A page table data structure stores the mapping between a process’s virtual pages and physical frames. When the CPU generates a virtual address, the MMU uses the page number to locate the appropriate page-table entry. The frame number is then combined with the offset to form the physical address.
The page table is stored in main memory at the time of process creation and its base address is stored in process control block (PCB). A page table base register (PTBR) is present in the system that points to the current page table. Changing page tbale requires only this one register at the time of context switching.
There is no external fragmentation in paging. Internal fragmentation may exist in the last page and is formulated as ceil(p/2), where p is the page size.
Paging Address Translation: A logical address is divided into two components: Logical Address = (p,d) where p = page number, d = offest within the page. The page number identifies the page. The offset identifies the byte or location within that page. The p is used as an index into a page table to get base address of the corresposning frame in physical memory.
The physical address becomes: Physical Address = (f,d) where f = frame number, d = the unchanged offset
Formulae: Let logical address space size be 2^m bytes. Page size be 2^n bytes. Physical memory be of size 2^k. Then,
Offset bits = n
Page number bits = m — n
Number of pages = Logical address space size / page size
Frame number bits = k — n
Number of frames = Physical memory size / frame size
Translation Lookaside Buffer (TLB): The Translation Lookaside Buffer (TLB) is a small, fast hardware cache that stores recently used address translations.
TLB hit: The required translation is found in the TLB. The frame number is obtained quickly. The physical memory access can proceed.
TLB miss: The translation is not found in the TLB. The system must consult the page table, usually in memory. The translation may then be cached in the TLB.
A TLB miss is not the same as a page fault.
Address space identifier (ASIDs) is stored in each entry of the TLB. ASID uniquely identifies each process, provides address space protection and allows TLB to contain entries for several different processes. When TLB attempts to resolve the virtual page numbers, it ensures that the ASID for the currently executing process matches the ASID associated with the virtual page. If it doesn’t match, the attempt is treated as TLB miss.
Effective Access Time (EAT): For a simplified single-level page table model, suppose memory access time = m, TLB lookup time = t, TLB hit ratio = h. Assume a TLB hit requires one TLB lookup and one memory access, while a TLB miss requires one TLB lookup and two memory accesses. Then,
EAT = h(t + m) + (1 — h) (t + 2m) = t + (2 — h)m
This formula assumes serial TLB lookup and memory accesses, with no page faults.
Multilevel paging: A single-level page table can become very large for a large virtual address space. Multilevel paging divides the page table into smaller structures. For example: A two level page table uses an outer page table and an inner page table. The outer table identifies the appropriate inner page table, which then identifies the physical frame.
It can reduce page-table memory overhead by allocating lower-level tables only for portions of the address space that need them. However, additional levels can increase address-translation overhead, although TLBs help reduce the impact.
The performance of a multi-level paging with TLB:
Effective memory access time EMAT = p (c+m) + (1-p)(c+(n+1)m), where p = TLB hit ratio, c = TLB access time, m = main memory access time for a n-level paging system.
Inverted paging: A conventional page table generally has entries corresponding to virtual pages. An inverted page table instead has an entry for each physical frame, identifying the virtual page and process occupying that frame. The number of entries in the inverted page table is equal to the number of the frames in the physical address space. This can substantially reduce page-table storage requirements for large virtual address spaces. However, finding a matching virtual page can require more complex lookup mechanisms, such as hashing.
Segmentation
Segmentation divides a program into variable-sized logical units. Examples of segments include: code segment, data segment, stack segment, heap segment. Unlike paging, segmentation follows the logical structure of a program. There is no internal fragmentation. The size of the segment table is generally less than the size of the page table. However, there might be external fragmentation. The different size of segment is not good at the time of swapping.
A logical address has two components. (s,d) where s is the segment number and d is the offset within that segment. Each segment has a base address and a limit indicating its length.
To translate an address:
1. Identify the segment number.
2. Check whether the offset is within the segment’s limit.
3. If valid, add the offset to the segment’s base address.
Physical address = Base[s] + d provided that d < Limit[s]. Otherwise, the address is invalid and an exception occurs.
12. Virtual Memory
Virtual memory allows a process to operate without requiring all of its pages to be present in physical RAM simultaneously. The OS and hardware maintain mappings between virtual addresses and physical memory. Pages that are not currently resident can remain in backing storage and be brought into RAM when needed. This enables efficient memory use and supports larger virtual address spaces than the available physical RAM.
Virtual memory can be implemented through demand paging or demand segmentation.
Demand Paging: Instead of loading every page of a process in advance, the system loads pages on demand.
Page Fault: A page fault occurs when a process accesses a page that is not currently mapped as a valid resident page in physical memory. the time taken to servuce a page fault is called page fault service time.
Lazy Swapper: A lazy swapper never swaps a page into memory unless that page is needed.
For a valid demand-paged access, the OS may need to:
1. Trap into the operating system.
2. Verify that the access is valid. The valid-invalid bit scheme in the page table is used to disntinguish between pages that are in memory and those that are in the disk. A value of 1 means the associated page is both legal and in memory. A value of 0 means that the page is either not valid or is valid bit is currently on the disk.
3. Locate the page in backing storage.
4. Find a free frame or select a victim page.
5. Load the required page into RAM.
6. Update the relevant page-table entry.
7. Resume the interrupted instruction.
If the access is invalid, the OS may instead terminate the process or deliver an appropriate exception.
Advantages of virtual memory: The degree of multi-programming will be increased. Uses can run large apps with less real physical memory.
Disadvantages of virtual memory: The system can be slower as swapping takes time. Thrashing may occur.
Temporal Issues: Let page fault service time = S, main memory access time = M, page fault rate = P, where 0 ≤ P ≤ 1. Assume page table access time is neglected.
Effective memory access time EMAT = P X S + (1 — P) X M.
Demand Paging with TLB: Assume TLB hit ratio = h, TLB access time = c, Page fault service time = s, main memory access time = m, page fault rate = Pwhere 0≤ P≤ 1.
Effective memory access time EMAT = h(c+m) + (1-h)(c+(P X S + (1 — P) X M))
Page Replacement Algorithms
What happens when a page fault occurs but there are no free frames? The operating system may have to evict a page from RAM to make room for the required page. A page replacement algorithm selects which page to remove.
- FIFO (First In, First Out): FIFO removes the page that has been in memory the longest. It maintains the order in which pages entered memory. It is simple to implement. However, it may remove a frequently used page simply because it is old. FIFO can exhibit Belady’s anomaly: increasing the number of page frames can sometimes increase the number of page faults.
- Optimal Page Replacement: Optimal replacement removes the page whose next use is farthest in the future. It produces the minimum possible number of page faults for a given reference string and initial condition. But, the OS cannot generally know future memory references exactly. Therefore, Optimal is primarily used as a theoretical benchmark.
- LRU (Least Recently Used): LRU removes the page that has not been used for the longest time in the past. Uses past behavior to estimate future needs. Exact LRU can require additional tracking hardware or bookkeeping. This can be implemented using counters or stack. Counters associate a time field with each page table entry. We replace the page with the smallest time value. Stacks keep a record of page number. Whenever a page is referenced, it is removed from the stack and put on top. This ensures that the most recently used is awlays on the top and the least recently used is always on the bottom. Doubly linked lists are used as entries need to be removed from the middle of the stack.
- Counting-based page replacement: It keeps a counter of the number of references that have been made to each page (Reference counting). Least frequently used (LFU) replaces the page with the lowest reference count, meaning the page that has been accessed the fewest times. Most frequently used (MFU) replaces the page with the highest reference count. This may seem counterintuitive as to why would we remove the page used most frequently?The reasoning is that a page with a low count might have been loaded recently and may still need to be accessed again, whereas a page with a high count might have completed its period of frequent use. This is a heuristic, not a guarantee that the selected page will be the best one to remove.
Optimal and LRU are stack algorithms and do not exhibit Belady’s anomaly.
Thrashing
Thrashing occurs when the system spends an excessive amount of time handling page faults rather than executing useful work. This usually happens when processes do not have enough physical frames to keep their actively used pages in memory.
Two important techniques to control thrashing:
- Working-Set Model: The working set represents the pages a process has referenced within a specified recent time window. The OS can use this information to estimate the process’s current memory requirements.
- Page-Fault Frequency (PFF): The OS monitors the rate of page faults. If the rate becomes too high, it may allocate more frames to the process, if possible, or reduce the number of processes competing for memory.
13. Disk Scheduling
A hard disk drive (HDD) stores data on rotating platters. A read/write head moves to the required track to access data. When multiple processes request data from different disk locations, the operating system must decide which disk request to serve first. This decision-making process is called disk scheduling.
Cylinder: A cylinder is a collection of tracks at the same radial position across the platters of a hard disk. In typical disk-scheduling problems, a cylinder number represents a position along the disk’s range of tracks.
Disk Head: The disk head reads or writes data on the disk surface. In HDD scheduling problems, we generally track the position of the read/write head as it moves between cylinders.
Seek Time: Seek time is the time required to move the disk head to the desired cylinder.
Rotational Latency: Rotational latency is the time spent waiting for the desired sector to rotate under the disk head. It depends on the rotational speed and the angular position of the required sector.
Transfer Time: Transfer time is the time required to transfer the requested data once the relevant location is ready.
Disk Access Time: Seek time + rotational latency + transfer time. Some models include additional overhead, such as controller or queueing delays.
Disk Scheduling Algorithms
Suppose: Cylinders are numbered from 0 to 199. The initial head position is 53. The request queue is: 98, 183, 37, 122, 14, 124, 65, 67. The initial direction for directional algorithms is toward higher-numbered cylinders.
- First Come First Serve (FCFS): FCFS serves requests in the order in which they arrive. It does not consider which request is closest to the current head position. It is simple to implement, fair in the sense that requests are serviced in arrival order, no request is deliberately postponed in favor of a later request. However, it can cause excessive head movement. Average seek time can be high.
Request sequence: 53 -> 98 ->183 -> 37 ->122 -> 14 -> 124 -> 65 -> 67
Total head movement: 45 + 85 + 146 + 85 + 108 + 110 + 59 + 2 = 640 cylinders
- Shortest Seek Time First (SSTF): SSTF selects the pending request that is closest to the current head position. It produces less head movement than FCFS. Can improve average seek time. A request far from the current head position may wait for a long time. It can cause starvation under some workloads.
Request sequence: 53 -> 65 -> 67 -> 37 -> 14 -> 98 -> 122 -> 124 -> 183.
Total head movement: 12 + 2 + 30 + 23 + 84 + 24 + 2 + 59 = 236 cylinders.
- SCAN (Elevator Algorithm): SCAN moves the head in one direction, servicing requests along the way. When it reaches the end of the disk, it reverses direction and services requests on the way back. It generally provides more predictable waiting time than SSTF. It reduces the risk of indefinite postponement associated with repeatedly favoring nearby requests. But the disadvantage is that the head may travel to the disk’s endpoint even when no request exists there. Requests near one end may experience different waiting times from those near the other end.
Considering the initial direction is toward higher-numbered cylinders.
Request sequence: 53 -> 65 -> 67 -> 98 -> 122 -> 124 -> 183 -> 199 -> 37 -> 14
Total head movement: upward movement + downward movement = (199–53) + (199–14) = 146 + 185 = 331 cylinders.
- Circular SCAN (C-SCAN): The head services requests in only one direction. After reaching the end of the disk, it returns to the opposite end and continues servicing requests in the same direction. It provides more uniform waiting-time behavior than SCAN under suitable workloads. The return movement can add considerable head movement. It may travel past locations that have no pending requests.
Request sequence: 53 -> 65 -> 67 -> 98 -> 122 -> 124 -> 183 -> 199 -> 0 ->14 -> 37
Total head movement: (199–53) + 199 + 37 = 382 cylinders.
- LOOK: LOOK is similar to SCAN, but the head does not travel to the physical end of the disk unless a request exists there. Instead, it reverses direction at the last pending request in its current direction. Avoids unnecessary travel to disk endpoints. Waiting times may differ depending on where requests are located. Requests arriving just after the head passes their location may have to wait for another sweep.
Request sequence: 53 -> 65 -> 67 -> 98 -> 122 -> 124 -> 183 -> 37 -> 14
Total head movement: (183–53) + (183–14) = 130 + 169 = 299 cylinders
- C-LOOK: C-LOOK is the circular version of LOOK. The head services requests in one direction until it reaches the last pending request in that direction. It then jumps to the lowest pending request and continues servicing in the same direction. Unlike C-SCAN, it does not travel to the physical disk endpoints unless requests exist there. The jump from the highest to the lowest pending request can be large. The return movement adds to total head movement.
Request sequence: 53 -> 65 -> 677 -> 98 -> 122 -> 124 -> 183 -> 14 -> 37
Total head movement: 130 + 169 + 23 = 322 cylinders
- N-step SCAN: N-Step SCAN divides the request queue into batches of at most N requests. Each batch is serviced using the SCAN algorithm. While one batch is being processed, newly arriving requests are placed into a later batch.
- FSCAN: FSCAN uses two queues. One queue is processed using SCAN. New requests are placed into the other queue. When the current queue is finished, the queues switch roles. This prevents newly arriving requests from continually changing the set of requests being serviced during a sweep.
14. File Systems
A file system is the part of an operating system responsible for organizing, storing, retrieving, naming, and protecting data on storage devices.
What does a file system manage ?
- File management: create, open, read, write, rename and delete files
- Directory management: organize files into directories
- Space allocation: assign disk blocks to files
- Free space management: track available disk blocks
- Metadata management: maintain file size, permissions, timestamps etc
- Protection: control who can access or modify files
- Reliability: help maintain consistency after crashes or failures
File: A file is a named collection of related information stored on secondary storage. Ex: notes.pdf, main.cpp, photo.jpg, dataset.csv
File Context: File context is stored in file control block (FCB). Files will have various types: .doc, .txt, .pdf, .exe, .obj, .dll, .png, .apk, .xls, .xlsx, .jpg, .mp3, .mp4, .avi, .flv, .mkv, .3gp, .c, .cpp, .java, .xml, .html
File Attributes
The OS maintains metadata about each file.
- Name: Human-readable file name
- Identifier: Unique internal identifier for the file
- Type: File type, where supported
- Location: Information identifying the file’s storage blocks
- Size: Current file size
- Protection: Access permissions
- Owner: User or group associated with the file
- Timestamps: Creation, modification, or access times, depending on the file system
The filename is not necessarily the file’s unique identifier. File systems often use an internal identifier, such as an inode number in Unix-like file systems.
File Operations
The OS commonly supports the following operations:
- create: create a new file
- open: prepare a file for access
- close: release the open-file state
- read: retrieve data from a file
- write: store data in a file
- append: add data to the end
- seek: change the current file position
- delete: remove a file
- truncate: remove file contents while retaining the file itself
- rename: change the file’s name
- hide
- save
- save as
- copy
- paste
- cut
- send/share
What happens when a file is opened ?
A simplified sequence is:
1. The process requests that a file be opened.
2. The OS resolves the filename or path.
3. It checks permissions.
4. It locates the file’s metadata.
5. It creates or updates open-file table entries.
6. It returns a file descriptor or handle to the process.
A file descriptor is a small integer used by a process in Unix-like systems to refer to an open file or another I/O resource.
For example, a program might receive file descriptor 3 when it opens a file.
The descriptor does not directly represent the file’s data blocks on the disk.
File Types
Common file types include:
- Regular files: Documents, images, source code, executables.
- Directories: Structures that organize file names.
- Character devices: Devices that expose character-oriented I/O.
- Block devices: Devices that expose block-oriented storage.
- Symbolic links: Objects that refer to another pathname.
- Pipes and sockets: Mechanisms for communication between processes.
Not every OS or file system supports all these types in the same way.
File Access Methods
A file system may support different ways of accessing file contents.
A. Sequential access: Data is accessed in order, from the beginning toward the end. This is useful for processing logs or reading a text file from beginning to end.
B. Direct access (random access): Any location in a file can be accessed directly, without reading all preceding data. This is useful for databases and large binary files.
C. Indexed access: An index helps locate the required record or data block. The system searches the index and uses the corresponding location to retrieve the record.
Directory Structures
A directory organizes file names and associates them with file information or identifiers.
i. Single-level directory: All files are stored in one directory. It is simple to implement and easy to understand. The disadvanatges include filename conflicts, poor organization, difficult to manage many users or files.
ii. Two-level directory: Each user has a separate directory. It reduces filename conflicts between users. However, sharing files between users is less convenient.
iii. Tree-structured directory: Directories can contain subdirectories, creating a hierarchy. This is the most familiar structure to users. The absolute path of a file specifies its location from the root. The relative path specifies its location relative to the current directory.
iv. Acyclic-graph directory: An acyclic-graph directory allows files or directories to be shared through multiple references, but cycles are prohibited. This avoids creating independent copies when the intention is to share the same object. However, the OS must manage issues such as: multiple references to the same file, deletion when other references still exist, reference counting or other mechanisms for tracking links.
v. General-graph directory: A general-graph directory allows cycles. Cycles complicate directory traversal, deletion, and storage reclamation. The OS may need cycle detection or restrictions on traversal.
File System Implementation
How does the OS translate a filename into actual data on storage?
The system needs to:
- Resolve the pathname through the directory structure.
- Identify the file’s metadata.
- Determine which disk blocks contain the file’s data.
- Retrieve those blocks.
- Return the data to the requesting process.
File Control Block (FCB): A File Control Block is a data structure containing information about a file. It can contain information such as: file size, ownership and permissions, timestamps, pointers or other information describing the file’s data blocks. The exact layout depends on the file system.
Inodes: In Unix-like file systems, an inode stores metadata about a file and information used to locate its data. An inode typically contains file type and permissions, owner and group information, file size, timestamps, link count, pointers or mappings to file data. An inode generally does not store the filename itself. Instead, a directory maps a filename to an inode number. The file’s contents are stored separately from the inode’s metadata.
File Allocation Methods
File allocation determines how a file’s data blocks are assigned on the storage device.
i. Contiguous allocation: In contiguous allocation, a file occupies consecutive disk blocks. If the file starts at block b, and the requested logical block number is i, then: Physical block = b + i. Ths is assuming zero-based logical block numbering.
Every file is associated with two parameters: (1) Starting DBA (Disk Block Address) (2) Size
Consecutive blocks are stored next to each other, making sequential reading efficient. The system can calculate the location of a block directly. Only the starting block and length may be needed for a simple implementation.
However, there are chances of external fragmentation, ie. free space may be divided into many small, noncontiguous regions. File growth is difficult, ie. if a file needs more space but the following blocks are occupied, the file may need to be relocated or handled through an extension mechanism. Internal fragmentation may exist in the last disk block of the file.
ii. Linked allocation/ Non-contiguous allocation: In linked allocation, the blocks of a file can be scattered throughout the disk. Each block contains file data and a pointer to the next block, or equivalent linkage information. The file’s metadata stores the first block, and following the links reveals the rest of the file.
Every file is associated with 2 parameters: (1) Starting DBA (2) Ending DBA
There is no external fragmentation for file allocation. Internal fragmentation may exits in the last disk block of the file. New blocks can be allocated wherever free space is available, subject to file-system constraints. There is poor direct access, since to reach logical block 3, the system may have to follow links through blocks 0, 1, and 2. It supports only sequential access of the file. There is a pointer overhead as each linked block must reserve space for linkage information, unless links are stored separately. There are reliability concerns because if a pointer becomes corrupted, part of the file’s block chain may become inaccessible.
A variation of linked allocation is the File Allocation Table (FAT). Instead of storing the next-block pointer inside every data block, the file system maintains a table containing the linkage information. The OS can follow the chain using table entries without reading each block’s embedded pointer. However, accessing a distant block may still require traversing many entries unless the relevant chain information is cached or otherwise optimized. FAT is associated with file systems commonly used on removable storage and other devices.
iii. Indexed allocation: In indexed allocation, each file has an index block containing pointers to its data blocks. Unlike linked allocation, the data blocks themselves do not need to form a linked chain. It supports direct access.
There is no external fragmentation for file allocation. Internal fragmentation may exist in the last disk block of the file. The data blocks need not be continguous. File growth is easy as additional data blocks can be allocated elsewhere, provided the indexing structure has capacity or can be extended.
There is an index-block overhead as file systems need space for the index structure. A small file may need an index block even if it contains very little data; this is a waste. There are maximum file size limitations as a single index block can hold only a finite number of block pointers.
Multilevel Indexing and UNIX Inodes
What happens when a file becomes too large for one index block? The file system can use multiple levels of indexing.
- Single indirect block: An inode points to an indirect block, which contains pointers to data blocks. If a block contains P pointers, the indirect block can address P data blocks.
Inode
|
v
Indirect block
├── Data block 1
├── Data block 2
├── Data block 3
└── ...- Double indirect block: A double indirect pointer points to a block containing pointers to indirect blocks. If each block contains P pointers, a double indirect structure can address: P² data blocks.
Inode
|
v
Double indirect block
|
├── Indirect block 1 → Data blocks
├── Indirect block 2 → Data blocks
└── ...- Triple indirect block: A triple indirect pointer adds another level. The number of data blocks addressable through a triple indirect structure is: P³ data blocks.
Inode
|
v
Triple indirect block
|
v
Double indirect block
|
v
Indirect block
|
v
Data blockFree Space Management
The file system must track which disk blocks are free and which are allocated.
- Bit vector (bitmap): Each disk block is represented by one bit. Simple representation. Easy to identify free blocks. Can help find consecutive free blocks. A large disk requires a large bitmap, although the bitmap is usually small relative to the disk itself. Searching can be costly without efficient scanning or indexing.
Example: Assume 1 means allocated. 0 means free. The exact bit convention can vary by implementation.
Block: 0 1 2 3 4 5 6 7
Bitmap: 1 1 0 0 1 0 1 0
- Linked free list: All free blocks are linked together. The file system maintains a pointer to the list’s beginning. Conceptually simple. Finding a particular number of free blocks or finding a large consecutive region may require traversing many entries.
- Grouping: A free block contains the addresses of several other free blocks. The last entry points to another block containing a further group of free-block addresses. This allows multiple free blocks to be identified at once, rather than following a single-block chain.
- Counting: Instead of recording every free block individually, the file system records a starting block and a count of consecutive free blocks.
Directory Implementation
A directory needs to map a filename to its corresponding file identifier.
- Linear list: The directory stores entries in a list. If there are n entries, a simple linear search takes: Best case: O(1) Worst case: O(n). Simple implementation. Easy to maintain. Slow searches in large directories. Duplicate-name checks can require scanning existing entries.
- Hash table: A hash function maps a filename to a position in a hash table. The OS searches the relevant bucket for the matching entry. With a suitable hash function and a well-managed table, lookup is typically O(1) on average. Worst-case lookup can still be O(n), depending on collisions and implementation.
File System Layers
A file system is often described using a layered architecture.
i. Logical file system: manages high-level file-system information, such as directories, file metadata, naming, protection and permissions.
ii. File-organization module: Handles how files are organized on storage. Its responsibilities can include: file allocation, logical-to-physical block mapping, free-space management.
iii. Basic file system: Issues generic block read and write requests.
iv. I/O control: Includes device drivers and interrupt-handling mechanisms used to communicate with hardware.
The precise boundaries vary between operating systems, but the model helps explain how a file request is translated into device operations.
Mounting a file system
Mounting makes a file system accessible through a directory in the operating system’s directory hierarchy.
For example, a USB drive might be mounted at: /media/usb. After mounting, the files on the USB drive can be accessed through paths such as: /media/usb/notes.pdf.
On Unix-like systems, mounting associates a file system with a mount point.A mount point is a directory at which the mounted file system becomes accessible.
A storage device can contain a file system, but the OS must make that file system available within its namespace before users can access it through the normal directory hierarchy. The details vary by operating system. Some systems automate mounting removable devices.
File Sharing, Links and Deletion
Hard Links: A hard link is another directory entry referring to the same underlying file object. If the contents are changed through one name, those changes are visible through the other name because both refer to the same underlying file. Removing one name does not necessarily delete the file’s data. The file’s storage can be reclaimed when its final hard link is removed and no process or other kernel reference still requires the file.
Symbolic Links: A symbolic link, or symlink, is a separate file-system object that refers to another pathname. Unlike a hard link, a symbolic link can generally refer to a target on another mounted file system.
File Protection and Access Control
File protection determines which users or processes can perform which operations on a file. In Unix-like systems, permissions are commonly represented for three categories:
- Owner: read, write, execute
- Group: read, execute
- Others: read
Each permission has a value. Read = 4, write = 2, execute = 1. Example: -rwxr-xr —
rwx = 4 + 2 + 1 = 7, r — x = 4 + 0 + 1 = 5, r — — = 4 + 0 + 0 = 4. So, the result is 754.
Access Control Lists (ACLs)
An ACL can specify permissions for individual users and groups, providing more flexibility than basic owner/group/other permission bits.
For example, the file owner might grant a particular colleague read access without granting access to everyone else.
Journaling
A journaling file system records certain intended changes in a journal or log before applying or committing them to the main file-system structures, according to the file system’s protocol. After a crash, the system can use the journal to help recover a consistent state. Journaling does not automatically mean that all file contents are protected against loss.
Depending on the file system and journaling mode, the journal may primarily protect metadata consistency rather than guaranteeing that every recently written data byte survives a crash.
Virtual File System (VFS)
VFS provides a common interface through which the OS can access different file-system implementations.
