Concepts of OS

Functions
Operating System Structure
System components
Operating system services
System programs and system calls
System structure
Types of operating system

Unit I
### INTRODUCTION: Basic Concepts of Operating System

An Operating System (OS) is a system software that acts as an

intermediary between the computer hardware and the computer user. Its
primary goal is to provide an environment in which a user can execute
programs in a convenient, efficient, and manageable manner.

Abstract View: From a user's perspective, it is a convenience,

providing a simpler machine to work with. From a system perspective, it
is a resource manager, allocating hardware resources among competing
application programs.

---
### 1. Functions of an Operating System

The OS performs several key functions:

1. Resource Management: The OS manages all hardware resources,

including the CPU, memory, disk drives, and I/O devices. It decides:
CPU Scheduling: Which process gets the CPU, when, and for how
long.
Memory Management: Which programs and data to keep in main
memory to ensure efficient execution.
File System Management: How to create, store, retrieve, and
organize files on storage devices.
I/O Device Management: How to control and interact with
peripheral devices like keyboards, printers, and network cards.

2. Process Management: A process is a program in execution. The OS

is responsible for:
Creating and deleting both user and system processes.
Suspending and resuming processes.
Providing mechanisms for process synchronization and
communication.
Handling deadlock (a situation where two or more processes are
waiting indefinitely for an event that can only be caused by one of the
waiting processes).

3. Providing a User Interface (UI): The OS provides interfaces for user

interaction.
Command-Line Interface (CLI): Uses text commands (e.g., Linux
Bash, Windows Command Prompt).
Graphical User Interface (GUI): Uses windows, icons, menus, and
a pointer (e.g., Windows, macOS, Ubuntu Desktop).
4. Protection and Security:
Protection: Ensuring that all access to system resources is
controlled. It prevents processes from interfering with each other and the
OS.
Security: Defending the system from external and internal
attacks through user authentication, firewalls, and access control lists.

---

### 2. Operating System Structure

#### A. System Components

An operating system is comprised of several key components that work

together:

1. Process Management Component: Handles process creation,

scheduling, termination, and inter-process communication.
2. Main Memory Management Component: Keeps track of which parts
of memory are in use and by whom. Allocates and deallocates memory
space as needed.
3. File Management Component: Manages files and directories.
Provides file creation, deletion, manipulation, and backup.
4. I/O System Management Component: Includes a buffer-caching
system, a general device-driver interface, and drivers for specific
hardware devices.
5. Secondary-Storage Management: Manages disk storage, handling
free space, storage allocation, and disk scheduling.
6. Networking (Distributed Systems): Provides access to shared
resources and files over a network.
7. Protection System: Controls access to programs, processes, and
user resources.
8. Command Interpreter System: The program that reads and
interprets user commands (the shell in UNIX/Linux).
#### B. Operating System Services

From the user's viewpoint, the OS provides several services for the
convenience of the programmer:
User Interface: (As described above)
Program Execution: The system must be able to load a program into
memory and run it.
I/O Operations: A running program may require I/O, which may
involve a file or an I/O device. The OS provides a uniform interface to
access these.
File-System Manipulation: Programs need to read, write, create, and
delete files.
Communications: Processes may need to exchange information with
other processes on the same computer or over a network. This is done via
shared memory or message passing .
Error Detection: The OS needs to be constantly aware of possible
errors in the CPU, memory hardware, I/O devices, or in user programs. It
must take appropriate action to ensure correct and consistent computing.

#### C. System Programs and System Calls

System Programs: These are application programs that are bundled

with the OS, providing a convenient environment for program
development and execution. They are not part of the OS kernel but use
system calls to interact with it. Examples include:
File management (e.g., `cp`, `mv`, `ls` in Linux).
Status information (e.g., `top`, `tasklist`).
File modification (text editors like `vim` or `notepad`).
Programming language support (compilers, debuggers).
Program loading and execution.
 System Calls: These are the programmatic interface between a
running application (user program) and the operating system kernel. They
provide a way for a program to request a service from the OS.
How they work: When a user program needs a service (e.g.,
reading a file), it executes a trap or software interrupt instruction.
This switches the CPU from user mode to kernel mode, and control is
transferred to the OS. The OS performs the requested service in kernel
mode and then returns control to the user program.
Categories of System Calls:
Process Control: `end`, `abort`, `load`, `execute`,
`create_process`.
File Management: `create_file`, `delete_file`, `open`,
`close`, `read`, `write`.
Device Management: `request_device`, `release_device`,
`read`, `write`.
Information Maintenance: `get_time`, `set_time`,
`get_system_data`.
Communications: `send_message`, `receive_message`.

#### D. System Structure

There are various ways to structure an OS:

1. Simple/Monolithic Structure: Found in early OSs like MS-DOS. The

entire OS is a single, static binary file containing all components. There is
no separation between kernel modules. It is efficient but difficult to
debug, modify, and maintain. A single bug can crash the entire system.
2. Layered Approach: The OS is broken into a number of layers
(levels). Each layer is built only on the layers beneath it. This simplifies
debugging and verification. The THE operating system is a classic
example.
3. Microkernels: This philosophy moves as much functionality as
possible from the kernel into "user space" as separate servers. The kernel
itself (the microkernel) provides only minimal services, such as process
management, memory management, and inter-process communication
(IPC). All other services (file system, networking) are implemented as
user-level servers that communicate via IPC. Benefits include easier
extensibility and security. Examples include Mach and QNX.
4. Modules/Monolithic with Modules: Most modern OSs like Linux and
Solaris use this. The kernel has a set of core components and can
dynamically load additional modules (e.g., device drivers, file systems) at
runtime. This combines the performance of a monolithic kernel with the
flexibility of a microkernel.

---

### 3. Types of Operating Systems

OSs have evolved significantly. Major types include:

1. Batch Operating Systems: The earliest systems. Users submitted

jobs (punched cards) to a computer operator, who batched similar jobs
together and ran them sequentially. No user interaction. Goal was to
maximize CPU utilization.
2. Multiprogramming Systems: Designed to improve CPU utilization.
Several jobs are kept in memory simultaneously. When one job waits for
I/O, the OS switches the CPU to another job. This keeps the CPU busy.
Note: This is not the same as multitasking; it does not provide user
interaction.
3. Multitasking (Time-Sharing) Systems: An extension of
multiprogramming with a focus on user interaction . The CPU executes
multiple jobs by switching among them so frequently (in time slices) that
the user can interact with each program while it is running. The response
time is crucial. This is the basis of all modern desktop and server OSs.
4. Real-Time Systems: Used when rigid time requirements are placed
on the operation of a processor. They are used to control scientific
experiments, medical imaging systems, and industrial control systems.
Hard Real-Time: Secondary storage is limited or absent. Critical
tasks must be guaranteed to be completed on time (e.g., flight control
systems).
Soft Real-Time: Less restrictive. Critical tasks have priority but no
absolute guarantee (e.g., multimedia systems).
5. Distributed Systems: A collection of physically separate, possibly
heterogeneous, computer systems that are networked to provide users
with access to the various resources. They enhance data sharing,
reliability, and computation speed.
6. Network Operating Systems: An OS that provides features like file
sharing and printer sharing over a network (e.g., Windows Server, Novell
NetWare).

---

### 4. Case Study: Pitfalls of Multitasking

While multitasking is a cornerstone of modern computing, it introduces

significant complexity and potential problems, as thoroughly discussed in
Silberschatz.

Core Problem: The OS must allow multiple processes to execute

concurrently, but it must also ensure that they do not interfere with each
other incorrectly. This leads to several critical pitfalls:

1. Race Conditions:
What it is: A situation where the outcome of execution depends
on the particular order in which multiple processes access and manipulate
shared data.
Example: Two processes, P1 and P2, share a variable `counter`.
Both execute `counter++`. This seems simple, but at the machine level,
`counter++` is not atomic; it involves:
1. `LOAD counter, REGISTER`
2. `INCREMENT REGISTER`
3. `STORE REGISTER, counter`
If the OS switches from P1 to P2 after P1 has loaded the value but
before it stores the new value, P2 will overwrite P1's increment. The final
value of `counter` may be one less than the correct value.
2. Critical-Section Problem:
This is the fundamental problem that race conditions expose. A
critical section is a segment of code in a process where the process may
be changing common variables, updating a table, writing a file, etc.
The Problem: How to design protocols so that when one process
is executing in its critical section, no other process is allowed to execute
in its critical section? This requires mutual exclusion .

3. Deadlocks:
What it is: A set of blocked processes, each holding a resource
and waiting to acquire another resource held by another process in the
set.
The Four Necessary Conditions (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.
3. No Preemption: Resources cannot be forcibly taken away from
a process; they must be released voluntarily.
4. Circular Wait: A set of waiting processes {P0, P1, ..., Pn}
must exist 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.
Example: Process A holds the printer and requests the scanner.
Process B holds the scanner and requests the printer. Both are stuck
forever.

4. Starvation (Indefinite Postponement):

What it is: A situation where a process is denied access to a
resource indefinitely, even though it is not deadlocked. This can happen
due to poor process scheduling algorithms.
Example: In a priority-based scheduler, if low-priority processes
are constantly preempted by new, high-priority processes, the low-priority
processes may never get to run.

5. Overhead and Performance Degradation:

 The act of switching between processes (context switching) is not
free. It requires saving the state of the current process and loading the
state of the new process.
Excessive multitasking can lead to thrashing , a state where the
system spends more time switching between processes (and swapping
pages of memory) than doing useful work.

Conclusion of the Case Study: The power of multitasking comes at the

cost of immense complexity. The OS must provide sophisticated
mechanisms (synchronization tools like semaphores and mutexes,
deadlock avoidance algorithms, and fair schedulers) to manage these
pitfalls and ensure correct, efficient, and fair operation.
Unit 2
### PART 1: PROCESSES

#### 1. Definition of a Process

A process is a fundamental concept in operating systems. It can be

defined as:
A program in execution.
An instance of a computer program that is being executed by one or
more threads.
The unit of work in a modern time-sharing system.

A process is more than just the program code (which is known as the
text section ). It also includes:
The current activity (represented by the value of the Program Counter
and the contents of the processor's registers).
The process stack containing temporary data (like function
parameters, return addresses, and local variables).
The data section containing global variables.
A heap , which is memory dynamically allocated during process run
time.

#### 2. Process State

As a process executes, it changes state. The state of a process is defined

in part by the current activity of that process. Each process may be in one
of the following states:

1. New: The process is being created.

2. Running: Instructions are being executed.
3. Waiting (or Blocked): The process is waiting for some event to
occur (such as an I/O completion or a signal from another process).
4. Ready: The process is waiting to be assigned to a processor.
5. Terminated: The process has finished execution.

These states form a cycle, often depicted as:

New → Ready ↔ Running → Waiting → Ready → ... → Terminated

#### 3. Process Control Block (PCB)

The operating system represents each process using a data structure

called a Process Control Block (PCB) . It is the "repository" for all the
data needed to manage a process. A PCB typically contains:

Process State: The current state of the process (new, ready,

running, waiting, etc.).
Process ID (PID): A unique identifier for the process.
Program Counter: The address of the next instruction to be
executed for this process.
CPU Registers: The contents of all process-centric registers
(accumulators, index registers, stack pointers, etc.) must be saved when
an interrupt occurs, so the process can be restarted correctly later.
CPU-Scheduling Information: Process priority, pointers to scheduling
queues, and other scheduling parameters.
Memory-Management Information: The value of the base and limit
registers, page tables, or segment tables (depending on the memory
system used).
Accounting Information: The amount of CPU and real time used,
time limits, account numbers, job or process numbers.
I/O Status Information: The list of I/O devices allocated to the
process, a list of open files, etc.
The PCB is the physical manifestation of a process in the OS. When a
process is context-switched, the state of the current process is saved into
its PCB, and the state of the new process is loaded from its PCB.

#### 4. Process Scheduling

The objective of multiprogramming is to have some process running at all

times to maximize CPU utilization. The objective of time-sharing is to
switch the CPU among processes so frequently that users can interact
with each program while it is running. Process scheduling is the activity of
the process manager that handles the removal of the running process
from the CPU and the selection of another process.

Scheduling Queues:
Job Queue: The set of all processes in the system.
Ready Queue: The set of all processes residing in main memory that
are ready and waiting to execute. This is typically stored as a linked list.
Device Queues: The set of processes waiting for a particular I/O
device.

Schedulers:
Long-Term Scheduler (Job Scheduler): Selects processes from the
mass-storage pool (disk) and loads them into memory for execution. It
controls the degree of multiprogramming (the number of processes in
memory). It is slow and is used less frequently in time-sharing systems.
Short-Term Scheduler (CPU Scheduler): Selects from among the
processes that are ready to execute and allocates the CPU to one of them.
It must be very fast as it is invoked frequently (every 100ms or so).

Context Switch: The mechanism of switching the CPU from one process
to another. It involves saving the state of the old process and loading the
saved state for the new process. This is pure overhead; the system does
no useful work while switching.
#### 5. Interprocess Communication (IPC)

Processes executing concurrently in the operating system may be either:

Independent Processes: Cannot affect or be affected by other
processes.
Cooperating Processes: Can affect or be affected by other processes.

Reasons for process cooperation:

Information Sharing: Several users may be interested in the same
piece of information.
Computation Speedup: Break a task into subtasks that can run in
parallel.
Modularity: Construct the system in a modular fashion.
Convenience: A single user may be performing many tasks
simultaneously.

Cooperating processes require an Interprocess Communication (IPC)

mechanism. There are two fundamental models:

1. Shared Memory:
A region of memory is shared by cooperating processes.
Processes can then exchange information by reading and writing
data to this shared region.
Pros: Can be very fast; communication is at memory speed.
Cons: Requires careful synchronization to avoid race conditions
(e.g., using semaphores).
Example: Producer-Consumer problem using a shared buffer.

2. Message Passing:
Communication takes place by means of messages exchanged
between cooperating processes.
Primitive operations: `send(message)` and `receive(message)`.
 Pros: Easier to implement and less prone to synchronization
errors for small amounts of data.
Cons: Typically slower than shared memory due to kernel
intervention.
Example: Chat applications between different machines.

---

### PART 2: CPU SCHEDULING

#### 1. Scheduling Criteria

The CPU scheduler selects a process from the ready queue. The choice is
made by a scheduling algorithm which may be based on one or more of
the following criteria:

CPU Utilization: Keep the CPU as busy as possible. (Maximize)

Throughput: Number of processes completed per unit time.
(Maximize)
Turnaround Time: The interval from the time of submission of a
process to the time of completion. (Minimize)
Waiting Time: The total amount of time a process has been waiting
in the ready queue. (Minimize)
Response Time: The time from the submission of a request until the
first response is produced (important in time-sharing systems).
(Minimize)

#### 2. Scheduling Algorithms

First-Come, First-Served (FCFS):

The process that requests the CPU first is allocated the CPU first.
Managed with a FIFO queue.
 Convoy Effect: Short processes wait for one long process to
finish.

Shortest-Job-First (SJF):
Associates with each process the length of its next CPU burst. The
CPU is assigned to the process with the smallest next CPU burst.
Optimal for minimizing average waiting time, but impossible to
implement as the next CPU burst length is unknown.
Preemptive SJF is called Shortest-Remaining-Time-First (SRTF)
.

Priority Scheduling:
A priority (integer) is associated with each process. The CPU is
allocated to the process with the highest priority.
Problem: Starvation – low-priority processes may never execute.
Solution: Aging – gradually increase the priority of processes that
wait in the system for a long time.

Round-Robin (RR):
Designed for time-sharing systems. Similar to FCFS, but preemption
is added to switch between processes.
Each process gets a small unit of CPU time ( time quantum or
time slice ), typically 10-100 milliseconds. After this time has elapsed,
the process is preempted and added to the tail of the ready queue.
Performance depends heavily on the size of the time quantum.

Multilevel Queue Scheduling:

The ready queue is partitioned into several separate queues (e.g.,
system processes , interactive processes , batch processes ).
Each queue has its own scheduling algorithm. There must be
scheduling between the queues, commonly fixed-priority preemptive
scheduling .
 Multilevel Feedback Queue Scheduling:
Allows a process to move between queues. This is the most general
and complex scheme.
It is defined by parameters: number of queues, scheduling
algorithm for each queue, method used to determine when to
upgrade/demote a process, etc.

---

### PART 3: THREADS

#### 1. Overview: Why Threads?

A thread is a basic unit of CPU utilization; it comprises a thread ID ,

a program counter , a register set , and a stack . It shares with
other threads belonging to the same process its code section, data
section, and other operating-system resources, such as open files and
signals.

Motivation:
A single application may be required to perform several similar tasks
(e.g., a web server handling multiple clients).
Creating a new process is heavyweight (resource-intensive). Creating a
new thread within an existing process is much lighter and faster.
Threads within a process can share data and resources easily, unlike
processes which require complex IPC.
Responsiveness: If one thread is blocked, another in the same
application can run (e.g., a user interface thread remains active while a
background thread performs a long calculation).
Resource Sharing: By default, threads share the memory and
resources of the process to which they belong.
Economy: Creating and context-switching threads is much faster
than doing so for processes.
 Scalability: Can utilize multiprocessor architectures more effectively;
threads can run in parallel on different CPUs.

#### 2. Multithreading Models

There is a relationship between user threads (threads managed by a

user-level library) and kernel threads (threads supported and managed
directly by the OS kernel).

Many-to-One Model:
Maps many user-level threads to one kernel thread.
Drawback: The entire process will block if one thread makes a
blocking system call. True parallelism is not achieved because only one
thread can access the kernel at a time.
Example: Older Green threads for Solaris.

One-to-One Model:
Maps each user thread to a kernel thread.
Advantage: Provides more concurrency; when one thread blocks,
another can run. Allows multiple threads to run in parallel on
multiprocessors.
Drawback: Creating a user thread requires creating a
corresponding kernel thread, which can be expensive and may limit the
number of threads.
Example: Windows, Linux.

Many-to-Many Model:
Multiplexes many user-level threads to a smaller or equal number of
kernel threads.
Advantage: Combines the best of both: developers can create as
many user threads as necessary, and the corresponding kernel threads
can run in parallel on a multiprocessor. The kernel can schedule another
thread if one blocks.
 Example: This was the goal of Solaris and other systems, though
its pure form is rare.

#### 3. Issues in Multithreading

The `fork()` and `exec()` System Calls:

Does `fork()` duplicate only the calling thread or all threads? Some
UNIX systems have two versions of `fork()` to handle both cases.
If a thread invokes `exec()`, the program specified in the
parameter will replace the entire process, including all its threads.

Signal Handling:
A signal is used in UNIX to notify a process that a particular event
has occurred. To which thread should a signal be delivered?
Options: Deliver the signal to the thread to which the signal applies,
deliver it to every thread, or deliver it to certain threads.

Thread Cancellation:
Terminating a thread before it has completed.
Asynchronous Cancellation: One thread immediately terminates
the target thread. This can be problematic if the target thread is in the
middle of updating shared data.
Deferred Cancellation: The target thread periodically checks if it
should terminate, allowing it to terminate itself in a safe manner. This is
the preferred approach.

Thread-Local Storage (TLS):

Allows each thread to have its own copy of data. Useful when you
don't have control over the thread creation process (e.g., in a thread
pool).

Scheduler Activations:
 A communication scheme between the user-thread library and the
kernel to maintain the correct number of kernel threads allocated to the
application, especially when a thread blocks on a page fault. This is a
complex issue for the Many-to-Many model.

Unit 3

Of course. Here are detailed notes on Process Synchronization and

Deadlocks based on the 9th Edition of *Operating System Concepts* by
Silberschatz, Galvin, and Gagne.

---

### **PART 1: PROCESS SYNCHRONIZATION**

#### **1. The Critical-Section Problem**

In a cooperative multiprocessing environment, several processes may

need to access and modify shared data concurrently. The unexpected
outcome of such access, where the final value of the shared data depends
on the order of execution of the processes, is known as a **race
condition**.

* **Critical Section:** A segment of code in a process where the

process may be changing common variables, updating a table, writing a
file, etc.
* **The Critical-Section Problem:** To design a protocol that the
processes can use to cooperate. When one process is executing in its
critical section, no other process is to be allowed to execute in its critical
section.
**A Solution to the Critical-Section Problem must satisfy three
conditions:**

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 executing in its critical section and
some processes wish to enter their critical sections, then only those
processes that are not executing in their remainder sections can
participate in the decision on which will enter its critical section next, and
this selection cannot be postponed indefinitely.
3. **Bounded Waiting:** There exists a bound, or limit, on the number
of times that 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.

#### **2. Synchronization Hardware**

Early solutions relied on hardware support, as direct software solutions

(like Peterson's Algorithm) are complex and don't guarantee correctness
on modern architectures.

* **Memory Barriers:** Ensure load and store instructions are executed

in order.
* **Hardware Instructions:** Special atomic (non-interruptible)
hardware instructions like `test_and_set()` and `compare_and_swap()`.
* **How they work:** These instructions are executed atomically at the
hardware level, allowing the implementation of locks without the need for
more complex software protocols.

#### **3. Mutex Locks**

The simplest synchronization tool to protect a critical section.

* **Concept:** A **mutex** (short for **mutual exclusion**) lock is a

variable that can be in one of two states: **locked** or **unlocked**.
* **Operations:**
* `acquire()`: A process calls this before entering its critical section.
If the lock is available, it acquires it and proceeds. If it's unavailable, the
process is blocked until the lock is released.
* `release()`: A process calls this after exiting its critical section,
making the lock available again.
* **Disadvantage:** Requires **busy waiting** in its simplest
implementation (a **spinlock**), which wastes CPU cycles. This is
acceptable only when locks are expected to be held for very short times.

#### **4. Semaphores**

A more robust synchronization tool that can be used for a wider range of
problems. A **semaphore** `S` is an integer variable that, apart from
initialization, is accessed only through two standard *atomic* operations:

* `wait(S)` (or `P(S)`):

```c
wait(S) {
while (S <= 0)
; // busy wait (for a spinlock semaphore)
S--;
}
```
* `signal(S)` (or `V(S)`):
```c
signal(S) {
S++;
}
```

**Types of Semaphores:**
* **Counting Semaphore:** Its integer value can range over an
unrestricted domain. Used to control access to a resource with a finite
number of instances.
* **Binary Semaphore:** Its integer value can range only between 0
and 1. It is similar to a mutex lock.

To avoid busy waiting, semaphores are implemented with a **waiting

queue**. When a process executes `wait()` and finds the semaphore
value not positive, it blocks itself and is moved to the waiting queue.
When another process executes `signal()`, it removes one process from
the waiting queue and wakes it up (places it in the ready queue).

#### **5. Classic Problems of Synchronization**

These problems are used to test nearly every new synchronization

scheme.

1. **The Bounded-Buffer Problem (Producer-Consumer):**

* **Scenario:** One or more producers generate data and put it into
a fixed-size buffer. One or more consumers take data from the buffer.
* **Synchronization Needs:**
* Mutual exclusion for accessing the buffer.
* Ensure a producer doesn't add data if the buffer is full.
* Ensure a consumer doesn't remove data if the buffer is empty.
* **Solution:** Typically uses three semaphores: `mutex` (for
mutual exclusion, initialized to 1), `full` (counts full buffers, initialized to
0), and `empty` (counts empty buffers, initialized to buffer size).

2. **The Readers-Writers Problem:**

* **Scenario:** A database is shared among multiple processes.
Some processes only want to read the database (**readers**), while
others want to update it (**writers**).
* **Synchronization Needs:**
 * Multiple readers can read simultaneously.
* Only one writer can write at a time.
* If a writer is writing, no reader can read.
* **Variations:** The first and second readers-writers problems deal
with potential starvation of writers or readers. Solved using semaphores
like `rw_mutex` (for writers) and a counter for readers protected by
`mutex`.

3. **The Dining-Philosophers Problem:**

* **Scenario:** Five philosophers sit around a table, alternating
between thinking and eating. There is one chopstick between each
philosopher. A philosopher needs two chopsticks to eat.
* **Synchronization Needs:** Allocate several resources among
several processes in a deadlock-free and starvation-free manner.
* **The Problem:** A simple solution (pick up left then right
chopstick) can lead to a **deadlock** (if all philosophers pick up their left
chopstick simultaneously).
* **Solutions:**
* Allow at most four philosophers to sit at the table
simultaneously.
* A philosopher picks up chopsticks only if both are available (done
atomically).
* Use an asymmetric solution: odd-numbered philosophers pick up
left first, even-numbered pick up right first.

#### **6. Critical Regions & Monitors**

High-level language constructs to simplify synchronization.

* **Critical Region:** A language construct that guards access to a

shared variable. The programmer only declares the shared variable and
the critical regions that access it; the compiler ensures mutual exclusion.
```pascal
region shared_variable do
 statement;
```
* **Monitors:** A higher-level synchronization construct that
encapsulates the shared data and all the procedures that can operate on
it.
* **Key Feature:** Mutual exclusion is guaranteed by the monitor's
implementation. Only one process can be *active* inside the monitor at a
time.
* **Synchronization:** Processes can temporarily block themselves
inside the monitor by executing a `wait()` operation on a **condition
variable**. They can be resumed by another process executing a
`signal()` operation on the same condition variable.
* **Advantage:** Moves the burden of synchronization from the
programmer to the compiler, reducing errors.

---

### **PART 2: DEADLOCK**

A **deadlock** is a state in a set of processes where each process is

waiting for an event that can only be caused by another process in the
set. This results in all processes being permanently blocked.

#### **1. Methods for Handling Deadlocks**

There are three principal approaches:

1. **Deadlock Prevention:** Ensure that the system will **never**

enter a deadlocked state by designing protocols that violate one of the
necessary conditions for deadlock.
2. **Deadlock Avoidance:** The OS is given advance information about
which resources a process will request and use during its lifetime. The OS
then **dynamically checks** if granting a resource request could lead to
a deadlock, and only grants it if it is safe.
3. **Deadlock Detection and Recovery:** The OS allows deadlocks to
occur. It then periodically **detects** them and takes action to
**recover**.

(The fourth approach, used by many operating systems, is to **ignore

the problem altogether** and pretend deadlocks never occur (the Ostrich
Algorithm). This is reasonable if deadlocks are very rare and the cost of
prevention is high.)

#### **2. Deadlock Prevention**

We can prevent deadlocks by ensuring that at least one of the four

necessary conditions for deadlock cannot hold.

* **Mutual Exclusion:** Cannot be denied for non-sharable resources

(e.g., a printer). For sharable resources (e.g., read-only files), deadlock
cannot occur.
* **Hold and Wait:** Guarantee that whenever a process requests a
resource, it does not hold any other resources.
* **Protocol 1:** A process must request and be allocated all its
resources before it begins execution.
* **Protocol 2:** A process can request resources only when it has
none. It must release all its resources before making a new request.
* **No Preemption:**
* **Protocol:** If a process that is holding some resources requests
another resource that cannot be immediately allocated to it, then all
resources currently being held are preempted (released). The process will
be restarted only when it can regain its old resources, as well as the new
ones it is requesting.
* **Circular Wait:** Impose a total ordering of all resource types and
require that each process requests resources in an increasing order of
enumeration.

#### **3. Deadlock Avoidance**

This approach requires that the OS has additional *a priori* information.

* **Safe State:** A state is **safe** if the system can allocate

resources to each process (up to its maximum) in some order and still
avoid a deadlock. More formally, a sequence of processes <P1, P2, ...,
Pn> is a **safe sequence** if for each Pi, the resources that Pi can still
request can be satisfied by the currently available resources plus the
resources held by all Pj, where j < i.
* **Resource-Allocation Graph Algorithm:** Used for systems where
each resource type has only one instance. A claim edge (Pi -> Rj) is
added to the graph to show that Pi may request Rj. A request can be
granted only if converting the request edge to an assignment edge does
not form a cycle. Cycle detection is used.
* **Banker's Algorithm:** Used for systems where each resource type
can have multiple instances.
* **Data Structures:**
* **Available:** A vector of length `m` indicating the number of
available resources of each type.
* **Max:** An `n x m` matrix defining the maximum demand of
each process.
* **Allocation:** An `n x m` matrix defining the number of
resources of each type currently allocated to each process.
* **Need:** An `n x m` matrix indicating the remaining resource
need of each process (Need = Max - Allocation).
* **Safety Algorithm:** Determines whether the system is in a safe
state.
* **Resource-Request Algorithm:** Determines if a request can be
granted safely. It checks if the request is less than the process's Need and
the Available resources. If so, it pretends to allocate the resources and
runs the Safety Algorithm to see if the resulting state is safe.

#### **4. Deadlock Detection**

If a system does not employ deadlock prevention or avoidance, it must

provide a mechanism for detection.
* **For Single Instance of Each Resource Type:** A wait-for graph can
be used. This is derived from the resource-allocation graph by removing
the resource nodes and collapsing the appropriate edges. A cycle in the
wait-for graph implies a deadlock.
* **For Multiple Instances of Each Resource Type:** An algorithm
similar to the Banker's Safety Algorithm is used. It checks for a state
where the system is not deadlocked (i.e., can find a process that can
finish with the current available resources). If no such process exists, the
system is deadlocked.

#### **5. Recovery from Deadlock**

Once a deadlock is detected, the system must recover.

1. **Process Termination:**
* **Abort all deadlocked processes.** This is sure to break the
deadlock but is costly.
* **Abort one process at a time** until the deadlock cycle is
eliminated. This incurs significant overhead as the detection algorithm
must be rerun after each abortion. The challenge is to choose the process
to terminate based on factors like priority, how long it has computed, and
what resources it holds.

2. **Resource Preemption:**
* Preempt resources from some processes and give them to others
until the deadlock is broken.
* **Issues:**
* **Selecting a Victim:** Which resources and which processes to
preempt? The goal is to minimize cost.
* **Rollback:** If a resource is preempted from a process, what
should be done with that process? It must be rolled back to a safe state
and restarted from that state.
* **Starvation:** How to ensure that the same process is not
always picked as a victim? A practical solution is to include the number of
rollbacks in the cost factor.
Problem 1: First-Come, First-Served (FCFS) Scheduling
Process Table:

Process Arrival Time Burst Time

P1 0 24

P2 0 3

P3 0 3

Q: Calculate the average waiting time.

Solution:​
In FCFS, processes are executed in the order they arrive. Since all arrive
at time 0, we assume the order is P1, P2, P3.
Gantt Chart:
text
|----P1-----|--P2--|-P3-|
0 24 27 30
Calculation of Waiting Times:
●​ Waiting Time = Start Time - Arrival Time
●​ P1: Starts at 0. Waiting Time = 0 - 0 = 0
●​ P2: Starts at 24. Waiting Time = 24 - 0 = 24
●​ P3: Starts at 27. Waiting Time = 27 - 0 = 27
Average Waiting Time: (0 + 24 + 27) / 3 = 51 / 3 = 17 ms
Conclusion: This demonstrates the Convoy Effect, where a short
process behind a long process has to wait a very long time.
Problem 2: Shortest-Job-First (SJF) Scheduling (Non-Preemptive)
Process Table:

Process Arrival Time Burst Time

P1 0 6

P2 0 8

P3 0 7

P4 0 3

Q: Find the average waiting time and average turnaround time.

Solution:​
In non-preemptive SJF, the scheduler selects the process with the
smallest burst time from the ready queue. All processes are available at
time 0.
Step 1: Sort by Burst Time.​
Order of execution: P4 (3), P1 (6), P3 (7), P2 (8)
Gantt Chart:
text
|-P4-|--P1--|----P3----|-----P2-----|
0 3 9 16 24
Step 2: Calculate Times.
●​ Turnaround Time = Completion Time - Arrival Time
●​ Waiting Time = Turnaround Time - Burst Time

Arrival Burst Completion Turnaround Waiting

Process
Time Time Time Time Time

P4 0 3 3 3-0=3 3-3=0

P1 0 6 9 9-0=9 9-6=3
 Arrival Burst Completion Turnaround Waiting
Process
Time Time Time Time Time

16 - 7 =
P3 0 7 16 16 - 0 = 16
9

24 - 8 =
P2 0 8 24 24 - 0 = 24
16

Step 3: Calculate Averages.

●​ Average Waiting Time: (0 + 3 + 9 + 16) / 4 = 28 / 4 = 7 ms
●​ Average Turnaround Time: (3 + 9 + 16 + 24) / 4 = 52 / 4 = 13
ms

Problem 3: Shortest-Remaining-Time-First (SRTF) Scheduling

(Preemptive SJF)
Process Table:

Process Arrival Time Burst Time

P1 0 8

P2 1 4

P3 2 9

P4 3 5

Q: Find the average waiting time.

Solution:​
In SRTF, the scheduler always chooses the process with the shortest
remaining burst time. It can preempt the currently running process.
Step-by-Step Execution:
●​ Time 0: Only P1 is available. It starts execution. Remaining: P1(7)
●​ Time 1: P2 arrives. Compare remaining times: P1(7) vs P2(4). P2 is
shorter. Preempt P1 and start P2. Remaining: P1(7), P2(3)
 ●​ Time 2: P3 arrives. Compare: P2(3), P1(7), P3(9). P2 still has the
shortest remaining time. Continue P2.
●​ Time 3: P4 arrives. P2 finishes at this moment. Compare remaining
times in ready queue: P1(7), P3(9), P4(5). P4 is shortest. Start P4.
●​ Time 4: (No new process). Compare: P4(4), P1(7), P3(9). P4 is still
shortest. Continue P4.
●​ Time 5: (No new process). Compare: P4(3), P1(7), P3(9). Continue
P4.
●​ ...
●​ Time 8: P4 completes. Compare: P1(7), P3(9). P1 is shortest. Start
P1.
●​ Time 15: P1 completes. Only P3 remains. Start P3.
●​ Time 24: P3 completes.
Gantt Chart:
text
|-P1-|-P2-|----P4----|-----P1------|--------P3---------|
0 1 4 8 15 24
Step 2: Calculate Waiting Times.
●​ Waiting Time = (Time of Completion) - (Arrival Time) - (Burst
Time)​
OR​
= (Start Time - Arrival Time) + (Time of Preemption - Time of
Re-entry) ... This is complex. The first formula is simpler if we know
the completion time.

Waiting
Arrival Burst Completion Waiting
Process Time
Time Time Time Time
Calculation

15 - 0 - 8 =
P1 0 8 15 7
7

4 - 1 - 4 =
P2 1 4 4
-1? Error

Let's calculate using the timeline method:

 ●​ P1: Ran from 0-1 and 8-15.
o​ Total Time in System = 15 - 0 = 15.
o​ Time spent executing = 8.
o​ Time spent waiting = 15 - 8 = 7.
●​ P2: Ran from 1-4.
o​ Total Time in System = 4 - 1 = 3.
o​ Time spent executing = 3? Wait, Burst Time is 4, but it
finished at 4, so it ran for 3 units? Let's check the Gantt chart:
P2 ran from time 1 to 4, which is 3 units of time, but its burst
time is 4. This is a discrepancy.
Let's correct the Gantt Chart. At time 1, P2 has a burst of 4. It runs until
time 4, which is 3 units. It still has 1 unit left. But at time 4, P4 has a
remaining time of 5, and P1 has 7. P2 has 1, which is the smallest. So P2
should continue.
Corrected Step-by-Step:
●​ Time 0: P1 starts. Rem: P1(7)
●​ Time 1: P2 arrives (Burst 4). P1(7) vs P2(4). Preempt P1, start
P2. Rem: P1(7), P2(3)
●​ Time 2: P3 arrives (Burst 9). Compare: P2(3), P1(7), P3(9).
Continue P2.
●​ Time 3: P4 arrives (Burst 5). Compare: P2(2), P1(7), P3(9), P4(5).
Continue P2.
●​ Time 4: P2 completes. Compare: P4(5), P1(7), P3(9). P4 is
shortest. Start P4.
●​ Time 5: (No new). Compare: P4(4), P1(7), P3(9). Continue P4.
●​ Time 6: (No new). Compare: P4(3), P1(7), P3(9). Continue P4.
●​ Time 7: (No new). Compare: P4(2), P1(7), P3(9). Continue P4.
●​ Time 8: (No new). Compare: P4(1), P1(7), P3(9). Continue P4.
●​ Time 9: P4 completes. Compare: P1(7), P3(9). P1 is shortest. Start
P1.
●​ Time 16: P1 completes. Start P3.
●​ Time 25: P3 completes.
Corrected Gantt Chart:
text
|-P1-|-P2-|-----P4------|-----P1------|---------P3----------|
0 1 4 9 16 25
Now Calculate Waiting Times (Timeline Method):
●​ P1: Ran [0-1] and [9-16].
o​ Waiting Time = (16 - 0) - 8 = 8
●​ P2: Ran [1-4].
o​ Waiting Time = (4 - 1) - 4 = -1? This is wrong. Let's do: Time
in system = 4-1=3. Burst Time=4. This is impossible.
The error is that at time 1, P2 has not run yet, so its remaining time is its
full burst time, which is 4. It runs for 3 units until time 4, so it should
have 1 unit left. Let's track Remaining Time correctly.
Final Corrected Step-by-Step (with Remaining Time):
●​ Time 0: P1 starts. Rem: P1(8)
●​ Time 1: P1 has run 1 unit. Rem: P1(7). P2 arrives. Rem: P2(4).
Shortest is P2. Preempt P1, start P2. Queue: P1(7)
●​ Time 2: P2 has run 1 unit. Rem: P2(3). P3 arrives. Rem: P3(9).
Shortest is P2(3). Continue P2. Queue: P1(7), P3(9)
●​ Time 3: P2 has run 2 units. Rem: P2(2). P4 arrives. Rem: P4(5).
Shortest is P2(2). Continue P2. Queue: P1(7), P3(9), P4(5)
●​ Time 4: P2 has run 3 units. Rem: P2(1). P2 completes its final unit.
P2 finishes at Time 5. Queue: P1(7), P3(9), P4(5)
●​ Time 5: P2 is done. Shortest in queue is P4(5). Start P4.
●​ Time 6: P4 has run 1 unit. Rem: P4(4). Continue P4. Queue: P1(7),
P3(9)
●​ Time 7: P4 has run 2. Rem: P4(3). Continue.
●​ Time 8: P4 has run 3. Rem: P4(2). Continue.
●​ Time 9: P4 has run 4. Rem: P4(1). Continue.
●​ Time 10: P4 completes. Shortest is P1(7). Start P1.
●​ Time 11: P1 has run 1 unit (1 from first run + 1 now = 2 total).
Rem: P1(6). Continue.
●​ ...P1 runs uninterrupted until it finishes.
 ●​ Time 17: P1 completes (It ran from 0-1 and 10-17, total 8 units).
Start P3.
●​ Time 26: P3 completes.
Final Corrected Gantt Chart:
text
|-P1-|-P2-|-----P4------|------P1-------|---------P3----------|
0 1 5 10 17 26
Final Waiting Time Calculation (Timeline Method):
●​ P1: Arrival=0, Burst=8. Ran [0-1] and [10-17].
o​ Waiting Time = (17 - 0) - 8 = 9. OR: Waited from time 1 to
10 = 9 units. 9
●​ P2: Arrival=1, Burst=4. Ran [1-5].
o​ Waiting Time = (5 - 1) - 4 = 0. 0
●​ P3: Arrival=2, Burst=9. Ran [17-26].
o​ Waiting Time = (26 - 2) - 9 = 15. 15
●​ P4: Arrival=3, Burst=5. Ran [5-10].
o​ Waiting Time = (10 - 3) - 5 = 2. 2
Average Waiting Time: (9 + 0 + 15 + 2) / 4 = 26 / 4 = 6.5 ms

Problem 4: Priority Scheduling (Non-Preemptive)

Process Table: (Lower number indicates higher priority)

Arrival
Process Burst Time Priority
Time

P1 0 10 3

P2 0 1 1

P3 0 2 4

P4 0 1 5
 Arrival
Process Burst Time Priority
Time

P5 0 5 2

Q: Find the average waiting time.

Solution:​
All processes arrive at time 0. The scheduler picks the one with the
highest priority (smallest number).
Order of Execution: P2 (Pri=1), P5 (Pri=2), P1 (Pri=3), P3 (Pri=4), P4
(Pri=5)
Gantt Chart:
text
|-P2-|-P5-|-----P1------|-P3-|-P4-|
0 1 6 16 18 19
Calculation of Waiting Times:
●​ P2: Starts at 0. Waiting Time = 0
●​ P5: Starts at 1. Waiting Time = 1 - 0 = 1
●​ P1: Starts at 6. Waiting Time = 6 - 0 = 6
●​ P3: Starts at 16. Waiting Time = 16 - 0 = 16
●​ P4: Starts at 18. Waiting Time = 18 - 0 = 18
Average Waiting Time: (0 + 1 + 6 + 16 + 18) / 5 = 41 / 5 = 8.2 ms

Problem 5: Round Robin (RR) Scheduling

Process Table:

Process Burst Time

P1 24

P2 3
Process Burst Time

P3 3

Q: Find the average waiting time with a Time Quantum of 4 ms.

Solution:​
In RR, each process gets a time slice. The ready queue is treated as a
circular FIFO queue.
Gantt Chart:
text
|-P1-|-P2-|-P3-|--P1--|--P1--|--P1--|--P1--|--P1--|
0 4 7 10 14 18 22 26 30
Explanation:
●​ Time 0: P1 runs for 4 ms. Remaining: P1(20)
●​ Time 4: P2 runs for 3 ms and finishes. Remaining: P1(20)
●​ Time 7: P3 runs for 3 ms and finishes. Remaining: P1(20)
●​ Time 10: Only P1 remains. It runs in repeated quanta of 4 until it
finishes.
Calculation of Waiting Times:
●​ Waiting Time = (Time of first start) - (Arrival Time) + (Time of
subsequent preemptions) - (Time of subsequent re-entries) ...​
Easier: Waiting Time = (Completion Time) - (Arrival Time) - (Burst
Time)
●​ P1: Completion Time = 30.
o​ Waiting Time = 30 - 0 - 24 = 6
o​ *(Check: P1 ran at 0-4, 10-14, 14-18, 18-22, 22-26, 26-30.
It waited from 4-10 (6), 14-14 (0), 18-18 (0), 22-22 (0),
26-26 (0). Total wait = 6)*
●​ P2: Completion Time = 7.
o​ Waiting Time = 7 - 0 - 3 = 4
o​ *(Check: P2 started at 4, waited from 0-4 = 4)*
●​ P3: Completion Time = 10.
o​ Waiting Time = 10 - 0 - 3 = 7
 o​ *(Check: P3 started at 7, waited from 0-7 = 7)*
Average Waiting Time: (6 + 4 + 7) / 3 = 17 / 3 ≈ 5.67 ms
Conclusion: RR provides fair allocation and good response time. The
waiting time is much lower than the 17 ms from the FCFS solution for the
same processes.