An Operating System (OS) is the software that sits between your programs and the hardware. It does four big jobs: it manages the CPU (decides who runs), manages memory (decides who gets RAM), manages files and devices, and gives programs a safe way to talk to hardware through system calls.

A program is a passive file on disk (like a.out). A process is a program that is running. One program can create many processes. A process has: code (text section), data section (global variables), heap (dynamic memory), stack (function calls, local variables), and the current CPU register values.

The OS keeps one PCB for each process. It is like the ID card + notebook of the process. It stores:

• Process state — new, ready, running, waiting, or terminated.
• Process ID (PID) — a unique number.
• Program counter — address of the next instruction to run.
• CPU registers — saved values of all registers.
• CPU scheduling info — priority, pointers to scheduling queues.
• Memory info — base/limit registers, page tables.
• Accounting info — CPU time used, time limits.
• I/O status — open files, devices in use.

A process moves through five states:

• New — the process is being created.
• Ready — it is loaded and waiting for the CPU.
• Running — instructions are executing on the CPU.
• Waiting (Blocked) — it is waiting for an event, like I/O to finish.
• Terminated — it has finished.

When the CPU switches from process A to process B, the OS must save the state of A into A's PCB and load the state of B from B's PCB. This is a context switch. During the switch the CPU does no useful work, so it is pure overhead. Typical time: a few microseconds. More context switches = more wasted time.

A thread is a lightweight unit of execution inside a process. Threads of the same process share the code, data, heap, and open files — but each thread has its own stack, program counter, and registers. Example: in a browser, one thread draws the page while another downloads images.

• User-level threads: managed by a library in user space. The kernel does not know about them. Creation and switching are very fast. Problem: if one thread makes a blocking system call, the whole process blocks.
• Kernel-level threads: managed by the OS itself. Slower to create, but the kernel can schedule them on different CPU cores, and one blocked thread does not block the others.
• Mapping models: many-to-one (many user threads on one kernel thread), one-to-one (Linux, Windows), many-to-many.

These three words sound alike, but they mean different things. BUET asked to define and compare them (April 2017), so learn them as a set:

• Multiprogramming: keep several jobs in memory at the same time. When the running job blocks (for example, it waits for I/O), the CPU switches to another job. The goal is throughput — the CPU is never idle. The switch happens only when a job blocks, not on a timer.
• Multitasking (time-sharing): the CPU switches between tasks very fast using a timer (preemption), so every user or program feels the machine responds instantly. The goal is responsiveness. It is multiprogramming plus rapid preemptive switching.
• Multithreading: many threads inside ONE process. All threads share the same address space (code, data, heap) but keep their own stack and registers. The goal is parallel work inside one program with cheap creation and cheap switching.

In UNIX/Linux, fork() creates a copy of the calling process. The copy is the child. fork() returns 0 to the child and the child's PID to the parent. Both continue running from the line right after fork().

Many processes wait in the ready queue, but the CPU can run only one at a time (per core). The CPU scheduler picks which process runs next. The goal is to keep the CPU busy and to make users happy.

Scheduling criteria (what we measure):

• CPU utilization — keep the CPU as busy as possible (maximize).
• Throughput — number of processes finished per unit time (maximize).
• Turnaround time — finish time − arrival time. Total time a process spends in the system (minimize).
• Waiting time — total time spent waiting in the ready queue = turnaround time − burst time (minimize).
• Response time — time from arrival until the first time the process gets the CPU (minimize).

Preemptive vs non-preemptive: In non-preemptive scheduling, once a process gets the CPU it keeps it until it finishes or blocks. In preemptive scheduling, the OS can take the CPU away (for example, when the time slice ends or a shorter job arrives).

Whoever arrives first runs first, like a queue at a shop. Simple, but a long job at the front makes everyone wait.

Pick the process with the smallest CPU burst. SJF is provably optimal for average waiting time — no other order can beat it. Problem: we usually do not know burst times in advance (we predict them), and long jobs can starve.

Same idea as SJF, but preemptive: if a new process arrives with a burst shorter than the remaining time of the running process, the new one takes over.

Each process gets a priority number; the highest-priority process runs first (here, smaller number = higher priority). Can be preemptive or non-preemptive. Big problem: starvation — a low-priority process may wait forever. Fix: aging — slowly raise the priority of processes that wait a long time.

Every process gets a small fixed time quantum (e.g., 4 ms). If it does not finish in that time, it goes to the back of the ready queue. Great for time-sharing systems: everyone gets a fair turn, response time is good.

The ready queue is split into several queues, e.g., foreground (interactive) using RR and background (batch) using FCFS. Each queue can have its own algorithm, and the queues themselves are scheduled (fixed priority, or time slices like 80% foreground / 20% background). A multilevel feedback queue also lets processes move between queues — a process that uses too much CPU drops to a lower queue; a process that waits too long moves up (this is aging in action).

When two or more processes/threads read and write shared data at the same time, the final result depends on the exact order of execution. This is a race condition.

Concrete example: Two threads both run counter++ once, starting from counter = 5. We expect 7. But counter++ is really three machine steps:

The critical section is the part of code where a process touches shared data. Only one process should be inside it at a time. A correct solution must satisfy three requirements:

1. Mutual exclusion — at most one process in the critical section at any moment.
2. Progress — if nobody is inside and someone wants in, the decision cannot be postponed forever; only processes trying to enter take part in the decision.
3. Bounded waiting — after a process asks to enter, there is a limit on how many times others can enter before it does (no starvation).

A classic software-only solution for two processes (P0 and P1). It uses two shared variables: flag[2] ("I want to enter") and turn ("it is your turn"). Each process politely gives the turn to the other; whoever's turn it is enters. It satisfies all three requirements (on old simple hardware).

A mutex (mutual exclusion lock) is the simplest tool: acquire() before the critical section, release() after. If the lock is taken, others spin or sleep. A lock where waiting processes keep looping is called a spinlock — it wastes CPU but avoids context switches, so it is good for very short waits on multi-core machines.

A semaphore S is an integer changed only by two atomic operations:

• wait(S) (also called P): decrement S; if S becomes negative, the caller blocks.
• signal(S) (also called V): increment S; if any process was blocked, wake one up.

Binary semaphore: value only 0 or 1 — works like a mutex. Counting semaphore: value can be any number — counts available copies of a resource (e.g., 5 printers → start S at 5).

A producer puts items into a buffer of size N; a consumer takes them out. We use three semaphores: mutex = 1 (protects the buffer), empty = N (counts empty slots), full = 0 (counts filled slots).

Semaphores are easy to misuse (forget a signal, wrong order). A monitor is a high-level language construct: a class where only one process can be active inside at a time, automatically. It also has condition variables with x.wait() (sleep until signaled) and x.signal() (wake one waiting process). Java's synchronized keyword is a monitor idea.

A deadlock is a situation where a set of processes are all blocked, each waiting for a resource that another process in the set holds. Nobody can move — like two cars facing each other on a one-lane bridge, each waiting for the other to back up.

Deadlock can happen only if all four hold at the same time:

1. Mutual exclusion — at least one resource can be used by only one process at a time (e.g., a printer).
2. Hold and wait — a process holds one resource while waiting for another.
3. No preemption — a resource cannot be taken away by force; the holder must release it voluntarily.
4. Circular wait — there is a cycle: P0 waits for P1's resource, P1 waits for P2's, ..., Pn waits for P0's.

Break any one condition and deadlock becomes impossible.

Circles are processes, squares are resources. An edge R → P means "R is assigned to P". An edge P → R means "P is requesting R".

• No cycle → definitely no deadlock.
• Cycle + one instance per resource → definitely deadlock.
• Cycle + multiple instances → deadlock is possible, not certain.

• Prevention — design the system so one Coffman condition can never hold. E.g., order all resources with numbers and always request in increasing order (kills circular wait); request everything at once (kills hold and wait).
• Avoidance — before granting a request, check that the system stays in a safe state (Banker's algorithm). Needs to know maximum needs in advance.
• Detection & recovery — let deadlock happen, run a detection algorithm from time to time, then recover by killing a process or preempting resources.
• Ignore it (Ostrich algorithm) — pretend it never happens. This is what most real OSes (Linux, Windows) actually do, because deadlocks are rare and the other methods are costly.

The system is in a safe state if there exists a safe sequence: an order in which every process can get its maximum need, finish, and return its resources. The algorithm:

1. Compute Need = Max − Allocation for each process.
2. Set Work = Available.
3. Find an unfinished process with Need ≤ Work. Pretend it finishes: Work = Work + its Allocation. Mark it finished.
4. Repeat. If all processes can finish → safe. If stuck → unsafe.

Handling a new request (Request ≤ Need and Request ≤ Available must both hold): pretend to grant it — Available −= Request, Allocation += Request, Need −= Request — then run the safety check again. If the new state is safe, grant it for real; if not, roll back and make the process wait. Example: P1 requests (1, 0, 2). Check: (1,0,2) ≤ Need(1,2,2) ✓ and ≤ Available(3,3,2) ✓. After pretending: Available = (2,3,0), P1 Alloc = (3,0,2), P1 Need = (0,2,0). The safety check still finds ⟨P1, P3, P4, P0, P2⟩ → grant it.

A logical (virtual) address is what the CPU generates — the address the program sees. A physical address is the real location in RAM. The MMU (Memory Management Unit) is hardware that translates logical → physical at run time. Simplest MMU: a relocation (base) register — physical = logical + base — and a limit register to stop the process from touching others' memory.

In contiguous allocation each process gets one continuous block. Free memory has "holes". Where do we put a new process?

• First fit: the first hole that is big enough. Fast.
• Best fit: the smallest hole that is big enough. Leaves tiny useless holes.
• Worst fit: the largest hole. Leaves big leftover pieces.

In practice, first fit and best fit beat worst fit in both speed and memory use.

• External fragmentation: total free memory is enough, but it is split into small non-contiguous holes, so a big request fails. Happens in contiguous allocation and segmentation. Fix: compaction (shuffle memory together) or use paging.
• Internal fragmentation: memory is given in fixed-size blocks; the unused part inside a block is wasted. Happens in paging (last page is rarely full). Average waste ≈ half a page per process.

Paging removes external fragmentation. Logical memory is cut into fixed-size pages; physical memory is cut into same-size frames. Any page can go into any free frame — no need to be contiguous. A per-process page table maps page number → frame number.

Address translation: if the page size is \( 2^n \) bytes, the CPU splits a logical address into a page number p (high bits) and an offset d (low n bits):

The page table lives in RAM, so a plain paged access needs two memory accesses (one for the table, one for the data). The TLB is a small, very fast hardware cache of recent page → frame translations. TLB hit: translation is almost free. TLB miss: go to the page table in memory.

Effective Access Time (EAT): with hit ratio \( h \), memory time \( m \), TLB time \( \epsilon \): \( EAT = h(m + \epsilon) + (1-h)(2m + \epsilon) \). Example: m = 100 ns, ε ≈ 0, h = 0.9 → EAT = 0.9×100 + 0.1×200 = 110 ns.

Segmentation divides a program the way the programmer sees it: code segment, data segment, stack segment, etc. Segments have different sizes. An address is a pair (segment number, offset). The segment table stores each segment's base and limit; the hardware checks offset < limit, then physical = base + offset. Because segments are variable-size, segmentation suffers external fragmentation.

Virtual memory lets a program be bigger than RAM. With demand paging, a page is loaded into RAM only when it is first used — "lazy loading". Each page table entry has a valid/invalid bit. Accessing an invalid page triggers a page fault. Steps of a page fault:

1. The MMU finds the invalid bit and traps to the OS.
2. The OS checks: is this a real invalid access (kill the process) or just a page not yet in RAM?
3. Find a free frame (if none, run a page replacement algorithm to evict one; write it to disk if dirty).
4. Read the wanted page from disk into the frame.
5. Update the page table (valid bit = 1, frame number).
6. Restart the instruction that faulted.

Effective access time with faults: if page fault rate is \( p \), memory access is \( m \), and fault service takes \( F \): \( EAT = (1-p) \times m + p \times F \). Faults are millions of times slower than RAM, so even a tiny \( p \) hurts a lot.

We use the classic reference string 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1 with 3 frames. In the tables below, each column is one reference; F marks a page fault, H a hit. Frames show their contents after the reference.

Evict the page that has been in memory the longest (the oldest arrival).

FIFO: 15 page faults (5 hits).

Evict the page that will not be used for the longest time in the future. It gives the minimum possible faults, but it needs future knowledge — so it is only a benchmark to compare against.

Optimal: 9 page faults. (At reference 4 we evict 1 because 0 and 2 are needed sooner; at reference 3 we evict 4 because it is never used again.)

Evict the page that was not used for the longest time in the past. LRU uses history as a guess of the future. It is close to Optimal and never suffers Belady's anomaly (it is a "stack algorithm").

LRU: 12 page faults. Summary on this string with 3 frames: Optimal 9 < LRU 12 < FIFO 15.

Normally more frames → fewer faults. But with FIFO, sometimes more frames give MORE faults. Classic string: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5 — FIFO gives 9 faults with 3 frames but 10 faults with 4 frames. LRU and Optimal never show this anomaly.

Thrashing: when a process does not have enough frames, it faults constantly — the system spends more time swapping pages than doing real work. CPU utilization drops, the OS thinks it should add more processes, and things get even worse.

Working set model: the working set is the set of pages a process used in the last \( \Delta \) references (its current "locality"). Give each process at least its working-set size of frames. If the total demand of all processes exceeds the number of frames, suspend some process — that prevents thrashing.

A file is a named collection of related data on storage. Typical attributes: name, identifier (a unique number), type, location on disk, size, protection (who can read/write/execute), timestamps (created/modified/accessed), owner. These attributes are stored in the directory / inode, not inside the file data.

Basic operations: create, open, read, write, seek (reposition), delete, truncate, close. The OS keeps an open-file table with the current position pointer for each open file.

• Single-level: all files in one directory. Naming clashes, no grouping.
• Two-level: one directory per user. Users are separated, but no sub-grouping.
• Tree: directories inside directories — what Windows/Linux use. Absolute path (from root, e.g. /home/user/a.txt) vs relative path (from the current directory).
• Acyclic graph: a tree plus shared files/directories via links (UNIX hard links, symbolic links). Must be careful about cycles and deletion.

How do we place a file's blocks on disk?

• Contiguous: the file occupies consecutive blocks. Directory stores (start, length).
• Linked: each block stores a pointer to the next block. Directory stores (first, last). FAT (File Allocation Table) is a smarter version: all the "next" pointers live in one table in memory.
• Indexed: one index block holds the addresses of all data blocks. Directory points to the index block.

UNIX uses inodes: one inode per file stores the attributes plus a mixed index — typically 12 direct pointers (to data blocks), 1 single indirect (points to a block full of pointers), 1 double indirect, and 1 triple indirect. Small files are fast (direct pointers), and huge files are still possible (indirect levels).

• Bit map (bit vector): one bit per block — 1 = free, 0 = used (or the opposite). Easy to find n consecutive free blocks; needs extra memory. Example: a 1 TB disk with 4 KB blocks needs 2²⁸ bits = 32 MB of bitmap.
• Linked list: free blocks are chained together. No wasted space, but slow to traverse and hard to grab contiguous runs.
• Grouping / counting: store addresses of many free blocks in one block, or store (start, count) pairs for runs of free blocks.

If power fails in the middle of a file operation, the file system can be left half-updated (metadata pointing to garbage). A journaling file system (ext4, NTFS) first writes the planned changes to a journal (log), then applies them, then marks them done. After a crash, the OS replays or discards journal entries — recovery takes seconds instead of a full disk scan (like old fsck).