Lesson Note: Structural Design Aspects of an Operating System

1. Process Model
A process is a program in execution. It consists of the program code, current activity,
processor registers, and variables. Process states include New, Ready, Running, Waiting,
and Terminated. The Process Control Block (PCB) contains essential information such as
process ID, state, priority, and memory limits.

2. Inter-Process Communication (IPC)

IPC enables processes to communicate and synchronize. Methods include message passing
(direct and indirect) and shared memory. Shared memory requires synchronization to
avoid race conditions.

3. Synchronization Mechanisms
These ensure orderly process execution. Mechanisms include critical section solutions like
Peterson’s Algorithm, hardware instructions like test-and-set, and higher-level abstractions
like semaphores and monitors.

4. Resource Management
Focuses on allocating CPU, memory, and I/O devices fairly and efficiently. Tools include
resource allocation graphs and various allocation policies. Accounting mechanisms track
resource use.

5. Scheduling
Scheduling determines which process runs next. Algorithms include First-Come-First-Serve,
Shortest Job First, Round Robin, and Multilevel Queue. Criteria include throughput, CPU
utilization, turnaround time, waiting time, and response time.

6. Protection Issues
Protection mechanisms prevent unauthorized access. Methods include Access Control Lists,
capability-based security, user authentication, and sandboxing. Policies include
discretionary, mandatory, and role-based access control.

7. Implementation Issues in Modern Operating Systems

Modern OS design includes monolithic and microkernel architectures. Modular kernels
support loadable modules. Key concerns include portability and performance optimization.

8. Distributed Operating Systems

These manage multiple computers as a single system. Features include transparency,
resource sharing, and fault tolerance. Examples include Amoeba, Sprite, and Plan 9.
9. Deadlock Detection, Recovery, and Avoidance
Deadlock requires mutual exclusion, hold and wait, no preemption, and circular wait.
Detection uses resource allocation graphs. Recovery involves terminating processes or
preempting resources. Avoidance strategies include the Banker’s Algorithm.

10. Case Studies

Unix/Linux uses a monolithic kernel. Windows NT uses a hybrid kernel. Android is based on
Linux with added middleware. Mac OS has a hybrid kernel combining Mach and BSD.

11. Project Ideas

Simulate scheduling algorithms, create a shell, detect and resolve deadlocks, build a
distributed file system prototype, or implement a semaphore library.

COS801: Operating Systems (3 Credit Units)

Detailed Lesson Note

1. Structural Design Aspects of an Operating System

a. Process Model

A process is a program in execution. It includes the program code, current activity (program
counter, registers), and a set of resources assigned to it (open files, memory, etc.).

Process Control Block (PCB): The OS maintains a PCB for each process, storing information
such as:

Process State (new, ready, running, waiting, terminated)

Program Counter (location of the next instruction)

CPU Registers

Memory management info (segment or page tables)

Accounting info (CPU usage, time limits)

I/O status info

Process States:

New: The process is being created.

Ready: Waiting to be assigned to the CPU.

Running: Instructions are being executed.

Waiting: Waiting for an event (e.g., I/O completion).

Terminated: Finished execution.

Context Switching: The act of saving the state of one process and loading another. This
allows multitasking and CPU sharing among processes.

Types of Processes:

User vs. System Processes: User processes are initiated by users; system processes are by
the OS.

Foreground vs. Background: Foreground processes interact with the user; background
processes run silently.
I/O-bound vs. CPU-bound: Based on whether the process spends more time on I/O or
computation.

b. Inter-Process Communication (IPC)

IPC enables processes to exchange data and synchronize their actions.

Shared Memory: Processes communicate by reading/writing to a shared memory area.

Requires synchronization tools to manage access.

Message Passing:

Direct Communication: Processes must name each other explicitly.

Indirect Communication: Via mailboxes or ports.

Blocking vs. Non-blocking: Sender/receiver may wait for each other.

Synchronization Tools:

Semaphores: Variables to signal and wait between processes.

Pipes: Unidirectional data streams.

Message Queues and Sockets: For more complex communication.

c. Synchronization Mechanisms

Concurrency may cause race conditions. Synchronization ensures orderly execution.

Critical Section Problem: Part of the program where shared resources are accessed. Only
one process should execute this at a time.

Solutions:

Semaphores: Binary (mutex) and counting semaphores.

Monitors: High-level synchronization primitive.

Mutex Locks: Used for mutual exclusion.

Barriers: Processes must all reach a point before any proceeds.

Spinlocks: Busy-wait locks used in multiprocessors.

Classical Problems:

Producer-Consumer: Shared buffer management.

Readers-Writers: Ensuring data integrity between readers and writers.

Dining Philosophers: Models resource sharing and deadlocks.

d. Resource Management

The OS manages all hardware and software resources.

Memory Management:

Paging: Divides memory into fixed-size pages and frames.

Segmentation: Divides programs logically (e.g., code, data).

Virtual Memory: Uses disk space to extend RAM.

File Management:

File Allocation: Contiguous, linked, and indexed methods.

Directory Structures: Single-level, two-level, tree, DAG.

File Permissions: Read, write, execute for users/groups.

I/O Management:

Buffering: Storing data temporarily to match device speeds.

Caching: Storing frequent data in faster storage.

Spooling: Staging output (e.g., printing).

CPU Management:
Allocation through scheduling algorithms.

Managing process priorities.

e. Scheduling

Determines which process runs next.

CPU Scheduling Algorithms:

First-Come First-Served (FCFS): Runs processes in arrival order.

Shortest Job Next (SJN): Runs shortest job first.

Priority Scheduling: Based on process priority.

Round Robin (RR): Time-sharing using a fixed time quantum.

Multilevel Queue: Different queues for different priority levels.

Multiprocessor Scheduling:

Load Balancing: Distribute load evenly.

Processor Affinity: Bind process to a specific CPU.

Real-Time Scheduling:
Rate-Monotonic: Static priorities based on request rate.

Earliest Deadline First (EDF): Dynamic priorities.

2. Protection Issues

Ensures that only authorized processes access system resources.

Access Control Lists (ACLs): List of permissions associated with each object.

Capabilities: Tokens associated with users granting access.

Authentication:

Passwords

Biometrics

Smart Cards

Encryption:

Symmetric: Same key for encryption/decryption.

Asymmetric: Public/private key pair.

Security Models:

Bell-LaPadula: Enforces confidentiality.

Biba: Enforces data integrity.

3. Implementation Issues of Modern Operating Systems

Portability: Ability to run on different hardware with minimal changes.

Modularity:

Monolithic Kernel: All OS services run in one large block.

Microkernel: Minimal kernel with most services in user space.

Performance Optimization:

Memory optimization (e.g., page replacement).

Disk I/O optimization (e.g., disk scheduling).

Fast system calls and interrupt handling.

Bootstrapping:

The process of loading the OS into memory.

Begins with BIOS, followed by boot loader.

Debugging and Monitoring:

Tracers, loggers, profilers, and analyzers for performance and error checking.

4. Distributed Operating Systems

Definition: OS that manages a group of distinct computers and presents them as a unified
system.

Transparency Types:

Access: Uniform access to resources.

Location: Resource location hidden.

Concurrency: Concurrent access handled.

Replication: Multiple copies managed.

Fault: Fault-tolerance mechanisms.

Resource Sharing: Across networked systems.

Scalability: Capable of expanding without performance loss.

Examples:

Amoeba, Plan 9, Kubernetes (container orchestration)

5. Deadlock Detection, Recovery, and Avoidance

a. Deadlock Conditions (Coffman)

Mutual Exclusion: Only one process accesses a resource at a time.

Hold and Wait: Process holds resources while waiting for others.

No Preemption: Resources cannot be forcibly taken.

Circular Wait: A circular chain of processes waiting on each other.

b. Detection

Resource Allocation Graph (RAG): Tracks resources and allocations.

Banker’s Algorithm: Detects unsafe states.

c. Recovery

Process Termination: Kill one or more processes.

Resource Preemption: Reallocate resources.

d. Avoidance

Safe State: System can allocate resources to all processes without deadlock.
Banker’s Algorithm: Checks for safe state before allocating resources.

6. Case Studies

a. UNIX/Linux

Monolithic kernel, command-line interface (shell), multi-user, multitasking.

Supports IPC, file systems, virtual memory.

b. Windows

Hybrid kernel, graphical user interface.

Uses threads, advanced scheduling, security features (e.g., UAC).

c. Android

Linux-based, designed for mobile devices.

Uses Dalvik/ART for application execution.

Handles permissions, touch input, and power management.

d. macOS

Unix-based, uses the XNU kernel.

Strong integration with Apple hardware and software.

e. File Systems

FAT32: Simple, widely used, no security.

NTFS: Windows, journaling, access control.

ext4: Linux, supports journaling, large volumes.

7. Projects

a. Process Scheduling Simulator

Build software that simulates FCFS, SJF, RR, etc.

Visualize process timelines using Gantt charts.

b. Deadlock Detector Tool

Accept input as resource graph.

Apply algorithms to detect and resolve deadlocks.

c. File System Simulator

Create a program simulating different allocation strategies.

Include user access controls and directory structure.

d. Mini Operating System Shell

Implement command parsing, execution, and I/O redirection.

Support piping, background processes.

e. Distributed File Sharing System

Simulate file sharing over a network using sockets.

Implement upload/download, peer discovery, and security.

This concludes the detailed lesson note for COS801: Operating Systems.