MODULE-01

[Link] are micro kernels ? with a neat figure, explain the micro kernel stucure ? point out
their advantages over layered approach

A microkernel is an operating system design approach in which only the most essential services are kept
inside the kernel, and all other services are moved to user space.

Minimal services in a microkernel

 Inter-Process Communication (IPC)

 Basic process & thread management
 Low-level memory management
 Hardware abstraction

All other OS services like:

 File systems
 Device drivers
 Networking
 System servers

�run as user-level processes.

The Mach OS (developed at Carnegie Mellon University) is a classic example of a microkernel.

Microkernel Structure (with neat figure)

Explanation
  The microkernel runs in kernel mode and provides only essential services.
 OS services run as separate user processes.
 Communication between applications and services happens via message passing (IPC).

Microkernel vs Layered Approach (Advantages over Layered OS)

Feature Microkernel Layered Approach

Kernel size Very small Large
Modularity High Limited
Flexibility Very high Rigid
Fault tolerance Better Poorer
Performance Slight overhead (IPC) Faster calls
Security Higher Lower
1. List and Explain the different computing environment.

A computing environment describes the way computing resources such as hardware, software,
networks, and users interact to process information.

The different types of computing environments are:

1. Traditional Computing Environment

 In earlier office environments, PCs were connected to a network with centralized

servers.
 Servers provided file services and print services.
 Remote access was difficult and limited.
 Portability was mainly achieved using laptops.
 Mainframe systems with attached terminals were widely used.
 Web technologies have extended traditional computing:
o Companies now use web portals for internal access.
o Network computers act as web-based terminals.
o Handheld devices and PDAs connect using wireless networks.

�This environment is mostly centralized and static.

2. Client–Server Computing Environment

 One of the most common modern computing models.
 The system is divided into:
o Clients – request services
o Servers – provide services
 Clients communicate with servers over a network.
Types of Server Systems

a) Compute-Server Systems

 The server performs computational tasks requested by the client.

 Client sends a request → Server processes → Result returned.
 Example: Database server responding to SQL queries.

b) File-Server Systems

 Server provides file system services.

 Clients can create, read, update, and delete files.
 Example: Web server delivering HTML files to browsers.

�This model offers centralized control, better management, and scalability.

3. Peer-to-Peer (P2P) Computing Environment

 A type of distributed system.
 No distinction between client and server.
 All nodes are called peers.
 Each peer can act as both:
o A service requester
o A service provider

Key Features

 Eliminates bottlenecks of centralized servers.

 Services are distributed across many nodes.
 More fault tolerant.

Service Discovery Methods

1. Centralized Lookup
o Peers register services with a central directory.
o Clients query the directory to locate services.
2. Broadcast Discovery
o Client broadcasts service request.
o Peers offering the service respond.
o Uses a discovery protocol.

�Common in file sharing systems and distributed applications.

4. Web-Based Computing Environment

 Computing is done using web technologies.
 Supports a wide range of devices:
o PCs
o Workstations
o PDAs
 o Smartphones
 Strong emphasis on networking.
 Both wired and wireless devices are connected.
 Faster access due to:
o Improved network technologies
o Optimized communication protocols

Load Balancers

 A new category of devices introduced.

 Distributes incoming requests among multiple servers.
 Improves:
o Performance
o Availability
o Reliability

[Link] Operating System . Briefly explain what OS do

An Operating System (OS) is a system software that manages the computer hardware and
provides a platform on which application programs can run.
It acts as an intermediary between the user and the computer hardware, ensuring that the
system operates in a convenient and efficient manner.

What Does an Operating System Do?

An operating system performs the following major functions:

1. Acts as an Interface

 Provides a way for users to interact with the computer.

 Interfaces may be:
o Command Line Interface (CLI)
o Graphical User Interface (GUI)

2. Resource Management

 Acts as a resource manager or central governor.

 Manages and controls:
o CPU
o Main memory
o I/O devices
o Storage devices
 Allocates and deallocates resources as needed.

3. Program Execution

 Loads programs into memory.

 Executes programs.
 Handles program termination and errors.
4. Hardware Management

 Controls and coordinates the use of hardware devices.

 Uses device drivers to communicate with hardware.

5. Provides a Convenient Execution Environment

 Ensures users can execute programs easily, safely, and efficiently.

 Hides hardware complexity from users.

Goals of an Operating System

Primary Goal

 To make the computer system convenient to use.

Secondary Goal

 To use the computer hardware efficiently.

Additional Goals

 Provide a friendly environment for user interaction.

 Allocate and deallocate system resources properly.

[Link] is caching ? list and explain performance of various levels of storage.

Caching is an important principle of computer systems in which a small, high-speed memory is used to
temporarily store frequently accessed data.

Working of Cache

 When a piece of information is needed:

o The system first searches the cache.
o If found → it is used directly from cache (fast access).
o If not found → data is fetched from the main source, and a copy is placed in the cache for
future use.
 This is based on the assumption that recently used data will be used again soon (locality of reference).

Key Points

 Internal CPU registers (like index registers) act as high-speed cache.

 Cache has limited size, so cache management is important.
 Same data may exist at multiple levels of storage hierarchy.
 In multiprocessor systems, maintaining cache coherency is essential.
 In distributed systems, multiple copies (replicas) must be kept consistent.

Performance of Various Levels of Storage

Computer systems use a hierarchical storage structure to balance speed, cost, and capacity.

Storage Hierarchy (Top → Bottom)

1. Registers
 Located inside the CPU.
 Fastest storage.
 Very small size.
 Used to store:
o Instructions
o Operands
o Intermediate results
 Highest performance, highest cost per bit.

2. Cache Memory
 Located between CPU and main memory.
 Faster than RAM but slower than registers.
 Stores frequently used data and instructions.
 Reduces average memory access time.
 Limited size → requires cache replacement policies.

3. Main Memory (RAM)

 Primary memory used for program execution.
 Slower than cache.
 Volatile (data lost when power is off).
 Stores:
o Currently executing programs
o Data in use
 Moderate speed and capacity.

4. Secondary Storage (Hard Disk / SSD)

 Used for permanent storage.
 Non-volatile.
 Much slower than main memory.
 Large storage capacity.
 Stores:
o Files
o Applications
 o Operating system

5. Tertiary Storage (Magnetic Tape)

 Used mainly for backup and archival purposes.
 Very slow access time.
 Lowest cost per bit.
 Access is usually sequential.

5. What are the different special purpose system ? list them and explain each in brief

Special purpose systems are computers designed to perform specific, limited tasks rather than general-
purpose computing.
They focus on restricted computation domains and are optimized for particular applications.

Examples

 Real-Time Embedded Systems

 Multimedia Systems
 Handheld Systems

1. Real-Time Embedded Systems

 Embedded computers are used in dedicated applications such as:
o Car engines
o Robots
o Alarm systems
o Medical imaging systems
o Industrial control systems
o Microwave ovens and weapon systems
 They perform specific tasks and usually have limited or no user interface.
 They run on a Real-Time Operating System (RTOS).
 A real-time system must meet strict time constraints; failure to meet deadlines leads to system failure.
 RTOS uses priority-based scheduling to meet response requirements.

Types of Real-Time Systems

a) Hard Real-Time Systems

 Guarantees that critical tasks are completed within deadlines.

 All system delays are strictly bounded.
 Used in robotics, industrial control, and medical systems.

b) Soft Real-Time Systems

 Less restrictive than hard real-time systems.

 Critical tasks get priority but missing deadlines is tolerable.
 Used in multimedia, virtual reality, and scientific applications.
 Requires:
o Priority-based CPU scheduling
 o Small dispatch latency

2. Multimedia Systems
 Designed to handle multimedia data such as:
o Audio
o Video
o Text and images
 Multimedia data must be delivered or streamed within time constraints.
 Timing is important to maintain quality of service.
 Examples include:
o Video conferencing
o Internet news streaming
o Live webcasts and online lectures

3. Handheld Systems
 Include devices such as:
o Personal Digital Assistants (PDAs)
o Mobile phones
o Palm and pocket PCs
 Use special-purpose embedded operating systems.

Characteristics / Limitations

 Memory: Limited memory, often without virtual memory support.

 Speed: Slower processors to conserve battery power.
 Display: Small screen size restricts output.
 Uses techniques like web clipping, where only part of a web page is displayed.

Advantages

 Small and lightweight → high portability.

 Can synchronize with desktop systems.

[Link] in detailes about Operating system structure.

The operating system structure defines how an OS organizes and manages processes, memory, CPU, and
I/O devices to ensure efficient system operation.
Two important concepts that form the base of OS structure are multiprogramming and time-sharing.

1. Multiprogramming System
Need for Multiprogramming

 A single user program cannot keep the CPU and I/O devices busy all the time.
 During I/O operations, the CPU remains idle in a non-multiprogrammed system.

Concept
  Multiprogramming increases CPU utilization by keeping multiple jobs in memory simultaneously.
 When one job waits for I/O, the CPU is switched to another job.

Working

1. Several jobs are loaded into main memory.

2. The OS selects one job and begins execution.
3. If the running job requests I/O:
o CPU is immediately assigned to another ready job.
4. Thus, CPU idle time is minimized.

Memory Layout (Conceptual)

Advantages

 Improved CPU utilization

 Better system throughput
 Efficient use of resources

2. Time-Sharing (Multitasking) System

Concept

 Time-sharing is a logical extension of multiprogramming.

 The CPU switches among processes very frequently, allowing users to interact with programs.

Key Features

 Supports multiple users simultaneously.

 Each user has at least one process executing in memory.
 Response time is less than 1 second.
 Provides an interactive computing environment.
Process

 A process is a program that is loaded into memory and currently executing.

 CPU time is divided into small units called time slices.
 Each process gets CPU time in a round-robin or priority manner.

Requirements

 Fast CPU scheduling

 Efficient memory management
 Frequent context switching

3. Job Scheduling
 A job pool contains all jobs residing on disk waiting to be loaded into main memory.
 When memory becomes available, the OS must decide:
o Which job should be brought into memory?
 This decision-making process is called job scheduling.
 Long-term scheduler handles job scheduling.

4. CPU Scheduling
 When multiple processes are ready to execute, the OS must decide:
o Which process should get the CPU next?
 This selection process is known as CPU scheduling.
 CPU scheduling is handled by the short-term scheduler.
 Common goals:
o Maximize CPU utilization
o Minimize waiting time
o Provide fairness

5. Swapping
 In a time-sharing system, main memory may not be sufficient to hold all active processes.
 Swapping involves:
o Moving a process from memory to disk
o Bringing another process from disk to memory
 Used to maintain reasonable response time.

Virtual Memory

 A common implementation of swapping.

 Allows execution of processes that are not completely in main memory.
 Main advantage:
o Enables users to run programs larger than physical memory.

[Link] the OS Services with respect to Program and users .

An Operating System (OS) provides an environment in which users can execute programs conveniently and
efficiently.
These services are broadly meant to support program execution and user interaction with the system.

Operating System Services for Users and Programs

1. User Interface (UI)

The OS provides an interface through which users interact with the computer system.

Types of User Interfaces:

 Command Line Interface (CLI):

Uses text commands entered via keyboard.
 Batch Interface:
Commands are stored in files and executed sequentially.
 Graphical User Interface (GUI):
Uses windows, icons, menus, and pointing devices; most user-friendly.

2. Program Execution

 The OS loads programs into main memory.

 Starts execution of the program.
 Handles normal and abnormal termination.
 Ensures proper cleanup of resources after execution.

3. I/O Operations

 Programs often need to interact with I/O devices (disk, printer, keyboard).
 Users cannot directly control hardware.
 OS provides system calls to perform safe and controlled I/O operations.

4. File System Manipulation

 OS manages files and directories.

 Supports operations such as:
o Create and delete files
o Read and write files
o Search and list files
 Provides access permissions to protect files.

5. Communication

Allows processes to exchange information.

Types of Communication:

1. Between processes on the same computer

2. Between processes on different computers connected via a network
Methods:

 Shared Memory
 Message Passing

6. Error Detection

 Errors may occur in:

o CPU
o Memory
o I/O devices
 OS continuously monitors for errors.
 Takes corrective actions to maintain system stability and consistency.

7. Resource Allocation

 When multiple users or programs run simultaneously, resources must be shared.

 OS allocates:
o CPU time
o Memory
o I/O devices
o Storage space
 Uses scheduling and allocation policies.

8. Accounting

 OS keeps track of:

o Resource usage by users and programs
 Used for:
o Billing
o Performance analysis
o System optimization

9. Protection and Security

 Protection: Controls access to system resources.

 Security: Prevents unauthorized access.
 Includes:
o User authentication (passwords)
o File access permissions
o Process isolation
 Protects against both internal and external threats.

[Link] the OS Services with respect to program and users

MODULE-02
1. Discuss the benifits of multithreaded programming explain the threading issues in detail
A thread is the basic unit of CPU utilization.
It consists of:

 Thread ID
 Program counter
 Register set
 Stack

Threads share the code section, data section, and OS resources (such as open files and signals) of the process
to which they belong.

A single-threaded process has only one thread of control, whereas a multithreaded process has multiple
threads and can perform multiple tasks concurrently.

Benefits of Multithreaded Programming

Multithreaded programming provides several important advantages:

1. Responsiveness

 Allows a program to remain responsive even if part of it is blocked or performing a lengthy operation.
 Example: A web browser can display images while another thread downloads data.
 Improves user experience.

2. Resource Sharing

 Threads share the same address space, code, and data of the process.
 Communication between threads is faster and simpler than inter-process communication.
 Enables multiple activities within the same process.

3. Economy

 Thread creation and termination is faster than process creation.

 Context switching between threads is cheaper due to shared resources.
 Reduces system overhead.

4. Utilization of Multiprocessor Architectures

 Threads can execute in parallel on multiple CPUs.

 Increases concurrency and throughput.
 Improves performance on multicore systems.

Threading Issues

When using multithreading, the operating system must address several important issues:

1. Semantics of fork() and exec()

 In a multithreaded process:
 o fork() may duplicate:
 Only the calling thread OR
 All threads of the process
 exec() replaces the entire process image, so all threads are replaced.
 Different operating systems define different semantics.

2. Signal Handling
 Signals are used to notify a process of an event.
 In multithreaded systems, signals can be:
o Delivered to a specific thread
o Delivered to all threads
o Delivered to a selected set of threads
 Proper handling is required to avoid inconsistent behavior.

3. Thread Cancellation
 Thread cancellation is the process of terminating a thread before it finishes execution.

Types of Cancellation

 Asynchronous Cancellation
o Thread is terminated immediately.
o Can cause resource leaks.
 Deferred Cancellation
o Thread checks for cancellation at safe points.
o Safer and more commonly used.

4. Thread Pools
 Creating and destroying threads repeatedly is expensive.
 A thread pool maintains a set of pre-created threads.
 Threads are reused to handle multiple tasks.
 Benefits:
o Faster request handling
o Limits number of active threads
o Better resource management

5. Thread-Specific Data
 Although threads share data, sometimes each thread needs private data.
 Thread-specific data allows each thread to have its own copy of a variable.
 Useful in libraries used by multithreaded applications.

6. Scheduler Activations
 Used to coordinate between kernel threads and user threads.
 Kernel informs the user-level thread library about scheduling events.
 Improves performance and responsiveness.
 2. Explain the Context_Switching.

Context switching is the mechanism by which the CPU switches from executing one process to another.
It occurs when an interrupt, system call, or scheduler decision requires the CPU to stop executing the current
process and start executing another process.

What is Context?
The context of a process is the information required to resume its execution later.
It includes:

 Program Counter (PC)

 CPU registers
 Stack pointer
 Process state
 Other CPU-related information

This information is stored in the Process Control Block (PCB) of the process.

Steps in Context Switching

1. Interrupt Occurs
o An interrupt (I/O completion, timer interrupt, system call) occurs while a process is running.
2. Save Current Process State
o The OS saves the current CPU state (context) of the running process into its PCB.
3. Select Next Process
o The CPU scheduler selects another ready process.
4. Restore New Process State
o The saved context of the selected process is loaded from its PCB into the CPU.
5. Resume Execution
o The CPU resumes execution of the new process from where it had stopped.

Why Context Switching is Needed

 To support multiprogramming
 To implement time-sharing systems
 To allow fair CPU sharing
 To handle I/O operations and interrupts

Context Switch Overhead

 Context switching takes CPU time.
 During a context switch:
o The system performs no useful work.
 Hence, it is considered an overhead.

Factors Affecting Context-Switch Time

  Speed of main memory
 Number of CPU registers to be saved and restored
 Hardware support for context switching
 Availability of special CPU instructions

Context-switch time varies from machine to machine.

[Link] is Multithreaded Process ? explain the four benefits of multithreaded programming.

A multithreaded process is a process that contains multiple threads of execution within the
same address space.

Benefits of Multithreaded Programming

Multithreaded programming provides several important advantages:

1. Responsiveness

 Allows a program to remain responsive even if part of it is blocked or performing a lengthy operation.
 Example: A web browser can display images while another thread downloads data.
 Improves user experience.

2. Resource Sharing

 Threads share the same address space, code, and data of the process.
  Communication between threads is faster and simpler than inter-process communication.
 Enables multiple activities within the same process.

3. Economy

 Thread creation and termination is faster than process creation.

 Context switching between threads is cheaper due to shared resources.
 Reduces system overhead.

4. Utilization of Multiprocessor Architectures

 Threads can execute in parallel on multiple CPUs.

 Increases concurrency and throughput.
 Improves performance on multicore systems.

[Link] with example of single threaded and multithreaded process

Single-Threaded Process
A single-threaded process has only one thread of control.

Explanation (Left side of the figure)

 The process contains:

o Code
o Data
o Files
 There is only one set of registers and one stack.
 Only one thread is executing inside the process.
 Tasks are performed sequentially, one after another.

Example

MS-DOS program or a simple calculator application:

 First accepts input

 Then performs calculation
 Then displays output
If one operation is delayed (e.g., waiting for input), the entire program waits.

Multithreaded Process
A multithreaded process contains multiple threads of control within the same process.

Explanation (Right side of the figure)

 Threads share:
o Code section
o Data section
o Open files
  Each thread has its own:
o Program counter
o Register set
o Stack
 Multiple threads execute concurrently.

Example

Web Browser (e.g., Chrome, Firefox):

 One thread handles user interface

 One thread downloads web data
 One thread displays images or videos
Even if downloading is slow, the browser remains responsive.

Another example:
Web Server

 Each client request is handled by a separate thread

 Multiple clients are served at the same time

[Link] the difference among short term , medium term and long term Scheduling.

6. Differentiate the advantages and disadvantages of synchronous and asynchronous

communication.

MODULE-03
 [Link] Reader’s and Writer’s problem in details

Readers–Writers Problem

The Readers–Writers problem is a classic synchronization problem in operating systems.

 A shared database is accessed by multiple concurrent processes.

 Some processes only read the data → Readers
 Some processes read and write (update) the data → Writers

Problem Definition
 Readers: Processes that only read the shared data
 Writers: Processes that modify (read + write) the shared data

Constraint

 Readers can share the database.

 Writers must have exclusive access.

This synchronization challenge is called the Readers–Writers Problem.

Variations of Readers–Writers Problem

1. First Readers–Writers Problem (Reader Priority)

 No reader should be forced to wait unless a writer has already obtained access.
 Readers get priority over writers.
 Advantage: High reader concurrency.
 Disadvantage: Writer starvation may occur.

2. Second Readers–Writers Problem (Writer Priority)

 Once a writer is ready, it should write as soon as possible.

 Writers get priority over readers.
 Advantage: Writers are not starved.
 Disadvantage: Reader starvation may occur.

Shared Data Structures (First Readers–Writers Problem)

semaphore mutex, wrt;
int readcount;

Initialization

mutex = 1;
wrt = 1;
readcount = 0;

Purpose

 mutex → ensures mutual exclusion while updating readcount

 wrt → ensures exclusive access for writers
 readcount → number of readers currently reading

Writer Process Code

do {
wait(wrt);
// writing is performed
signal(wrt);
} while (TRUE);

Explanation

 Writer waits on wrt semaphore.

 Ensures no reader or writer is accessing the database.
 After writing, releases wrt.

Reader Process Code

do {
wait(mutex);
readcount++;
if (readcount == 1)
wait(wrt);
signal(mutex);

// reading is performed

wait(mutex);
readcount--;
if (readcount == 0)
signal(wrt);
signal(mutex);
} while (TRUE);

Explanation

1. First reader locks wrt to block writers.

2. Multiple readers can read concurrently.
3. Last reader releases wrt, allowing writers to proceed.
4. mutex protects readcount from race conditions.

[Link] is critical Section problem and Solutions to the Problem ? How the solve using
Semaphore
Critical-Section Problem

Definition
In a system consisting of n concurrent processes

{P0,P1,P2,…,Pn−1}\{P_0, P_1, P_2, \ldots, P_{n-1}\}{P0,P1,P2,…,Pn−1}

each process contains a segment of code called the critical section.

Program Structure of a Process

Each process is divided into four sections:

Entry Section
Critical Section
Exit Section
Remainder Section

 Entry section → Request permission to enter the critical section

 Critical section → Access shared resources
 Exit section → Release permission
 Remainder section → Other code not involving shared data

Critical-Section Problem
The critical-section problem is to design a protocol that allows processes to cooperate such that:

1. Only one process executes in the critical section at a time

2. System remains efficient and deadlock-free

Requirements of a Correct Solution

A correct solution must satisfy three conditions:

1. Mutual Exclusion

Only one process can be in its critical section at any time.

2. Progress

If no process is in the critical section, and some wish to enter, the selection cannot be postponed indefinitely.

3. Bounded Waiting

A limit must exist on the number of times other processes can enter their critical sections after a process has
requested entry.
Semaphore

A semaphore is a synchronization tool represented by an integer variable that can be accessed only through
two atomic operations:

 wait() (also called P operation)

 signal() (also called V operation)

Semaphore Operations
wait(S) Operation
wait(S) {
while (S <= 0)
; // busy waiting
S--;
}

 If S > 0, the process continues

 If S ≤ 0, the process waits
 Decrements semaphore value

signal(S) Operation
signal(S) {
S++;
}

 Increments semaphore value

 Wakes up waiting processes (if any)

Important Property

wait() and signal() operations are atomic, meaning they execute indivisibly.

Solution to Critical-Section Problem Using Semaphore

Binary Semaphore (Mutex)

A binary semaphore is used to ensure mutual exclusion.

semaphore mutex = 1;

Process Structure Using Semaphore

do {
wait(mutex); // Entry section

// Critical Section
// Access shared resources
 signal(mutex); // Exit section

// Remainder Section
} while (TRUE);

Working Explanation
1. Initially, mutex = 1
2. A process executes wait(mutex)
o If mutex = 1, it enters critical section
o mutex becomes 0
3. Other processes attempting wait(mutex) must wait
4. After finishing, process executes signal(mutex)
o mutex becomes 1
o Another waiting process may enter

3. Explain the Critical bounded buffer problem of Synchronization Give the solution.

What is the Bounded Buffer Problem?

The Bounded Buffer Problem (also called the Producer–Consumer Problem) is a critical synchronization
problem where:

 A producer generates data items and places them into a shared buffer
 A consumer removes data items from the same buffer
 The buffer has a fixed size (n buffers)

The challenge is to synchronize access so that:

1. Producer does not add data when the buffer is full

2. Consumer does not remove data when the buffer is empty
3. Producer and Consumer do not access the buffer simultaneously (critical section)

Why is it a Critical Problem?

Because:

 The buffer is a shared resource

 Simultaneous access can lead to race conditions
 Incorrect synchronization can cause:
o Data inconsistency
o Deadlock
o Buffer overflow / underflow

Hence, mutual exclusion + coordination are required.

Synchronization Tools Used

Three semaphores are used:
Producer Process (Explanation)
do {
// produce an item in nextp
wait(empty); // ensure there is an empty buffer
wait(mutex); // enter critical section

// add nextp to buffer

signal(mutex); // leave critical section

signal(full); // increase count of full buffers
} while (TRUE);

How Producer Works:

1. wait(empty)
→ Producer waits if buffer is full
2. wait(mutex)
→ Ensures exclusive access to buffer
3. Add item to buffer (critical section)
4. signal(mutex)
→ Releases the buffer
5. signal(full)
→ Notifies consumer that a new item is available

Consumer Process (Explanation)

do {
wait(full); // ensure buffer is not empty
wait(mutex); // enter critical section

// remove an item from buffer to nextc

signal(mutex); // leave critical section

signal(empty); // increase count of empty buffers

// consume the item in nextc

} while (TRUE);

How Consumer Works:

1. wait(full)
→ Consumer waits if buffer is empty
2. wait(mutex)
→ Ensures exclusive access
3. Remove item from buffer
4. signal(mutex)
→ Releases buffer
5. signal(empty)
→ Notifies producer that space is available

Interpretation of the Problem

As mentioned:
✔ Producer produces full buffers for the consumer
✔ Consumer produces empty buffers for the producer

This creates a cyclic dependency that is safely handled using semaphores.

[Link] is Critical section ? what are the requiriments for the solution in Critical Section
problem ? Explain patterson’s solution.

Definition
In a system consisting of n concurrent processes

{P0,P1,P2,…,Pn−1}\{P_0, P_1, P_2, \ldots, P_{n-1}\}{P0,P1,P2,…,Pn−1}

each process contains a segment of code called the critical section.

Program Structure of a Process

Each process is divided into four sections:

Entry Section
Critical Section
Exit Section
Remainder Section

 Entry section → Request permission to enter the critical section

 Critical section → Access shared resources
 Exit section → Release permission
 Remainder section → Other code not involving shared data

Critical-Section Problem
The critical-section problem is to design a protocol that allows processes to cooperate such that:

4. Only one process executes in the critical section at a time

5. System remains efficient and deadlock-free

Requirements of a Correct Solution

A correct solution must satisfy three conditions:

1. Mutual Exclusion

Only one process can be in its critical section at any time.

2. Progress
If no process is in the critical section, and some wish to enter, the selection cannot be postponed indefinitely.

3. Bounded Waiting

A limit must exist on the number of times other processes can enter their critical sections after a process has
requested entry.

Peterson’s Solution (Critical Section Problem)

Peterson’s solution is a classic software-based solution to the critical-section problem.
It provides a correct way to achieve process synchronization using shared variables only,

It works only for two processes, which alternate between:

 Critical Section
 Remainder Section

The two processes are:

 P0 and P1
or generally Pi and Pj where j = 1 − i

Shared Data Items Used

Peterson’s solution requires two shared variables:

int turn;
boolean flag[2];

Purpose of Variables

 turn
Indicates whose turn it is to enter the critical section.
o If turn == i, then process Pi is allowed to enter.
 flag[i]
Indicates whether process Pi is ready to enter its critical section.
o flag[i] = true → Pi wants to enter critical section
o flag[i] = false → Pi is not interested

Working Principle
To enter the critical section, process Pi:

1. Sets flag[i] = true (shows interest)

2. Sets turn = j (gives chance to the other process)
3. Waits until either:
o flag[j] == false OR
o turn == i

If both processes try to enter at the same time, the last assignment to turn determines who enters first.
Algorithm for Process Pi
do {
flag[i] = true;
turn = j;
while (flag[j] == true && turn == j)
; // busy wait

// Critical Section

flag[i] = false;

// Remainder Section
} while (TRUE);

Correctness of Peterson’s Solution

To prove correctness, we must show that it satisfies:

1 Mutual Exclusion

 A process enters the critical section only if:

 flag[j] == false OR turn == i
 If both flag[0] == true and flag[1] == true, then:
o Only one value of turn is possible (0 or 1)
 Therefore, only one process can enter the critical section at a time.

✔ Mutual exclusion is preserved

2 Progress Requirement

 If Pi wants to enter the critical section:

o It can be blocked only if Pj is also interested and turn == j
 If Pj is not interested, flag[j] == false and Pi enters immediately
 If Pj enters first, it must exit and reset flag[j] = false

✔ No unnecessary delay → progress is guaranteed

3 Bounded Waiting

 Pi can be delayed only once by Pj

 After Pj exits:
o It sets flag[j] = false
o Or if it re-enters, it sets turn = i
 Hence, Pi gets a chance within a bounded time

✔ Bounded waiting is satisfied

[Link] is deadlock ? Explain the situation of the dinnin philosophers problem.

Deadlock is a situation where a set of processes are blocked each process is holding a resource
and waiting for another resource held by some other process.

The Dining-Philosophers Problem

The Dining-Philosophers Problem is a classic synchronization problem used to illustrate issues of:

 Deadlock
 Starvation
 Resource sharing
in operating systems.

It represents processes competing for limited shared resources.

Situation Description
 There are five philosophers sitting around a circular table.
 Each philosopher has one chair.
 At the center is a bowl of rice.
 There are five chopsticks, one between each pair of philosophers.

Each philosopher alternates between:

 Thinking
 Eating

Semaphore-Based Representation
Shared Data

Each chopstick is represented as a binary semaphore:

semaphore chopstick[5];

 All chopsticks are initialized to 1 (available).

Structure of Philosopher i
do {
wait(chopstick[i]); // pick left chopstick
wait(chopstick[(i+1) % 5]); // pick right chopstick

// eat

signal(chopstick[i]); // release left chopstick

signal(chopstick[(i+1) % 5]); // release right chopstick

// think
} while (TRUE);

The Problem: Deadlock

Deadlock Situation

 Suppose all five philosophers become hungry at the same time

 Each philosopher picks up her left chopstick
 Now, all chopsticks are held → semaphore values become 0
 Each philosopher tries to pick up her right chopstick
 But the right chopstick is already held by her neighbor

Result:
No philosopher can proceed → deadlock occurs

Conditions for Deadlock (Satisfied Here)

1. Mutual Exclusion – Chopsticks cannot be shared
2. Hold and Wait – Each philosopher holds one chopstick and waits for another
3. No Preemption – Chopsticks cannot be forcibly taken
4. Circular Wait – Each philosopher waits for the next one

All four conditions satisfied → deadlock possible

Remedies to the Deadlock Problem

1 Allow at Most Four Philosophers

 Restrict number of philosophers at the table to 4

 At least one philosopher can always eat

Breaks circular wait

2 Pick Up Both Chopsticks Together

 Philosopher picks up chopsticks only if both are available

 Done inside a critical section

Prevents hold-and-wait condition

3 Asymmetric Solution

 Odd-numbered philosophers pick up:

o Left → Right
 Even-numbered philosophers pick up:

Breaks circular wait

[Link] necessary conditions of deadlock and what are methods used for handling deadlocks .

Deadlock – Necessary Conditions

A deadlock is a situation in which a set of processes are blocked forever, each holding at
least one resource and waiting for another resource held by some other process in the set.

Deadlock can occur only if all the following four conditions hold simultaneously.

1 Mutual Exclusion

 At least one resource must be non-sharable.

 Only one process at a time can use the resource.
 If another process requests the same resource, it must wait.

Example: Printer, tape drive, mutex lock

Necessary because sharable resources cannot cause deadlock.

2 Hold and Wait

 A process is holding at least one resource

 While holding it, the process waits for additional resources that are currently held by other processes.

Example:
Process P₁ holds a printer and waits for a tape drive.

This condition allows processes to accumulate resources.

3 No Preemption

 Resources cannot be forcibly taken away from a process.

 They must be released voluntarily after the process completes its task.

Example:
A printer cannot be taken away from a process while it is printing.

Prevents the system from breaking deadlock by force.

4 Circular Wait

 A circular chain of processes exists:

o P₀ waits for P₁
o P₁ waits for P₂
o …
o Pₙ waits for P₀

Example:
P₀ → P₁ → P₂ → P₀

This forms a closed loop of waiting.

.Methods for Handling Deadlocks

Operating systems use four main approaches to deal with deadlocks.

1 Deadlock Prevention
Idea:

Prevent at least one of the four necessary conditions from occurring.

Techniques:

 Mutual Exclusion: Make resources sharable (when possible)

 Hold and Wait: Require processes to request all resources at once
 No Preemption: Preempt resources from waiting processes
 Circular Wait: Impose resource ordering

2 Deadlock Avoidance
Idea:

System dynamically decides whether granting a resource request will lead to deadlock.

Key Concept:

 System must know maximum resource requirement in advance

 Uses safe state concept

�Example:
Banker’s Algorithm

3 Deadlock Detection and Recovery

Idea:

 Allow deadlock to occur

 Detect it
 Recover from it

Detection:

 Use resource-allocation graphs

 Detect cycles

Recovery Methods:

 Terminate processes
 Preempt resources
 Rollback processes

4 Deadlock Ignorance (Ostrich Approach)

Idea:

Ignore the deadlock problem completely.

Used in:

 UNIX
 Windows (mostly)

MODULE-04

1. what is Fragmentation ? list and explain its types.

What is Fragmentation?

Fragmentation is a condition in memory management where available memory is wasted and

cannot be efficiently used to satisfy memory requests, even though sufficient memory may
exist.

It occurs due to dynamic allocation and deallocation of memory blocks.

Types of Fragmentation
Memory fragmentation is broadly classified into two types:

1. External Fragmentation
2. Internal Fragmentation

1 External Fragmentation
External fragmentation occurs when total free memory is sufficient to satisfy a request, but the free memory
is not contiguous.
Memory is broken into many small holes scattered throughout.

Explanation

 Occurs mainly in variable-sized partition allocation

 Free memory exists as several small blocks
 No single block is large enough for the request

�Example:
Free blocks = 5 KB + 10 KB + 8 KB
Request = 20 KB
→ Total free = 23 KB, but not contiguous → request fails

Solutions to External Fragmentation

1. Compaction
 o
Moves all free memory together into one large block
o
Requires dynamic relocation at execution time
2. Non-Contiguous Memory Allocation
o Paging
o Segmentation

2 Internal Fragmentation
Internal fragmentation occurs when allocated memory is slightly larger than the requested
memory, and the unused space inside the allocated block cannot be used by other processes.

Explanation

 Occurs in fixed-size partition allocation

 Memory is allocated in blocks of fixed size
 Extra unused memory inside the partition is wasted

�Example:

 Hole size = 18,464 bytes

 Process requests = 18,462 bytes
 Leftover = 2 bytes
 This 2 bytes is internal fragmentation

The overhead of managing this small hole is greater than the hole itself.

[Link] is Paging ? Differentiate between paging and segmentation.

�What is Paging?
�Definition

Paging is a memory management scheme that allows the physical address space of a process to be non-
contiguous.
Paging is supported by hardware and is used to eliminate external fragmentation.

Difference Between Paging and Segmentation

Feature Paging Segmentation
Basis Physical memory Logical program structure
Memory blocks Fixed size Variable size (segments)
(pages/frames)
Programmer’s view Not visible Visible
Address format Page number + offset Segment number + offset
Fragmentation Internal fragmentation External fragmentation
Memory allocation Non-contiguous Non-contiguous
Hardware support Required Required
Protection Page-level Segment-level
Sharing Difficult Easy

3. illustrate how demand paging affects system perfoemance What is thrashing how it can
be controlled ?

Demand Paging
Demand paging is a virtual memory technique in which pages are loaded into main memory
only when they are required. Instead of swapping the entire process, a pager loads only the
needed pages, reducing memory usage.

Performance of Demand Paging

Demand paging can significantly affect system performance because disk access time is much
slower than memory access time.

Effective Access Time (EAT)

Let:

 ma = memory access time (10–200 ns)

 p = probability of page fault
 Page fault service time ≈ 8 ms = 8,000,000 ns

Formula

EAT=(1−p)×ma+p×(page fault time

Example Calculation

EAT=(1−p)×200+p×8,000,000

=200+7,999,800p

If 1 access out of 1,000 causes a page fault:

p=0.001

EAT=200+7,999.8

=8.2 microseconds

Result:
The system becomes ~40 times slower due to demand paging.
Performance Requirement

To keep performance degradation below 10%:

220>200+7,999,800

p<0.0000025

Thus, page-fault rate must be extremely low to maintain good performance.

Conclusion on Demand Paging

Demand paging improves memory utilization but high page-fault rates drastically degrade
performance. Efficient memory management and low page-fault probability are essential for
acceptable system speed.

Thrashing

Definition
A process is said to be thrashing if it spends more time paging than executing.

Thrashing occurs when the system continuously swaps pages between main memory and
disk, resulting in poor CPU utilization.

Cause of Thrashing
 Insufficient number of frames allocated to processes
 High degree of multiprogramming
 Global page replacement algorithms
 Frequent page faults

As more processes are loaded:

 CPU utilization initially increases

 After a point, excessive paging starts
 CPU utilization drops sharply

This condition is called thrashing.

Effect of Thrashing
 Very high paging activity
 Low CPU utilization
 Poor system throughput
  Severe performance degradation

Control / Prevention of Thrashing

Local Page Replacement

 Pages are replaced only within the process

 Prevents one process from stealing frames from others

Reduce Degree of Multiprogramming

 Suspend or swap out some processes

 Allocate more frames to active processes

Provide Minimum Required Frames

 Each process must have enough frames to execute without excessive faults

Working Set Model

 Allocate frames equal to the working set of a process

 Ensures all frequently used pages are in memory

4. Explain Fragmentation in detail

Fragmentation

� Definition
Fragmentation refers to the condition in memory management where available memory is wasted and cannot
be efficiently used to satisfy memory allocation requests.

Fragmentation occurs because memory is allocated and deallocated dynamically as processes enter and leave
the system.

Types of Fragmentation
There are two types of fragmentation:

1. External Fragmentation
2. Internal Fragmentation
1. External Fragmentation
Definition

External fragmentation exists when enough total free memory is available to satisfy a request,
but the free memory is not contiguous. Memory is broken into many small holes scattered
throughout main memory.

Explanation

 Occurs in variable-sized partition allocation.

 Even though the total free space is sufficient, it cannot be used because it is divided into small non-
adjacent blocks.

Example

If memory has free holes of:

 5 KB, 8 KB, 6 KB

Total free memory = 19 KB,

but a process requesting 15 KB cannot be allocated because no single hole is large enough.

50-Percent Rule

Statistical analysis of the First-Fit allocation strategy shows:

 For every N allocated blocks, about 0.5N blocks are lost to fragmentation.
 Roughly one-third of memory becomes unusable.

This phenomenon is called the 50-percent rule.

Solutions to External Fragmentation

Compaction

 All free memory holes are moved together to form one large contiguous block.
 Requires dynamic relocation at execution time.
 Expensive in terms of CPU overhead.

Non-Contiguous Memory Allocation

 Allow a process’s logical address space to be non-contiguous.

 Implemented using Paging or Segmentation.
 Completely eliminates external fragmentation (paging).

2. Internal Fragmentation
Definition
Internal fragmentation occurs when allocated memory is slightly larger than the requested memory,
resulting in unused space within the allocated block.

Explanation

 Happens in fixed-size partitioning.

 Memory is allocated in blocks of fixed size.
 The unused space inside the partition cannot be used by other processes.

Example

Consider:

 A hole of 18,464 bytes

 Process requests 18,462 bytes

Remaining unused space = 2 bytes

The overhead required to manage this 2-byte hole is greater than the hole itself, making it inefficient.

Cause of Internal Fragmentation

To avoid tiny holes, memory is allocated in fixed-sized blocks.

If a process does not exactly fit the block size, the extra space remains unused.

Avoiding Internal Fragmentation

 Use smaller block sizes (trade-off with overhead).
 Use paging with appropriate page size.
 Internal fragmentation is reduced but not eliminated.

5. Explain with a neat diagram paging for 32-bytes memory with 4-byte page.

Paging
Definition

Paging is a memory management scheme that allows the physical address space of a process
to be non-contiguous. Logical memory is divided into pages and physical memory into frames
of the same size. Paging is supported by hardware.

Basic Method
 Physical memory is divided into fixed-size blocks called frames.
 Logical memory is divided into fixed-size blocks called pages.
 Page size = Frame size.
 A page table maps pages to frames.
 Paging eliminates external fragmentation, but may cause internal fragmentation.
Given
 Physical memory size = 32 bytes
 Page (Frame) size = 4 bytes

Calculations:

 Number of frames = 32 / 4 = 8 frames

 Frames are numbered 0 to 7

Logical Address Structure

Logical address is divided into:

 Page number (p)

 Page offset (d)

Since page size = 4 bytes = 222^222,

 Offset = 2 bits
 Page number = remaining bits

Neat Diagram: Paging for 32-byte Memory with 4-byte Page

Physical Memory (Frames)

Frame No. Address Range
--------------------------------
Frame 0 → 0 – 3
Frame 1 → 4 – 7
Frame 2 → 8 – 11
Frame 3 → 12 – 15
Frame 4 → 16 – 19
Frame 5 → 20 – 23
Frame 6 → 24 – 27
Frame 7 → 28 – 31

Page Table (Example Mapping)

Page No. Frame No.
-----------------------
Page 0 → Frame 5
Page 1 → Frame 6
Page 2 → Frame 1
Page 3 → Frame 2

Address Mapping Examples

(a) Logical Address = 0

 Page = 0, Offset = 0
 Page 0 → Frame 5
 Physical Address = (5 × 4) + 0 = 20

(b) Logical Address = 3

 Page = 0, Offset = 3
 Page 0 → Frame 5
 Physical Address = (5 × 4) + 3 = 23

(c) Logical Address = 4

 Page = 1, Offset = 0
 Page 1 → Frame 6
 Physical Address = (6 × 4) + 0 = 24

(d) Logical Address = 13

 Page = 3, Offset = 1
 Page 3 → Frame 2
 Physical Address = (2 × 4) + 1 = 9

Advantages of Paging
 Eliminates external fragmentation
 Allows non-contiguous memory allocation
 Efficient memory utilization

Disadvantage
 Causes internal fragmentation (unused space in last page)
 6. Explain with a neat diagram Segmentation hardware.

Segmentation
Definition

Segmentation is a memory management scheme that supports the user’s logical view of
memory. The user views memory as a collection of variable-sized segments such as code,
data, stack, etc., with no fixed ordering.

Basic Method
 Logical memory is divided into segments.
 Each segment has:
o Segment number (s)
o Segment length
 Logical address is of the form:

< Segment Number , Offset >

 Segments are variable in size.

 Segmentation allows programs to be divided based on logical units, not fixed size
blocks.

Segmentation Hardware Support

Segment Table

 Segment table maps 2-D logical addresses to 1-D physical addresses.

 Each entry in the segment table contains:
o Base → starting physical address of the segment
o Limit → length of the segment
Neat Diagram: Segmentation Hardware

Address Translation Mechanism

1. CPU generates a logical address ⟨s, d⟩.
2. Segment number s is used as an index into the segment table.
3. Offset d is checked against the limit:
o If d ≥ limit → trap to OS (illegal access).
4. If valid:
5. Physical Address = Base + Offset

Example
Segment Base Limit
0 1400 1000
2 4300 400
3 3200 1100

(a) Address ⟨2, 53⟩

 53 < 400 → Valid

 Physical Address = 4300 + 53 = 4353

(b) Address ⟨3, 852⟩

 852 < 1100 → Valid

 Physical Address = 3200 + 852 = 4052

(c) Address ⟨0, 1222⟩

 1222 > 1000 → Invalid

 Trap to Operating System
Advantages of Segmentation
 Matches user’s logical view of memory
 Supports protection and sharing
 No internal fragmentation

Disadvantages
 Suffers from external fragmentation
 Requires compaction

7. Explain Demand Paging with a neat diagram.

Demand Paging
Definition

Demand Paging is a virtual memory management technique in which pages are loaded into
main memory only when they are required for execution. Virtual memory is implemented
using demand paging.

Instead of loading the entire process into memory, only the needed pages are brought into
memory on demand.

Concept of Demand Paging

 Processes reside initially in secondary memory (disk).
 A lazy swapper (pager) loads pages only when referenced.
 A swapper deals with whole processes, whereas a pager works with individual pages.
 This reduces memory usage and improves multiprogramming.

Neat Diagram: Demand Paging System

Handling a Page Fault
When a page fault occurs, the following steps are performed:

1. Trap to the Operating System.

2. Save user registers and process state.
3. Check whether the reference is valid or invalid.
o If invalid → terminate the process.
4. Find a free frame in main memory.
5. Schedule a disk I/O to read the required page.
6. Read the page into the free frame.
7. Update the page table (mark page as valid).
8. Restart the interrupted instruction.

Pure Demand Paging

 A process starts execution with no pages in memory.
 Pages are loaded only when referenced.
 The system continues to fault until all required pages are loaded.
 This approach never preloads pages.

Hardware Support Required

 1. Page Table
o Contains valid–invalid bit.
2. Secondary Memory
o Stores pages not present in main memory.
o Known as swap device and swap space.

Performance of Demand Paging

Let:

 ma = memory access time

 p = probability of page fault

Effective Access Time (EAT)

EAT = (1 − p) × ma + p × page fault service time

Example:

 ma = 200 ns
 Page fault service time = 8 ms = 8,000,000 ns

EAT = 200 + 7,999,800 × p

Performance degrades sharply even for small page fault rates.

Advantages
 Efficient memory utilization
 Reduced I/O overhead
 Supports large virtual address spaces

Disadvantages
 Page faults cause large delays
 Poor performance if page fault rate is high
 May lead to thrashing

[Link] Thrashing with a neat diagram.

Thrashing
Definition
Thrashing is a condition in a computer system where a process (or the system) spends more
time paging (handling page faults) than executing useful instructions.

In thrashing, pages are continuously swapped between main memory and secondary
storage, causing severe performance degradation.

Explanation
 Each process requires a minimum number of frames to execute properly.
 If the number of frames allocated to a process falls below this minimum, the process
starts to page fault frequently.
 Each page fault causes the OS to replace a page, which is soon needed again.
 This leads to a cycle of:
o Page fault → page replacement → another page fault
 As a result, CPU remains idle most of the time, waiting for disk I/O.

This excessive paging activity is called thrashing.

Neat Diagram: Thrashing Effect

CPU Utilization vs Degree of Multiprogramming

 Initially, increasing multiprogramming increases CPU utilization.

 After a point, memory becomes insufficient.
 Page faults increase drastically.
 CPU utilization drops sharply → Thrashing begins.

Causes of Thrashing
1. Insufficient Frames
o Processes do not have enough pages in memory.
2. High Degree of Multiprogramming
o Too many processes competing for limited memory.
3. Global Page Replacement
 Pages are replaced without considering the owning process.
o
4. OS Misinterpretation
o OS sees low CPU utilization and incorrectly adds more processes.

Effects of Thrashing
 Very high page fault rate
 Low CPU utilization
 Excessive disk I/O
 Poor system throughput
 System appears extremely slow

Control and Prevention of Thrashing

1. Reduce Degree of Multiprogramming

 Suspend or swap out some processes.

2. Use Local Page Replacement

 Each process replaces only its own pages.

3. Provide Minimum Frames

 Allocate at least the minimum number of frames required by a process.

4. Working Set Model

 Allocate frames based on the working set size of a process.

5. Page Fault Frequency Control

 Monitor page fault rate and adjust frame allocation.

9. Discuss the following First fit , Best fit , and Worst fit

Memory Allocation Strategies

The Operating System maintains a table that indicates:

 Which parts of memory are occupied

 Which parts are free (holes)

When a process arrives, memory is allocated from the available holes using one of the
following strategies.
1. First Fit
Definition

First Fit allocates the first hole that is large enough to satisfy the request.

Working

 The OS scans memory from:

o the beginning of the hole list, or
o where the previous search ended
 As soon as a suitable hole is found, allocation is done.

Advantages

 Simple and fast

 Less search time
 Good overall performance

Disadvantages

 Leads to many small holes at the beginning of memory

 Causes external fragmentation

Example

Holes: 100 KB, 500 KB, 200 KB

Request: 150 KB
→ Allocated from 500 KB (first suitable hole)

2. Best Fit
Definition

Best Fit allocates the smallest hole that is large enough to satisfy the request.

Working

 Entire list of holes is searched

 The hole with minimum leftover space is chosen

Advantages

 Minimizes wasted memory per allocation

 Produces smallest leftover hole
Disadvantages

 Requires searching the entire list (slow)

 Creates many tiny unusable holes
 Increases external fragmentation

Example

Holes: 100 KB, 500 KB, 200 KB

Request: 150 KB
→ Allocated from 200 KB (best fit)

3. Worst Fit
Definition

Worst Fit allocates the largest available hole.

Working

 Entire hole list is searched

 Largest hole is selected for allocation

Advantages

 Leaves large leftover holes

 Reduces creation of tiny holes

Disadvantages

 Poor memory utilization

 Requires full search of hole list
 Large holes are quickly broken down

MODULE-05
1. Discuss different file access methods.

File Access Methods

A file is a collection of information stored on secondary storage. The Operating System
provides different file access methods to read and write this information efficiently, depending
on usage requirements.
The main file access methods are:

1. Sequential Access
2. Direct (Relative) Access
3. Sequential Indexed (Other) Access Methods

1. Sequential Access
Definition

Sequential access is the simplest file access method, where data is accessed in order, one
record after another.

Characteristics

 File is processed sequentially

 A file pointer keeps track of the current position
 Operations:
o read next → reads the next record
o write next → writes at the end of the file
 File pointer automatically advances after each operation
 File can be reset to the beginning
 Limited forward/backward movement may be allowed

Examples

 Text editors
 Compilers
 Log files

Advantages

 Simple to implement
 Efficient for sequential devices (tapes)
 Low overhead

Disadvantages

 Very slow for random searches

 Not suitable for large databases

Diagram Idea
2. Direct Access (Relative Access)
Definition

Direct access allows random access to any block or record of the file without reading all
preceding records.

Characteristics

 File consists of fixed-length records

 Records are numbered
 Operations:
o read n → reads record number n
o write n → writes record number n
 Block numbers are relative to the beginning of the file
 Based on disk model of file storage

Example

In an airline reservation system:

 Information of flight 713 is stored in block 713

 Seats for flight 713 can be accessed directly

Advantages

 Fast access to any record

 Suitable for large databases
 Efficient searching

Disadvantages

 More complex than sequential access

 Requires fixed-size records

Simulation

 Sequential access can be simulated by maintaining a current position (cp)

  Simulating direct access on sequential files is inefficient

Diagram Idea

3. Indexed Access (Other Access Methods)

Definition

Indexed access uses an index file containing pointers to actual data blocks.

Characteristics

 Index is similar to a book index

 Searching is done in the index first
 Index contains:
o Key values
o Pointers to data blocks
 Supports both:
o Sequential access
o Direct access

Multilevel Indexing

 Large files require large index files

 Solution:
o Index of index (multilevel indexing)
 Primary index → Secondary index → Data blocks

Example: ISAM (Indexed Sequential Access Method)

 Uses a master index pointing to secondary index blocks

 Secondary index points to actual data blocks
 File is sorted on a key
 At most two disk accesses needed to locate a record
Advantages

 Very fast searching

 Efficient for large files
 Supports random and sequential access

Disadvantages

 Extra storage needed for index

 Index maintenance overhead

Diagram Idea

2. What is File ? Explain the file Mounting .

What is a File?

A file is a named collection of related information stored on secondary storage devices such
as disks, SSDs, or magnetic tapes.

File System Mounting

Definition

File system mounting is the process by which the operating system makes a file system
available for access by attaching it to a directory structure.
Need for Mounting

 A file system must be mounted before processes can access it

 Without mounting, files on that device remain inaccessible

Procedure for File System Mounting

1. Specify Device and Mount Point

o OS is given:
 Name of the device
 Location in directory structure called mount point
o Mount point must be an empty directory

Example (UNIX):

/device/dsk mounted at /users

To access user Jane’s directory:

/users/Jane

2. Verification of File System

o OS verifies whether the device contains a valid file system
o This is done using device drivers
3. Mounting the File System
o If verification succeeds, OS attaches the file system to the mount point
o Files in the mounted file system become accessible

Illustration Explanation

 Before mounting: only existing file system files are accessible

 After mounting: the new file system becomes part of the directory tree

Mounting in Different Operating Systems

UNIX / Linux

 Mounting is usually done using explicit mount commands

 Configuration file (/etc/fstab) stores mount information for automatic mounting at
boot time
 Manual mounting is also possible
Windows

 Automatically detects devices

 Mounts all file systems during boot time
 Uses drive letters (C:, D:) instead of mount points
3. Explain the different file allocation methods.

File Allocation Methods

File allocation methods define how disk blocks are assigned to files on secondary storage.
An operating system must efficiently manage disk space and support fast file access.

Major File Allocation Methods

1. Contiguous Allocation
2. Linked Allocation
3. Indexed Allocation

1. Contiguous Allocation
Definition

In contiguous allocation, a file occupies a single continuous set of disk blocks.

Method

 At file creation time, a contiguous block of disk space is allocated.

 File Allocation Table (Directory entry) contains:
o Starting block address
o Length (number of blocks)

Diagram (Conceptual)
Advantages

Simple to implement
Supports sequential access
Supports direct (random) access
Requires only one disk access to read any block

Disadvantages

Suffers from external fragmentation

File size must be known in advance (pre-allocation)
Causes internal fragmentation if file grows slowly
Compaction is required to reclaim space

Modified Contiguous Allocation (Extent-Based)

 Allocate initial contiguous space

 If more space is needed, allocate another contiguous block called an extent
 File is represented as:
o Starting block
o Block count
o Link to next extent

2. Linked Allocation
Definition
In linked allocation, each file is a linked list of disk blocks.
Each block contains a pointer to the next block.

Method

 Disk blocks can be scattered anywhere

 Directory entry contains:
o Pointer to first block
o Pointer to last block

Diagram (Conceptual)

Advantages

No external fragmentation
File size need not be declared in advance
Files can grow dynamically

Disadvantages

Only efficient for sequential access

Direct access is slow (must traverse links)
Pointer overhead wastes space
Reliability issues if a pointer is lost

Improvement: File Allocation Table (FAT)

 FAT is stored at the beginning of disk

  Each disk block has an entry in FAT
 Directory entry points to the first block
 FAT entry points to next block number
Example

File blocks: 217 → 618 → 339 → EOF

FAT[217] = 618
FAT[618] = 339
FAT[339] = EOF

Faster access than pure linked allocation

FAT occupies significant memory for large disks

3. Indexed Allocation
Definition

Each file has a separate index block that contains pointers to all disk blocks of the file.

Method

 Directory entry points to the index block

 Index block contains addresses of file’s data blocks
 ith index entry → ith data block

Diagram (Conceptual)

Advantages
Supports direct access
Supports sequential access
No external fragmentation
File can grow dynamically

Disadvantages

Wasted space if index block is not fully used

Pointer overhead is high
Index block must be kept in memory for fast access

Handling Large Files in Indexed Allocation

a) Linked Index Blocks

 Index block contains pointers to data blocks and pointer to next index block
 Suitable for very large files

b) Multilevel Indexing

 First-level index points to second-level index blocks

 Second-level index points to data blocks
 Can extend to third or fourth level

c) Combined Scheme (UNIX Inode Structure)

 Used in UNIX File System (UFS)

 First 12 pointers → direct blocks
 Next pointer → single indirect
 Next → double indirect
 Last → triple indirect

✔ Efficient for both small and large files

4. List and Explain different goals and protection of an operating system.

Protection in an Operating System

In a multiprogramming operating system, many processes execute concurrently and share

system resources such as CPU, memory, files, and I/O devices.
To prevent unauthorized access, accidental misuse, or malicious damage, the operating
system must enforce protection mechanisms.
Goals of Protection
The main goals of protection in an operating system are:

1. Prevent Unauthorized Access

 Prevents mischievous or intentional violations of access restrictions by users or

processes.
 Ensures that a process cannot interfere with another process’s data or execution.

2. Enforce Correct Resource Usage

 Ensures each program uses system resources strictly according to defined policies.
 Example: A user program should not directly access hardware devices.

3. Improve System Reliability

 Protection helps in detecting latent errors at the interfaces between subsystems.

 Faulty processes are isolated, reducing the risk of system crashes.

4. Distinguish Authorized and Unauthorized Use

 A protection-oriented system clearly differentiates between legal and illegal operations.

 Example: Read-only access vs read-write access.

5. Policy Enforcement

 Provides mechanisms to enforce rules governing resource usage, such as file

permissions and memory access rights.

Principles of Protection
1. Principle of Least Privilege

 A program, user, or system component should be given only the minimum privileges
required to perform its task.
 Reduces damage caused by bugs, failures, or attacks.

Advantages:

 Limits scope of errors

 Improves security
 Enhances system stability

2. Need-to-Know Principle
  A process should access only those resources it currently needs.
 Prevents unnecessary exposure of sensitive resources.

Domain of Protection
Definition

A domain specifies:

 The objects a process may access

 The operations that may be performed on those objects

An access right is the permission to perform a specific operation on an object.

Representation

A domain is represented as:

<object-name, right-set>

Example:

<File F, {read, write}>

A process can read and write file F, but cannot execute or delete it.

Key Points

 Domains may share access rights

 Domains may be static or dynamic
 Dynamic association allows domain switching