UNIVERSITY OF NAIROBI

FEE 3232: COMPUTER SYSTEMS ENGINEERING

TAKE-AWAY CAT SOLUTIONS

QUESTION 1: PROCESS MANAGEMENT

a) Consider a scenario where a computer system is running multiple processes
simultaneously. Describe how the operating system manages these processes in terms
of process scheduling, process creation, and termination.

In a computer system running multiple processes simultaneously, the OS plays a crucial

role in managing these processes efficiently. The OS handles process
scheduling, process creation, and termination through a series of sophisticated
mechanisms and algorithms.

Process scheduling involves deciding which process runs at any given time. The
primary goals are to maximize CPU utilization, ensure fair process allocation, and meet
system performance criteria. The OS employs various scheduling algorithms,
including:
• Processes are executed in the order they arrive.
• Processes with the shortest execution time are scheduled next. This minimizes
average waiting time but requires knowing execution times in advance.
• Each process gets a small, fixed amount of CPU time (time slice or quantum). After
this time, the process is moved to the back of the queue if it’s not finished, providing
a fair time-sharing system.
• Processes are assigned priorities, and the process with the highest priority is
executed first. This can be pre-emptive (the current process can be interrupted if a
higher priority process arrives) or non-pre-emptive.
• Processes are divided into queues based on priority or type (interactive, batch), and
each queue has its own scheduling algorithm.

Process creation is initiated through system calls, typically by a running process. The
parent process creates a child process, which may run concurrently with the
parent. Key steps in process creation include:
• Fork: The fork() system call in Unix/Linux creates a new process by duplicating
the calling process. The new process, called the child process, gets a unique process
identifier (PID).
• Exec: The exec() system call replaces the current process memory space with a new
program. This is often used after a fork by the child process to run a different
program than the parent.

Page 1 of 9
 • Process Control Block (PCB): When a process is created, the OS constructs a PCB
containing information about the process state, PID, program counter, CPU
registers, memory management information, and I/O status.
• Resource Allocation: The OS allocates necessary resources (memory, I/O, etc.) to
the new process.

Process termination is the process of ending a running process. Termination can occur
when:
• The process completes its execution and exits voluntarily using an exit system call
(e.g., exit() in Unix/Linux).
• The process encounters an error (e.g., division by zero, invalid memory access)
and is terminated by the OS.
• One process can terminate another process using system calls like kill() in
Unix/Linux. This often requires appropriate permissions.
• If a parent process terminates, the OS may terminate all its child processes
depending on the implementation.

b) Discuss how a process communicates with the operating system and other processes
using system calls and inter-process communication mechanisms such as pipes and
shared memory.

System calls provide a controlled interface for processes to request services from the
OS kernel. These services include file operations, process control, and communication.
System calls act as a bridge between user space (where applications run) and kernel
space (where the OS operates). Examples of common system calls include:

File Operations: open(), read(), write(), close()

When a process makes a system call, it triggers a context switch from user mode to
kernel mode, allowing the OS to execute the requested service. After completing the
service, control is returned to the user mode.

Inter-process communication (IPC) mechanisms enable processes to exchange data

and synchronize their actions. The primary IPC mechanisms include pipes, shared
memory, message queues, and semaphores.

i) Pipes
Pipes are used for unidirectional communication between processes. There are two
main types of pipes:
a) Anonymous Pipes: Used for communication between a parent and child process.
b) Named Pipes (FIFOs): Allow communication between unrelated processes.

ii) Shared Memory

Shared memory allows multiple processes to access a common memory segment. It is
the fastest form of IPC because processes can directly read and write to the memory.

Page 2 of 9
 Synchronization mechanisms like semaphores are often used with shared memory to
prevent race conditions.

iii) Message Queues

Message queues allow processes to exchange messages in a queued manner. Message
queues are suitable for complex communication scenarios where messages need to be
prioritized.

iv) Semaphores
Semaphores are used for signaling and controlling access to shared resources. They
can synchronize processes by ensuring that only a specific number of processes can
access a resource at a time.

QUESTION 2: MEMORY MANAGEMENT

a) Imagine a computer system with limited physical memory but a large virtual address
space. Explain how the operating system manages memory allocation and addresses
the challenges of fragmentation.

The OS employs virtual memory to efficiently manage the limited physical memory
while providing a larger virtual address space to processes. Virtual memory allows
processes to use more memory than physically available by using disk space as an
extension of RAM.

The key principles in virtual memory management include:

i) Paging:
• Memory is divided into fixed-size blocks called pages.
• Physical memory is divided into frames of the same size as pages.
• Virtual addresses are translated to physical addresses via a page table that maps
virtual pages to physical frames.
ii) Page Tables:
• Each process has its own page table.
• Page tables keep track of the mapping between virtual pages and physical
frames.
• Entries in the page table include the frame number and status bits (e.g.,
valid/invalid, dirty, access permissions).
iii) Page Replacement Algorithms:
• When a process accesses a page not currently in physical memory (a page fault),
the OS must load the page from disk into RAM.
• If RAM is full, the OS uses a page replacement algorithm to decide which page
to swap out.

Fragmentation occurs in two forms: internal and external.

Internal Fragmentation occurs when allocated memory blocks have unused space,
typically because of fixed-size allocation units (pages or frames).

Page 3 of 9
 Solution: Since paging uses fixed-size pages and frames, internal fragmentation is
minimal but can be managed by ensuring the page size is appropriately chosen for the
typical workload.

External Fragmentation occurs when free memory is scattered in small blocks

between allocated blocks, making it difficult to allocate contiguous memory.

Solution: Paging inherently eliminates external fragmentation since any free frame can
be allocated to any page. However, for systems using both paging and segmentation,
the OS must manage external fragmentation within segments.

b) Consider a scenario where a program requires more memory than is available in

physical memory. Describe how the operating system handles this situation using
techniques such as paging and swapping.

When physical memory is scarce, the OS uses swapping and demand paging:
• Swapping: Entire processes are swapped in and out of physical memory to and from
disk. This method is less efficient than paging due to the large size of process images.
• Demand Paging: Only the necessary pages of a process are loaded into physical
memory, reducing the overhead of loading entire processes. Pages are brought into
memory on demand when accessed by the process.

QUESTION 3: FILE SYSTEM MANAGEMENT

a) Suppose a user wants to create a new file and store data in it. Describe the sequence of
operations performed by the operating system, starting from the user's request to the
actual storage of data on disk.

When a user wants to create a new file and store data in it, the OS performs a sequence
of operations to fulfill this request. Here’s a detailed breakdown of these operations:

1. User Request
The user initiates the process, typically through an application or command-line
interface, by invoking a command or using an API to create a file and write data to it.
2. System Call
The application makes a system call to the OS to create a new file. In Unix/Linux, this
might be done using the open() system call with the appropriate flags, or a higher-level
call like fopen() in C.
3. File System Handling
The OS's file system component processes the system call to create the file:
4. File Descriptor Allocation
The OS allocates a file descriptor to the process. The file descriptor is an integer that
uniquely identifies the open file within the process. This file descriptor will be used for
subsequent read/write operations.
5. Writing Data

Page 4 of 9
 The user or application then writes data to the file using system calls like write() or
through higher-level APIs like fprintf().
6. Data Handling by the OS
When the write() system call is made, the OS performs the following steps: buffering,
block allocation, updating file metadata.
7. Actual Data Storage
The OS eventually writes the buffered data to the physical disk. This can happen
immediately or be delayed depending on the file system's write policy (e.g., write-
through, write-back).
8. Closing the File
Once the data is written, the user or application typically closes the file using the close()
system call:

b) Consider a scenario where multiple users are accessing and modifying the same file
simultaneously. Discuss how the operating system ensures data consistency and
handles file locking to prevent conflicts.
When multiple users access and modify the same file simultaneously, the operating system
must ensure data consistency and manage file locking to prevent conflicts. This involves
several mechanisms and strategies to synchronize access to the file and avoid issues like
race conditions, data corruption, and inconsistencies.
File locking is a primary technique used by the OS to manage concurrent access to files.
Locks can be classified as either advisory or mandatory:
1. Advisory Locking: Locks are respected by programs that explicitly check for them. If
a process does not check for locks, it can still access the file.
2. Mandatory Locking: Locks are enforced by the OS, preventing any access that
conflicts with the lock, regardless of whether the program checks for locks.
Here’s how the OS typically handles file locking to ensure data consistency:
1. Request Lock: A process requests a lock on a file using system calls.
2. Check for Conflicts: The OS checks if the requested lock conflicts with any existing
locks. For an exclusive lock, it checks if any shared or exclusive locks exist. For a
shared lock, it checks if any exclusive locks exist.
3. Grant or Block Access: If no conflicts are found, the lock is granted, and the process
proceeds with its operations. If conflicts are found, the requesting process is blocked
until the conflicting lock is released (for blocking locks) or immediately fails (for non-
blocking locks).
4. Perform File Operations: Once the lock is acquired, the process performs the
necessary read or write operations. During this period, other processes are blocked from
performing conflicting operations, ensuring data consistency.
5. Release Lock: After completing the file operations, the process releases the lock.

Page 5 of 9
QUESTION 4: INPUT/OUTPUT MANAGEMENT
a) Imagine a computer system with multiple I/O devices such as keyboards, mice, and
printers. Explain how the operating system coordinates I/O operations from different
devices using interrupt-driven I/O and device drivers.
In an interrupt-driven I/O system, the CPU is not actively involved in waiting for I/O
operations to complete. Instead, when an I/O device needs attention (e.g., data transfer is
complete or a new input is available), it raises an interrupt signal to the CPU. Here's how the
process works:
1. Device Initialization: The OS initializes I/O devices during system boot-up or when
they are connected to the system. This involves configuring device registers, setting up
buffers, and loading appropriate device drivers.
2. I/O Request: When an application requires an I/O operation (e.g., reading from a
keyboard or writing to a printer), it sends a request to the OS.
3. Device Driver Handling: The OS uses device drivers to interact with I/O devices.
Device drivers are software components that provide an interface between the OS and
hardware devices. When an I/O request is received, the OS selects the appropriate
device driver for the requested device.
4. Initiating I/O Operation: The OS instructs the selected device driver to initiate the
I/O operation. For output operations, data is sent to the device driver to be transmitted
to the device. For input operations, the device driver prepares to receive data from the
device.
5. Interrupt Generation: The device performs the requested operation asynchronously.
When the operation is complete or when the device has new data available, it raises an
interrupt signal to the CPU.
6. Interrupt Handling: Upon receiving an interrupt, the CPU suspends the current
execution and transfers control to the interrupt handler, a piece of OS code responsible
for handling interrupts. The interrupt handler determines the cause of the interrupt (e.g.,
which device triggered it) and takes appropriate action.
7. Data Transfer: In the case of input operations, the interrupt handler retrieves the data
from the device driver's buffer and passes it to the requesting application. For output
operations, the interrupt handler acknowledges the completion of the operation and
informs the requesting application.
Device drivers play a crucial role in managing I/O devices. They provide a standardized
interface for the OS to communicate with various hardware devices. Key functions of device
drivers include:
• Initialization: Initializing the device during system startup.
• Data Transfer: Managing the transfer of data between the CPU and the device.
• Interrupt Handling: Handling interrupts generated by the device.
• Error Handling: Managing errors and exceptions encountered during I/O operations.

Page 6 of 9
 • Power Management: Controlling power state transitions of the device to conserve
energy when not in use.

b) Consider a scenario where a user is copying a large file from one disk to another.
Describe how the operating system optimizes I/O performance using techniques such
as buffering, caching, and prefetching.
Through buffering, caching, and prefetching, the OS optimizes the performance of large file
copy operations. Buffering helps to smooth out read and write operations, caching reduces
repeated disk accesses, and prefetching anticipates future data needs to minimize wait times.
These techniques work together to ensure efficient and fast data transfer between disks,
enhancing overall system performance.
Buffering involves using a temporary storage area (buffer) in memory to hold data while it is
being transferred between the source and destination disks. This helps to smooth out
differences in data transfer rates between the disks and the CPU.
Caching involves keeping frequently accessed data in a faster storage medium (usually RAM)
to reduce access times. For file copying, caching can help by storing recently read or written
data in memory, reducing the need to access the slower disk.
Prefetching involves reading data into memory before it is actually needed, based on
anticipated future access patterns. This helps to minimize wait times for data access by ensuring
that data is already available in memory when required.

QUESTION 5: SYNCHRONIZATION AND DEADLOCK

a) Suppose multiple processes are accessing shared resources concurrently. Discuss the
challenges of synchronization and potential issues such as race conditions and data
corruption.
Challenges of Synchronization
1. Concurrency Control: Ensuring that multiple processes or threads can safely access
shared resources without interfering with each other.
2. Mutual Exclusion: Guaranteeing that only one process can access a critical section (a
portion of the code that accesses shared resources) at a time to prevent conflicts.
3. Deadlock: Avoiding situations where two or more processes are waiting indefinitely
for each other to release resources, causing a standstill.
4. Starvation: Preventing scenarios where a process never gets the resources it needs
because other processes are continually prioritized.
5. Fairness: Ensuring that all processes get a fair chance to access shared resources
without being unduly delayed.

Page 7 of 9
Potential Issues
1. Race Conditions
A race condition occurs when the behavior of a software system depends on the
sequence or timing of uncontrollable events such as process scheduling. It typically
arises when:
• Processes access and modify shared data concurrently without proper synchronization.
• The final outcome depends on the timing of context switches between processes.
2. Data Corruption
Data corruption occurs when concurrent access to shared resources leads to inconsistent
or invalid data. This is often a result of race conditions but can also stem from other
synchronization failures.

b) Consider a scenario where two processes are waiting for each other to release a
resource, resulting in a deadlock. Explain how the operating system detects and
resolves deadlocks using techniques such as deadlock prevention, avoidance, and
detection.
Deadlock Prevention
Deadlock prevention aims to ensure that at least one of the necessary conditions for deadlock
cannot hold, thereby preventing deadlocks from occurring. The four necessary conditions for
deadlock are mutual exclusion, hold and wait, no preemption, and circular wait.
1. Mutual Exclusion: This condition cannot be eliminated entirely because some
resources, like printers, must be exclusively used by one process at a time.
2. Hold and Wait: Ensure that whenever a process requests a resource, it does not hold
any other resources. This can be achieved by requiring processes to request all needed
resources at once, or by releasing all currently held resources before requesting new
ones.
3. No Preemption: Allow the operating system to forcibly take away resources from
processes. If a process holding some resources requests another resource that cannot be
immediately allocated, all resources currently held are preempted and added to the list
of available resources.
4. Circular Wait: Impose a total ordering on all resource types and require each process
to request resources in an increasing order of enumeration.

Deadlock Avoidance
Deadlock avoidance involves ensuring that a system will never enter an unsafe state where
deadlock is possible. The most common algorithm used for deadlock avoidance is the Banker’s
Algorithm.

Page 8 of 9
Banker's Algorithm: This algorithm works by simulating the allocation of resources and
ensuring that after allocation, the system remains in a safe state. A safe state is one where there
is at least one sequence of processes that can finish execution without entering a deadlock. The
algorithm checks whether the requested resources can be allocated safely before granting the
request.

Deadlock Detection and Recovery

When deadlock prevention and avoidance are not feasible, the operating system may use
deadlock detection and recovery mechanisms to handle deadlocks that occur.
1. Deadlock Detection: The OS periodically checks for deadlocks by examining the state
of resource allocation and waiting processes. A common method is to use a resource
allocation graph (RAG) and detect cycles in the graph. A cycle indicates a deadlock.
2. Deadlock Recovery: Once a deadlock is detected, the OS must break the deadlock by
taking corrective actions such as resource preemption or process termination.
Recovery Methods:
• Resource Preemption: Temporarily take resources away from processes
and reallocate them to break the deadlock. This may involve rolling back
some processes to earlier states.
• Process Termination: Abort one or more processes involved in the
deadlock. This can be done by terminating all processes in the cycle or
terminating one process at a time and checking for deadlock again until the
cycle is broken.

Page 9 of 9