Operating Systems exam preparation.
Practice questions for every unit in the style of the R23 end exam, a model answer for each, and a one-page revision summary. Built on the official syllabus units.
- Practice questions in the exam's style
- Drafted with AI and checked by a second AI pass. Doubtful points were verified against public sources. Report a mistake
- Units
- 5
- Questions
- 60
- 2-mark
- 30
- 10-mark
- 30
- Done
- Checked on
Exam guide
Paper pattern
Semester-end theory paper, 70 marks, from the JNTUK B.Tech R23 Regulations, end-examination pattern for theory subjects.
- Question 1 · 20 marksTen compulsory short-answer questions of 2 marks each (two from every unit).
- Questions 2 to 6 · 50 marksFive either/or questions of 10 marks each, one per unit. You answer one of the two in each.
- The semester-end examination carries 70 marks; internal assessment carries 30.
- Mid-semester examinations are separate: a 20-minute objective paper (10 marks) and a 90-minute subjective paper with three either/or questions of 10 marks (condensed to 15 marks).
- The regulations text does not state the length of the end examination. Use the duration printed on your hall ticket or question paper.
How to split your time
This plan assumes a 3-hour paper. If yours is different, keep the same proportions. Marks per minute stay roughly even across Question 1 and the 10-mark answers.
- 10 minRead the paper and choose one option in each either/or question
- 30 minQuestion 1: ten short answers (about 3 minutes each)
- 130 minQuestions 2 to 6: one 10-mark answer per unit (about 26 minutes each)
- 10 minFinal check of numbering, calculations and diagrams
Study tips for Operating Systems
- Practise CPU scheduling problems (FCFS, SJF, SRTF, Priority, Round Robin) by drawing a neat Gantt chart first, then tabulating completion, turnaround and waiting times for each process before computing the averages. Recheck every sum so one slip does not spoil the final answer.
- For the Banker's algorithm, always write out the Need matrix (Max minus Allocation) and show each step of the safety sequence with the updated Available vector. Graders can then follow your reasoning even if one number goes wrong.
- Work page replacement (FIFO, LRU, Optimal) and disk scheduling (FCFS, SSTF, SCAN, C-SCAN, LOOK) problems on paper with a frame-by-frame table or a head-movement diagram, and count page faults or total cylinder movement step by step.
- Write semaphore-based pseudocode for the producer-consumer, readers-writers and dining philosophers problems from memory until you can reproduce wait and signal placement correctly. Practise labelled diagrams too, such as the process state diagram, the paging hardware with TLB, and the file allocation methods.
Operating Systems Overview and System Structures
Syllabus: Introduction and operating system functions; Operating system operations; Computing environments; Free and open-source operating systems; Operating system services; User and operating-system interface; System calls and types of system calls; System programs; Operating system design and implementation; Operating system structure; Building and booting an operating system; Operating system debugging
One-page revision summary
- An operating system is an intermediary between users and hardware, acting as a resource allocator and control program; the kernel is the program that runs at all times.
- Multiprogramming increases CPU utilisation by keeping several jobs in memory, while multitasking switches rapidly to give users quick response.
- Computing environments include traditional, mobile, client-server, peer-to-peer, cloud (SaaS, PaaS, IaaS; public, private, hybrid) and real-time embedded systems.
- Open-source systems such as Linux and FreeBSD ship their source code. The GNU GPL is a copyleft licence: anyone who distributes a modified version must release its source under the same licence.
- OS services are grouped into user-convenience services (UI, execution, I/O, files, communication, error detection) and system-efficiency services (allocation, logging, protection).
- Users reach the OS through a command interpreter (shell), a GUI, a touch-screen interface or batch files.
- Programs normally call system calls through APIs such as POSIX or the Windows API, and the system-call interface uses a numbered table to find the kernel routine.
- System programs (system utilities) sit between the kernel and application programs and provide a convenient environment for developing and running programs. Most users see the OS through these programs rather than through raw system calls.
- System-program categories: file management (create, delete, copy, rename, list); status information (date, time, free memory, disk space, logs); file modification (editors, search tools); programming-language support (compilers, assemblers, debuggers, interpreters); program loading and execution (loaders, linkers); communications (remote login, file transfer, messaging); background services (daemons).
- Background services, or daemons, are started at boot and run continuously; examples are network listeners, schedulers and logging services.
- Application programs such as browsers, word processors and games are often supplied with an OS but are not part of the OS itself.
- OS design starts with user goals and system goals, and it separates policy (what to do) from mechanism (how to do it).
- Modern operating systems are written mostly in C or C++ with a little assembly, which makes them easier to port and maintain.
- OS structures include monolithic, layered, microkernel, loadable-module and hybrid designs, each trading performance against simplicity and extensibility.
- Building Linux involves configuring, compiling the kernel and modules, installing them and rebooting; a distribution can also be installed in a virtual machine.
- Booting proceeds from firmware (BIOS or UEFI) to a disk-resident boot loader (for example GRUB), then to the kernel and initramfs, the root file system, and finally init/systemd.
- OS debugging uses log files, core dumps and crash dumps for failures, and counters (top, vmstat) and tracing tools (strace, perf, BCC/eBPF) for performance tuning.
Learn these by heart
- Mode bit: 0 = kernel mode, 1 = user mode; privileged instructions run only in kernel mode.
- Mechanism decides how something is done; policy decides what will be done.
- Six types of system calls: process control, file management, device management, information maintenance, communications, protection.
- Three ways to pass system-call parameters: in registers, in a memory block whose address is in a register, or on the stack.
- Seven categories of system programs: file management, status information, file modification, programming-language support, program loading and execution, communications, background services.
- Boot sequence: Power on → BIOS/UEFI (POST) → boot loader (GRUB, on disk) → kernel + initramfs → mount root → init/systemd (PID 1).
- Timer = fixed-rate clock + counter; an interrupt at zero returns control to the OS and prevents a program from monopolising the CPU.
- Microkernel: a minimal kernel with services in user space that communicate by message passing.
2-mark questions
1 Define an operating system and state any two of its functions. 2 marks
An operating system is system software that acts as an intermediary between the user and the computer hardware, managing resources and providing an environment for running programs. Two functions:
- Process management: creating, scheduling and terminating processes.
- Memory management: allocating and freeing main memory for programs.
2 What is dual-mode operation? Why is a mode bit needed? 2 marks
In dual-mode operation the CPU runs either in user mode (mode bit = 1) or kernel mode (mode bit = 0). Privileged instructions execute only in kernel mode. The hardware mode bit tells the CPU which mode is active, so a faulty or malicious user program cannot directly harm the OS or other programs.
3 Define a system call and give one example. 2 marks
A system call is the programming interface through which a user program requests a service from the OS kernel. It causes a trap that switches the CPU from user mode to kernel mode. Example: open() in UNIX/Linux asks the kernel to open a file and return a file descriptor.
4 Differentiate between a command-line interface and a graphical user interface. 2 marks
In a CLI the user types text commands, which a shell such as bash interprets. It is powerful and scriptable but requires remembering commands.
In a GUI the user works with windows, icons, menus and a pointer on a desktop. It is easy to learn but less efficient for repetitive tasks and uses more resources.
5 Distinguish between mechanism and policy in operating system design. 2 marks
A mechanism decides how something is done, while a policy decides what will be done. For example, the timer is a mechanism for CPU protection, but how long the timer is set for a given user is a policy. Separating the two lets policies change without rewriting mechanisms.
6 What is a bootstrap program (boot loader)? 2 marks
A bootstrap program is the code that starts the computer at power-on. A small bootstrap stored in firmware (BIOS or UEFI) runs self-tests, initialises the hardware and loads a boot loader from disk, such as GRUB. The boot loader then loads the kernel into memory and starts its execution.
10-mark questions
1 Explain the various services provided by an operating system. Describe the user interfaces through which users access these services. 10 marks
An operating system provides an environment in which programs execute. Some of its services make the system convenient for the user, while others keep the system itself running efficiently.
Services helpful to the user:
1. User interface: Almost every OS provides one. It may be a command-line interface, a graphical user interface, a touch-screen interface or a batch interface where commands are stored in files. 2. Program execution: The OS loads a program into memory and runs it. It then ends the program normally or abnormally and reports any error. 3. I/O operations: Users cannot control devices directly, for reasons of efficiency and protection, so the OS performs I/O on their behalf. 4. File-system manipulation: Programs can create, delete, read, write, search and list files and directories, and manage their permissions. 5. Communication: Processes exchange information on the same machine or across a network, using shared memory or message passing. 6. Error detection: The OS watches for errors in the CPU, memory and devices, such as a parity error or a network failure. It also watches user programs for faults like arithmetic overflow or illegal memory access, and takes suitable action.
Services for efficient operation of the system:
7. Resource allocation: CPU cycles, memory, storage and devices are shared among concurrent jobs using scheduling and allocation routines. 8. Logging (accounting): The OS records which users use how much of each resource, for billing or statistics. 9. Protection and security: Protection controls access to resources. Security defends the system against outsiders through authentication such as passwords.
User and OS interface:
- Command interpreter (shell): Examples are bash and the C shell. The shell reads a command and executes it. In some systems the command code is built into the interpreter. In UNIX, most commands are separate programs; for example, rm file.txt loads the rm program and passes it the file name.
- GUI: Uses a desktop metaphor in which clicking an icon opens a file or runs a program.
- Touch interface: Mobile devices use gestures such as tap and swipe.
Administrators and power users prefer the CLI because it supports shell scripts. Casual users prefer a GUI or touch interface.
In conclusion, OS services combine convenience (interface, execution, I/O, files, communication, error detection) with efficiency and safety (allocation, accounting, protection), and the user interface is the gateway to all of them.
2 What is a system call? Explain how system calls are used, how parameters are passed to the OS, and the types of system calls with examples. 10 marks
System calls are the interface to the services an operating system provides. They are generally available as functions written in C or C++, with some low-level routines in assembly.
1. How system calls are used: Even a simple program that copies one file to another needs many system calls:
- Write a prompt and read the two file names.
- Open the input file and create the output file.
- Loop: read from the input and write to the output.
- Close both files and print a completion message.
- Terminate normally.
Each step may also need error handling, for example when a file does not exist.
2. API and system-call interface: Programmers usually call an API rather than raw system calls. Common APIs are the Windows API, POSIX (UNIX, Linux, macOS) and the Java API. The run-time support library provides a system-call interface that works as follows:
- Each system call has a number, and a table is indexed by these numbers.
- When an API function is called, the interface traps into the kernel.
- The kernel runs the matching routine and returns the status and result.
The caller does not need to know how the call is implemented.
3. Parameter passing: There are three methods.
- Registers: parameters are placed in CPU registers. This is the simplest method but limits the number of parameters.
- Memory block: parameters are stored in a block or table in memory, and the block's address is passed in a register. Linux uses this when there are more than five parameters.
- Stack: the program pushes parameters onto the stack, and the OS pops them off.
The block and stack methods do not limit the number or length of parameters.
4. Types of system calls:
- Process control (create, terminate, load, execute, wait): UNIX fork(), exec(), exit(), wait(); Windows CreateProcess(), ExitProcess(), WaitForSingleObject().
- File management (create, open, read, write, close, delete): UNIX open(), read(), write(), close(); Windows CreateFile(), ReadFile(), WriteFile(), CloseHandle().
- Device management (request, release, read and write devices): UNIX ioctl(), read(), write(); Windows SetConsoleMode(), ReadConsole(), WriteConsole().
- Information maintenance (time, date, process attributes): UNIX getpid(), alarm(), sleep(); Windows GetCurrentProcessID(), SetTimer(), Sleep().
- Communications (message passing, shared memory): UNIX pipe(), shm_open(), mmap(); Windows CreatePipe(), CreateFileMapping(), MapViewOfFile().
- Protection (get or set permissions): UNIX chmod(), umask(), chown(); Windows SetFileSecurity().
In conclusion, system calls are the controlled gateway from user programs into the kernel. APIs hide their details and make programs portable.
3 Explain the functions of an operating system and its operations: interrupts, multiprogramming, multitasking, dual-mode operation and the timer. 10 marks
An operating system manages the computer hardware and provides a base for application programs.
- From the user's view, it should be easy to use.
- From the system's view, it is a resource allocator and a control program.
- The kernel is the one program that runs at all times.
Main functions:
- Process management: create, delete, schedule and synchronise processes.
- Memory management: track memory use and allocate or free space.
- Storage and file management: files, directories, disks and free-space management.
- I/O management: device drivers, buffering, caching and spooling.
- Protection and security: controlling access and defending against attacks.
Operating-system operations:
1. Interrupt-driven nature: After booting, the kernel waits for events.
- Hardware raises interrupts.
- Software raises traps (exceptions), either because of errors such as division by zero or invalid memory access, or because a program requests a service through a system call.
- A separate service routine handles each type of interrupt.
2. Multiprogramming: Several jobs are kept in memory so the CPU always has one to run. When a job waits for I/O, the CPU switches to another job. This keeps the CPU busy and raises utilisation.
3. Multitasking (time sharing): This extends multiprogramming. The CPU switches among jobs so frequently that each user can interact with a running program, with response times usually under a second. It requires CPU scheduling, memory management, virtual memory and protection.
4. Dual-mode operation: A hardware mode bit separates the two modes (0 = kernel, 1 = user).
- The system boots in kernel mode, then starts user programs in user mode.
- Any trap or interrupt switches the CPU to kernel mode.
- The OS switches back to user mode before returning control to the program.
- Privileged instructions (I/O control, timer management, interrupt management) can run only in kernel mode. If a user program tries one, the hardware traps to the OS, which treats it as illegal.
- CPUs that support virtualisation add an extra mode for the virtual machine manager.
5. Timer: The timer stops a user program from looping forever or never giving back the CPU.
- It is built from a fixed-rate clock and a counter.
- The OS loads the counter, which is a privileged operation.
- The counter is decremented on every tick.
- When it reaches zero, an interrupt returns control to the OS, which may end the program or give it more time.
In conclusion, the OS performs its functions safely because of interrupts, multiprogramming, multitasking, dual-mode protection and the timer.
4 Discuss the different computing environments. Also explain free and open-source operating systems. 10 marks
A computing environment describes how computing resources are organised and accessed, and the OS must adapt to each one. Free and open-source operating systems have also become important in education and industry.
Computing environments:
1. Traditional computing: Offices once used PCs connected to servers for file and print services. Web portals, thin clients and wireless networks now extend this model.
2. Mobile computing: Smartphones and tablets are portable and contain sensors such as GPS, accelerometers and gyroscopes. They connect through Wi-Fi or cellular data. The leading mobile OSes are Apple iOS and Google Android.
3. Client-server computing: Servers answer requests from clients.
- A compute server performs an action, such as a database query, and returns the result.
- A file server lets clients create, read and update files; a web server delivering pages is an example.
4. Peer-to-peer computing: No node is fixed as client or server; each can act as either. A new node registers its services with a central lookup service or broadcasts requests to discover peers. Examples are file-sharing networks and some VoIP services.
5. Cloud computing: Computing, storage and applications are delivered as services over a network, built on virtualisation.
- Deployment types: public, private and hybrid clouds.
- SaaS: applications, such as an online office suite.
- PaaS: a ready software stack, such as a database server.
- IaaS: raw servers or storage.
6. Real-time embedded systems: These control cars, microwave ovens, robots and medical devices. Their real-time OSes have fixed time constraints: processing must finish within its deadline, or the system fails.
Free and open-source operating systems:
- Open source: the OS is distributed as source code, not only as compiled binaries, for example Linux and FreeBSD. Closed-source systems such as Windows are proprietary.
- Free software (Free Software Foundation, GNU project): users may run, study, change and redistribute it.
- GNU GPL: a copyleft licence. Anyone who distributes a modified version must make its source code available to the recipients under the same licence. Changes kept for private use need not be released.
- Open-source software is not always free software in this stricter sense.
- GNU/Linux: the Linux kernel plus GNU tools, packaged in distributions such as Ubuntu, Fedora and Debian.
- BSD UNIX: variants include FreeBSD, NetBSD and OpenBSD; Darwin, the core of macOS, is also open source.
Benefits: students learn from real code, a large community fixes bugs, public review improves security, and there is no licence cost. Such systems can be tried safely in a virtual machine.
In conclusion, operating systems now span devices from embedded controllers to clouds, and open-source systems make studying and changing them practical.
5 Explain operating system design goals and implementation, and describe the various operating system structures with their merits and demerits. 10 marks
A large operating system must be engineered carefully so that it works correctly and can be modified easily.
Design and implementation:
- User goals: the system should be convenient, easy to learn, reliable, safe and fast.
- System goals: it should be easy to design, implement and maintain, as well as flexible, reliable, error-free and efficient.
- Policy versus mechanism: separating what is done from how it is done is a key principle.
- Implementation: modern OSes are written mostly in C or C++, with small parts in assembly. This makes them easier to write, understand, debug and port.
Structures:
1. Monolithic structure: All kernel functions sit in one static binary running in a single address space.
- Example: in original UNIX, the kernel provided the file system, CPU scheduling and memory management through system calls.
- Merits: little overhead and fast communication inside the kernel.
- Demerits: hard to implement, extend and debug.
2. Layered approach: The OS is divided into layers, from layer 0 (hardware) up to layer N (user interface). Each layer uses only the services of the layers below it.
- Merits: simple to build and debug. Layer 1 is tested first, then layer 2 assuming layer 1 is correct, and so on.
- Demerits: layers are hard to define, and requests crossing many layers reduce performance.
3. Microkernel: Non-essential parts are moved out of the kernel into user-level programs. The kernel keeps only minimal process management, memory management and message passing. A client program and a file server communicate by exchanging messages through the kernel.
- Examples: Mach and QNX.
- Merits: easy to extend and port. It is also secure and reliable, because a failed service does not crash the kernel.
- Demerits: copying messages and switching between processes adds performance overhead.
4. Loadable kernel modules: A core kernel links in extra services, such as device drivers and file systems, at boot time or while running. Linux uses this approach.
- Each module has a defined interface, and any module can call another directly.
- This makes it more flexible than layering and more efficient than a microkernel.
5. Hybrid systems: Most real systems combine structures.
- macOS and iOS use the Darwin kernel, which combines the Mach microkernel with BSD UNIX parts.
- Android runs on a modified Linux kernel with the ART runtime and native libraries.
- Windows is largely monolithic but keeps some microkernel features and supports loadable modules.
In conclusion, good design starts from clear goals and the separation of policy from mechanism. The chosen structure is a trade-off between performance, simplicity and extensibility.
6 Explain how an operating system is built and booted. Discuss the techniques used for operating system debugging, including failure analysis and performance tuning. 10 marks
An operating system is designed to run on many machine configurations. Before use it must be built (generated) for a target system and then booted. Once running, its failures and performance problems are found and fixed through debugging.
Building an OS (Linux example):
1. Obtain the source code. 2. Configure the kernel. For example, make menuconfig chooses features and drivers and writes a .config file. 3. Compile the kernel with make, which produces the kernel image (vmlinuz). 4. Compile the modules with make modules. 5. Install the modules with make modules_install. 6. Install the new kernel with make install, then reboot.
As an alternative, an ISO image of a distribution can be installed inside a virtual machine such as VirtualBox.
The degree of tailoring varies:
- A fully custom-compiled kernel is the most efficient but the least general.
- Linking precompiled modules is quicker to build.
- A table-driven system that selects components at run time is the most general but also the largest.
Booting:
1. At power-on, firmware (BIOS or UEFI) runs. 2. The firmware runs diagnostics (POST) and initialises devices. 3. With BIOS, a tiny loader in the boot block (MBR) loads a second-stage boot loader. UEFI uses a single complete boot manager instead. 4. The boot loader, for example GRUB, loads the kernel and an initramfs (a temporary root file system) into memory. Boot parameters can be chosen at this stage. 5. The kernel initialises hardware and drivers, then switches to the real root file system. 6. The kernel starts the first process, init or systemd. This process starts system services and finally presents the login prompt.
Operating system debugging:
1. Failure analysis:
- When a process fails, the OS writes error information to a log file and may save the process's memory as a core dump. A debugger such as gdb can then examine the dump.
- When the kernel fails, the event is called a crash. The kernel's memory state is saved as a crash dump, often in a reserved disk area, because the file system may be unreliable at that moment.
2. Performance tuning: The goal is to find and remove bottlenecks.
- Counters: tools such as ps, top, vmstat, netstat and iostat read system counters, often through the /proc file system. Windows offers the Task Manager.
- Tracing: tools such as strace (system calls), gdb, perf and tcpdump record data for specific events.
3. BCC and eBPF: These Linux tools perform dynamic tracing of the running kernel. Small verified programs are inserted safely with low overhead, so even live production systems can be studied.
In conclusion, building tailors the OS to its hardware, booting brings the kernel to life step by step, and debugging tools keep the system correct and fast.
Processes, Threads and CPU Scheduling
Syllabus: Process concept; Process scheduling; Operations on processes; Inter-process communication; Multithreading models; Thread libraries; Threading issues; CPU scheduling: basic concepts; Scheduling criteria; Scheduling algorithms; Multiple-processor scheduling
One-page revision summary
- A process is a program in execution with text, data, heap and stack sections. The kernel represents it by a PCB, and it moves through the new, ready, running, waiting and terminated states.
- The long-term scheduler controls the degree of multiprogramming. The short-term scheduler picks the next process for the CPU. The medium-term scheduler swaps processes out and back in.
- In UNIX, fork() creates a child, exec() loads a new program, wait() collects a child's exit status and exit() ends the process.
- IPC uses either shared memory or message passing. Shared memory is fast but the processes must synchronise themselves. Message passing (send/receive) can be direct or indirect, blocking or non-blocking, with zero, bounded or unbounded buffering.
- Multithreading models: many-to-one blocks the whole process when one thread makes a blocking call; one-to-one gives true parallelism but needs one kernel thread per user thread; many-to-many multiplexes user threads onto an equal or smaller number of kernel threads.
- Pthreads is a POSIX specification, not an implementation. Windows threads are provided by a kernel-level library. Java threads are managed by the JVM on top of the host OS's thread library.
- Implicit threading is a separate topic from the threading issues. Here libraries, compilers or run-time systems create and manage threads instead of the programmer. Examples are thread pools (a fixed set of threads waits for tasks), fork-join, OpenMP and Grand Central Dispatch.
- Threading issue 1, fork() and exec(): some UNIX systems offer two forms of fork(), one that duplicates every thread and one that duplicates only the calling thread. exec() always replaces the whole process, including all its threads. If exec() is called right after fork(), copying only the calling thread is enough.
- Threading issue 2, signal handling: a synchronous signal (for example an illegal memory access) goes to the thread that caused it. An asynchronous signal (for example a terminate key-press) may be delivered to all threads, to some threads, or to one thread chosen to receive signals. POSIX provides pthread_kill() to send a signal to a specific thread.
- Threading issue 3, thread cancellation: a target thread is terminated before it finishes. Asynchronous cancellation kills it at once, which may leave resources unreleased. Deferred cancellation only marks the request; the target checks it at cancellation points (for example pthread_testcancel()) and can clean up safely.
- Threading issue 4, thread-local storage (TLS): each thread keeps its own copy of certain data. Unlike ordinary local variables, TLS persists across function calls, behaving like static data that is private to each thread. This is useful when threads are created implicitly, as in thread pools.
- Threading issue 5, scheduler activations: in many-to-many and two-level models, the kernel gives the thread library lightweight processes (LWPs) that act as virtual processors. The kernel informs the library of events through upcalls. For example, when a thread is about to block, the kernel makes an upcall and supplies a new LWP so that another user thread can run.
- Process execution alternates between CPU bursts and I/O bursts. CPU-bound processes have long CPU bursts; I/O-bound processes have short ones.
- A scheduling decision occurs when a process switches from running to waiting, from running to ready, from waiting to ready, or terminates. Non-preemptive scheduling acts only on the first and last of these.
- Scheduling aims to maximise CPU utilisation and throughput and to minimise turnaround, waiting and response time.
- FCFS can suffer from the convoy effect. SJF is optimal for average waiting time but needs burst prediction. Priority scheduling risks starvation. Round Robin gives each process a fixed time quantum in turn.
- Multilevel queue scheduling assigns processes permanently to fixed queues. Multilevel feedback queues let processes move between queues according to their observed behaviour.
- In asymmetric multiprocessing one master processor makes all scheduling decisions. In symmetric multiprocessing (SMP) each processor schedules itself from a common or private ready queue.
- Load balancing in SMP uses push migration and pull migration. It works against processor affinity, because a migrated process loses its warm cache contents.
- Multicore processors suffer memory stalls, so hardware multithreading places several hardware threads on each core to keep the core busy.
Learn these by heart
- Turnaround time = Completion time − Arrival time; Waiting time = Turnaround time − Burst time; Response time = Time of first CPU allocation − Arrival time.
- fork() returns 0 in the child, the child's pid (a positive value) in the parent, and a negative value on failure.
- SJF gives the minimum average waiting time for a given set of processes; SRTF is its preemptive form.
- Round Robin: with n ready processes and quantum q, no process waits more than (n−1)×q before its next turn. A very large q behaves like FCFS; a very small q causes heavy context-switch overhead.
- Bounded buffer with a circular array: the buffer is full when (in+1) % BUFFER_SIZE == out and empty when in == out.
- Aging gradually raises the priority of long-waiting processes and so prevents starvation in priority scheduling.
- Process states: New → Ready → Running → (Waiting → Ready) → Terminated; a waiting process never goes directly to Running.
- The five threading issues are fork()/exec() semantics, signal handling, thread cancellation, thread-local storage and scheduler activations. Thread pools belong to implicit threading, not to the threading issues.
- Deferred cancellation is safer than asynchronous cancellation, because the target thread stops only at a cancellation point where it can release its resources.
2-mark questions
1 What is a Process Control Block (PCB)? List any four pieces of information stored in it. 2 marks
A PCB is the kernel data structure that represents one process. It holds what the OS needs to manage the process and resume it later. Typical fields are the process state, program counter, CPU register contents, CPU-scheduling information (priority, queue pointers), memory-management information, accounting information and I/O status (open files, allocated devices).
2 What is a context switch? Why is it called overhead? 2 marks
A context switch saves the state of the running process (registers, program counter and so on) into its PCB. It then loads the saved state of the next process chosen to run. It is overhead because the CPU does no useful user work during the switch. Its duration depends on the amount of state and on hardware support.
3 Distinguish between asynchronous and deferred thread cancellation. 2 marks
Thread cancellation ends a thread before it has finished, for example when one search thread finds the result and the others are no longer needed. In asynchronous cancellation, another thread terminates the target at once, which can leave resources unreleased or shared data half-updated. In deferred cancellation, the target only checks for a pending request at safe cancellation points, such as pthread_testcancel(), so it can clean up and exit safely.
4 Define dispatcher and dispatch latency. 2 marks
The dispatcher is the module that hands the CPU to the process chosen by the short-term scheduler. It switches context, switches to user mode and jumps to the correct location in the user program. Dispatch latency is the time the dispatcher takes to stop one process and start another one running.
5 A process arrives at time 2 ms, needs a CPU burst of 5 ms and completes at time 12 ms. Find its turnaround time and waiting time. 2 marks
Turnaround time = completion time − arrival time = 12 − 2 = 10 ms.
Waiting time = turnaround time − burst time = 10 − 5 = 5 ms.
So the process spent 10 ms in the system. Of that, 5 ms was spent waiting in the ready queue.
6 What is processor affinity? Distinguish soft and hard affinity. 2 marks
Processor affinity means a process tends to keep running on the same processor in a multiprocessor system. This lets it reuse data already loaded in that processor's cache. Soft affinity is only a preference: the OS tries to keep the process on the same CPU but may migrate it. Hard affinity lets a process restrict itself to a specified set of CPUs.
10-mark questions
1 Explain the concept of a process. Draw and explain the process state transition diagram, and describe the scheduling queues and the different types of schedulers. 10 marks
A process is a program in execution. A program is a passive file stored on disk, whereas a process is an active entity. It has a program counter, a stack, a data section, a heap and a set of allocated resources. Several processes may run the same program, yet each one is a separate process.
1. Process states
- New: the process is being created.
- Ready: it is in main memory and waiting to be given the CPU.
- Running: its instructions are being executed.
- Waiting (blocked): it is waiting for an event such as I/O completion.
- Terminated: it has finished execution.
2. State diagram
A waiting process never moves directly to Running; it must first become Ready.
3. Process Control Block Each process is represented by a PCB. It holds the process state, program counter, registers, scheduling information, memory-management information, accounting data and I/O status. The context is saved in the PCB during a context switch.
4. Scheduling queues
- Job queue: all processes in the system.
- Ready queue: processes in memory that are ready to run, usually kept as a linked list of PCBs.
- Device (wait) queues: processes waiting for a particular I/O device or event.
A process moves among these queues during its lifetime. A queueing diagram shows this movement, with rectangles for queues and circles for resources such as the CPU and I/O devices.
5. Schedulers
- Long-term scheduler (job scheduler): picks jobs from the disk pool and loads them into memory. It controls the degree of multiprogramming and should admit a balanced mix of I/O-bound and CPU-bound processes. It runs infrequently.
- Short-term scheduler (CPU scheduler): picks one ready process for the CPU. It runs every few milliseconds, so it must be very fast.
- Medium-term scheduler: swaps processes out of memory and later swaps them back in. This reduces the degree of multiprogramming or improves the process mix.
Conclusion: The process abstraction gives the OS a precise record of every activity. The PCB, the queues and the three schedulers together let the OS multiplex many processes on the CPU.
2 Explain the operations of process creation and process termination. Illustrate with the UNIX system calls fork(), exec(), wait() and exit(), and explain zombie and orphan processes. 10 marks
The two basic operations an operating system provides on processes are creation and termination. UNIX-like systems perform them with the system calls fork(), exec(), wait() and exit().
1. Process creation
- A parent process can create child processes, which can create further processes. Together they form a process tree, and each process has a unique process identifier (pid).
- Resource sharing: the child may share all, some or none of the parent's resources.
- Execution: the parent either runs concurrently with its children or waits until some or all of them finish.
- Address space: the child is either a duplicate of the parent or loads a new program.
2. UNIX system calls
- fork() creates a new process whose address space is a copy of the parent's. It returns 0 in the child and the child's pid in the parent; a negative value means failure.
- The exec() family (for example execlp) replaces the caller's memory image with a new program.
- wait() blocks the parent until a child finishes and collects the child's exit status.
pid_t pid = fork();
if (pid < 0) {
fprintf(stderr, "fork failed");
} else if (pid == 0) { /* child */
execlp("/bin/ls", "ls", NULL);
} else { /* parent */
wait(NULL);
printf("Child complete");
}In this program the child replaces itself with the ls program. The parent waits for it and then prints a message.
3. Process termination
- A process ends normally by calling exit(). Its status reaches the parent through wait(), and the OS reclaims its memory, open files and buffers.
- A parent may terminate a child, for example with kill(). Typical reasons are that the child has exceeded its resource limits, its task is no longer needed, or the parent itself is exiting.
- Cascading termination: some systems do not let a child outlive its parent, so all descendants are terminated along with it.
4. Zombie and orphan processes
- Zombie: a child that has terminated but whose parent has not yet called wait(). Its process-table entry remains so that the exit status can still be collected.
- Orphan: a child whose parent terminated without calling wait(). In UNIX/Linux the orphan is adopted by init (or systemd), which periodically calls wait() to clean it up.
Conclusion: fork(), exec(), wait() and exit() together give a simple but powerful model for building process hierarchies and cleaning them up.
3 What is inter-process communication? Explain the shared-memory and message-passing models in detail, with the producer–consumer example. 10 marks
Processes are either independent or cooperating. Cooperating processes share data, so they need inter-process communication (IPC). Reasons for cooperation include information sharing, computation speed-up, modularity and convenience. There are two basic IPC models: shared memory and message passing.
1. Shared-memory model
- The cooperating processes set up a memory region that is attached to the address space of each of them. They exchange data simply by reading and writing that region.
- The kernel is needed only to create the region. Later accesses are ordinary memory operations, so this model is fast.
- The processes themselves must synchronise their accesses, otherwise the shared data can become inconsistent.
- Example: a producer and a consumer share a bounded buffer. It is implemented as a circular array with two indices, in and out.
/* producer */
while (true) {
while (((in + 1) % BUFFER_SIZE) == out)
; /* buffer full */
buffer[in] = next_produced;
in = (in + 1) % BUFFER_SIZE;
}
/* consumer */
while (true) {
while (in == out)
; /* buffer empty */
next_consumed = buffer[out];
out = (out + 1) % BUFFER_SIZE;
}This version holds at most BUFFER_SIZE − 1 items at a time.
2. Message-passing model
- Processes communicate through two kernel operations, send(message) and receive(message). No shared variables are needed, so the model also suits distributed systems.
- Naming: in direct communication each process names its partner, as in send(P, msg). In indirect communication messages go through mailboxes (ports), as in send(A, msg), and one mailbox may be shared by several processes.
- Synchronisation: send and receive may each be blocking (synchronous) or non-blocking (asynchronous). When both are blocking, the exchange is called a rendezvous.
- Buffering: with zero capacity the sender must wait for the receiver. With bounded capacity the sender blocks only when the queue is full. With unbounded capacity the sender never blocks.
3. Comparison
- Shared memory is faster once it is set up. Message passing needs a system call for every message.
- Message passing is easier for small amounts of data and works across machines.
Conclusion: Most systems provide both models. Shared memory suits large, fast exchanges on one machine, while message passing suits simpler or distributed communication.
4 Explain the different multithreading models with neat diagrams. Describe the Pthreads, Windows and Java thread libraries. 10 marks
A thread is the basic unit of CPU utilisation. Each thread has its own thread ID, program counter, register set and stack, but it shares code, data and open files with the other threads of its process. Multithreading brings responsiveness, resource sharing, economy and scalability on multicore machines. User threads are managed by a library without kernel involvement, while kernel threads are managed by the OS. A multithreading model defines how user threads are mapped to kernel threads.
1. Many-to-one model
- Many user threads are mapped onto a single kernel thread. Thread management happens in user space, so it is efficient.
- Drawbacks: one blocking system call blocks the entire process. Threads also cannot run in parallel on multiple cores.
2. One-to-one model
- Each user thread is mapped to its own kernel thread.
- When one thread blocks, others can still run, and threads can run in parallel on multiprocessors.
- Drawback: every user thread needs a kernel thread, which adds overhead and may limit the number of threads. Linux and Windows use this model.
3. Many-to-many model
- Many user threads are multiplexed onto a smaller or equal number of kernel threads.
- Programmers can create as many threads as they need, yet true parallelism is still possible. A blocking call does not block the whole process.
- The two-level model is a variation that also allows a user thread to be bound permanently to one kernel thread.
4. Thread libraries A thread library provides the API for creating and managing threads. It may run entirely in user space or be supported by the kernel.
- POSIX Pthreads: a specification, not an implementation, used on UNIX, Linux and macOS. pthread_create() starts a thread and pthread_join() waits for it.
- Windows threads: a kernel-level library. CreateThread() starts a thread and WaitForSingleObject() waits for it.
- Java threads: created by extending Thread or implementing Runnable and then calling start(); join() waits for completion. The JVM maps Java threads onto the host operating system's threads.
pthread_t tid;
pthread_attr_t attr;
pthread_attr_init(&attr);
pthread_create(&tid, &attr, runner, argv[1]);
pthread_join(tid, NULL);Conclusion: The one-to-one model with a kernel-supported library is the most common choice today. Modern systems can afford one kernel thread per user thread, and the model gives real parallelism on multicore hardware.
5 Four processes P1, P2, P3 and P4 arrive at time 0 in that order, with CPU burst times 8, 4, 9 and 5 ms respectively. Draw Gantt charts and find the average waiting time and average turnaround time under (i) FCFS, (ii) non-preemptive SJF and (iii) Round Robin with time quantum 4 ms. Compare the results. 10 marks
The short-term scheduler decides which ready process gets the CPU. We use two formulas: TAT = completion time (CT) − arrival time (AT), and WT = TAT − burst time (BT). All processes arrive at 0, so TAT = CT here. The total burst time is 8 + 4 + 9 + 5 = 26 ms.
(i) FCFS Processes run in arrival order. Gantt chart: | P1 0–8 | P2 8–12 | P3 12–21 | P4 21–26 |
- P1: TAT 8, WT 0
- P2: TAT 12, WT 8
- P3: TAT 21, WT 12
- P4: TAT 26, WT 21
Average WT = (0+8+12+21)/4 = 41/4 = 10.25 ms Average TAT = (8+12+21+26)/4 = 67/4 = 16.75 ms
(ii) Non-preemptive SJF The shortest burst runs first, giving the order P2(4), P4(5), P1(8), P3(9). Gantt chart: | P2 0–4 | P4 4–9 | P1 9–17 | P3 17–26 |
- P1: TAT 17, WT 9
- P2: TAT 4, WT 0
- P3: TAT 26, WT 17
- P4: TAT 9, WT 4
Average WT = (9+0+17+4)/4 = 30/4 = 7.5 ms Average TAT = (17+4+26+9)/4 = 56/4 = 14 ms
(iii) Round Robin, q = 4 ms Step 1: P1 runs 0–4 (remaining 4). Step 2: P2 runs 4–8 and finishes. Step 3: P3 runs 8–12 (remaining 5). Step 4: P4 runs 12–16 (remaining 1). Step 5: P1 runs 16–20 and finishes. Step 6: P3 runs 20–24 (remaining 1). Step 7: P4 runs 24–25 and finishes. Step 8: P3 runs 25–26 and finishes. Gantt chart: | P1 0–4 | P2 4–8 | P3 8–12 | P4 12–16 | P1 16–20 | P3 20–24 | P4 24–25 | P3 25–26 |
- P1: CT 20, TAT 20, WT 20−8 = 12
- P2: CT 8, TAT 8, WT 8−4 = 4
- P3: CT 26, TAT 26, WT 26−9 = 17
- P4: CT 25, TAT 25, WT 25−5 = 20
Average WT = (12+4+17+20)/4 = 53/4 = 13.25 ms Average TAT = (20+8+26+25)/4 = 79/4 = 19.75 ms
Comparison
- Average waiting time: SJF 7.5 < FCFS 10.25 < RR 13.25 ms. SJF gives the minimum average waiting time for a given set of jobs.
- FCFS suffers from the convoy effect, because the long job P1 delays the shorter jobs behind it.
- RR has the worst averages here, but it gives the best response time. First-response times under RR are 0, 4, 8 and 12 ms (average 6 ms), against 10.25 ms for FCFS and 7.5 ms for SJF.
- RR also pays for 7 context switches.
Conclusion: SJF is best for average waiting time, while RR is preferred in time-sharing systems where responsiveness matters most.
6 Explain the CPU scheduling criteria. For the processes below, find the average waiting time and average turnaround time using (i) preemptive SJF (SRTF) and (ii) non-preemptive priority scheduling, where a smaller number means higher priority. P1: arrival 0, burst 7, priority 3; P2: arrival 1, burst 4, priority 1; P3: arrival 2, burst 1, priority 4; P4: arrival 3, burst 4, priority 2. 10 marks
Scheduling criteria are the measures used to compare scheduling algorithms:
- CPU utilisation: keep the CPU as busy as possible (maximise).
- Throughput: number of processes completed per unit time (maximise).
- Turnaround time (TAT): completion time − arrival time (minimise).
- Waiting time (WT): total time spent in the ready queue, equal to TAT − burst time (minimise).
- Response time: time from arrival until the process first gets the CPU (minimise; important in interactive systems).
(i) SRTF Step 1: At t=0 only P1 is present, so P1 starts. Step 2: At t=1 P2 arrives with burst 4. This is less than P1's remaining 6, so P1 is preempted and P2 runs. Step 3: At t=2 P3 arrives with burst 1. This is less than P2's remaining 3, so P3 runs and finishes at t=3. Step 4: At t=3 P4 arrives with burst 4. The remaining times are P1 = 6, P2 = 3 and P4 = 4, so P2 runs from 3 to 6. Step 5: P4 runs from 6 to 10, and finally P1 runs from 10 to 16. Gantt chart: | P1 0–1 | P2 1–2 | P3 2–3 | P2 3–6 | P4 6–10 | P1 10–16 |
- P1: CT 16, TAT 16−0 = 16, WT 16−7 = 9
- P2: CT 6, TAT 6−1 = 5, WT 5−4 = 1
- P3: CT 3, TAT 3−2 = 1, WT 1−1 = 0
- P4: CT 10, TAT 10−3 = 7, WT 7−4 = 3
Average TAT = (16+5+1+7)/4 = 29/4 = 7.25 ms Average WT = (9+1+0+3)/4 = 13/4 = 3.25 ms
(ii) Non-preemptive priority Step 1: At t=0 only P1 is ready. It runs to completion from 0 to 7, even though higher-priority processes arrive meanwhile. Step 2: At t=7 the ready processes are P2 (priority 1), P3 (4) and P4 (2). P2 runs from 7 to 11. Step 3: P4 (priority 2) runs from 11 to 15. Step 4: P3 runs from 15 to 16. Gantt chart: | P1 0–7 | P2 7–11 | P4 11–15 | P3 15–16 |
- P1: CT 7, TAT 7, WT 0
- P2: CT 11, TAT 10, WT 6
- P3: CT 16, TAT 14, WT 13
- P4: CT 15, TAT 12, WT 8
Average TAT = (7+10+14+12)/4 = 43/4 = 10.75 ms Average WT = (0+6+13+8)/4 = 27/4 = 6.75 ms
Conclusion: SRTF gives clearly lower averages (WT 3.25 ms against 6.75 ms) because a short job is never stuck behind a long one. Priority scheduling can starve low-priority processes such as P3. The remedy is aging, which gradually raises the priority of processes that have waited a long time.
Synchronization and Deadlocks
Syllabus: The critical-section problem; Peterson's solution; Mutex locks; Semaphores; Monitors; Classic problems of synchronization; Deadlocks: system model; Deadlock characterization; Methods for handling deadlocks; Deadlock prevention; Deadlock avoidance; Deadlock detection; Recovery from deadlock
One-page revision summary
- A race condition occurs when the outcome of concurrent access to shared data depends on the order of execution, and this is what critical sections guard against.
- Peterson's solution handles two processes using flag[2] and turn, but needs memory barriers on modern hardware.
- Hardware instructions such as test_and_set and compare_and_swap execute atomically and can be used to build locks.
- Mutex locks use acquire() and release(); spinlocks busy-wait but avoid context switches, so they suit short waits on multiprocessors.
- Misusing semaphores, for example swapping wait and signal or omitting one, can cause deadlock, starvation or loss of mutual exclusion.
- A monitor allows only one active process at a time; condition variables provide wait and signal, using signal-and-wait or signal-and-continue semantics.
- The classic synchronization problems are bounded buffer, readers-writers and dining philosophers.
- In the first readers-writers solution, rw_mutex = 1, mutex = 1 and read_count = 0; many readers may read together but writers may starve.
- Dining-philosopher deadlock can be avoided by allowing at most four philosophers at the table, picking up both chopsticks together, or using an asymmetric pick-up order.
- In the deadlock system model, resources are typed with several identical instances, and a process uses each one by request, use and release.
- Resource-allocation graph rule: no cycle means no deadlock, a cycle with single-instance resources means deadlock, and a cycle with multiple instances means possible deadlock.
- Deadlocks can be handled by prevention, avoidance, detection and recovery, or by ignoring them as most general-purpose operating systems do.
- Avoidance for single-instance resources uses claim edges in the resource-allocation graph; for multiple instances it uses the Banker's algorithm.
- Detection uses a wait-for graph (cycle search in O(n²)) for single instances, and a Work/Finish algorithm for multiple instances.
- Recovery is by aborting all or some deadlocked processes, or by preempting resources with victim selection, rollback and protection against starvation.
Learn these by heart
- Critical-section requirements: mutual exclusion, progress, bounded waiting.
- Blocking semaphore: wait(S): S.value--, block if S.value < 0; signal(S): S.value++, wake one process if S.value ≤ 0.
- Bounded buffer initial values: mutex = 1, empty = n, full = 0.
- Four necessary (Coffman) conditions, all of which must hold together: mutual exclusion, hold and wait, no preemption, circular wait.
- Need[i][j] = Max[i][j] − Allocation[i][j].
- Banker's request rule: grant only if Request ≤ Need, Request ≤ Available, and the state after pretending to allocate is safe.
- A safe state means no deadlock; an unsafe state means deadlock is possible but not certain.
- The safety and detection algorithms each take O(m × n²) time for m resource types and n processes.
2-mark questions
1 State the three requirements that any solution to the critical-section problem must satisfy. 2 marks
- Mutual exclusion: at most one process executes in its critical section at any time.
- Progress: if no process is in its critical section, only processes wanting to enter take part in choosing the next one, and the choice cannot be postponed forever.
- Bounded waiting: after a process has requested entry, there is a limit on how many times other processes may enter their critical sections before that request is granted.
2 What is a mutex lock, and why is it also called a spinlock? 2 marks
A mutex lock is a simple synchronization tool based on a boolean variable 'available'. A process calls acquire() before its critical section and release() after it, and both calls are atomic. If acquire() keeps looping while the lock is busy, the waiting process spins on the CPU. Such a lock is therefore called a spinlock.
3 Differentiate between a counting semaphore and a binary semaphore. 2 marks
A counting semaphore can take any non-negative integer value. It is used to control access to a resource that has several identical instances, and it is initialised to the number of instances. A binary semaphore takes only the values 0 and 1. It behaves like a mutex lock and gives mutual exclusion for one critical section.
4 Under the deadlock system model, in what sequence does a process use a resource? 2 marks
A process uses a resource in three steps:
- Request: it asks for the resource and waits if the resource is not free.
- Use: it operates on the resource, for example printing on a printer.
- Release: it gives the resource back.
Request and release are done through system calls such as open/close or wait/signal.
5 List the methods for handling deadlocks. 2 marks
- Prevention: make sure that at least one necessary condition can never hold.
- Avoidance: grant a request only if the system stays in a safe state, as in the Banker's algorithm.
- Detection and recovery: let deadlock happen, find it, then recover.
- Ignoring: pretend deadlocks never occur, which is what most general-purpose operating systems do.
6 Mention the two broad approaches to recovering from a deadlock. 2 marks
- Process termination: abort all deadlocked processes, or abort them one at a time until the cycle is broken.
- Resource preemption: take resources away from victim processes.
Preemption raises three issues: choosing a victim at minimum cost, rolling the victim back to a safe point, and avoiding starvation of the same victim.
10-mark questions
1 Explain the critical-section problem. Describe Peterson's solution for two processes and prove that it satisfies mutual exclusion, progress and bounded waiting. 10 marks
A critical section is the part of a process's code in which it reads or updates shared data. When several cooperating processes run such code at the same time, a race condition can occur. In a race condition the result depends on the order in which the processes happen to execute. The critical-section problem is to design an entry section and an exit section so that processes can share data safely. A solution must satisfy three requirements:
- Mutual exclusion: only one process is in its critical section at a time.
- Progress: the choice of the next process to enter is made only by the processes that want to enter, and it is not postponed forever.
- Bounded waiting: there is a limit on how many times other processes may enter ahead of a waiting process.
Peterson's solution is a software solution for two processes Pi and Pj, where j = 1 - i. It uses two shared variables:
- int turn: says whose turn it is to enter.
- boolean flag[2]: flag[i] = true means Pi wants to enter.
do {
flag[i] = true; /* entry section */
turn = j;
while (flag[j] && turn == j)
; /* busy wait */
/* critical section */
flag[i] = false; /* exit section */
/* remainder section */
} while (true);Working: 1. Pi announces its interest by setting flag[i] = true. 2. Pi politely hands the turn to the other process by setting turn = j. 3. Pi waits only while Pj is also interested and it is Pj's turn. 4. On leaving, Pi sets flag[i] = false, so Pj can enter.
Proof of correctness: 1. Mutual exclusion. Suppose both processes are in their critical sections. Then flag[0] = flag[1] = true. Each process passed its while test, so each must have found turn equal to its own index. But turn holds only one value, 0 or 1, at any moment. This is a contradiction, so only one process can be inside. 2. Progress. If Pj is not interested, flag[j] is false and Pi enters at once. If both are interested, the last value written to turn decides who enters. So the decision depends only on the competing processes and is made in finite time. 3. Bounded waiting. When Pj leaves, it sets flag[j] = false. If Pj tries to enter again, it first sets turn = i, which lets the waiting Pi go in. Hence Pi waits for at most one entry by Pj.
Limitations: the solution works only for two processes and uses busy waiting. Modern processors and compilers may reorder memory operations, so the solution can fail unless memory barriers are added.
Conclusion: Peterson's solution clearly shows how shared flags and a turn variable together meet all three critical-section requirements.
2 What is a semaphore? Explain the wait() and signal() operations, give an implementation without busy waiting, and solve the bounded-buffer producer-consumer problem using semaphores. 10 marks
A semaphore S is an integer variable used for synchronization. Apart from initialisation, it is accessed only through two atomic operations: wait() (also called P) and signal() (also called V). A counting semaphore is not restricted to a fixed range of values. In the simple busy-waiting version it never drops below 0, but in the blocking version below it can become negative. A binary semaphore takes only the values 0 and 1.
Basic definition (with busy waiting):
wait(S) { while (S <= 0) ; S--; }
signal(S) { S++; }Implementation without busy waiting. Each semaphore keeps a list of blocked processes:
typedef struct { int value; struct process *list; } semaphore;
wait(semaphore *S) {
S->value--;
if (S->value < 0) { add this process to S->list; block(); }
}
signal(semaphore *S) {
S->value++;
if (S->value <= 0) { remove a process P from S->list; wakeup(P); }
}Here block() suspends the caller and wakeup(P) moves P to the ready queue. A positive value is the number of available resources. A negative value means processes are waiting, and its magnitude equals the number of waiting processes. No CPU time is wasted on spinning.
Bounded-buffer problem. A buffer has n slots. Producers insert items and consumers remove them. Three semaphores are used:
- mutex = 1, for mutual exclusion on the buffer.
- empty = n, which counts the free slots.
- full = 0, which counts the filled slots.
Producer:
do {
/* produce an item in next_produced */
wait(empty);
wait(mutex);
/* add next_produced to the buffer */
signal(mutex);
signal(full);
} while (true);Consumer:
do {
wait(full);
wait(mutex);
/* remove an item into next_consumed */
signal(mutex);
signal(empty);
/* consume next_consumed */
} while (true);Working: 1. A producer blocks on empty when all n slots are full. 2. A consumer blocks on full when the buffer is empty. 3. mutex makes sure that only one process changes the buffer at a time. 4. Each signal(full) by a producer lets one consumer proceed. Each signal(empty) by a consumer frees one slot for a producer.
The order of the wait calls matters. Suppose a producer called wait(mutex) before wait(empty) while the buffer was full. It would then block while holding mutex. No consumer could enter to free a slot, so the system would deadlock.
Conclusion: blocking semaphores give efficient synchronization. The bounded-buffer solution uses them both for mutual exclusion and for counting resources.
3 What is a monitor? Explain its structure and condition variables, and give a deadlock-free monitor solution to the dining-philosophers problem. 10 marks
A monitor is a high-level synchronization construct. It is an abstract data type that groups shared variables, the procedures that operate on them, and initialisation code. The monitor itself guarantees that only one process is active inside it at a time. The programmer therefore does not write explicit locks, which avoids errors such as swapping wait and signal.
Condition variables. A process may need to wait for some condition inside the monitor. Two operations are available:
- x.wait(): the caller is suspended and leaves the monitor free for others.
- x.signal(): resumes exactly one process suspended on x. If none is waiting, it has no effect, unlike a semaphore signal.
There are two signalling policies. In signal-and-wait, the signaller waits while the resumed process runs. In signal-and-continue, the signaller continues and the resumed process runs later.
Dining philosophers. Five philosophers sit at a round table with one chopstick between each pair. A philosopher needs both neighbouring chopsticks to eat. If every philosopher picks up the left chopstick at the same time, a deadlock results. In the monitor solution, a philosopher takes both chopsticks only when both are free.
monitor DP {
enum {THINKING, HUNGRY, EATING} state[5];
condition self[5];
void pickup(int i) {
state[i] = HUNGRY;
test(i);
if (state[i] != EATING) self[i].wait();
}
void putdown(int i) {
state[i] = THINKING;
test((i + 4) % 5); /* left neighbour */
test((i + 1) % 5); /* 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();
}
}
init() { for (int i = 0; i < 5; i++) state[i] = THINKING; }
}Philosopher i repeats: DP.pickup(i); eat; DP.putdown(i); think.
Working: 1. A hungry philosopher eats only if neither neighbour is eating. Otherwise it waits on self[i]. 2. After eating, putdown tests both neighbours and wakes any hungry neighbour that can now eat. 3. Chopsticks are never held one at a time, so hold and wait cannot occur. There is no circular wait and therefore no deadlock.
Limitation: a philosopher can still starve if its two neighbours keep eating alternately.
Conclusion: monitors with condition variables give a clean, structured and deadlock-free solution to classic synchronization problems.
4 Explain the deadlock system model and the four necessary conditions for deadlock with a resource-allocation graph. How can each condition be prevented? 10 marks
A deadlock is a situation in which every process in a set waits for an event that only another process in the same set can cause. As a result, none of them ever proceeds.
System model. A system has a finite number of resource types R1, R2, ..., Rm, such as CPU cycles, files, locks and printers. Each type has one or more identical instances. A process uses a resource in three steps: request, use and release.
Deadlock characterization. A deadlock can arise only if all four of the following conditions hold at the same time: 1. Mutual exclusion: at least one resource is non-sharable. 2. Hold and wait: a process holds at least one resource while waiting for others. 3. No preemption: a resource can be released only voluntarily by the process holding it. 4. Circular wait: there is a chain P0 → P1 → ... → Pn → P0 in which each process waits for a resource held by the next.
Resource-allocation graph (described in words). Processes are drawn as circles and resource types as rectangles, with one dot for each instance. A request edge goes from a process to a resource. An assignment edge goes from a resource instance to a process. Consider this example: P1 holds R1 and requests R2, while P2 holds R2 and requests R1. The edges form the cycle P1 → R2 → P2 → R1 → P1, so the two processes are deadlocked.
Rules for reading the graph:
- No cycle means no deadlock.
- A cycle in which every resource type has a single instance means deadlock.
- A cycle involving resource types with several instances means deadlock is possible but not certain.
Deadlock prevention means making sure that at least one condition can never hold: 1. Mutual exclusion: make resources sharable where possible, such as read-only files. Some resources, like mutex locks, are inherently non-sharable, so this condition usually cannot be denied. 2. Hold and wait: require a process to request all its resources before it starts. Alternatively, allow a request only when the process holds none. The drawbacks are low resource utilisation and possible starvation. 3. No preemption: if a process holding resources is refused a new request, it releases everything it holds and restarts later. This suits resources whose state is easily saved, such as CPU registers and memory. 4. Circular wait: give every resource type a unique number and require requests in increasing order only. For example, a process holding R3 may request R5 but not R2. Circular wait then becomes impossible.
Conclusion: denying circular wait through resource ordering is the most practical prevention technique. All prevention methods trade some resource utilisation for safety from deadlock.
5 A system has five processes P0 to P4 and resource types A, B, C with 9, 6 and 7 instances. Allocation: P0 (1,1,2), P1 (2,0,1), P2 (3,1,1), P3 (0,2,0), P4 (1,1,1). Max: P0 (4,3,3), P1 (3,2,2), P2 (4,1,3), P3 (2,4,2), P4 (2,2,4). Using the Banker's algorithm, (a) find Available and Need, (b) check whether the state is safe, (c) decide whether a request (1,0,1) by P1 can be granted immediately. 10 marks
The Banker's algorithm is a deadlock-avoidance algorithm. It grants a request only if the system remains in a safe state afterwards. It uses four data structures: Available, Max, Allocation and Need, where Need = Max − Allocation.
Step 1: Available. Total allocated = (1+2+3+0+1, 1+0+1+2+1, 2+1+1+0+1) = (7, 5, 5). Available = (9, 6, 7) − (7, 5, 5) = (2, 1, 2).
Step 2: Need = Max − Allocation.
- P0: (4,3,3) − (1,1,2) = (3,2,1)
- P1: (3,2,2) − (2,0,1) = (1,2,1)
- P2: (4,1,3) − (3,1,1) = (1,0,2)
- P3: (2,4,2) − (0,2,0) = (2,2,2)
- P4: (2,2,4) − (1,1,1) = (1,1,3)
Step 3: Safety algorithm. Set Work = Available and Finish[i] = false for every process. Find a process i with Finish[i] = false and Need[i] ≤ Work. Then set Work = Work + Allocation[i] and Finish[i] = true. Repeat. If every Finish value becomes true, the state is safe.
Trace starting with Work = (2,1,2): 1. P0 needs (3,2,1): A is short. P1 needs (1,2,1): B is short. P2 needs (1,0,2) ≤ (2,1,2), so P2 runs. Work = (2,1,2) + (3,1,1) = (5,2,3). 2. P0 needs (3,2,1) ≤ (5,2,3), so P0 runs. Work = (5,2,3) + (1,1,2) = (6,3,5). 3. P1 needs (1,2,1) ≤ (6,3,5), so P1 runs. Work = (6,3,5) + (2,0,1) = (8,3,6). 4. P3 needs (2,2,2) ≤ (8,3,6), so P3 runs. Work = (8,3,6) + (0,2,0) = (8,5,6). 5. P4 needs (1,1,3) ≤ (8,5,6), so P4 runs. Work = (8,5,6) + (1,1,1) = (9,6,7).
All processes finish. As a check, the final Work equals the total resources (9,6,7). The state is safe, with safe sequence <P2, P0, P1, P3, P4>.
Step 4: Request (1,0,1) by P1. 1. Is Request ≤ Need1? (1,0,1) ≤ (1,2,1): yes. 2. Is Request ≤ Available? (1,0,1) ≤ (2,1,2): yes. 3. Pretend to allocate: Available = (1,1,1), Allocation1 = (3,0,2), Need1 = (0,2,0). 4. Run the safety check with Work = (1,1,1):
- P0 (3,2,1): A short
- P1 (0,2,0): B short
- P2 (1,0,2): C short
- P3 (2,2,2): short
- P4 (1,1,3): C short
No process can finish, so the new state is unsafe.
Result: the request (1,0,1) by P1 cannot be granted immediately. The old state is restored and P1 must wait, even though the resources are physically free.
Conclusion: the original state is safe with sequence <P2, P0, P1, P3, P4>. The Banker's algorithm refuses P1's request because granting it would lead to an unsafe state.
6 Explain the deadlock-detection algorithm for multiple instances of resources. Apply it to the following system with resources A, B, C (total 5, 3, 4): Allocation P0 (1,0,1), P1 (0,1,1), P2 (2,0,0), P3 (1,1,0), P4 (0,0,1); Request P0 (0,1,1), P1 (4,0,0), P2 (0,3,0), P3 (0,0,3), P4 (1,0,1). Identify any deadlocked processes and explain how to recover. 10 marks
When neither prevention nor avoidance is used, the system must detect deadlocks from time to time and then recover from them. With single-instance resources, a wait-for graph is searched for cycles. With multiple instances, the following algorithm is used. It works on Available, Allocation and Request, where Request is the current outstanding demand of each process.
Algorithm: 1. Set Work = Available. For each process i, set Finish[i] = false if Allocation[i] ≠ 0, otherwise true. 2. Find a process i with Finish[i] = false and Request[i] ≤ Work. If there is none, go to step 4. 3. Set Work = Work + Allocation[i] and Finish[i] = true. Go to step 2. This step optimistically assumes the process will finish and release its resources. 4. Every process with Finish[i] = false is deadlocked. The algorithm takes O(m × n²) time.
Application. Allocated = (1+0+2+1+0, 0+1+0+1+0, 1+1+0+0+1) = (4,2,3). Available = (5,3,4) − (4,2,3) = (1,1,1). Every process holds something, so all Finish values start as false.
Pass 1, with Work = (1,1,1):
- P0 requests (0,1,1) ≤ (1,1,1), so P0 finishes. Work = (1,1,1) + (1,0,1) = (2,1,2).
- P1 requests (4,0,0): A is short.
- P2 requests (0,3,0): B is short.
- P3 requests (0,0,3): C is short, since only 2 are free.
- P4 requests (1,0,1) ≤ (2,1,2), so P4 finishes. Work = (2,1,2) + (0,0,1) = (2,1,3).
Pass 2:
- P3 requests (0,0,3) ≤ (2,1,3), so P3 finishes. Work = (2,1,3) + (1,1,0) = (3,2,3).
Pass 3:
- P1 requests (4,0,0): 4 > 3, so it cannot proceed.
- P2 requests (0,3,0): 3 > 2, so it cannot proceed.
No further progress is possible. P1 and P2 are deadlocked. P1 waits for instances of A held by P2, and P2 waits for an instance of B held by P1.
Recovery: 1. Process termination. We can abort all deadlocked processes, or abort one at a time and run detection again after each abort.
- Abort P2: Work = (3,2,3) + (2,0,0) = (5,2,3). P1's request (4,0,0) can now be met, and Work then becomes (5,3,4).
- Abort P1 instead: Work = (3,2,3) + (0,1,1) = (3,3,4). P2's request (0,3,0) can now be met.
Aborting either one breaks the deadlock. The victim is chosen by cost factors such as priority, how long it has run, the resources it holds and whether it is interactive. 2. Resource preemption. Take resources from a victim, roll it back to a safe checkpoint or restart it, and count rollbacks so that the same process is not always chosen. This prevents starvation.
Conclusion: the detection algorithm finds that P1 and P2 are deadlocked. Terminating one of them, or preempting its resources, restores progress for the whole system.
Memory Management, Virtual Memory and Storage
Syllabus: Memory management: introduction; Contiguous memory allocation; Paging; Structure of the page table; Swapping; Virtual memory: introduction; Demand paging; Copy-on-write; Page replacement; Allocation of frames; Thrashing; Overview of mass storage structure; HDD scheduling
One-page revision summary
- The MMU maps CPU-generated logical addresses to physical addresses, and base and limit registers protect each process's memory.
- Address binding can occur at compile, load or execution time; only execution-time binding lets a process move during execution.
- Contiguous allocation uses first-fit, best-fit or worst-fit and suffers external fragmentation, which compaction can reduce.
- Paging splits memory into equal frames and logical space into pages, removing external fragmentation but leaving some internal fragmentation.
- A TLB caches recent page-to-frame mappings so most accesses avoid an extra memory reference for the page table.
- Hierarchical, hashed and inverted page tables reduce the memory needed to hold page tables for large address spaces.
- Swapping moves processes or individual pages to a backing store; modern systems swap pages rather than whole processes because whole-process swapping is slow.
- Virtual memory separates logical from physical memory so programs larger than RAM can run and more processes can be resident.
- Demand paging loads a page only on first reference, and an access to a page marked invalid triggers a page-fault trap.
- Copy-on-write lets parent and child share pages after fork() and copies a page only when one of them writes to it.
- Page replacement chooses a victim frame: FIFO is simplest, Optimal gives fewest faults, and LRU approximates Optimal using past use.
- The dirty bit avoids writing unchanged victim pages back to disk, and the reference bit supports LRU approximations like the second-chance (clock) algorithm.
- Frames may be allocated equally or proportionally to process size, and replacement may be global (any frame) or local (own frames only).
- Every process needs a minimum number of frames fixed by the machine architecture so that any single instruction can complete.
- Thrashing is controlled with the working-set model or page-fault-frequency control and by reducing the degree of multiprogramming.
- An HDD has platters, tracks, sectors and cylinders, while SSDs and other non-volatile memory devices have no moving parts and no seek time.
- Disk scheduling: FCFS is fair but slow, SSTF may starve far requests, and SCAN, C-SCAN and LOOK give more uniform service.
Learn these by heart
- EAT with TLB = h × (t + m) + (1 − h) × (t + 2m), where h is hit ratio, t TLB time and m memory time.
- EAT with demand paging = (1 − p) × memory access time + p × page-fault service time.
- Proportional frame allocation: a_i = (s_i / S) × m, where S is the sum of all process sizes and m the free frames.
- With page size 2^n, the low n bits of a logical address are the offset; physical address = frame number × page size + offset.
- Disk access time = seek time + rotational latency + transfer time; average rotational latency is half of one rotation.
- Belady's anomaly: FIFO may give more faults with more frames; LRU and Optimal (stack algorithms) never do.
- Thrashing occurs when the sum of working-set sizes of all processes exceeds the total number of available frames.
2-mark questions
1 Distinguish between a logical address and a physical address, and name the hardware unit that converts one into the other at run time. 2 marks
A logical (virtual) address is generated by the CPU while a program runs. A physical address is the actual location in main memory seen by the memory unit. The Memory Management Unit (MMU) maps logical addresses to physical addresses at run time, for example by adding the relocation (base) register value.
2 What is the difference between internal fragmentation and external fragmentation in memory allocation? 2 marks
Internal fragmentation is unused space inside an allocated block, because the block given is larger than the request, as in fixed partitions or the last page of a process. External fragmentation is free memory split into many small non-contiguous holes, so a request fails even though total free space is enough.
3 A system uses 32-bit logical addresses and a page size of 4 KB. Calculate the number of bits used for the page offset, the number of bits used for the page number, and the number of entries in a single-level page table. 2 marks
Page size = 4 KB = 2^12 bytes, so the offset needs 12 bits. Page number bits = 32 − 12 = 20. Number of page-table entries = 2^20 = 1,048,576. With 4-byte entries, the single-level table needs 4 MB for each process.
4 Using proportional frame allocation, how many frames are given to two processes of sizes 20 pages and 100 pages when 60 frames are free? Show the calculation. 2 marks
Proportional allocation gives a_i = (s_i / S) × m. Here S = 20 + 100 = 120 and m = 60. Process 1 gets (20/120) × 60 = 10 frames. Process 2 gets (100/120) × 60 = 50 frames. Total = 10 + 50 = 60 frames.
5 Define thrashing in a virtual memory system and state its main cause. 2 marks
Thrashing is a condition in which processes spend more time servicing page faults than executing, so CPU utilisation drops sharply. It happens when processes do not have enough frames to hold their actively used pages (working set), usually because the degree of multiprogramming has been raised too high.
6 What is swapping in memory management? Mention one drawback of swapping entire processes. 2 marks
Swapping temporarily moves a process, or some of its pages, from main memory to a backing store and later brings it back to continue execution. It lets the total memory of all processes exceed physical memory. Drawback: moving an entire process takes long, so context-switch time becomes very high.
10-mark questions
1 Explain contiguous memory allocation with fixed and variable partitions. Free holes of 150 KB, 400 KB, 250 KB, 300 KB and 600 KB exist in this memory order. Show how first-fit, best-fit and worst-fit place processes of 230 KB, 380 KB, 120 KB and 500 KB (arriving in that order), and state which strategy uses memory best here. 10 marks
In contiguous memory allocation every process occupies a single continuous block of main memory. The operating system keeps a list of allocated partitions and free blocks called holes. Protection uses a relocation (base) register and a limit register: each logical address is checked against the limit and then added to the base by the MMU.
Types of partitioning:
- Fixed partitioning: memory is divided into partitions of fixed size in advance, one process per partition. It is simple but wastes space inside partitions (internal fragmentation).
- Variable partitioning: a block of exactly the requested size is cut from a hole. There is no internal fragmentation, but over time memory breaks into scattered small holes (external fragmentation).
Placement strategies: 1. First fit: choose the first hole that is large enough. 2. Best fit: choose the smallest hole that is large enough. 3. Worst fit: choose the largest hole.
Worked example (H1 = 150, H2 = 400, H3 = 250, H4 = 300, H5 = 600 KB).
First fit:
- 230 KB → H2 (400), leaves 170
- 380 KB → H5 (600), leaves 220
- 120 KB → H1 (150), leaves 30
- 500 KB → holes are 30, 170, 250, 300, 220; none is 500 or more, so it must wait
Best fit:
- 230 KB → H3 (250), leaves 20
- 380 KB → H2 (400), leaves 20
- 120 KB → H1 (150), leaves 30
- 500 KB → H5 (600), leaves 100
- All four processes are placed
Worst fit:
- 230 KB → H5 (600), leaves 370
- 380 KB → H2 (400), leaves 20
- 120 KB → H5 (370), leaves 250
- 500 KB → holes are 150, 20, 250, 300, 250; largest is 300, so it must wait
Observation: in first fit and worst fit the total free memory is 1700 − 730 = 970 KB, which is more than 500 KB, yet the request fails because no single hole is large enough. This is external fragmentation. Here best fit performs best because it kept the large 600 KB hole intact.
Remedies for external fragmentation:
- Compaction: move processes together so all holes merge into one large block. It requires execution-time address binding and costs CPU time.
- Non-contiguous allocation such as paging or segmentation, which lets a process use scattered frames.
Conclusion: contiguous allocation is easy to implement with base and limit registers, but its placement choice strongly affects fragmentation. In this example only best fit could allocate all four processes, while the other two strategies left 970 KB free yet unusable.
2 Explain paging with the help of a hardware diagram described in words. How does a translation look-aside buffer (TLB) speed up address translation? Calculate the effective memory access time when TLB lookup takes 10 ns, memory access takes 80 ns and the TLB hit ratio is 90%. 10 marks
Paging is a non-contiguous memory management scheme. Physical memory is divided into fixed-size blocks called frames and logical memory into blocks of the same size called pages. Any page can go into any free frame, so external fragmentation disappears; only the last page of a process may have internal fragmentation.
Address translation steps: 1. The CPU generates a logical address split into page number p and offset d. If the page size is 2^n, the low n bits form d and the remaining high bits form p. 2. p indexes the page table of the running process, located through the page-table base register (PTBR). 3. The page-table entry supplies the frame number f. 4. Physical address = f × page size + d.
Example: page size 1 KB = 1024 bytes, logical address 3500.
- p = 3500 div 1024 = 3
- d = 3500 − 3 × 1024 = 3500 − 3072 = 428
- If page 3 is in frame 7, physical address = 7 × 1024 + 428 = 7168 + 428 = 7596
Role of the TLB: The page table lives in main memory, so without help every data access needs two memory accesses: one for the page-table entry and one for the data. The TLB is a small, fast associative cache of recent (page, frame) pairs, searched in parallel.
- TLB hit: the frame number is available at once.
- TLB miss: the page table in memory is read, and the new pair is inserted into the TLB, replacing an old entry if it is full.
- Address-space identifiers (ASIDs) in TLB entries avoid flushing the TLB at every context switch.
Effective access time (EAT): TLB time t = 10 ns, memory time m = 80 ns, hit ratio h = 0.90.
- Cost on hit = t + m = 10 + 80 = 90 ns
- Cost on miss = t + m + m = 10 + 80 + 80 = 170 ns
- EAT = h × 90 + (1 − h) × 170 = 0.90 × 90 + 0.10 × 170 = 81 + 17 = 98 ns
Without a TLB each access costs 2 × 80 = 160 ns, a 100% slowdown. With the TLB the slowdown is (98 − 80)/80 = 22.5%.
Conclusion: paging removes external fragmentation and simplifies allocation, and the TLB makes it practical by cutting the effective access time from 160 ns to 98 ns in this example.
3 Describe the common structures used for page tables: hierarchical (multilevel) paging, hashed page tables and inverted page tables. Using a 32-bit address space with 4 KB pages, explain why a simple single-level page table is impractical. 10 marks
For large logical address spaces the page table itself becomes very large, so operating systems use special structures to store it efficiently. Each entry typically holds a frame number plus a valid bit, protection bits, a dirty bit and a reference bit.
Why a single-level table is impractical:
- Page size 4 KB = 2^12, so the offset is 12 bits and the page number is 32 − 12 = 20 bits.
- The table has 2^20 = 1,048,576 entries; at 4 bytes each this is 4 MB per process.
- This 4 MB must be contiguous, and most entries are unused because programs use only a small part of their address space.
1. Hierarchical (multilevel) paging The page table is itself paged. In two-level paging the 20-bit page number is split into p1 and p2: logical address = p1 (10 bits) | p2 (10 bits) | d (12 bits)
- p1 indexes the outer page table, which points to an inner page table.
- p2 indexes that inner table to obtain frame f.
- Physical address = f combined with d.
Each inner table has 2^10 entries × 4 bytes = 4 KB, so it fits exactly in one frame, and inner tables for unused regions need not be created at all.
Drawback: each level adds a memory access on a TLB miss, and 64-bit spaces would need too many levels.
2. Hashed page tables Used for address spaces larger than 32 bits.
- The virtual page number is passed through a hash function to select a slot.
- Each slot holds a linked list of elements containing the virtual page number, the frame number and a pointer to the next element.
- The chain is searched for a matching page number; on a match the frame number forms the physical address.
A variant, the clustered page table, keeps mappings for several consecutive pages in one element, which suits sparse address spaces.
3. Inverted page tables
- There is one table for the whole system with one entry per physical frame, instead of one table per process.
- Each entry stores <process-id, page number>.
- A logical address <pid, p, d> is searched in the table; if the match is at entry i, the physical address is <i, d>.
Advantage: table size depends on physical memory, not on virtual address space size. Disadvantages: searching is slow (a hash table is added to speed it up), and shared memory is difficult because each frame records only one virtual page.
Conclusion: hierarchical tables avoid allocating unused parts of the table, hashed tables suit very large sparse address spaces, and inverted tables minimise total table memory at the cost of slower lookup.
4 What is virtual memory? Explain demand paging and the steps taken by the operating system to handle a page fault, and describe copy-on-write. If memory access time is 100 ns, page-fault service time is 5 ms and one access in 1000 causes a fault, compute the effective access time. Also find the maximum fault rate that keeps the slowdown below 10%. 10 marks
Virtual memory separates the logical memory seen by a program from the physical memory installed. Only the parts of a program currently needed are kept in RAM; the rest stays on secondary storage. Benefits: programs larger than physical memory can run, more processes fit in memory (higher CPU utilisation), less I/O is needed to start programs, and pages can be shared.
Demand paging: A page is brought into memory only when it is referenced (a lazy pager). Each page-table entry has a valid–invalid bit: valid means the page is legal and in memory; invalid means it is outside the address space or currently on disk. Touching an invalid page causes a page-fault trap.
Steps to handle a page fault: 1. The OS checks an internal table kept with the PCB. If the reference is illegal, the process is terminated. 2. If it is legal but not in memory, a free frame is taken from the free-frame list; if none is free, a page replacement algorithm selects a victim. 3. A disk read is scheduled to load the page into that frame; the CPU may run another process meanwhile. 4. When the read completes, the page table is updated with the frame number and the valid bit is set. 5. The instruction that caused the fault is restarted and now finds the page in memory.
Copy-on-write: When fork() creates a child, the parent's pages are not copied. Parent and child share the same frames, marked copy-on-write. If either process writes to such a page, the OS copies that page into a new frame, maps the copy into the writer's page table and lets the write proceed. Unmodified pages are never copied, so process creation is faster and memory is saved, especially when the child immediately calls exec().
Performance calculation: ma = 100 ns, service time = 5 ms = 5,000,000 ns, p = 0.001. EAT = (1 − p) × ma + p × service time = 0.999 × 100 + 0.001 × 5,000,000 = 99.9 + 5000 = 5099.9 ns ≈ 5.1 µs This is about 51 times slower than a plain memory access.
For slowdown below 10%, EAT < 110 ns: 100 + p × (5,000,000 − 100) < 110 4,999,900 × p < 10 p < 2.0 × 10^-6 So fewer than about one fault in every 500,000 accesses is allowed.
Conclusion: demand paging gives the illusion of a very large memory and copy-on-write makes fork() cheap, but because a fault costs millions of times more than a memory access, the page-fault rate must be kept extremely low.
5 Explain FIFO, Optimal and LRU page replacement algorithms. For the reference string 2, 3, 1, 4, 2, 3, 5, 2, 3, 1, 4, 5 with 3 frames (initially empty), show the frame contents after each reference and count the page faults for each algorithm. Also explain Belady's anomaly. 10 marks
When a page fault occurs and no frame is free, a page replacement algorithm chooses a victim page. If the victim's dirty bit is set it is written back to disk first. A good algorithm gives the lowest page-fault count.
1. FIFO replaces the page that has been in memory the longest. 2. Optimal replaces the page whose next use is farthest in the future. It needs future knowledge, so it is used as a benchmark. 3. LRU replaces the page that has not been used for the longest time, using the recent past to approximate the future.
In the tables below, F marks a fault and - marks a hit.
FIFO: Ref: 2 3 1 4 2 3 5 2 3 1 4 5 Frame1: 2 2 2 4 4 4 5 5 5 5 5 5 Frame2: - 3 3 3 2 2 2 2 2 1 1 1 Frame3: - - 1 1 1 3 3 3 3 3 4 4 Result: F F F F F F F - - F F - Page faults = 9
Optimal: Ref: 2 3 1 4 2 3 5 2 3 1 4 5 Frame1: 2 2 2 2 2 2 2 2 2 1 4 4 Frame2: - 3 3 3 3 3 3 3 3 3 3 3 Frame3: - - 1 4 4 4 5 5 5 5 5 5 Result: F F F F - - F - - F F - Page faults = 7 At reference 4, page 1 is used farthest ahead, so it is replaced; at reference 5 (seventh), page 4 is replaced. Near the end, pages never used again are replaced, ties broken arbitrarily.
LRU: Ref: 2 3 1 4 2 3 5 2 3 1 4 5 Frame1: 2 2 2 4 4 4 5 5 5 1 1 1 Frame2: - 3 3 3 2 2 2 2 2 2 4 4 Frame3: - - 1 1 1 3 3 3 3 3 3 5 Result: F F F F F F F - - F F F Page faults = 10
Comparison: Optimal 7, FIFO 9, LRU 10. Optimal is always the lowest. Here LRU does slightly worse than FIFO because the string revisits pages in a cycle just after they become least recently used; this shows that results depend on the reference pattern.
Belady's anomaly: Normally more frames should mean fewer faults. With FIFO, however, some reference strings produce more faults when the number of frames is increased. This happens because the set of pages held with n frames is not always a subset of the set held with n + 1 frames. LRU and Optimal are stack algorithms, for which this subset property always holds, so they never show the anomaly.
Conclusion: FIFO is simple but can behave badly, Optimal is the ideal reference, and LRU (or its clock approximations) is preferred in practice.
6 Describe the structure of a hard disk drive and the components of disk access time. A disk has cylinders 0 to 199; the head is at cylinder 60 moving towards higher cylinders, and the request queue is 120, 30, 175, 85, 10, 140, 45, 190. Compute the total head movement for FCFS, SSTF, SCAN, C-SCAN and LOOK, and compare them. 10 marks
Secondary storage keeps data permanently and backs virtual memory. The hard disk drive (HDD) is the traditional mass storage device, while non-volatile memory devices such as SSDs have no moving parts.
HDD structure:
- One or more circular platters coated with magnetic material rotate at a constant speed (for example 7200 RPM).
- A read-write head sits just above each surface on a disk arm; all arms move together.
- Each surface is divided into concentric tracks, and tracks into sectors.
- The tracks at one arm position on all surfaces form a cylinder.
Disk access time = seek time + rotational latency + transfer time. Seek time (moving the arm to the cylinder) is usually the largest part, so the OS orders pending requests to reduce head movement.
Calculations (head at 60, moving up):
1. FCFS (serve in arrival order): 60→120→30→175→85→10→140→45→190 60 + 90 + 145 + 90 + 75 + 130 + 95 + 145 = 830 cylinders
2. SSTF (nearest request first): 60→45→30→10→85→120→140→175→190 15 + 15 + 20 + 75 + 35 + 20 + 35 + 15 = 230 cylinders
3. SCAN (move up to the end, then reverse): 60→85→120→140→175→190→199→45→30→10 (199 − 60) + (199 − 10) = 139 + 189 = 328 cylinders
4. C-SCAN (move up to the end, jump to cylinder 0, continue up): 60→85→120→140→175→190→199→0→10→30→45 139 + 199 + 45 = 383 cylinders (184 if the return jump is not counted)
5. LOOK (like SCAN, but reverse at the last request): 60→85→120→140→175→190→45→30→10 (190 − 60) + (190 − 10) = 130 + 180 = 310 cylinders
Comparison:
- FCFS is fair but gives wild arm swings (830).
- SSTF gives the least movement here (230) but can starve requests far from the head.
- SCAN and LOOK act like an elevator; LOOK saves the trip to the disk end.
- C-SCAN gives more uniform waiting time because it serves in one direction only.
Conclusion: for this queue SSTF moves the head least, while SCAN, C-SCAN and LOOK balance movement and fairness. For SSDs, which have no seek time, simple FCFS-style ordering is usually sufficient.
File Systems and Protection
Syllabus: File concept; Access methods; Directory structure; File-system structure; File-system operations; Directory implementation; Allocation methods; Free-space management; File-system mounting; Partitions and mounting; File sharing; Goals of protection; Principles of protection; Protection rings; Domain of protection; Access matrix
One-page revision summary
- A file is a named collection of related data on secondary storage, described by attributes such as name, identifier, type, location, size, protection and timestamps.
- Basic file operations are create, open, read, write, reposition (seek), delete, truncate and close; open files are tracked through open-file tables and file pointers.
- Sequential access reads records in order, direct access reads any numbered block, and indexed access first searches an index to locate the block.
- Directory structures range from single-level and two-level to tree, acyclic-graph and general-graph; graphs allow sharing but need reference counts or garbage collection.
- A file system is layered as application programs, logical file system, file-organisation module, basic file system, I/O control and devices.
- On-disk structures include the boot control block, volume control block (superblock), directory structure and FCB (inode); in-memory structures include the mount table and the system-wide and per-process open-file tables.
- Directories are implemented as linear lists, which are simple but slow, or as hash tables, which are fast but need collision handling.
- Contiguous allocation gives fast access but suffers external fragmentation; linked allocation avoids fragmentation but suits only sequential access; indexed allocation supports direct access at the cost of an index block.
- Free space is tracked with a bit vector, a linked free list, grouping or counting.
- A disk is divided into partitions that are either raw or hold a file system, and the root partition is mounted at boot time.
- Mounting attaches a file system at a mount point in the existing directory tree after the OS verifies its superblock.
- File sharing uses owner and group IDs for permission checks, and remote sharing uses client-server distributed file systems such as NFS.
- Consistency semantics include UNIX semantics (immediate visibility), session semantics (visible after close) and immutable shared files.
- The goals of protection are to prevent misuse, enforce resource-use policies, detect interface errors early and separate policy from mechanism.
- Protection principles include least privilege, need-to-know, compartmentalisation, defence in depth and audit trails.
- Protection rings are hardware privilege levels: ring 0 runs the kernel, outer rings run less-privileged code, and inner rings are entered only through gates such as system calls.
- A protection domain is a set of <object, rights> pairs, and processes may switch domains statically or dynamically, for example through setuid.
- The access matrix has domains as rows and objects as columns; it is implemented as a global table, access lists (ACLs), capability lists or a lock-key scheme.
Learn these by heart
- Bit vector size = (disk size / block size) bits; divide by 8 to get bytes.
- First free block in a bitmap = (bits per word) × (number of zero-valued words) + offset of the first 1 bit.
- Pointers per index block = block size / pointer size; maximum file size with one index block = pointers × block size (4 KB / 4 B gives 1024 pointers and 4 MB).
- Contiguous allocation: physical block = start block + logical block number.
- Access right = <object-name, rights-set>; access(i,j) = operations a process in domain Di may perform on object Oj.
- Principle of least privilege: grant only the minimum rights needed, for only as long as they are needed.
- ACL = a column of the access matrix stored with the object; capability list = a row of the access matrix stored with the domain.
2-mark questions
1 Define a file and list any four attributes of a file. 2 marks
A file is a named collection of related information stored on secondary storage. It is the smallest logical unit of storage that a user sees. Common attributes are name, identifier, type, location, size, protection (access permissions), and time, date and owner information.
2 Distinguish between sequential access and direct access methods. 2 marks
In sequential access, records are processed in order, one after another, using read-next and write-next operations that advance a file pointer, as on a tape. In direct (relative) access, the file is a set of numbered fixed-length blocks. Any block n can be read or written in any order, which suits databases.
3 What is meant by mounting a file system? What is a mount point? 2 marks
Mounting attaches a file system on a partition or device to the existing directory tree so that its files become accessible. The mount point is the directory, usually empty, where the root of the new file system is attached. For example, a USB drive can be mounted at /media/usb.
4 State the principle of least privilege. 2 marks
The principle of least privilege says that every program, user and system component should get only the minimum privileges needed for its task, and only for as long as they are needed. This limits the damage that a faulty or compromised component can do.
5 What are protection rings? 2 marks
Protection rings are privilege levels arranged in a hierarchy and enforced by hardware. Ring 0, the innermost ring, has the most privilege and runs the kernel. Outer rings, up to ring 3 on x86, have fewer privileges and run user code. Control passes to an inner ring only through controlled gates such as system calls or traps.
6 A 16 GB disk uses 4 KB blocks. Find the size of the bit vector used for free-space management. 2 marks
Number of blocks = 16 GB / 4 KB = 2^34 / 2^12 = 2^22 = 4,194,304 blocks.
The bit vector needs one bit per block, so it holds 2^22 bits.
Size = 2^22 / 8 = 2^19 bytes = 524,288 bytes = 512 KB.
10-mark questions
1 Explain the different directory structures used in operating systems with neat diagrams. Discuss the merits and demerits of each. 10 marks
A directory organises the files on a volume and maps each file name to its file control block. Its structure decides how easily users can name, search, group and share files. Five organisations are commonly used.
1. Single-level directory: All files of all users are kept in one directory.
It is simple to build and easy to search when there are few files. However, every file needs a unique name, so two users cannot both have a file called test. Grouping is impossible when the number of files grows.
2. Two-level directory: A master file directory (MFD) has one entry per user. Each entry points to that user's own user file directory (UFD).Different users can reuse the same name, and users are isolated from each other. A file is named by a path such as user1/test. The drawbacks are that a user cannot group his own files, and sharing needs access to another user's directory.
3. Tree-structured directory: This generalises the idea to any depth. There is one root, and every directory may hold files and subdirectories. Every file has a unique path from the root.Each process has a current directory. Names may be absolute (/home/ravi/os/lab1.c) or relative (os/lab1.c). Grouping is natural and searching is efficient. However, a file cannot appear in two directories, so sharing is awkward. Deleting a non-empty directory also needs a policy: either refuse or delete recursively.
4. Acyclic-graph directory: A file or subdirectory may appear in several directories, but cycles are not allowed.Sharing is done with links. A symbolic link stores a path; a hard link shares the same inode. Problems: one file has several names, so a traversal may visit it twice. Deletion can also leave dangling pointers. A reference count is therefore kept, and the file is removed only when the count reaches zero.
5. General-graph directory: Links may point to any directory, so cycles can form. Searches must avoid infinite loops, for example by limiting the number of directories visited. A cycle can also keep a reference count above zero after the file has become unreachable, so costly garbage collection is needed.
In short, moving from single-level to graph structures increases flexibility in naming, grouping and sharing, but also increases complexity. Most modern systems, such as UNIX, use a tree with links (an acyclic graph) because it balances flexibility with simplicity.
2 Explain the layered structure of a file system. Describe the on-disk and in-memory structures used to carry out file-system operations such as create, open, read and close. 10 marks
The file system gives efficient and convenient access to storage by mapping logical files onto physical disk blocks. It is built in layers, each using the services of the layer below. It keeps some structures on disk and others in memory.
Layered structure.
1. I/O control: device drivers and interrupt handlers. They turn requests such as read physical block 1234 into controller-specific commands. 2. Basic file system: issues generic block read and write commands to the drivers, manages buffers and caches, and schedules I/O. 3. File-organisation module: converts logical block numbers into physical block numbers using the allocation method. It also contains the free-space manager. 4. Logical file system: manages metadata, namely the directory structure and the file control blocks (FCBs; inodes in UNIX). It also enforces protection. Layering avoids duplicate code, because one I/O control layer can serve several file systems. The cost is extra overhead at every layer.
On-disk structures:
- Boot control block: the information needed to boot the OS from the volume.
- Volume control block (superblock): total blocks, block size, free-block count and free-block pointers.
- Directory structure: file names and their FCB numbers.
- Per-file FCB: owner, permissions, dates, size and data-block pointers.
In-memory structures:
- Mount table with one entry per mounted volume.
- Cache of recently used directories.
- System-wide open-file table: a copy of each open file's FCB and an open count.
- Per-process open-file table: a pointer into the system-wide table, the current file position and the access mode.
- Buffers that hold blocks in transit.
Operations: 1. create(): the logical file system allocates a new FCB. It reads the target directory, adds the new name and FCB, and writes the directory back to disk. 2. open(): the system-wide table is searched first. If the file is already open, its open count is increased. Otherwise the directory is searched and the FCB is copied into the system-wide table. An entry is then made in the per-process table, and its index is returned as a file descriptor (UNIX) or file handle (Windows). 3. read()/write(): the descriptor leads to the per-process entry, which gives the file position, and to the FCB, which gives the block locations. The file-organisation module maps logical blocks to physical blocks, and the basic file system moves the data. 4. close(): the per-process entry is removed and the open count is decreased. When the count reaches zero, the updated metadata is written to disk and the system-wide entry is freed.
In conclusion, layering keeps the design modular, and the in-memory tables make repeated operations fast while the disk copy stays consistent.
3 Explain contiguous, linked and indexed allocation of disk space with diagrams. Compare them and find the maximum file size possible with a single index block when the block size is 4 KB and a disk address is 4 bytes. 10 marks
Allocation methods decide how disk blocks are assigned to files. A good method uses space well and lets files be accessed quickly. The three main methods are described below.
1. Contiguous allocation: each file occupies consecutive blocks. The directory entry stores the start block and the length.
Logical block i of a file starting at b is at physical block b + i. Both sequential and direct access are therefore fast, with little head movement. The drawbacks are:
- External fragmentation, which may need compaction.
- The file size must be known when the file is created.
- Files are hard to grow.
Using extents, where extra contiguous chunks are linked to the file, eases growth.
2. Linked allocation: a file is a linked list of blocks that may lie anywhere on disk. The directory keeps pointers to the first and last blocks, and each block holds a pointer to the next.There is no external fragmentation, and files grow easily. The drawbacks are:
- Only sequential access is efficient, because reaching block i needs i disk reads.
- Pointers take space; a 4-byte pointer in a 512-byte block uses 4/512, about 0.78 percent.
- One damaged pointer loses the rest of the file.
The File Allocation Table (FAT) variant keeps all next-block pointers in a table at the start of the volume. The table can be cached, which makes random access faster.
3. Indexed allocation: all pointers of a file are gathered into one index block. Entry i points to block i of the file, and the directory stores the address of the index block.Direct access is supported without external fragmentation. However, even a small file needs a whole index block. Large files need linked index blocks, multilevel indexes, or the combined UNIX inode scheme of 12 direct pointers plus single, double and triple indirect pointers.
Calculation:
- Pointers per index block = 4096 / 4 = 1024.
- Maximum file size with one index block = 1024 × 4 KB = 4096 KB = 4 MB.
- With a two-level index, it would be 1024 × 1024 × 4 KB = 4 GB.
Comparison:
- Access: contiguous supports sequential and direct; linked supports sequential only; indexed supports both.
- External fragmentation: present in contiguous; absent in linked and indexed.
- File growth: difficult in contiguous; easy in the other two.
- Space overhead: lowest in contiguous; one pointer per block in linked; one index block per file in indexed.
In conclusion, contiguous allocation suits read-only media, linked allocation (FAT) suits simple sequential use, and indexed allocation, as in UNIX inodes, is the general-purpose choice.
4 Explain the free-space management techniques used by file systems with a suitable example. Also explain how directories can be implemented. 10 marks
The file system must track free disk blocks so it can allocate them to new or growing files and reclaim them after deletion. It must also implement directories so that names can be found quickly. Both tasks are described below.
Free-space management:
1. Bit vector (bitmap): each block has one bit, with 1 meaning free and 0 meaning allocated. Example: a disk has blocks 0 to 15, and blocks 1, 2, 5, 6, 7, 11 and 14 are free. The bitmap is 0110 0111 0001 0010. To find the first free block, scan the words for one that is not zero, then find its first 1 bit: block number = (bits per word) × (number of all-zero words) + offset of the first 1 bit. With 8-bit words, word 0 = 01100111 is not zero and its first 1 is at offset 1. So the block is 8 × 0 + 1 = 1. The method is simple and makes contiguous free runs easy to find. However, the bitmap must stay in memory. For a 1 TB disk with 4 KB blocks, it needs 2^40/2^12 = 2^28 bits = 2^25 bytes = 32 MB.
2. Linked list: all free blocks are chained together, and a pointer to the first one is kept in a special location. Allocation simply takes the head block. Walking the whole list is slow, but this is rarely needed.
3. Grouping: the first free block stores the addresses of n free blocks. The first n-1 of these are free; the last one holds the next n addresses. Many free blocks can therefore be found quickly.
4. Counting: free blocks often occur in runs, so each run is stored as a pair (first free block, count). For the example above, the list is (1,2), (5,3), (11,1), (14,1). This is compact when runs are long.
Directory implementation:
1. Linear list: the directory is a list of entries, each holding a file name and a pointer to its FCB. It is simple to program. However, every lookup, and every create (which must check for a duplicate name), needs a linear search. Deletion either marks the entry unused or moves the last entry into the gap. A sorted list, a balanced tree, or caching of recent entries speeds up searches.
2. Hash table: a linear list is still used, but a hash of the file name gives the position of the entry directly. Lookup takes close to constant time. Collisions are handled by chaining entries that hash to the same slot. A fixed-size table is a problem: if 64 slots map names to 0-63 and more entries are needed, a new hash function and rehashing of every entry are required. Chained overflow buckets reduce this problem.
In conclusion, bitmaps and counting are popular for free space because they are compact, and hash tables give fast directory lookup at the cost of managing table size.
5 Explain the goals and principles of protection. Describe the domain of protection and the access matrix model with an example, along with methods to implement the access matrix. 10 marks
Protection is the set of mechanisms that control how processes and users access the resources defined by a computer system: files, memory, devices and CPU.
Goals of protection:
- Prevent deliberate, mischievous violation of access restrictions.
- Ensure that each component uses resources only in ways allowed by stated policies.
- Detect latent errors early at the interfaces between subsystems, which improves reliability.
- Separate mechanism (how access is checked) from policy (what is allowed), so that policies can change without changing the mechanisms.
Principles of protection:
- Least privilege: give each subject only the rights it needs, for only as long as it needs them.
- Need-to-know: at any moment a process may access only the objects its current task requires.
- Compartmentalisation and defence in depth: separate components and use several layers of checks.
- Audit trails: record accesses so that violations can be traced.
Domain of protection: A process runs inside a protection domain, which is a set of access rights. An access right is an ordered pair <object-name, rights-set>, for example <F1, {read, write}>. Domains may overlap. A domain can correspond to a user, a process or a procedure. The link between a process and its domain may be static, or dynamic with domain switching. For example, the UNIX setuid bit runs a program in its owner's domain.
Access matrix: rows are domains and columns are objects. Entry access(i,j) is the set of operations a process in domain Di may perform on object Oj. Example (domain: object rights):
- D1: F1 {read}, F3 {read}
- D2: Printer {print}
- D3: F2 {read}, F3 {execute}
- D4: F1 {read, write}, F3 {read, write}
Domains can also be columns, so that a switch right in entry (D2, D3) lets a process move from D2 to D3. Special rights control changes to the matrix:
- Copy (written as read*): lets a right be copied within its column.
- Owner: lets rights in that column be added or removed.
- Control: lets one domain change the entries in another domain's row.
Implementation of the access matrix: 1. Global table: a list of triples <domain, object, rights-set>. It is simple, but it is too large to keep in memory and cannot group related entries. 2. Access lists: each column is stored with its object as a list of <domain, rights-set> pairs, plus a default set. This is the access control list (ACL) used by file systems, and revoking rights is easy. 3. Capability lists: each row is stored with its domain as a list of protected object references (capabilities). Possessing a capability grants access, but revocation is harder. 4. Lock-key: each object has locks and each domain has keys; access is allowed when a key matches a lock. Real systems combine methods. UNIX checks the ACL when a file is opened and then uses the file descriptor as a capability.
In conclusion, the access matrix gives a clean, general model that separates policy from mechanism, and ACLs and capabilities make it practical.
6 Discuss file sharing in multi-user and networked environments, including consistency semantics. Also explain partitions and file-system mounting. 10 marks
Sharing files lets users cooperate, but it raises questions of identity, protection and consistency. Before files can be shared at all, their file systems must be made accessible through partitions and mounting.
File sharing among multiple users: 1. The OS records an owner (user ID) and a group (group ID) for every file. The owner may change attributes and grant access. Group members get a subset of rights, and all other users get another subset. UNIX, for example, keeps read, write and execute bits for owner, group and others. 2. When a user requests an operation, the user ID and group ID are compared with the file's attributes to decide which permissions apply.
Remote file sharing: 1. Early methods transferred whole files explicitly, as FTP does. Later methods include distributed file systems such as NFS, where remote directories appear as local ones, and the World Wide Web. 2. The client-server model: the server exports file systems, and clients mount them. Clients are identified by network address or authenticated identity, and user IDs must match on both machines. 3. Failure modes: network or server failures can break operations in progress. Stateless protocols such as early NFS put full information in each request, so recovery is simple.
Consistency semantics define when one user's writes become visible to other users of the same file:
- UNIX semantics: writes are visible at once to all users who have the file open. A shared file pointer can also be used.
- Session semantics (as in AFS): writes are visible only to sessions that open the file after the writer closes it. Several copies may exist for a time.
- Immutable shared files: once a file is declared shared, it cannot be changed, so consistency is trivial.
Partitions: 1. A disk is divided into partitions (slices). Each one may hold a file system (cooked) or be used raw, for example for swap space or databases that manage their own blocks. 2. A boot partition holds the boot loader, which may support several operating systems (dual booting). 3. The root partition, holding the OS kernel and system files, is mounted at boot time.
Mounting: 1. A file system must be mounted before use. The OS is given the device name and a mount point, which is an empty directory in the existing tree. 2. The OS checks that the device holds a valid file system by reading its superblock. It then records the mount in the in-memory mount table. 3.
4. UNIX attaches volumes anywhere in one tree. Windows gives each volume a drive letter such as D:, though it also supports mounting at folders. Mounting over a non-empty directory hides its original files until the volume is unmounted.
In conclusion, careful ownership checks and clear consistency semantics make sharing safe, while partitions and mounting combine many devices into one directory namespace.
Public sources that settled doubtful points
Only the points the second AI pass doubted were looked up. These are the pages that confirmed or contradicted them; nothing here is copied from them.
Further reading
Titles only, for your own study. Nothing on this page is copied from them. The units follow the official JNTUK R23 CSE syllabus (PDF) ↗.
- Operating System Concepts · A. Silberschatz, P. B. Galvin and G. Gagne
- Modern Operating Systems · A. S. Tanenbaum
- Operating Systems: Internals and Design Principles · W. Stallings
- Operating Systems: A Concept Based Approach · D. M. Dhamdhere