Schedulers in Operating System

A scheduler is a part of the operating system that selects processes for execution in a particular
order.
It decides which process runs, when, and how long, ensuring efficient CPU and memory
utilization.

There are three types of schedulers:

Long-term Scheduler (Job Scheduler)

• Function: Controls the admission of new processes into the system for processing.

• It selects jobs from the job pool on the disk and loads them into main memory for
execution.

• Controls the degree of multiprogramming (number of processes in memory).

• Runs less frequently (e.g., when a new process is created).

• Decides: Which processes are to be brought into memory.

Medium-term Scheduler (Swapper)

• Function: Responsible for swapping processes in and out of main memory.

• Temporarily removes (suspends) processes from memory to free space and improve
performance.

• Later, it resumes (swaps in) the suspended process back to main memory for execution.

• Used in systems with medium-term scheduling policies (like time-sharing systems).

• Runs occasionally, based on memory load and process behavior.

Short-term Scheduler (CPU Scheduler)

• Function: Selects one process from the ready queue and allocates the CPU to it.

• Runs very frequently (every few milliseconds).

• Responsible for context switching between processes.

• Uses various CPU scheduling algorithms like FCFS, SJF, Round Robin, and Priority
scheduling.

• Should be fast and efficient since it directly affects system performance.

e) Define Independent and Dependent Processes.

Independent Process:
A process that does not share data or resources with any other process.

• Execution of one does not affect another.

• Example: Two separate programs running independently.

Dependent (Cooperating) Process:

A process that shares data, resources, or communicates with other processes.

• Execution of one affects or depends on others.

• Example: Producer–Consumer problem.

Q3 4 marks each

a) Multithreading Models in Operating System

Definition:
Multithreading allows a process to have multiple threads running concurrently, sharing the
same code, data, and resources — but each having its own register set and stack.

To manage threads efficiently, the relationship between user threads and kernel threads is
defined using multithreading models.

Types of Multithreading Models

Many-to-One Model

• Many user threads → One kernel thread.

• Thread management is done in user space.

• Disadvantage: If one thread makes a blocking system call, entire process blocks.

• Used in: Older systems like Green Threads in Solaris.

One-to-One Model

• Each user thread → One kernel thread.

• Allows true parallelism on multiprocessor systems.

• Disadvantage: Creating a large number of threads causes overhead (each needs a kernel
thread).

• Used in: Windows, Linux.

Many-to-Many Model
 • Many user threads → Mapped to a smaller or equal number of kernel threads.

• Combines advantages of both previous models.

• OS can schedule kernel threads efficiently while user space manages multiple user
threads.

• Used in: Solaris 9, Windows with ThreadFiber package.

b) Which three requirements must be satisfied while designing a solutions to the critical
section problem? Explain in detail.

A critical section is a part of the program where shared resources (like variables, files, or data
structures) are accessed.
To prevent race conditions, only one process must execute its critical section at a time.

To design a correct solution to this problem, three requirements must be satisfied:

Mutual Exclusion

• Only one process can be inside its critical section at any given time.

• If one process is executing in the critical section, no other process can enter.

Progress

• If no process is in the critical section, and some wish to enter, only those not in
remainder section should decide who enters next.

• The decision should not be postponed indefinitely.

Bounded Waiting (No Starvation)

• There must be a limit on how long a process waits before it can enter its critical section.

• Ensures fairness — every process gets a chance eventually.

a) Process Control Block (PCB)

-A Process Control Block (PCB) is a data structure used by the operating system to store all
the essential information about a process.

-It helps the OS keep track of each process during execution and switching.
 -Every process has its own PCB, created when the process starts and deleted once it
terminates.

The PCB contains several important fields such as :

process ID (PID): uniquely identifies the process.

process state: showing whether it is new, ready, running, waiting, or terminated.

program counter: which stores the address of the next instruction to be executed

CPU registers: which save the process’s temporary data during execution.

In addition, the PCB holds memory management information, It also stores accounting
information such as CPU usage, process priority, and execution time, along with I/O status
information.

During context switching, the OS saves the current process’s PCB and loads the next process’s
PCB so that execution can resume smoothly from where it was left . Thus, PCB plays a key role in
process management and multitasking within an operating system.

b) Bounded Buffer Problem

-The Bounded Buffer Problem, also known as the Producer–Consumer Problem, is a classic
example of a synchronization issue in operating systems.

-In this problem, two processes—the producer and the consumer—share a common, finite-size
buffer. The producer’s job is to generate data items and place them into the buffer, while the
consumer removes and uses those items.

-The problem arises because both processes must not access the buffer simultaneously in a
conflicting way.

-The producer should wait if the buffer is full, and the consumer should wait if the buffer is
empty. To handle this safely, synchronization tools like semaphores are used.
By using these semaphores, the system avoids problems such as race conditions, buffer
overflow, and underflow, ensuring that the producer and consumer work together smoothly
without interfering with each other.

Q 3marks

b) Segmentation in Operating System

-Segmentation is a memory management technique that divides a process into variable-sized

segments, such as code, data, and stack.

-Each segment represents a logical unit of the program rather than fixed-size pages.

Every segment has a base address and a limit stored in the segment table. The base holds the
starting address of the segment in main memory, and the limit specifies the segment’s length.

When a program references a memory location, the logical address (segment number, offset) is
translated into a physical address using the formula:

Physical Address = Base + Offset

Segmentation is efficient because it reflects the logical structure of programs, supports

protection and sharing, and minimizes internal fragmentation.

April 2023:

1 marks:
b) What is a Thread?

A thread is the smallest unit of CPU execution within a process. Multiple threads in a process
share the same memory and resources but run independently, enabling faster and concurrent
execution.

c) List Types of System Calls.

The main types of system calls are:

1. Process control (create, terminate).

2. File management (open, read, write).

3. Device management (request, release).

4. Information maintenance (get/set attributes).

5. Communication (send, receive messages).

d) Role of Medium-Term Scheduler.

The medium-term scheduler temporarily removes (suspends) processes from memory and
moves them to secondary storage, freeing memory for other processes. It later swaps them
back into ready state when resources are available.

e) What is CPU–I/O Burst Cycle?

The CPU–I/O burst cycle represents the alternating behavior of a process: periods of CPU
execution (CPU burst) followed by periods of waiting for I/O operations (I/O burst). Most
processes repeatedly switch between these two states.

g) Define Response Time.

Response time is the total time interval between submitting a request and receiving the first
response from the system. It is a key measure of performance in interactive systems.

i) What is Page Table?

A page table is a data structure used in paging systems to map logical (virtual) addresses to
physical memory addresses. Each entry in the table stores the frame number where the page is
located in main memory.
j) What is Segmentation?

Segmentation is a memory management technique where a process is divided into variable-

sized logical units called segments (like code, data, and stack). Each segment has its own base
and limit stored in the segment table.

2 marks:

a) What is Operating System? List Objectives of Operating System.

An Operating System (OS) is a system software that manages computer hardware and software
resources and provides services to users and applications.

Objectives:

1. To provide an easy and user-friendly interface between user and hardware.

2. To manage resources efficiently (CPU, memory, I/O).

3. To ensure system security and stability.

4. To enable multitasking and maximize performance.

b) Define Critical Section Problem. Explain in Detail.

The Critical Section Problem occurs when multiple processes access shared resources (like
variables or files) at the same time, which may cause race conditions.

The goal is to design a protocol that allows only one process to execute its critical section at a
time while satisfying:

• Mutual Exclusion: Only one process in the critical section.

• Progress: No unnecessary waiting if section is free.

• Bounded Waiting: Every process gets a fair chance.

c) Compare LFU and MFU (Two Points).

d) What is the Purpose of Scheduling Algorithm?

The purpose of a scheduling algorithm is to determine the order in which processes will execute
in the CPU to achieve efficient utilization. It aims to maximize CPU usage, minimize waiting and
turnaround time, and ensure fairness among all processes.

4 marks:

a) Process States (with Diagram)

c) Requirements for Critical Section Problem

A critical section is a part of the program where a shared resource is accessed. To prevent errors
like race conditions, only one process should be in its critical section at a time.

For an effective solution, the following three requirements must be satisfied:

1. Mutual Exclusion:
Only one process can be inside its critical section at any moment. If one process is
executing in its critical section, others must wait.
Example: If Process P1 is modifying a shared variable, Process P2 must not access it
simultaneously.

2. Progress:
If no process is in its critical section and some wish to enter, the selection of which
process enters next should not be delayed indefinitely. Only processes not in the
remainder section can participate in the decision.
Meaning: The system must allow fair progress and avoid unnecessary waiting.

3. Bounded Waiting:
A limit must exist on how long a process waits before it can enter its critical section. This
ensures fairness and prevents starvation.
Meaning: Every process eventually gets a turn to enter the critical section.
Disadvantages of Distributed Operating System:

1. Complexity:
Distributed systems are more complex to design and manage because they involve
coordination among multiple computers and communication over networks.

2. Security Issues:
Data is transmitted across networks, making the system more vulnerable to hacking,
unauthorized access, and data breaches.

3. High Setup and Maintenance Cost:

Requires multiple interconnected systems, high-speed networks, and skilled
administration — all of which increase cost.

3 marks
Swapping

Swapping is a memory management technique in which a process is temporarily moved from

the main memory (RAM) to the secondary storage (disk) and later brought back into memory
for execution.

This is done to free up memory space and allow multiple processes to share the CPU efficiently.

Working:

• When main memory is full, the OS selects an idle (waiting) process and swaps it out to
the disk.

• When that process is needed again, it is swapped back in to main memory.

• The CPU can then resume its execution from the same point.

Advantages:

• Allows better CPU utilization.

• Helps in executing more processes than the available physical memory.

Disadvantage:

• Frequent swapping causes high I/O overhead and increased response time.
April 2022:

1 marks

b) POSIX Pthread:

POSIX Pthread (Portable Operating System Interface Threads) is a standard API used for
creating and managing threads in UNIX/Linux systems. It allows concurrent execution within
a process.

d) Solutions to Critical Section Problem:

1. Peterson’s Solution

2. Bakery Algorithm

3. Hardware-based solutions (Test-and-Set, Swap)

4. Semaphore and Monitor solutions

e) Page Hit:

A page hit occurs when the required page is already present in main memory, so the CPU
can access it without a page fault.

f) Kernel:

The kernel is the core part of the operating system that manages CPU, memory, devices,
and system calls between hardware and software.

g) Ready Queue:

A ready queue holds all processes that are loaded in main memory and waiting for CPU
execution.
 i) Types of Semaphores:

1. Counting Semaphore

2. Binary Semaphore (Mutex)

j) Virtual Memory:

Virtual memory is a technique that gives an illusion of a large main memory by using a part
of the disk as memory space.

2 marks

a) What is System Call? Explain system calls related to device manipulation.

A system call is a way for a user program to request a service from the operating system’s
kernel, such as file handling or device control.

Device manipulation system calls are used for controlling hardware devices. Examples include:

• read() – to read data from a device.

• write() – to send data to a device.

• ioctl() – to control device operations (e.g., changing device parameters).

b) Write short note on Multilevel Queue Scheduling.

Multilevel Queue Scheduling divides the ready queue into multiple queues based on process
types, such as foreground (interactive) and background (batch).

• Each queue has its own scheduling algorithm (e.g., RR for foreground, FCFS for
background).

• Processes are permanently assigned to one queue.

• CPU is allocated among queues based on fixed priority or time slices.

c) Explain Producer–Consumer Problem.

The Producer–Consumer Problem is a classic synchronization problem where:

 • The producer generates data and places it in a buffer.

• The consumer removes data from the buffer.

• Synchronization ensures the producer doesn’t add data when buffer is full and the
consumer doesn’t remove data when buffer is empty.

• Semaphores or mutex locks are used to solve this problem.

d) Explain Paging in brief.

Paging is a memory management technique that divides the logical memory and physical
memory into fixed-size blocks called pages and frames, respectively.

• The page table maps logical pages to physical frames.

• It eliminates external fragmentation and allows non-contiguous memory allocation.

4 marks

Logical and Physical Address Binding

Definition:
When a program is executed, addresses used by the program are called logical (virtual)
addresses, and the actual addresses in the main memory are called physical addresses.
The process of mapping logical addresses to physical addresses is known as address binding.

Types of Address Binding:

1. Compile-time Binding:

o Occurs when memory location is known at compile time.

o If the location changes, the program must be recompiled.

2. Load-time Binding:

o Binding is done when the program is loaded into memory.

o The loader relocates addresses before execution.

3. Execution-time (Run-time) Binding:

o Done by the Memory Management Unit (MMU) at run-time.

 o Allows a process to move in memory during execution.

Reader–Writer Problem

The Reader–Writer Problem is a classic synchronization problem that deals with a shared
resource (like a file or database) that can be accessed by multiple readers and writers. The main
goal is to ensure that data consistency is maintained when multiple processes try to read and
write simultaneously.

• Readers are processes that only read the data and do not make changes, so multiple
readers can read at the same time without conflict.

• Writers are processes that modify the data, so only one writer should access the shared
resource at a time.

• When a writer is writing, no reader or writer should be allowed to access the resource
to avoid inconsistency.

• The main challenge is to synchronize readers and writers to prevent data inconsistency
and starvation (when one group gets delayed for too long).

To solve this problem, semaphores are used. Three semaphores are commonly used —

1. mutex to protect the reader count variable,

2. wrt to ensure mutual exclusion for writers, and

3. a counter readcount to keep track of how many readers are reading.

3 marks:
a) Layered Operating System (with diagram)

A Layered Operating System is organized in the form of hierarchical layers, where each layer is
built on top of the lower one.
Each layer performs specific functions and communicates only with the layer directly below or
above it.
This design helps in modularity, debugging, and easy maintenance of the system.

Working:

• The bottom layer interacts directly with hardware.

• The middle layers handle device drivers, memory, and process management.

• The top layer provides user-level programs and system calls.

Advantages:

• Easy to debug and modify.

• Enhances system security and reliability.

Diagram:

b) First Fit, Best Fit, Worst Fit, and Next Fit Algorithms

These are memory allocation techniques used in contiguous memory management to assign
processes to free memory blocks (holes).

1. First Fit:

o Allocates the first available block that is large enough.

 o Simple and fast but may cause fragmentation.

2. Best Fit:

o Allocates the smallest block that is large enough to reduce wasted space.

o Slower due to searching for the best match.

3. Worst Fit:

o Allocates the largest available block, leaving large leftover spaces.

o Aims to avoid small unusable holes but often leads to wastage.

4. Next Fit:

o Similar to First Fit, but instead of starting from the beginning, it continues
searching from the last allocated position.

o Reduces search time and spreads memory usage evenly.

Oct 2024

Q) 1 marks

1. What is Batch Operating System?

A Batch Operating System groups similar jobs together and executes them sequentially without
user interaction. The jobs are processed in batches to increase CPU utilization.

2. List any two advantages of Multithreaded Programming.

• Increases CPU utilization by running multiple threads concurrently.

• Improves application performance through parallel execution.

3. Define Dispatch Latency.

Dispatch latency is the time taken by the CPU scheduler to stop one process and start another,
i.e., the delay in context switching.

4. “Counting Semaphore can be implemented by using Binary Semaphore”. True/False. Justify.

 True.
A counting semaphore can be implemented using multiple binary semaphores and counters to
manage access to a finite number of resources.

5. Define Logical Address Space.

Logical address space is the set of all logical (virtual) addresses generated by a program’s CPU
during execution, before being mapped to physical memory.

6. Define Spooling.

Spooling (Simultaneous Peripheral Operations On-Line) is a technique where data is temporarily

stored in a buffer to coordinate input/output operations (e.g., print spooling).

7. What is Ready Queue?

The Ready Queue is a list of all processes that are loaded in main memory and waiting to be
assigned to the CPU for execution.

8. What will happen if all processes are I/O bound in the system?

If all processes are I/O bound, the CPU remains idle most of the time while processes wait for
I/O operations to complete, reducing CPU utilization.

9. Define Semaphore.

A Semaphore is a synchronization tool used to control access to a shared resource by multiple

processes in a concurrent system.

10. List various dynamic memory allocation methods.

• First Fit

• Best Fit

• Worst Fit
 • Next Fit

Q) 2 marks

a) What is Page Table? What are its contents?

A Page Table is a data structure used by the operating system to map logical (virtual) addresses
to physical addresses in memory.
It keeps track of where each page of a process is stored in main memory.

Contents of Page Table:

• Page Number: Index of the page in logical memory.

• Frame Number: Corresponding physical frame in memory.

• Control Bits: Include valid/invalid bit, protection bit, and dirty bit for access control.

b) What is Critical Section Problem?

The Critical Section Problem is a synchronization problem that occurs when multiple processes
access and modify a shared resource concurrently.
The goal is to ensure that only one process executes in the critical section at a time to maintain
data consistency.
A correct solution must satisfy mutual exclusion, progress, and bounded waiting conditions.

c) What is Pre-emptive and Non-preemptive Scheduling?

• Pre-emptive Scheduling:
The CPU can be taken away from a running process and assigned to another process
with higher priority or better scheduling criteria.
Example: Round Robin, SJF (preemptive).

• Non-preemptive Scheduling:
Once a process starts execution, it runs until completion or waiting state; the CPU
cannot be taken forcibly.
Example: FCFS, SJF (non-preemptive).

d) Explain the Functions Performed by Dispatcher.

The Dispatcher is responsible for giving control of the CPU to the process selected by the short-
term scheduler.
Its functions include:

1. Context Switching – Saving and restoring process states.

2. Switching to user mode from kernel mode.

3. Jumping to the proper program location in the user program to restart execution.
It ensures smooth CPU handover between processes.

e) Write the Advantages of Microkernel.

1. Modularity: Easier to maintain and extend since each service (file, memory, process)
runs separately in user mode.

2. Reliability: Failure in one service does not crash the entire system.

3. Security: Less code runs in kernel mode, reducing vulnerabilities.

4. Portability: Easier to adapt to new hardware due to minimal kernel design.

Q)4 marks

c) Differentiate between Internal and External Fragmentation

Definition:
Fragmentation occurs when memory is used inefficiently, leading to wasted space. It is of two
types: Internal and External Fragmentation.

Basis Internal Fragmentation External Fragmentation

Occurs when fixed-sized memory blocks Occurs when free memory is scattered
are allocated, and a process does not into small non-contiguous blocks, making
Meaning
use the entire allocated space, leaving it difficult to allocate memory to new
unused space inside the block. processes.

Fixed-size partitions cause unused space Variable-size partitions cause free space
Cause
inside allocated blocks. between allocated blocks.
Basis Internal Fragmentation External Fragmentation

Memory
Wastage occurs within a partition. Wastage occurs between partitions.
Wastage

Can be reduced by using smaller Can be reduced by compaction or using

Solution
partition sizes. paging/segmentation.

Process of 18 KB in a 20 KB block → 2 KB Multiple small free blocks of 5 KB each

Example
wasted inside block. cannot fit a 15 KB process.

Q) 3 mark

a) What is System Call? Explain System Calls for Process and Job Control

A System Call is a mechanism that allows a user-level program to request a service from the
operating system’s kernel, such as process creation, file handling, or device control.
It acts as an interface between user programs and the OS.

System Calls for Process and Job Control:

These system calls manage the creation, execution, and termination of processes. Common
examples include:

1. fork() – Used to create a new process by duplicating the parent process.

2. exec() – Replaces the current process with a new program.

3. wait() – Makes a process wait until its child process finishes execution.

4. exit() – Terminates the currently running process.

5. getpid() and getppid() – Return the process ID and parent process ID.

These system calls together help the OS handle process creation, execution, synchronization,
and termination efficiently.
b) Explain Swapping in Detail

Swapping is a memory management technique in which entire processes are moved between
main memory and secondary storage (like a hard disk) to optimize CPU utilization.
When the main memory becomes full, inactive or waiting processes are swapped out to the
disk, and when required, they are swapped back in.

Steps in Swapping:

1. The OS selects an idle or waiting process and transfers it from main memory to
secondary storage (swap space).

2. When that process becomes ready to execute again, it is brought back into main
memory.

3. The CPU can then resume its execution from where it left off.

Advantages:

• Allows multiprogramming, as more processes can reside in the system.

• Increases CPU utilization by keeping the CPU busy while other processes wait in
secondary memory.

Diagram