Q1) Attempt any Eight of the following:
a) Define bootstrapping.
Sol:
Bootstrapping in computing refers to the process of starting a computer and loading the
operating system into memory. It involves a series of steps executed by the system's
firmware to initialize hardware components and load the initial program (bootstrap loader)
that eventually loads the operating system.
b) Explain POSIX pthread.
Sol:
POSIX (Portable Operating System Interface) pthread (POSIX threads) is a standard for
implementing multithreading in Unix-like operating systems. It defines a set of C
programming language types, functions, and constants for creating and manipulating
threads, ensuring portability across different platforms.
c) What is the role of dispatcher?
Sol:
The dispatcher is a component of the operating system responsible for assigning CPU time
to processes. It switches the CPU from one process to another, manages the execution of
processes, and ensures that processes are allocated fair and efficient use of the CPU.
d) List the solutions to the critical section problem.
Sol:
Solutions to the critical section problem include:
1. Peterson's Algorithm
2. Bakery Algorithm
3. Semaphores
4. Mutex Locks
5. Monitors These solutions ensure mutual exclusion, progress, and bounded waiting.
e) What do you mean by page hit?
Sol:
A page hit occurs when the requested data is found in the main memory (RAM) rather than
requiring access from slower secondary storage. Page hits improve the performance of
memory access operations by reducing the time required to fetch data.
f) What is kernel?
Sol:
The kernel is the core component of an operating system. It manages system resources,
including memory, CPU, and I/O devices, and provides essential services such as process
management, memory management, and device drivers.
g) What is ready queue?
Sol:
The ready queue is a list of processes that are ready to execute and waiting for CPU time.
Processes in the ready queue are in the "Ready" state and are scheduled by the CPU
scheduler.
h) What do you mean by I/O bound process?
Sol:
An I/O bound process is a process that spends more time performing input/output
operations than computational tasks. It is limited by the speed of I/O devices and often
requires frequent waiting for I/O completion.
i) What are the two types of semaphores?
Solution:
The two types of semaphores are:
1. Binary Semaphore: Can take only two values (0 and 1), used for implementing
mutual exclusion (mutex).
2. Counting Semaphore: Can take non-negative integer values, used for managing
access to a resource with a finite number of instances.
j) What is virtual memory?
Sol:
Virtual memory is a memory management technique that allows the execution of
processes that may not be completely in the main memory. It uses disk space as an
extension of RAM, enabling larger programs to run on systems with limited physical
memory.
Q2) Attempt any Four of the following:
a) What is system call? Explain system call related to device manipulation.
Sol:
A system call is a mechanism that provides an interface between user programs and the
operating system. It allows user-level processes to request services and resources from
the OS kernel.
System calls related to device manipulation:
1. open(): Opens a device file for reading, writing, or both.
2. read(): Reads data from a device into a buffer.
3. write(): Writes data from a buffer to a device.
4. ioctl(): Performs device-specific input/output operations and control functions.
b) Write a short note on multilevel queue scheduling.
Sol:
Multilevel queue scheduling is a CPU scheduling algorithm that divides processes into
several separate queues based on their priority or type (e.g., interactive, batch). Each
queue has its own scheduling algorithm, and the scheduler selects processes from these
queues based on predefined policies.
c) Explain producer-consumer problem.
Sol:
The producer-consumer problem is a classic synchronization problem where two types of
processes, producers and consumers, share a fixed-size buffer. Producers add items to the
buffer, and consumers remove items. The challenge is to ensure that producers do not add
to a full buffer and consumers do not remove from an empty buffer.
d) Explain paging in brief.
Sol:
Paging is a memory management technique that divides the process's memory into fixed-
size blocks called pages and the main memory into blocks of the same size called frames.
Pages are loaded into available frames, enabling non-contiguous memory allocation and
reducing fragmentation.
e) Write the difference between pre-emptive and non-preemptive scheduling.
Sol:
Feature Preemptive Scheduling Non-Preemptive Scheduling
Allows the process to be
Process A process runs until it finishes
interrupted and moved to
Interruption or voluntarily yields the CPU.
the ready queue.
Context More context switches, Fewer context switches, less
Switching leading to overhead. overhead.
More responsive to urgent Less responsive to urgent
Responsiveness
tasks. tasks.
Higher risk of starvation for
Starvation Lower risk of starvation.
low-priority processes.
FCFS (First-Come, First-
Round-Robin, Priority
Examples Served), SJF (Shortest Job
Scheduling
First)
Q3) Attempt any Two of the following:
a) What is thread? Explain any two multithreading models in brief with diagram.
Sol:
A thread is the smallest unit of execution within a process. It is a lightweight process that
shares resources with other threads within the same process but executes independently.
Multithreading Models:
1. Many-to-One Model:
o Multiple user-level threads are mapped to a single kernel thread.
o Pros: Efficient thread management, less overhead.
o Cons: One thread blocking causes the entire process to block.
Diagram:
User Threads: T1 T2 T3
\ | | /
\| |/
\| |/
Kernel Thread
2. One-to-One Model:
o Each user-level thread is mapped to a kernel thread.
o Pros: True parallelism on multiprocessor systems, better performance.
o Cons: Higher overhead due to creation of kernel threads for each user
thread.
Diagram:
User Threads: T1 T2 T3
| | |
Kernel Threads: T1 T2 T3
b) Write a short note on logical address and physical address binding with diagram.
Sol:
Logical Address:
• Also known as the virtual address.
• Generated by the CPU during program execution.
• Used as a reference to access memory.
Physical Address:
• Actual location in memory.
• Used by the memory management unit (MMU) to fetch data from physical memory.
Address Binding:
• The process of mapping logical addresses to physical addresses.
• Done at different stages: compile-time, load-time, and execution-time.
Diagram:
Logical Address -> | Address Binding | -> Physical Address
(Generated by CPU) (MMU or OS) (Actual Memory Location)
c) Consider the following set of processes with the length of CPU burst time and
arrival time given in milliseconds. Calculate waiting time, turnaround time for each
process. Also, calculate the average waiting time and average turnaround time using
preemptive priority scheduling.
Burst Arrival
Process Priority
Time Time
P1 14 4 3
P2 5 2 1
P3 6 9 2
P4 5 5 3
P5 9 0 4
Sol:
Gantt Chart: -
| P5 | P2 | P5 | P3 | P5 | P1 | P4 |
0 2 7 9 15 23 27 32
Calculations
Arrival Burst Completion Turnaround Waiting
Process
Time Time Time Time (TAT) Time (WT)
P1 4 14 27 23 9
P2 2 5 7 5 0
P3 9 6 15 6 0
P4 5 5 32 27 22
P5 0 9 23 23 14
Average Turnaround Time (Avg TAT):
Avg TAT = 23 + 5 + 6 + 27 + 23 / 5 = 84 / 5 = 16.8
Average Waiting Time (Avg WT):
Avg WT = 9 + 0 + 0 + 22 + 14 / 5 = 45 / 5 = 9
Q4) Attempt any Two of the following:
a) Define process. Explain process state diagram in brief.
Sol:
A process is a program in execution. It is an active entity that includes the program code,
current activity, and the process control block (PCB). A process goes through several states
during its lifecycle.
Process State Diagram:
States:
1. New: The process is being created.
2. Ready: The process is waiting to be assigned to a processor.
3. Running: Instructions are being executed.
4. Blocked (or Waiting): The process is waiting for some event to occur (such as I/O
completion).
5. Terminated: The process has finished execution.
Transitions:
• Admit: Moving from New to Ready.
• Dispatch: Moving from Ready to Running.
• I/O or Event Wait: Moving from Running to Blocked.
• I/O or Event Completion: Moving from Blocked to Ready.
• Exit: Moving from Running to Terminated.
b) Explain the reader-writer problem in brief.
Sol:
The reader-writer problem is a classic synchronization problem that involves a shared
resource being accessed by multiple readers and writers. The challenge is to ensure that
readers can read the resource simultaneously, but writers must have exclusive access to
modify the resource.
Types:
1. First Reader-Writer Problem:
o Ensures no reader is kept waiting unless a writer has already acquired the
resource.
o May lead to writer starvation if readers keep coming in.
2. Second Reader-Writer Problem:
o Ensures no writer is kept waiting for the resource once it has requested
access.
o May lead to reader starvation if writers keep coming in.
Solution Using Semaphores:
1. Semaphore rw_mutex: Ensures mutual exclusion for writers.
2. Semaphore mutex: Ensures mutual exclusion for updating the reader count.
3. Integer read_count: Keeps track of the number of readers currently accessing the
resource.
Example Code:
semaphore rw_mutex = 1;
semaphore mutex = 1;
int read_count = 0;
void reader() {
wait(mutex);
read_count++;
if (read_count == 1) wait(rw_mutex);
signal(mutex);
// Reading section
wait(mutex);
read_count--;
if (read_count == 0) signal(rw_mutex);
signal(mutex);
void writer() {
wait(rw_mutex);
// Writing section
signal(rw_mutex);
}
c) Consider a reference string 3, 2, 1, 0, 3, 2, 4, 3, 2, 1, 0, 4. No. of frames = 3. Find out
the number of page faults using:
• i) LRU
• ii) OPT
Sol:
1. LRU (Least Recently Used) Page Replacement Algorithm:
o Reference String: 3, 2, 1, 0, 3, 2, 4, 3, 2, 1, 0, 4
o Frames: 3
Page Faults Calculation:
Reference | Frames | Page Fault
------------------------------------
3 |3 | Page Fault
2 |32 | Page Fault
1 |321 | Page Fault
0 |021 | Page Fault
3 |023 | Page Fault
2 |023 |
4 |423 | Page Fault
3 |423 |
2 |423 |
1 |421 | Page Fault
0 |021 | Page Fault
4 |024 | Page Fault
Total Page Faults (LRU) = 8
2. OPT (Optimal) Page Replacement Algorithm:
o Reference String: 3, 2, 1, 0, 3, 2, 4, 3, 2, 1, 0, 4
o Frames: 3
Page Faults Calculation:
Reference | Frames | Page Fault
------------------------------------
3 |3 | Page Fault
2 |32 | Page Fault
1 |321 | Page Fault
0 |021 | Page Fault
3 |321 | Page Fault
2 |321 |
4 |324 | Page Fault
3 |324 |
2 |324 |
1 |124 | Page Fault
0 |120 | Page Fault
4 |420 | Page Fault
Total Page Faults (OPT) = 8
Q5) Attempt any One of the following:
a) Explain layered operating system in brief with diagram.
Sol:
A layered operating system is structured in layers, where each layer performs a specific set
of functions. The system is designed to simplify implementation, debugging, and
maintenance by ensuring that each layer interacts only with the layers directly above and
below it.
Layers (from bottom to top):
1. Hardware: The physical components of the computer system.
2. Kernel: The core layer responsible for low-level tasks such as process management,
memory management, and I/O operations.
3. System Calls: Interface between the kernel and user programs, providing a way for
applications to request services from the operating system.
4. Utility Programs: Programs that provide system services, such as file management,
network communication, and security tools.
5. User Applications: End-user programs, such as web browsers, office suites, and
games.
Advantages:
1. Modularity: The system is divided into layers, each with a specific function, making
it easier to manage.
2. Abstraction: Each layer hides the complexity of the layers below, simplifying
interactions.
3. Maintainability: Bugs and issues can be isolated and addressed within specific
layers without affecting the entire system.
Disadvantages:
1. Overhead: The abstraction and additional interfaces between layers can introduce
performance overhead.
2. Complexity: Designing and managing interactions between layers can be complex.
Diagram: -
+------------------------+
| User Applications |
+------------------------+
| Utility Programs |
+------------------------+
| System Calls |
+------------------------+
| Kernel |
+------------------------+
| Hardware |
+------------------------+
b) Explain first fit, best fit, worst fit, next fit algorithm.
Sol:
Memory Allocation Algorithms:
1. First Fit:
o Allocates the first block of memory that is large enough to satisfy the request.
o Example:
Memory Blocks: 100 KB, 500 KB, 200 KB, 300 KB
Request: 150 KB
Allocation: 200 KB block
2. Best Fit:
o Allocates the smallest block of memory that is large enough to satisfy the request,
minimizing wasted space.
o Example:
Memory Blocks: 100 KB, 500 KB, 200 KB, 300 KB
Request: 150 KB
Allocation: 200 KB block
3. Worst Fit:
o Allocates the largest block of memory available, leaving the largest possible
remaining hole.
o Example:
Memory Blocks: 100 KB, 500 KB, 200 KB, 300 KB
Request: 150 KB
Allocation: 500 KB block
4. Next Fit:
o Similar to the first fit but starts searching from the last allocated block rather than
the beginning.
o Example:
Memory Blocks: 100 KB, 500 KB, 200 KB, 300 KB
Request: 150 KB
Allocation: 200 KB block (if the last allocation was before it)