Operating Systems | Semester 3 Core Notes
An operating system manages processes, CPU time, memory, files and devices, and provides services that programs use through system calls. These notes explain process states, scheduling, synchronization, deadlock and virtual memory, then connect the concepts to solved exam problems and runnable teaching programs.
Semester 3 - Page 2: Operating Systems. 36 numbered topics, highlighted rules, worked examples, answered exam questions, three diagrams and four complete Python 3 simulations. General common-core BTech CSE guide, not an official assessed syllabus or past-paper prediction. Compare your assigned outline.
Operating Systems study map
Topic map
- OS purpose and services
- Kernel, user mode and system calls
- OS structures and workload types
- Program, process and PCB
- Process states
- Context switch and interrupts
- Process creation and IPC
- Threads and shared state
- Scheduling metrics
- FCFS scheduling
- SJF and shortest remaining time
- Round robin
- Priority and feedback scheduling
- Multiprocessor and real-time scheduling
- Races and critical sections
- Mutexes, spinlocks and atomics
- Semaphores
- Condition variables and monitors
- Producer-consumer and readers-writers
- Deadlock conditions
- Prevention, avoidance and recovery
- Banker safety test
- Address spaces and relocation
- Paging and address splitting
- TLBs and effective access time
- Demand paging and page faults
- FIFO, LRU and optimal replacement
- Working set and thrashing
- Allocation and fragmentation
- Files, directories and descriptors
- Allocation, inodes and free space
- Buffering, durability and journaling
- Devices, interrupts and DMA
- Disk scheduling and SSD caveat
- Protection, security and virtualization
- Exam revision and limitations
1. OS purpose and services
An OS manages resources and provides controlled abstractions for programs. Virtualization, concurrency and persistence are useful organizing ideas.
Answer: No. Resource management, isolation and device control remain even without a graphical interface.
2. Kernel, user mode and system calls
User programs invoke controlled OS services through system calls. A library function is not automatically a system call; it may wrap one or work entirely in user space.
Answer: No. A mode transition is different from a process context switch.
3. OS structures and workload types
Monolithic kernels integrate many services; microkernel designs move selected services outside the kernel. Batch, time-sharing and real-time describe workload goals, not one universal implementation.
Answer: No. Correctness includes meeting specified timing constraints.
4. Program, process and PCB
A program is stored instructions; a process is a running instance with execution state and resources. A process control block records scheduling and management state.
Answer: No. It includes a current execution state and resources.
5. Process states
Ready waits for CPU time; running uses CPU; blocked waits for an event or I/O. Textbooks may add new, terminated or suspended states.
Answer: Not until its waiting condition is resolved.
6. Context switch and interrupts
A context switch saves/restores execution state. Interrupts notify events; traps provide synchronous entry for exceptions or system calls. Switching adds overhead.
Answer: No. The handler may return to the same process.
7. Process creation and IPC
Creation, execution and waiting depend on OS APIs. In POSIX, fork duplicates a process, exec replaces its program image and wait collects child status. IPC includes pipes, shared memory and messages.
Answer: No. It replaces the current process image on success.
8. Threads and shared state
Threads in a process share address space and many resources, but have separate stacks and execution registers. User/kernel threading mappings affect scheduling behavior.
Answer: They can share explicitly mapped memory; default private address spaces are not the only arrangement.
9. Scheduling metrics
For a single CPU-burst model, turnaround=completion-arrival, waiting=turnaround-burst, response=first-run-arrival. State assumptions about I/O and switch cost.
Answer: No. Time spent blocked on I/O must be accounted for separately.
10. FCFS scheduling
First-come first-served chooses ready work in arrival order and is non-preemptive in the basic model. Long work can delay short work, the convoy effect.
Answer: Advance to the next arrival rather than inventing waiting work.
11. SJF and shortest remaining time
Non-preemptive SJF chooses the smallest available burst estimate. SRTF can preempt for a smaller remaining estimate. Long jobs may starve.
Answer: No. Schedulers need estimates or workload information.
12. Round robin
Give ready tasks at most a quantum before requeueing unfinished work. Specify arrivals, tie rules and context-switch overhead.
Answer: FCFS for this single-burst, all-arrive-together model.
FCFS, SJF and round-robin simulation
from collections import deque
def schedule(bursts, policy="fcfs", quantum=2):
# All arrive at zero; one CPU burst, no I/O or switch cost.
if any(type(b) is not int or b <= 0 for b in bursts):
raise ValueError("positive integer bursts required")
if policy not in {"fcfs", "sjf", "rr"}:
raise ValueError("unknown policy")
if type(quantum) is not int or quantum <= 0:
raise ValueError("positive integer quantum required")
order = list(range(len(bursts)))
if policy == "sjf":
order.sort(key=lambda i: (bursts[i], i))
ready = deque(order)
left = list(bursts)
first = [None] * len(bursts)
completion = [0] * len(bursts)
trace = []
time = 0
while ready:
i = ready.popleft()
if first[i] is None:
first[i] = time
run = min(left[i], quantum) if policy == "rr" else left[i]
trace.append((i, time, time + run))
time += run
left[i] -= run
if left[i]:
ready.append(i)
else:
completion[i] = time
waiting = [completion[i] - bursts[i] for i in range(len(bursts))]
return trace, completion, waiting, first
for policy in ["fcfs", "sjf", "rr"]:
trace, completion, waiting, response = schedule([5, 2, 3], policy)
print(policy, trace)
print("completion:", completion, "waiting:", waiting)
print("average wait:", f"{sum(waiting) / len(waiting):.3f}", "ms")
try:
schedule([5, 0])
except ValueError:
print("invalid burst rejected")Checked output:
fcfs [(0, 0, 5), (1, 5, 7), (2, 7, 10)] completion: [5, 7, 10] waiting: [0, 5, 7] average wait: 4.000 ms sjf [(1, 0, 2), (2, 2, 5), (0, 5, 10)] completion: [10, 2, 5] waiting: [5, 0, 2] average wait: 2.333 ms rr [(0, 0, 2), (1, 2, 4), (2, 4, 6), (0, 6, 8), (2, 8, 9), (0, 9, 10)] completion: [10, 4, 9] waiting: [5, 2, 6] average wait: 4.333 ms invalid burst rejected
13. Priority and feedback scheduling
Priorities choose among ready jobs; aging can reduce starvation. MLFQ adjusts priority using observed behavior and needs explicit rules for boosts and time allotments.
Answer: No. Queue levels, boosts and allotments are policy choices.
14. Multiprocessor and real-time scheduling
Multiple CPUs add load balancing, cache affinity and shared-runqueue issues. Real-time policies depend on deadlines, execution budgets and assumptions.
Answer: No. It omits timing and platform assumptions needed for a guarantee.
15. Races and critical sections
A race occurs when correctness depends on an uncontrolled interleaving. Critical sections protect shared invariants; compiler and hardware memory rules matter.
Answer: No. Unsynchronized conflicting accesses can cause undefined behavior; use a supported synchronization model.
16. Mutexes, spinlocks and atomics
A mutex has ownership and may block; a spinlock waits actively. Atomic operations support defined individual operations, but compound invariants may still need locks.
Answer: No. Wait duration, CPU count and scheduling context affect the choice.
17. Semaphores
Wait acquires a permit or blocks; post releases a permit. Counting semaphores coordinate capacity; ownership semantics differ from a mutex.
Answer: No. Ownership and permitted release behavior differ.
18. Condition variables and monitors
A condition variable waits for a predicate under a mutex. Recheck in a while loop because wakeups do not guarantee the predicate. A monitor groups guarded state and operations.
Answer: Not generally. Condition-variable signals are not counting-semaphore permits.
19. Producer-consumer and readers-writers
Bounded buffers need capacity and mutual exclusion. Readers-writers policies must specify fairness. Sleeping or spinning without a protocol is not synchronization.
Answer: Yes. Holding a needed mutex while blocking on a permit can deadlock another participant.
20. Deadlock conditions
Classical resource deadlock requires mutual exclusion, hold-and-wait, no preemption and circular wait. Starvation and livelock are different failures.
Answer: Not generally. The simple cycle test is sufficient in the single-instance model.
21. Prevention, avoidance and recovery
Prevention breaks a necessary condition; avoidance checks allocations against future claims; detection finds existing deadlock and recovery chooses a policy..
Answer: No. Unsafe means no guaranteed safe completion sequence under the model; deadlock may not yet exist.
22. Banker safety test
Compute Need=Max-Allocation. Start Work=Available; repeatedly select an unfinished process whose Need fits Work, then release its Allocation to Work.
Answer: No. Validate request<=Need and <=Available, tentatively allocate, then test the resulting state.
Banker safety simulation
def safety(allocation, maximum, available):
# Nonnegative integer resources; fixed maximum claims.
def valid(values):
return all(type(v) is int and v >= 0 for v in values)
n, m = len(allocation), len(available)
if m == 0 or len(maximum) != n or not valid(available):
raise ValueError("invalid dimensions or resources")
if any(len(row) != m or not valid(row)
for row in allocation + maximum):
raise ValueError("invalid row")
if any(allocation[i][j] > maximum[i][j]
for i in range(n) for j in range(m)):
raise ValueError("allocation exceeds claim")
need = [[maximum[i][j] - allocation[i][j] for j in range(m)]
for i in range(n)]
work = list(available)
done = [False] * n
sequence = []
while len(sequence) < n:
progress = False
for i in range(n):
if not done[i] and all(need[i][j] <= work[j] for j in range(m)):
work = [work[j] + allocation[i][j] for j in range(m)]
done[i] = True
sequence.append(i)
progress = True
if not progress:
return False, sequence
return True, sequence
allocation = [[1], [1]]
maximum = [[2], [3]]
print("available 1:", safety(allocation, maximum, [1]))
print("available 0:", safety(allocation, maximum, [0]))
try:
safety([[3]], [[2]], [1])
except ValueError:
print("invalid claim rejected")Checked output:
available 1: (True, [0, 1]) available 0: (False, []) invalid claim rejected
23. Address spaces and relocation
Virtual addresses describe a process view. Base/limit relocation translates and checks bounds; segmentation uses separate regions with sizes and permissions.
Answer: Only with enforced validity and access permissions.
24. Paging and address splitting
Fixed-size pages map to frames; offset is unchanged. With page size S, page=address//S and offset=address%S.
Answer: No. The page table supplies the mapping.
Address translation with explicit page mapping
def translate(address, page_size, mapping):
if type(address) is not int or address < 0:
raise ValueError("nonnegative integer address required")
if type(page_size) is not int or page_size <= 0:
raise ValueError("positive integer page size required")
if any(type(page) is not int or page < 0 or
type(frame) is not int or frame < 0
for page, frame in mapping.items()):
raise ValueError("invalid mapping")
page, offset = divmod(address, page_size)
if page not in mapping:
raise KeyError("page absent from supplied map")
return page, offset, mapping[page] * page_size + offset
print("page, offset, physical:", translate(8197, 4096, {2: 7}))
for address in [8192, 12287]:
print(address, translate(address, 4096, {2: 7}))
try:
translate(0, 4096, {2: 7})
except KeyError:
print("absent mapping reported")
try:
translate(-1, 4096, {2: 7})
except ValueError:
print("invalid address rejected")Checked output:
page, offset, physical: (2, 5, 28677) 8192 (2, 0, 28672) 12287 (2, 4095, 32767) absent mapping reported invalid address rejected
An absent key here means only that the supplied dictionary has no mapping. It does not distinguish a valid nonresident page from an invalid address; a real OS tracks validity, residence and permissions separately.
25. TLBs and effective access time
A TLB caches translations, not the page contents. Timing formulas must state lookup ordering, miss work and whether faults are excluded.
Answer: No. A fault introduces a much larger separate path.
26. Demand paging and page faults
A nonresident valid page can be loaded on demand; an invalid or disallowed address is different. Fault handling may allocate, evict and update mappings.
Answer: No. Demand paging uses faults as part of normal operation.
27. FIFO, LRU and optimal replacement
FIFO evicts oldest admission, LRU least recent use, optimal farthest future use. Optimal is an offline benchmark. State frame count and hit behavior.
Answer: Yes. Belady's anomaly can occur; LRU's stack property avoids this anomaly in the ideal model.
FIFO and LRU page replacement simulation
def replacement(references, capacity, policy):
if type(capacity) is not int or capacity <= 0:
raise ValueError("positive integer capacity required")
if policy not in {"fifo", "lru"}:
raise ValueError("unknown policy")
if any(type(page) is not int or page < 0 for page in references):
raise ValueError("nonnegative integer pages required")
frames, trace, faults = [], [], 0
for page in references:
hit = page in frames
if hit:
if policy == "lru":
frames.remove(page)
frames.append(page)
else:
faults += 1
if len(frames) == capacity:
frames.pop(0)
frames.append(page)
trace.append((page, "hit" if hit else "fault", list(frames)))
return faults, trace
references = [1, 2, 1, 3, 1, 2]
for policy in ["fifo", "lru"]:
faults, trace = replacement(references, 2, policy)
print(policy, "faults:", faults)
for row in trace:
print(row)
try:
replacement(references, 0, "fifo")
except ValueError:
print("invalid capacity rejected")Checked output:
fifo faults: 5 (1, 'fault', [1]) (2, 'fault', [1, 2]) (1, 'hit', [1, 2]) (3, 'fault', [2, 3]) (1, 'fault', [3, 1]) (2, 'fault', [1, 2]) lru faults: 4 (1, 'fault', [1]) (2, 'fault', [1, 2]) (1, 'hit', [2, 1]) (3, 'fault', [1, 3]) (1, 'hit', [3, 1]) (2, 'fault', [1, 2]) invalid capacity rejected
FIFO lists admission order and does not refresh on hits; LRU lists oldest-to-newest use and moves a hit to the end. These simple Python lists make membership and removal linear in frame count, so do not infer an efficient OS implementation from the simulator.
Put the policy rules into practice with six solved FIFO, LRU and Optimal page replacement problems, including frame tables, hit ratios and Belady's anomaly. For implementation, compare the FIFO and LRU C programs in the OS lab file.
28. Working set and thrashing
A working set is recently needed pages over a defined window. Too few frames can cause repeated faults and low useful progress. Local/global replacement affects competition.
Answer: No. Memory pressure can cause more paging and less useful CPU work.
29. Allocation and fragmentation
Contiguous placement has external fragmentation; fixed pages can waste space internally. First-fit, best-fit and worst-fit choose holes under stated policies.
Answer: No. It removes the same contiguous-allocation external problem but can still waste space internally and use metadata.
30. Files, directories and descriptors
A file is a persistent object; names live in directories. A file descriptor references open state with access and position semantics. Names and open handles have different lifetimes.
Answer: No. Rename, unlink and replacement can change name bindings.
31. Allocation, inodes and free space
File systems track data blocks, metadata and unused blocks. Contiguous, linked and indexed layouts trade locality, growth and random access. An inode-like record stores metadata and references, not every filename.
Answer: No. This is a conceptual model, not a universal on-disk format.
32. Buffering, durability and journaling
A successful buffered write is not automatically durable. Flush/sync and crash guarantees depend on the API and file system. Journaling orders logged changes for recovery; it is not a backup.
Answer: Not universally. Directory operations and platform guarantees need separate handling.
33. Devices, interrupts and DMA
Drivers translate OS requests for devices. Polling checks status; interrupts notify events. DMA transfers data with less CPU copying but still requires setup and coordination.
Answer: No. Setup, completion, mapping and synchronization remain.
34. Disk scheduling and SSD caveat
FCFS follows order; SSTF chooses nearest request and may starve distant ones; SCAN sweeps directionally, C-SCAN returns to one end. State endpoints and direction for seek calculations.
Answer: No. SSDs have different access and erase behavior, not a moving head.
35. Protection, security and virtualization
Protection controls access; security considers threats and defenses. Least privilege limits damage. A virtual machine virtualizes a machine interface; containers isolate workloads sharing a host kernel.
Answer: No. Their shared-kernel and hypervisor models differ.
36. Exam revision and limitations
Explain assumptions, trace state and distinguish policy from mechanism. Simulators here teach algorithms; they do not manage your computer or certify a college syllabus.
Answer: Inputs, units, policy/tie rules, intermediate trace, checked result and limits.
Scheduling comparison: A=5,B=2,C=3 ms, arrival zero, one burst, no switch cost. Values remain associated with job labels even when execution order changes.
Scheduling answer table
| Policy | Completion times | Waiting times | Average wait |
|---|---|---|---|
| FCFS A,B,C | A5 B7 C10 | A0 B5 C7 | 4.000 ms |
| SJF B,C,A | A10 B2 C5 | A5 B0 C2 | 2.333 ms |
| RR quantum2 | A10 B4 C9 | A5 B2 C6 | 4.333 ms |
Checked calculation table
| Example | Result | Assumption |
|---|---|---|
| 8197 / 4096-byte pages | Page2,offset5 | Integer quotient/remainder |
| Frame7 translation | 28677 bytes | Supplied valid mapping |
| TLB hit90% | 120 ns | Sequential lookup10ns; memory100ns; one-level table; no faults |
| Replacement 1,2,1,3,1,2 / 2frames | FIFO5,LRU4,optimal4 faults | Initially empty; hits as defined |
| Banker available1 / available0 | Safe[0,1] / unsafe | Allocation[1,1],Max[2,3],one resource |
| Head50 requests10,60,20 | FCFS130,SSTF60 tracks | No endpoints needed for these two policies |
| 6KiB in 4KiB pages | 2KiB unused | Two pages; no metadata counted |
Distinctions to remember
- Ready is CPU waiting; blocked is event waiting.
- A system-call mode transition is not always a process switch.
- Unsafe is not automatically deadlocked.
- A TLB miss is not automatically a page fault.
- Valid nonresident pages differ from invalid addresses.
- Buffered writes differ from durable storage; journaling differs from backups.
Practice resources
Use the Operating Systems Lab File, Lab Files index and Online Compiler. Choose Python for the portable simulations above; choose C for the linked C lab programs. POSIX process/thread examples need a compatible environment.
Sources
Definitions and policy limits use open textbook chapters and course notes. Worked examples and simulator code here are original teaching material.
Comments
Post a Comment