Operating System Notes - From Basics to Advanced Concepts | Free Download

Introduction to Operating Systems

1. Definition and Functions of OS

Definition:

An Operating System (OS) is system software that manages computer hardware and software resources and provides common services for computer programs.

Functions:

• Process Management: Handles process scheduling, creation, execution, and termination.
• Memory Management: Allocates and deallocates memory space as needed.
• File System Management: Organizes, stores, retrieves, and secures files.
• Device Management: Controls peripheral devices like printers, keyboards, and monitors.
• Security & Access Control: Protects against unauthorized access.
• Error Handling: Detects and recovers from system failures.

Example:

Windows OS manages multiple applications like Chrome, MS Word, and Spotify simultaneously without interference.

2. Types of Operating Systems

1. Batch Operating System:

• Processes similar jobs together without user interaction.
• Example: IBM Mainframe OS

2. Multi-Programming OS:

• Executes multiple programs by sharing CPU time.
• Example: UNIX

3. Time-Sharing OS:

• Allows multiple users to interact with the system simultaneously by allocating time slices.
• Example: Windows Server

4. Real-Time OS (RTOS):

• Provides immediate response for critical applications.
• Hard RTOS: Strict time constraints (e.g., Airbag System).
• Soft RTOS: Tolerant to some delays (e.g., Video Streaming).

5. Distributed OS:

• Manages multiple computers as a single system.
• Example: Google’s Cloud Infrastructure

6. Embedded OS:

• Designed for specialized hardware.
• Example: Android in Smart TVs, iOS in iPhones

3. OS Services and System Calls

OS Services:

• Program Execution: Loads and runs programs.
• I/O Operations: Manages input and output devices.
• File Manipulation: Creates, reads, writes, and deletes files.
• Communication: Allows inter-process communication (IPC).
• Error Detection: Identifies and handles system failures.

System Calls:

System calls are used by programs to request services from the OS.

Type	Example
Process Control	fork()>, exit()>
File Management	open()>, read()>, write()>
Device Management	ioctl()>, read()>, write()>
Information Maintenance	getpid()>, gettimeofday()>
Communication	send()>, recv()>

Example:

• fork()>: Creates a child process in UNIX/Linux.
• open()>: Opens a file in a file system.

4. Structure of OS

1. Monolithic OS:

• Entire OS is in a single layer.
• Fast but difficult to maintain.
• Example: MS-DOS

2. Layered OS:

• Organized in layers where each layer performs specific functions.
• Easy to debug but slower due to layer dependency.
• Example: THE OS

3. Microkernel OS:

• Only essential services run in the kernel, reducing system crashes.
• Example: QNX, MINIX

4. Hybrid OS:

• Combination of monolithic and microkernel features.
• Example: Windows NT

5. Modular OS:

• Components are separate modules that can be loaded as needed.
• Example: Linux Kernel Modules

Practice Questions:

1. Define an Operating System and explain its key functions.
2. Differentiate between Batch OS and Time-Sharing OS.
3. What are the advantages of using a Microkernel over a Monolithic OS?
4. Explain the role of system calls with suitable examples.
5. Compare and contrast Real-Time OS and Distributed OS.
6. Describe the structure of an OS and provide an example for each type.

Process Management

1. Process Concept

A process is a program in execution. It consists of the program code, data, stack, and heap.

Process States

A process undergoes different states during execution:

• New: Process is being created.
• Ready: Process is waiting for CPU allocation.
• Running: Process is executing instructions.
• Blocked (Waiting): Process is waiting for I/O or resource.
• Terminated: Process has completed execution.

Process Control Block (PCB)

A PCB stores process information, including:

• Process ID: Unique identifier.
• Program Counter: Stores next instruction address.
• CPU Registers: Stores intermediate calculations.
• Memory Management Information: Page table, segment table.
• I/O Information: Open files, devices in use.

Example

A text editor being used is a process. If minimized, it goes to the Ready state; if waiting for file loading, it enters the Blocked state.

2. Process Scheduling

Process scheduling determines which process gets CPU time.

Preemptive vs. Non-Preemptive Scheduling

• Preemptive: CPU can be taken from a process (e.g., Round Robin, Priority Scheduling).
• Non-Preemptive: CPU is released only when the process completes (e.g., FCFS, SJF).

Example

In an OS, if a high-priority process arrives, it may interrupt a lower-priority running process (Preemptive Scheduling). In contrast, FCFS serves processes one by one in arrival order (Non-Preemptive Scheduling).

3. CPU Scheduling Algorithms

(i) First-Come, First-Served (FCFS)

• Non-preemptive, serves processes in arrival order.
• Example: Bank queue.

(ii) Shortest Job First (SJF)

• Non-preemptive/preemptive, executes the shortest process first.
• Example: Downloading small files before large ones.

(iii) Round Robin (RR)

• Preemptive, each process gets CPU for a fixed time (time quantum).
• Example: Time-sharing systems like time slots in an online exam.

(iv) Priority Scheduling

• Preemptive/non-preemptive, highest priority process runs first.
• Example: Emergency room patients prioritized.

(v) Multilevel Queue Scheduling

• Processes are divided into queues with different scheduling algorithms.
• Example: System processes vs. user processes.

4. Threading

A thread is a lightweight process.

Single vs. Multithreading

• Single-threaded: One task at a time (e.g., Notepad).
• Multithreading: Multiple threads run concurrently (e.g., Web browser handling multiple tabs).

Multithreading Models

• Many-to-One: Multiple user threads map to a single kernel thread.
• One-to-One: Each user thread has a corresponding kernel thread.
• Many-to-Many: Multiple user threads map to multiple kernel threads.

5. Inter-Process Communication (IPC)

Processes need to communicate for data exchange.

(i) Shared Memory

• Processes share a memory segment.
• Example: Two processes accessing the same database table.

(ii) Message Passing

• Processes communicate via messages.
• Example: Sending emails between servers.

Questions for Practice

1. Explain the different states of a process with an example.
2. Compare preemptive and non-preemptive scheduling.
3. Describe the working of the Round Robin scheduling algorithm.
4. What are the advantages of multithreading?
5. Differentiate between shared memory and message passing in IPC.

Process Synchronization & Deadlocks

---

1. Critical Section Problem

Definition:

• The critical section is a part of a program where shared resources (variables, files, etc.) are accessed.
• Multiple processes should not enter the critical section simultaneously to prevent data inconsistency.

Solution Requirements (Mutual Exclusion, Progress, Bounded Waiting):

1. Mutual Exclusion: Only one process can enter the critical section at a time.
2. Progress: If no process is in the critical section, others should decide in a finite time.
3. Bounded Waiting: A process should not wait indefinitely to enter the critical section.

Example:

Process 1:                          Process 2:
while(flag2);  // Wait               flag2 = true;
critical section;                    while(flag1);
flag1 = false;                        critical section;
                                      flag2 = false;
>

This is an implementation of Peterson’s Algorithm for two processes.

---

2. Synchronization Mechanisms

2.1 Semaphores

• A semaphore is an integer variable used to control access to a shared resource.
• Operations:
  • wait(S)>: Decreases the semaphore value (blocks if < 0).
  • signal(S)>: Increases the semaphore value (wakes a waiting process).
• Example:

Semaphore S = 1;
wait(S);
   // Critical Section
signal(S);
>

2.2 Mutex (Mutual Exclusion)

• A binary semaphore (0 or 1) that ensures mutual exclusion.
• Only one process can hold the lock at a time.

2.3 Monitors

• A higher-level synchronization construct.
• Provides automatic mutual exclusion using condition variables.
• Example:

monitor example {
   condition X;
   void wait() { X.wait(); }
   void signal() { X.signal(); }
}
>

---

3. Classic Synchronization Problems

3.1 Producer-Consumer Problem

• Issue: A producer adds data to a buffer, and a consumer removes data.
• Solution: Use semaphores to synchronize access.
• Example:

Semaphore full = 0, empty = n, mutex = 1;
Producer: wait(empty); wait(mutex); add item; signal(mutex); signal(full);
Consumer: wait(full); wait(mutex); remove item; signal(mutex); signal(empty);
>

3.2 Reader-Writer Problem

• Issue: Multiple readers can read simultaneously, but only one writer can write at a time.
• Solution: Use semaphores to enforce order.

3.3 Dining Philosophers Problem

• Issue: Five philosophers sit at a table, alternating between eating and thinking. They need two forks to eat, leading to deadlock.
• Solution: Use semaphores or monitors to ensure correct resource allocation.

---

4. Deadlocks

4.1 Conditions for Deadlock (Coffman’s Conditions)

1. Mutual Exclusion – A resource is assigned to only one process at a time.
2. Hold and Wait – A process holding a resource is waiting for additional ones.
3. No Preemption – Resources cannot be forcibly taken.
4. Circular Wait – A circular chain of waiting processes exists.

4.2 Deadlock Prevention

• Break at least one of Coffman’s conditions:
  • Mutual Exclusion: Use spooling (printing systems).
  • Hold and Wait: Allocate all resources at the start.
  • No Preemption: Allow resource preemption.
  • Circular Wait: Impose an ordering on resource allocation.

4.3 Deadlock Avoidance: Banker’s Algorithm

• Ensures safe state allocation:
• Example:
  • Available> = (3, 3, 2)
  • Max> = (7, 5, 3), (3, 2, 2), (9, 0, 2), (2, 2, 2), (4, 3, 3)
  • Allocation> = (0, 1, 0), (2, 0, 0), (3, 0, 2), (2, 1, 1), (0, 0, 2)

4.4 Deadlock Detection & Recovery

• Detection:
  • Check for circular wait conditions using resource allocation graphs.
• Recovery:
  • Terminate processes or preempt resources.

---

Example Questions

1. What is the critical section problem? How can it be solved?
2. Explain semaphores with an example.
3. Discuss the Producer-Consumer problem with a solution.
4. What are the conditions for deadlock? How can deadlocks be prevented?
5. Explain the Banker’s Algorithm with an example.

---

Memory Management in Operating Systems

1. Logical vs Physical Address Space

Logical Address:

• Generated by the CPU during execution.
• Virtual address used by programs.

Physical Address:

• Actual address in memory (RAM).
• Used by the memory unit to access data.

Example:

A program generates a logical address 0x1234, which is mapped to a physical address 0x5678 by the memory management unit (MMU).

Question:

Q: What is the main difference between logical and physical addresses? A: Logical addresses are used by programs, while physical addresses are actual locations in RAM.

---

2. Contiguous Memory Allocation

Fixed Partitioning:

• Memory is divided into fixed-size partitions.
• Can lead to internal fragmentation (unused space inside partitions).

Variable Partitioning:

• Partitions are created dynamically based on process needs.
• Can lead to external fragmentation (scattered free memory blocks).

Example:

If a system has 3 partitions (100MB, 200MB, 300MB) and a process requires 150MB, it can’t use the 100MB partition, leading to fragmentation.

Question:

Q: What is internal fragmentation? A: Wasted memory within allocated space due to fixed partition sizes.

---

3. Paging & Segmentation

Paging:

• Divides memory into fixed-size pages.
• Pages map to frames in physical memory.
• Eliminates external fragmentation but may cause internal fragmentation.

Segmentation:

• Divides memory into variable-size segments based on logical divisions (e.g., code, data, stack).
• Can lead to external fragmentation.

Example:

A process of 10MB is divided into 4 pages of 2.5MB each, which fit into available frames in physical memory.

Question:

Q: What is the main difference between paging and segmentation? A: Paging divides memory into fixed-size blocks, whereas segmentation divides it based on logical divisions.

---

4. Virtual Memory

Demand Paging:

• Loads pages into memory only when needed.
• Reduces memory usage but may cause page faults.

Page Replacement Algorithms:

• FIFO (First-In-First-Out): Replaces the oldest page.
• LRU (Least Recently Used): Replaces the least accessed page.
• Optimal: Replaces the page that will not be used for the longest time (ideal but impractical).

Example:

If frames = 3 and pages are requested in order (1, 2, 3, 4, 2, 1), FIFO will remove 1 when 4 arrives.

Question:

Q: Why is the Optimal page replacement algorithm not used in practice? A: It requires future knowledge of page requests, which is not feasible.

---

5. Thrashing and Working Set Model

Thrashing:

• When excessive paging reduces CPU performance.
• Happens when a process doesn’t have enough frames.

Working Set Model:

• Defines a set of pages needed by a process at a given time.
• Ensures sufficient frames are allocated to prevent thrashing.

Example:

If a process needs 5 pages but only 3 frames are allocated, frequent page swaps will lead to thrashing.

Question:

Q: How can the working set model prevent thrashing? A: By ensuring a process has enough frames to hold its active pages.

---

File System Management

1. File Concepts

A file is a collection of related information stored on secondary storage.

1.1 File Attributes

Each file has metadata that describes its properties:

• Name: Human-readable identifier.
• Identifier: Unique number to identify the file.
• Type: System-defined format (e.g., .txt, .exe).
• Location: Address of file on storage.
• Size: Current file size in bytes.
• Protection: Access control mechanisms.
• Time, Date, and User ID: Tracking modifications and ownership.

1.2 File Types

Files can be categorized as:

• Text files (.txt, .doc) - Human-readable content.
• Binary files (.exe, .bin) - Executable programs or compiled code.
• Multimedia files (.mp3, .mp4, .jpg) - Contain images, audio, or video.

1.3 File Access Methods

• Sequential Access: Data is read in order from start to end (e.g., tape storage).
• Direct (Random) Access: Data can be read or written at any position (e.g., hard drives).
• Indexed Access: Uses an index to locate data quickly.

Example:

• A text editor reads a document sequentially.
• A database allows random access to retrieve specific records.

---

2. Directory Structure

A directory organizes files and provides navigation.

2.1 Types of Directory Structures

1. Single-Level Directory
   • All files are stored in a single directory.
   • Simple but inefficient for large systems.
2. Two-Level Directory
   • Each user has a separate directory.
   • Provides better organization.
3. Hierarchical Directory
   • Tree structure with subdirectories.
   • Used in modern operating systems (Windows, Linux).
4. Acyclic Graph Directory
   • Allows shared files using links.
   • Prevents circular references.

Example:

• In Windows, C:\Users\Documents\file.txt> follows a hierarchical structure.

---

3. File Allocation Methods

Determines how files are stored on disk.

3.1 Contiguous Allocation

• Files occupy consecutive disk blocks.
• Pros: Fast access.
• Cons: External fragmentation.

3.2 Linked Allocation

• Each file block contains a pointer to the next.
• Pros: No fragmentation.
• Cons: Slow access.

3.3 Indexed Allocation

• Uses an index block to store pointers to file blocks.
• Pros: Fast direct access.
• Cons: Extra space needed for index.

Example:

• Contiguous: Movie file stored in a single block range.
• Linked: Text document stored with scattered blocks linked together.
• Indexed: File table stores addresses of different parts of a large document.

---

4. File System Mounting

• Process of making a file system accessible to the OS.
• Root directory is mounted first.
• Example: USB drive mounting in Windows.

---

5. File Protection

• Ensures security and integrity of files.

5.1 Protection Mechanisms

• Access Control Lists (ACLs): Defines permissions for users.
• User Authentication: Ensures only authorized access.
• Encryption: Secures data by encoding.
• Backup and Recovery: Prevents data loss.

Example:

• Linux uses permissions (chmod 755 file.txt>) to control access.

---

Questions

1. What are the different types of file access methods?
2. Compare hierarchical and acyclic directory structures.
3. How does indexed file allocation work?
4. Explain the significance of file mounting.
5. What mechanisms help protect files in an OS?

---

Storage & I/O Management

1. Disk Structure

• Disk: A storage device divided into tracks, sectors, and cylinders.
• Sectors: Smallest storage units.
• Tracks: Circular paths on a disk where data is stored.
• Cylinders: Set of tracks aligned vertically across platters.

2. Disk Scheduling Algorithms

(a) FCFS (First-Come, First-Served)

• Requests are served in the order they arrive.
• Example:
  • Request queue: 98, 183, 37, 122, 14, 124, 65, 67
  • Head starts at 53 → Total head movement = 640 cylinders.

(b) SSTF (Shortest Seek Time First)

• Selects request with the shortest seek time from the current head position.
• Example:
  • Queue: 98, 183, 37, 122, 14, 124, 65, 67 (Head at 53)
  • Shortest seek time first → 65, 67, 37, 14, 98, 122, 124, 183

(c) SCAN (Elevator Algorithm)

• Moves the head in one direction servicing requests, then reverses.
• Example:
  • Head moves from 53 to the highest request before reversing.

(d) C-SCAN (Circular SCAN)

• Similar to SCAN but jumps back to the beginning after reaching the end.

(e) LOOK & C-LOOK

• LOOK: Similar to SCAN but stops at the last request before reversing.
• C-LOOK: Similar to C-SCAN but jumps back after servicing the last request.

3. RAID Levels and Disk Management

• RAID (Redundant Array of Independent Disks) enhances performance and reliability.
  • RAID 0: Striping (No redundancy, high speed).
  • RAID 1: Mirroring (Data duplication for fault tolerance).
  • RAID 5: Striping with parity (Balanced speed and redundancy).
  • RAID 10: Combination of RAID 1 and RAID 0.

4. I/O System

(a) Device Drivers

• Software that allows the OS to communicate with hardware devices.

(b) I/O Buffering

• Temporary storage of data for smooth input/output operations.
• Example: Keyboard buffering to prevent data loss.

(c) Direct Memory Access (DMA)

• Allows devices to transfer data to memory without CPU involvement.
• Example: Disk-to-memory data transfer without CPU overload.

---

Security & Protection

1. OS Security Threats

(a) Malware

• Malicious software including viruses, worms, and Trojans.

(b) Viruses

• Self-replicating programs that attach to files.
• Example: File infector virus.

(c) Worms

• Self-replicating but do not require a host file.
• Example: Internet worm spreading via networks.

(d) Trojans

• Disguised as legitimate software but contain malicious code.
• Example: Fake antivirus programs.

2. Authentication & Authorization Techniques

• Authentication: Verifies identity (e.g., passwords, biometrics).
• Authorization: Grants permissions based on identity.
• Example: Multi-factor authentication (MFA) using password + OTP.

3. Access Control Mechanisms

(a) ACLs (Access Control Lists)

• Define user permissions for files and directories.
• Example:
  • File X: Read (User A), Write (User B)

(b) Capability Lists

• Assigns specific rights to objects.
• Example: User A has “Read” access to File X, User B has “Write” access.

4. Security Policies and Firewalls

• Security Policy: Rules defining secure access to a system.
• Firewall: Blocks unauthorized access to a network.
• Example: Network firewall blocking incoming attacks.

---

Case Studies

1. Windows OS Architecture

• Layers:
  • User Mode (Applications, Environment Subsystems)
  • Kernel Mode (Executive, Microkernel, HAL)
• Features: GUI-based, NTFS file system, multitasking.

2. Linux OS Architecture

• Layers:
  • User Space (Shell, Applications)
  • Kernel Space (Process Management, File System, Drivers)
• Features: Open-source, monolithic kernel, multi-user support.

3. Android OS Overview

• Based on Linux Kernel with additional libraries for mobile devices.
• Architecture:
  • Applications Layer (Apps)
  • Application Framework (Activity Manager, Window Manager)
  • Native Libraries (SQLite, WebKit)
  • Android Runtime (ART, Java Libraries)
  • Linux Kernel (Drivers, Memory Management)
• Features: Touchscreen UI, app-based ecosystem, security sandboxing.

---

Sample Questions

Storage & I/O Management

1. Explain the difference between FCFS and SSTF disk scheduling algorithms with examples.
2. What is RAID 5, and how does it improve fault tolerance?
3. How does Direct Memory Access (DMA) improve system performance?

Security & Protection

1. Differentiate between authentication and authorization.
2. What is a Trojan, and how does it differ from a worm?
3. Explain the role of a firewall in system security.

Case Studies

1. Describe the architecture of the Windows operating system.
2. How does the Linux kernel manage processes and memory?
3. What are the key differences between Android and traditional Linux distributions?

---