COMPREHENSIVE OPERATING SYSTEMS NOTES (KNEC SYLLABUS)

Table of Contents

1. Introduction to Operating Systems

2. Operating System Structures
3. Process Management
4. CPU Scheduling Algorithms
5. Process Synchronization & Deadlocks
6. Memory Management
7. Virtual Memory
8. File Systems
9. I/O System Management
10. Sample KNEC Questions & Answers

1. Introduction to Operating Systems

1.1 Definition
An Operating System (OS) is a crucial piece of system software that acts as
an intermediary between the computer user and the computer hardware. Its
primary purpose is to provide an environment in which a user can execute programs in a
convenient and efficient manner. It is a resource manager, deciding how to allocate the
computer's hardware (CPU, memory, disks, I/O devices) among competing application
programs.

1.2 Key Objectives

 Convenience: Makes the computer easier to use by providing abstractions (e.g., files
instead of disk blocks).
 Efficiency: Allows the computer system to be used in an efficient manner, maximizing
throughput and minimizing response time.
 Ability to Evolve: Should be constructed to permit the effective development, testing,
and introduction of new system functions without interfering with existing services.

1.3 Core Functions/Responsibilities

1. Process Management: The OS is responsible for:
o Creating and deleting both user and system processes.
o Suspending and resuming processes.
o Providing mechanisms for process synchronization and process communication.
2. Memory Management: The OS must:
o Keep track of which parts of memory are currently being used and by whom.
o Decide which processes are to be loaded into memory when space becomes available.
o Allocate and deallocate memory space as needed.
3. File Management: The OS manages the file system, which includes:
o Creating and deleting files and directories.
o Supporting primitives for manipulating files and directories (read, write, create, delete).
o Mapping files onto secondary storage (disks).
o Backing up files onto stable (non-volatile) storage media.
4. Device Management: The OS manages device communication via their drivers. This
involves:
o Buffering, caching, and spooling data for devices.
o Enforcing preemptive and non-preemptive device scheduling.
5. Security and Protection: The OS ensures that all access to system resources is
controlled.
o Protection: involves ensuring that all access to system resources is controlled.
o Security: defends the system from external and internal attacks via user authentication,
firewalls, etc.

1.4 Types of Operating Systems

 Batch Operating Systems: Users submit jobs to an operator who batches similar jobs
together. No direct user interaction. High throughput but long turnaround time.
 Multiprogramming Systems: Several jobs are kept in main memory at the same time.
The CPU switches between them. This increases CPU utilization and overall throughput.
 Multitasking / Time-Sharing Systems: The CPU executes multiple jobs by switching
among them so frequently that users can interact with each program while it is running.
Very short response time.
 Real-Time Systems (RTOS): Used when rigid time requirements are placed on the
operation of a processor. Must serve requests within a guaranteed time frame.
o Hard Real-Time: Missing a deadline is a critical failure (e.g., flight control systems).
o Soft Real-Time: Missing a deadline is undesirable but not critical (e.g., multimedia
streaming).
 Distributed Systems: Operate on a collection of independent, networked computers
that appear to the user as a single coherent system (e.g., cloud computing platforms).
 Network Operating Systems: Run on a server and provide capabilities for managing
data, users, groups, security, and applications over a network (e.g., Windows Server,
Linux servers).

2. Operating System Structures

2.1 System Components

 Process Management
 Main Memory Management
 File Management
 I/O System Management
 Secondary Storage Management
 Networking
 Protection System
 Command Interpreter (Shell)

2.2 Operating System Services

 User Interface (CLI, GUI, Batch)

 Program Execution
 I/O Operations
 File System Manipulation
 Communications (Shared Memory, Message Passing)
 Error Detection and Handling
 Resource Allocation
 Accounting (log usage)
 Protection and Security

2.3 System Calls

 System calls provide the interface between a running program and the OS. They are
typically written in C/C++.
 Types: Process Control, File Manipulation, Device Manipulation, Information
Maintenance, Communications.
 3. Process Management
3.1 Process Concept

 Program vs. Process: A program is a passive entity—a set of instructions stored on

disk (an executable file). A process is an active entity—a program in execution. A
process requires resources like CPU time, memory, files, and I/O devices.
 Process Control Block (PCB): The OS's data structure that represents a process. It is the
"manifestation" of a process in the OS. It contains all crucial information about the
process:
o Process State: e.g., running, waiting, ready.
o Process ID (PID): A unique identifier.
o Program Counter (PC): The address of the next instruction to execute.
o CPU Registers: The contents of all process-centric registers.
o CPU Scheduling Information: Process priority, pointers to scheduling queues.
o Memory Management Information: Base/limit registers, page tables.
o Accounting Information: CPU time used, time limits, process number.
o I/O Status Information: List of I/O devices allocated to the process, list of open files.

3.2 Process States

A process moves through a lifecycle of discrete states:

1. New: The process is being created.

2. Ready: The process is loaded in main memory and waiting to be assigned to the CPU.
3. Running: The process's instructions are being executed by the CPU.
4. Waiting/Blocked: The process is waiting for an event to occur (e.g., I/O completion,
reception of a signal). It cannot run even if the CPU is free.
5. Terminated: The process has finished execution. Its PCB remains until the OS cleans it
up.

3.3 Process Scheduling

The OS must select which available process will run on the CPU. This is the role of
the scheduler. The queues involved are:

 Job Queue: All processes in the system.

 Ready Queue: Set of all processes residing in main memory, ready and waiting to
execute.
 Device Queues: Set of processes waiting for a specific I/O device.

Schedulers:
 Long-Term Scheduler (Job Scheduler): Selects which processes are brought from the
disk (mass storage) into the ready queue in main memory. It controls the degree of
multiprogramming.
 Short-Term Scheduler (CPU Scheduler): Selects which process from the ready queue
is to be executed next and allocates the CPU to it. This scheduler is invoked very
frequently (every few milliseconds).
 Medium-Term Scheduler: Used in systems with time-sharing. It can remove (swap out)
a process from memory to reduce multiprogramming and later reintroduce it (swap in).
This is key to managing virtual memory.

3.4 Context Switch

The process of saving the state of the currently running process and restoring the state
of the next process to run.

 The state of the old process is saved into its PCB.

 The state of the new process is loaded from its PCB.
 Context switch time is pure overhead; the system does no useful work while switching.
Its speed is heavily dependent on hardware support.

3.5 Operations on Processes

 Process Creation: Processes create other processes, forming a process tree.

o The creator is the parent process; the new process is the child process.
o Mechanisms: fork() (creates a child as a copy of the parent) and exec() (loads a new
program into a process's memory space) in Unix/Linux.
 Process Termination: A process terminates when it finishes executing its final
statement. It may also be terminated by its parent or by the OS due to an error.
Resources are deallocated, and the parent is informed via a signal.
 4. CPU Scheduling
4.1 Basic Concepts
The objective of multiprogramming is to have some process running at all times to
maximize CPU utilization. The CPU scheduler selects from among the processes in the
ready queue and allocates the CPU to one of them.

4.2 Scheduling Criteria

 CPU Utilization: Keep the CPU as busy as possible (maximize).

 Throughput: Number of processes completed per time unit (maximize).
 Turnaround Time: The interval from the time of submission of a process to the time of
completion (minimize). (Completion time - Arrival time)
 Waiting Time: Total time a process spends waiting in the ready queue (minimize).
 Response Time: The time from the submission of a request until the first response is
produced (minimize). Important for interactive systems.

4.3 Scheduling Algorithms

Algorithm Description Pros Cons

The simplest
algorithm. The
Convoy effect: Short
First-Come, process that Simple, easy to
processes wait behind
First-Served requests the CPU understand &
one long process.
(FCFS) first is allocated the implement.
Poor for time-sharing.
CPU first. Managed
with a FIFO queue.

Associates with each

process the length Optimal – gives Impossible to know
Shortest- of its next CPU burst. minimum average the length of the next
Job-First The scheduler picks waiting time for a CPU burst. Can lead
(SJF) the process with the given set of to starvation for
smallest next CPU processes. longer processes.
burst.
Algorithm Description Pros Cons

A priority (integer) is
Starvation – low
associated with each
priority processes may
process. The CPU is Flexible, priorities
never
Priority allocated to the can be defined
execute. Aging is a
Scheduling process with the internally or
solution (gradually
highest priority. Can externally.
increasing priority of
be preemptive or
waiting processes).
non-preemptive.

Designed for time-

sharing. Each
process gets a small
unit of CPU time Performance depends
(time quantum, Good response heavily on the size of
Round
usually 10-100ms). time, fair to all the time quantum.
Robin (RR)
After time expires, processes. High overhead if
the process is quantum is too small.
preempted and
added to the tail of
the ready queue.

The ready queue is

partitioned into
several separate
Can apply
queues (e.g., system
Multilevel different policies Risk of starvation for
processes,
Queue to different types lower-priority queues.
interactive, batch).
of jobs.
Each queue has its
own scheduling
algorithm.
Algorithm Description Pros Cons

Allows a process to
move between
queues. A process
that uses too much Highly flexible and
Multilevel CPU time is moved adaptive. Can be
Complex to implement
Feedback to a lower-priority configured to
and tune.
Queue queue. This is the match a specific
most complex but system.
also the most
general and adaptive
scheme.
 5. Process Synchronization & Deadlocks
5.1 The Critical-Section Problem

 Critical Section: A segment of code in which a process may be accessing and updating
shared data (a variable, file, table).
 The critical-section problem is to design a protocol that processes can use to
cooperate. Any solution must satisfy:
1. Mutual Exclusion: If process Pi is executing in its critical section, then no other
processes can be executing in their critical sections.
2. Progress: If no process is in its critical section and some processes wish to enter, then
only those processes not in their remainder section can participate in the decision, and
the selection cannot be postponed indefinitely.
3. Bounded Waiting: There exists a bound on the number of times other processes are
allowed to enter their critical sections after a process has made a request to enter its
critical section and before that request is granted.

5.2 Synchronization Hardware

 TestAndSet(): An atomic hardware instruction that tests a value and sets it to true
without allowing any other interrupt.
 Swap(): An atomic instruction that swaps the contents of two memory words.

5.3 Semaphores
A synchronization tool that uses an integer variable (S) to control access to a common
resource by multiple processes. They can only be accessed via
two atomic operations: wait(S) (or P(S)) and signal(S) (or V(S)).

 Usage:
o Counting Semaphore: The integer value can range over an unrestricted domain. Used
to control access to a resource with multiple instances.
o Binary Semaphore: The integer value can only be 0 or 1. Simpler to implement. Used to
implement mutual exclusion (mutex locks).

5.4 Deadlocks
A set of processes is in a deadlocked state if every process in the set is waiting for an
event that can only be caused by another process in the set (a classic "circular wait").

Necessary Conditions for Deadlock (Coffman Conditions):

1. Mutual Exclusion: At least one resource must be held in a non-sharable mode.

2. Hold and Wait: A process must be holding at least one resource and waiting to acquire
additional resources held by other processes.
3. No Preemption: Resources cannot be preempted; they can only be released voluntarily
by the process holding it.
4. Circular Wait: There must exist a set of waiting processes {P0, P1, ..., Pn} such that P0 is
waiting for a resource held by P1, P1 is waiting for a resource held by P2, ..., Pn is waiting
for a resource held by P0.

Methods for Handling Deadlocks:

 Prevention: Ensure that at least one of the four necessary conditions cannot hold. Very
restrictive.
 Avoidance: Requires the OS to have a priori information about how resources are to be
requested. The OS uses algorithms (like the Banker's Algorithm) to decide if a resource
allocation should be made to avoid entering an unsafe state.
 Detection & Recovery: Allow the system to enter a deadlock state, then have an
algorithm to detect it (using resource-allocation graphs) and a strategy to recover from
it (e.g., process termination, resource preemption).
 Ignore: Pretend deadlocks never happen. Used by most operating systems, including
Windows and Linux. The problem is "solved" by rebooting.
 6. Memory Management
6.1 Background

 Main memory (RAM) is central to a modern computer system. It is a large array of words
or bytes, each with its own address.
 The CPU fetches instructions from memory based on the value of the program counter
(PC).
 The fundamental task of the Memory Manager is to manage the hierarchy of memory
(cache, RAM, disk) to keep the CPU utilized efficiently.

6.2 Logical vs. Physical Address Space

 Logical Address (Virtual Address): An address generated by the CPU. It is the address
of an instruction or data as seen by the process.
 Physical Address: The actual address in the computer's memory unit that is loaded into
the memory address register.
 The Memory Management Unit (MMU) is the hardware device that at run time maps
virtual addresses to physical addresses. The value in the relocation register (base
register) is added to every logical address generated by a user process.

6.3 Memory Allocation Schemes

1. Contiguous Allocation

 Single-Partition Allocation: The OS resides in low memory, and a single user process is
loaded into the remaining high memory. Uses a relocation-register scheme to protect
the OS and user processes from each other.
 Multiple-Partition Allocation:
o Fixed Partitioning: Memory is divided into several fixed-sized partitions. Each partition
can hold exactly one process. Leads to internal fragmentation (unused memory inside
a partition).
o Dynamic Partitioning: Partitions are created dynamically to fit the exact size of the
incoming process. This eliminates internal fragmentation but causes external
fragmentation (free memory is broken into small, scattered pieces over time). Solved
by compaction.

2. Non-Contiguous Allocation

 Paging: Allows the physical address space of a process to be noncontiguous. Solves the
external fragmentation problem.
o Divides physical memory into fixed-sized blocks called frames.
o Divides logical memory into blocks of the same size called pages.
o The OS maintains a page table for each process to translate logical page numbers to
physical frame numbers.
o Advantages: No external fragmentation.
o Disadvantages: Page table overhead, can still have internal fragmentation (in the last
page).
 Segmentation: A memory-management scheme that supports the user's view of
memory. A program is a collection of segments (e.g., main function, stack, variables,
array).
o A logical address is a pair: <segment-number, offset>.
o Each segment has a name, length, and is assigned a base address in memory.
o The OS maintains a segment table for each process, containing the base address and
length (limit) of each segment.
o Advantages: Matches the programmer's logical view, easy to share code/data.
o Disadvantages: Suffers from external fragmentation.

7. Virtual Memory
7.1 Background

 Virtual memory is a technique that allows the execution of processes that are not
completely in memory. It separates logical memory from physical memory.
 It enables programs to be larger than physical memory. It frees programmers from
worrying about memory-storage limitations.
 Implemented via Demand Paging.

7.2 Demand Paging

 A paging system where pages are only loaded into memory when they are demanded
by the program (i.e., when a page fault occurs).
 Pages reside in secondary storage (usually a special area of the disk called the swap
space).
 Lazy swapper: Never swaps a page into memory unless it will be needed.

7.3 Page Fault

 Occurs when a process tries to access a page that is mapped in its address space but
not currently loaded in physical memory (RAM).
 Steps to handle a page fault (crucial for exams):
1. The memory reference is checked for validity. If invalid, the process is terminated.
2. If valid, but the page is not in memory, it is a page fault. The OS finds a free frame.
3. If no free frame exists, a page replacement algorithm is used to select a victim frame.
4. The desired page is read from the disk into the newly allocated frame.
5. The page table is updated to reflect the new mapping (page -> frame).
6. The instruction that caused the page fault is restarted.

7.4 Page Replacement

 When a page fault occurs and there are no free frames, the OS must choose a page in
memory to evict to make room.
 Goal: To reduce the page fault rate.
 Basic Page Replacement:
1. Find the location of the desired page on the disk.
2. Find a free frame: a) If there is a free frame, use it. b) If not, use a page-replacement
algorithm to select a victim page.
3. Write the victim page to the disk (if it was modified - dirty bit).
4. Read the desired page into the newly freed frame.
5. Update the page and frame tables.
6. Restart the process.

7.5 Page Replacement Algorithms

 First-In-First-Out (FIFO): The oldest page is replaced. Simple to implement but suffers
from Belady's Anomaly (more frames can lead to more page faults).
 Optimal Algorithm (OPT): Replace the page that will not be used for the longest
period of time in the future. This is the ideal algorithm, but it is impossible to implement
as it requires knowledge of the future. Used as a benchmark.
 Least Recently Used (LRU): Replace the page that has not been used for the longest
time. It is based on the principle of locality. It is a good approximation of OPT but is
expensive to implement perfectly.

8. File Systems
 8.1 File Concept

 A file is a named collection of related information recorded on secondary storage.

 File Attributes: Name, Identifier, Type, Location, Size, Protection, Time & Date.
 File Operations: Create, Write, Read, Reposition within file (seek), Delete, Truncate.

8.2 File Access Methods

 Sequential Access: Information is processed in order, one record after another (like a
tape). read next and write next operations.
 Direct Access (Random Access): A file is made up of fixed-length logical records.
Programs can read and write records in any order without a defined sequence. Essential
for databases.

8.3 Directory Structure

 A collection of nodes containing information about all files. It organizes files logically.
 Operations on a Directory: Search for a file, Create a file, Delete a file, List a directory,
Rename a file, Traverse the file system.
 Common Structures:
o Single-Level Directory: All files are contained in one directory. Simple but leads to
naming conflicts and poor organization.
o Two-Level Directory: Separate directory for each user. Solves name collision problems.
o Tree-Structured Directory: Most common. Allows users to create their own
subdirectories and organize their files hierarchically. A file is specified by
its pathname (e.g., /home/user/docs/report.txt).
o Acyclic-Graph Directory: Allows directories to have shared subdirectories and files
(links). More flexible but more complex.

8.4 File-System Implementation

 File Allocation Methods: How the disk blocks are allocated for a file.
o Contiguous Allocation: Each file occupies a set of contiguous blocks on the disk.
Simple, fast sequential access. Suffers from external fragmentation.
o Linked Allocation: Each file is a linked list of disk blocks. Blocks may be scattered.
Solves fragmentation. Inefficient for direct access.
o Indexed Allocation: Brings all pointers together into one location: the index block.
Each file has its own index block, which is an array of disk-block addresses. Supports
direct access without external fragmentation.
 Free-Space Management:
o Bit Vector (Bitmask): Each block is represented by a bit. 1 = free, 0 = allocated. Efficient
for finding free space.
o Linked List: Links together all the free disk blocks. Poor performance for finding a large
contiguous free space.
o Grouping: Stores the addresses of n free blocks in the first free block.

9. I/O System Management

9.1 Overview
The I/O subsystem is responsible for memory management of I/O including buffering,
caching, and spooling. A key concept is device independence, where programs can
access I/O devices without specifying the device in advance.

9.2 I/O Hardware

 Port: A connection point for devices (e.g., USB port, SATA port).
 Bus: A set of wires that define a set of commands and data transfer protocols (e.g., PCI
bus).
 Device Controller: An electronic component that operates a port, bus, and a device. It
has local buffer storage and special-purpose registers.
 The Device Controller provides an interface between the OS and the hardware device.

9.3 Application I/O Interface

The OS structures all device drivers and I/O devices into a uniform and standardized
interface for applications. Key device types include:

 Block Devices: e.g., disks. Commands include read, write, seek. Accessed via file-system
interfaces or raw I/O.
 Character Devices: e.g., keyboards, mice. Commands include get(), put(). Accessed via
a sequential stream of characters.
 Network Devices: e.g., network cards. Have their own unique interface (sockets).

9.4 Kernel I/O Subsystem

 Scheduling: The OS uses device queues to schedule I/O requests to devices. I/O
scheduling can significantly improve overall system performance (e.g., disk scheduling
algorithms like SSTF, SCAN, C-SCAN).
 Buffering: A buffer is a memory area that stores data while it is being transferred
between two devices or between a device and an application. It is used to:
o Cope with speed mismatches between producer and consumer (e.g., printer spooling).
o Adapt between data-transfer sizes.
o Support copy semantics for application I/O.
 Caching: A cache is a region of fast memory that holds copies of data from a slower
device. The goal is to increase performance and reduce I/O operations. The main
difference between a buffer and a cache is that a buffer may hold the only copy of a
data item, while a cache is a redundant copy.
 Spooling (Simultaneous Peripheral Operations On-Line): A technique that uses a
buffer to hold output for a device, such as a printer,