OS MODULE BANK(M1 T1)
BY CSBS BATCH 4
1.
a) Define LINUX operating system and explain its architecture by analyzing its
structure and core functional layers.
Linux is a community-developed, open-source, Unix-like operating system based on the Linux kernel.
Created by Linus Torvalds in 1991, it was designed as a portable, multitasking, multi-user system.
Linux Architecture and Layers:
Linux uses a monolithic structure for efficiency, where core functions run in a single kernel space to reduce
context-switch overhead. It has three main layers:
• Kernel (Kernel Mode): The core of the system, linking applications and hardware while managing CPU
scheduling, memory, device drivers, and networking. It is modular, allowing kernel modules to be loaded or
removed without rebooting.
• System Libraries: Provide standard functions for applications and convert their requests into system calls
that move from user mode to kernel mode.
• Shell and Utilities (User Mode): The shell offers a command-line interface to interact with the kernel,
while utilities handle everyday tasks like file management and system administration.
b) Demonstrate your understanding of LINUX commands by identifying and
explaining the syntax and usage of commands for the following tasks: i) List the
contents of a directory ii) Create a file iii) Copy a file from one location to another iv)
Display the absolute pathname of the current working directory.
Here are the basic Linux commands for those tasks:
• List Directory Contents (ls): This command lists the files and directories in your current location.
o Syntax: ls [OPTIONS]... [FILE].
o Usage: Running ls -l displays detailed information like file size and permissions, while ls
-a reveals hidden "dot" files.
• Create a File (cat or touch): You can create a file using cat with the redirection operator or by
using touch.
o Syntax: cat > filename or touch filename.
o Usage: With cat > [Link], you can type content directly; press Ctrl+D to save and
exit. touch is typically used to create an empty file.
• Copy a File (cp): This duplicates a file from a source to a destination.
o Syntax: cp [OPTIONS]... SOURCE DEST.
o Usage: cp [Link] [Link] creates a copy of "[Link]" named "[Link]".
• Display Current Path (pwd): The "print working directory" command shows your exact location in
the filesystem.
o Syntax: pwd.
o Usage: It outputs the absolute pathname starting from the root directory /.
c) . Apply pattern matching in LINUX by writing and analyzing a grep command that
prints lines starting and ending with the word "LINUX".
To match lines that start and end with the word "LINUX" in the terminal, you would use the following
command:
grep "^LINUX.*LINUX$" filename
Analysis of the Command:
• grep: The utility used to search for text patterns within files.
• ^LINUX: The caret (^) is a special character that matches the pattern at the beginning of a line.
• .*: The dot (.) matches any single character, and the asterisk (*) matches zero or more occurrences
of the preceding character. This allows for any text to exist between the two "LINUX" words.
• LINUX$: The dollar sign ($) is a special character that matches the pattern at the end of a line.
If you meant a line that consists only of the word "LINUX," you would use grep "^LINUX$" filename.
2)
a) Discuss the organization of the LINUX file system and explain the concept of file
permissions, detailing how they are assigned and managed for files and directories.
The Linux file system follows a tree-like hierarchy starting at the root (/). In Linux, "everything is a file,"
including hardware.
Core Directories
• /bin: Essential command binaries.
• /etc: System configuration files.
• /home: Personal user folders.
• /dev: Hardware device files.
File Permissions
Access is managed for three groups: User (Owner), Group, and Others.
Permission File Action Directory Action Value
Read (r) View contents List files 4
Write (w) Modify file Add/delete files 2
Execute (x) Run as program Enter (cd) directory 1
Management Commands
• chmod: Changes permissions.
o Symbolic: chmod g+w file (Adds write for group).
o Octal: chmod 751 file (User: rwx, Group: r-x, Others: --x).
• chown: Changes file ownership or group.
b) Analyze the three utilities in the grep family by explaining their functionalities,
highlighting the differences in their pattern matching capabilities, and providing
appropriate use cases for each utility.
The grep family consists of three utilities used to search files for specific patterns and print the matching
lines.
Functionality and Pattern Matching Differences
• grep (Global Regular Expression Print): The standard utility that uses Basic Regular
Expressions (BRE) to find matches.
• egrep (Extended grep): An enhanced version, equivalent to grep -E, that utilizes Extended
Regular Expressions (ERE). It supports complex operators like + (one or more) and ? (zero or one)
which basic grep does not natively recognize without escaping.
• fgrep (Fixed grep): Also known as grep -F, it treats all patterns as fixed strings. It does not
recognize regular expressions or meta-characters (like * or .), treating them as literal characters
instead.
Use Cases
• grep: Ideal for standard, everyday searches using simple pattern matching.
• egrep: Best for complex queries that require advanced logic, such as using the pipe (|) for "OR"
conditions or specific quantifiers.
• fgrep: Recommended when searching for strings that contain many special characters to avoid the
need for backslash escaping, and for maximizing speed during literal string searches.
c) Define what system calls are and explain how they differ from library functions.
Provide examples to illustrate the key differences between these two concepts.
A system call is a function invocation made from user space to the kernel to request a service or hardware
resource.
Key Differences
• Execution Mode: Library functions typically run in user mode, while system calls trigger a
hardware "trap" to transition the CPU into privileged kernel mode.
• Layering: Library functions often act as high-level "wrappers" that sit on top of system calls to
provide a more convenient and portable API.
• Performance and Buffering: System calls are "expensive" due to the overhead of switching modes.
Library functions mitigate this by using user-space buffering (e.g., fread) to group many small
requests into a single, efficient system call.
Examples
• Output: printf() is a library function that handles complex formatting before ultimately invoking
the write() system call to send data to the hardware.
• File Management: fopen() is a library function that creates a FILE structure in the program’s heap,
whereas the underlying open() system call merely returns a raw integer file descriptor from the
kernel.
3.
a) Discuss the method of passing arguments to a shell script in LINUX and show, with
an example, how the script accesses and uses these arguments.
In Linux, you pass arguments to a shell script by entering them immediately after the script's name on the
command line,. The script then accesses these values using positional parameters, where $0 represents the
script name and $1 through $n represent the individual arguments provided,. Additionally, special variables
like $# provide the total count of arguments, while $* or $@ retrieve the entire list of parameters,.
For example, consider a script named [Link] containing these lines:
#!/bin/bash
echo "Script Name: $0"
echo "First Argument: $1"
echo "Total Count: $#"
If you execute this script by typing ./[Link] Hello World, the output will display the script name as
./[Link], the first argument as Hello, and a total count of 2.
b) What is the sed utility in LINUX? Describe its format and demonstrate its operation
with the help of suitable examples.
sed (Stream Editor) is a powerful utility used to search for, replace, insert, or delete text in a file or data
stream. Unlike interactive editors, it processes text line-by-line according to a script or command, making it
ideal for automated editing.
General Format
The basic syntax for a sed command is: sed 'command' filename
Common Operations and Examples
Symbol Purpose Example Usage
s Substitute: Replaces the first occurrence of a pattern in sed 's/Linux/UNIX/' [Link]
each line.
g Global: Replaces all occurrences of a pattern in a line. sed 's/Linux/UNIX/g' [Link]
d Delete: Removes specific lines or lines matching a sed '4d' [Link] (Deletes line
pattern. 4)
i Insert: Adds a line before a matching pattern. sed '/kernel/i Section'
[Link]
a Append: Adds a line after a matching pattern. sed '/grep/a Info' [Link]
Practical Demonstration
If you have a file named [Link] and want to replace every instance of "Linux" with "UNIX" globally,
you would run: sed 's/Linux/UNIX/g' [Link]
c) Analyze the differences in CPU utilization strategies between multiprogramming and
time-sharing operating systems. How does each approach impact system responsiveness
and efficiency.
Multiprogramming and time-sharing represent different stages in the evolution of CPU utilization:
• Multiprogramming Strategy: The OS keeps several jobs in memory simultaneously and switches
the CPU to another job only when the current one must wait, such as for an I/O operation. This
strategy is designed for efficiency, maximizing hardware utilization by ensuring the CPU is rarely
idle. However, it offers poor responsiveness because it lacks user interaction; it is fundamentally a
batch system concept.
• Time-Sharing (Multitasking) Strategy: This is a logical extension of multiprogramming where the
CPU switches between jobs so frequently—using timer interrupts—that users can interact with each
program while it runs. It prioritizes responsiveness, typically aiming for a response time of less than
one second.
• Efficiency Impact: While time-sharing improves the user experience, it is technically less
"efficient" for the CPU than pure multiprogramming. The frequent switching creates overhead,
which is CPU time lost to performing context switches (saving and restoring registers/states) rather
than executing productive work.
4.
a) List and explain the five major activities performed by an operating system related
to process management and memory management.
The operating system performs the following major activities to manage processes and memory:
Process Management Activities
• Creation and Deletion: The OS starts and removes both user and system processes.
• Suspension and Resumption: It pauses active processes when resources are needed elsewhere and
restarts them when appropriate.
• Synchronization: It provides mechanisms, like locks, to coordinate processes so they do not
interfere with each other's data.
• Communication: It enables processes to exchange information through shared memory or message
passing.
• Deadlock Handling: It provides tools to prevent or resolve situations where processes are stuck
waiting for each other.
Memory Management Activities
• Usage Tracking: The OS keeps track of which parts of memory are currently in use and by which
user or process.
• Process Selection: It decides which processes (or parts of code/data) should be moved into or out of
main memory.
• Allocation and Deallocation: It grants memory space to processes when they need it and reclaims
that space when they are finished.
b) Analyze the purpose of the command interpreter and justify why it is usually
implemented separately from the kernel.
The operating system performs the following major activities to manage processes and memory:
Process Management Activities
• Creation and Deletion: The OS starts and removes both user and system processes.
• Suspension and Resumption: It pauses active processes when resources are needed elsewhere and
restarts them when appropriate.
• Synchronization: It provides mechanisms, like locks, to coordinate processes so they do not
interfere with each other's data.
• Communication: It enables processes to exchange information through shared memory or message
passing.
• Deadlock Handling: It provides tools to prevent or resolve situations where processes are stuck
waiting for each other.
Memory Management Activities
• Usage Tracking: The OS keeps track of which parts of memory are currently in use and by which
user or process.
• Process Selection: It decides which processes (or parts of code/data) should be moved into or out of
main memory.
• Allocation and Deallocation: It grants memory space to processes when they need it and reclaims
that space when they are finished.
c) Identify the system calls that a command interpreter or shell must execute to start a
new process and discuss the role of system programs in the operation of an operating
system
Before we dive in, what is your main goal for learning about Linux internals, and how familiar are you with
how the command line works?
To start a new process, a shell typically executes the fork() system call to create a duplicate of itself,. It
then uses an exec() variant to load and execute the new program image,. Finally, the shell usually executes
wait() to stay suspended until the child process finishes,.
System programs provide a convenient environment for program development and execution,. They serve as
the primary interface through which users interact with the operating system, performing tasks like file
management, status inquiries, and communications,. Because they hide the complexity of the kernel, most
users perceive these programs as the operating system itself,.
5.
a) The services and functions provided by an operating system can be divided into two
main categories. Briefly describe the two categories and discuss how they differ.
Operating System Services
Operating system services fall into two categories: those that help the user and those that maintain the
system.
1. User-Focused Services
These prioritize accessibility and convenience.
• Interfaces: CLI, GUI, or Batch environments.
• Execution: Running programs and managing I/O operations.
• Management: Manipulating file systems and detecting errors.
2. System-Focused Services
These prioritize efficiency, fairness, and integrity.
• Resource Allocation: Managing CPU cycles and memory for multiple tasks.
• Accounting: Tracking usage and resource consumption.
• Security: Protecting data and ensuring system-wide protection.
OS Storage: Firmware vs. RAM
In devices like game consoles or handhelds, the OS is often stored in firmware for a smaller footprint and
better security.
• Pros: Rugged, highly secure against viruses.
• Cons: Slower execution than RAM; harder to update (requires flashing chips).
b) Analyze why certain systems store the operating system in firmware while others
choose to store it on disk. Provide reasons for these design choices.
In contrast, large operating systems like Windows or Linux are stored on disk to accommodate their
significant size and to allow for frequent, easy software updates. Disk-based systems use a multi-step boot
process where a tiny bootstrap loader in ROM fetches a more complex program from the disk to finally load
the kernel.
c) Explain how the distinction between kernel mode and user mode serves as a basic
protection mechanism in an operating system. Illustrate its role in ensuring system
security.
The operating system uses a hardware-provided mode bit to differentiate between user-level and kernel-
level code. In user mode, programs are restricted from directly accessing hardware or executing "privileged
instructions". Conversely, kernel mode grants the operating system full, unrestricted access to all machine
resources. This distinction ensures system security by preventing user programs from accidentally or
intentionally overwriting critical system data or interfering with other processes. Any attempt to perform a
restricted operation in user mode triggers a hardware trap, allowing the OS to intervene and potentially
terminate the offending process.
6.
a) Illustrate the layered architecture of an operating system using a neat diagram and
analyze how this structure contributes to system modularity and simplifies the
debugging process.
A layered architecture organizes an operating system into a hierarchy where each level is built on the
one below it.
Layered Diagram:
• Layer 0 (Hardware): The lowest level contains the physical hardware.
• Intermediate Layers (1 to N-1): Each layer performs specific OS functions and uses only the services
of the layer beneath it.
• Layer N (User Interface): The highest layer provides the interface for user interaction.
Modularity and Debugging:
• Modularity: Each layer acts as an abstract unit with its own data and operations, hiding internal details
to keep the system organized and easy to modify.
• Simplified Debugging: Layers can be verified from the bottom up—once a lower layer is confirmed
correct, any error must lie in the current layer being tested.
b) Describe how user programs interact with system services in a microkernel
architecture. Furthermore, evaluate the disadvantages of using the microkernel
approach, particularly in terms of communication overhead and system complexity.
Microkernel Architecture
Microkernels use message passing rather than direct interaction. When a user program needs a service (like
file access), it sends a message to the microkernel, which forwards it to a service process running in user
mode.
Disadvantages
• Communication Overhead: Performance is slower due to frequent context switches between user
and kernel modes. Moving data between separate address spaces is less efficient than the direct calls
used in monolithic systems.
• System Complexity: It is difficult to decide which functions belong in the kernel versus user space.
This independent layering can lead to complex "chicken-and-egg" dependencies, making debugging
harder.
c) Compare and contrast the design and functioning of monolithic and microkernel
operating systems.
Monolithic kernels (like Linux) run all core OS services—such as memory management, CPU scheduling,
and file systems—within a single, large binary in kernel space. This design offers high performance because
components communicate via direct function calls, avoiding the need for expensive context switches.
However, a bug in any one component can crash the entire system, making these kernels more difficult to
maintain.
In contrast, microkernels (like Mach) remove non-essential services from the kernel and implement them as
independent programs in user space. They rely on message passing through the kernel to facilitate
communication between these services. While this structure is more secure and reliable—because a service
failure does not impact the rest of the kernel—it suffers from performance overhead due to the constant
context switching required between user and kernel modes.
7.
a) Analyze the trade-offs between different scheduling criteria by discussing how the
following pairs can conflict in specific scenarios. Support your discussion with practical
examples:
1. CPU utilization vs. response time
2. Average turnaround time vs. maximum waiting time
3. I/O device utilization vs. CPU utilization
Scheduling Trade-offs
Scheduling criteria are often a "tug-of-war"—improving one metric usually degrades another.
1. CPU Utilization vs. Response Time
• The Conflict: High utilization requires keeping the CPU busy by minimizing context switches
(using long time slices). However, this makes interactive users wait longer, increasing response time.
• Example: In Round-Robin, a small time quantum improves responsiveness but wastes CPU cycles
on frequent switching.
2. Average Turnaround Time vs. Maximum Waiting Time
• The Conflict: To lower the average time it takes to finish jobs, systems often prioritize short tasks
(e.g., Shortest Job First). This can lead to starvation, where long jobs wait indefinitely.
• Example: If short 10ms tasks keep arriving, a 10-second job may never run, causing its waiting time
to skyrocket.
3. I/O Device Utilization vs. CPU Utilization
• The Conflict: Keeping both the CPU and I/O devices busy requires a balanced "process mix." If the
scheduler favors CPU-heavy tasks, I/O devices sit idle.
• Example: The Convoy Effect occurs in First-Come, First-Served (FCFS) scheduling when I/O-
bound jobs get stuck behind one long CPU-bound process, leaving I/O hardware unproductive.
b) Given a workload of processes arriving at time 0 as below. Construct a Gantt chart
for Round Robin scheduling with a time quantum of 20 unit. Based on your chart,
compute and evaluate the average waiting time and average turnaround time.
In Round-Robin (RR) scheduling, the CPU cycles through the ready queue, granting each process a
maximum of one time quantum ($q$) before moving it to the tail of the queue.
Gantt Chart ($q = 20$)
Time Process Action
0 – 20 P1 Runs for 20 units; 33 remaining.
20 – 37 P2 Runs for its full burst (17 units); Finishes at 37.
37 – 57 P3 Runs for 20 units; 48 remaining.
57 – 77 P4 Runs for 20 units; 4 remaining.
77 – 97 P1 Runs for 20 units; 13 remaining.
97 – 117 P3 Runs for 20 units; 28 remaining.
117 – 121 P4 Runs for its remaining 4 units; Finishes at 121.
121 – 134 P1 Runs for its remaining 13 units; Finishes at 134.
134 – 154 P3 Runs for 20 units; 8 remaining.
154 – 162 P3 Runs for its remaining 8 units; Finishes at 162.
Metrics Computation
Turnaround Time (Finish Time - Arrival Time):
• P1: 134 – 0 = 134
• P2: 37 – 0 = 37
• P3: 162 – 0 = 162
• P4: 121 – 0 = 121
• Average Turnaround Time: (134 + 37 + 162 + 121) / 4 = 113.5 units
Waiting Time (Turnaround Time - Burst Time):
• P1: 134 – 53 = 81
• P2: 37 – 17 = 20
• P3: 162 – 68 = 94
• P4: 121 – 24 = 97
• Average Waiting Time: (81 + 20 + 94 + 97) / 4 = 73 units
Evaluation
The RR algorithm prioritized response time over turnaround time, allowing P2 to finish significantly earlier
than it would have under FCFS. However, the average turnaround time is relatively high because longer
processes like P3 were repeatedly preempted, extending their completion times.
c) Discuss the role of time quantum in Round Robin scheduling. How does changing the
time quantum affect waiting time, turnaround time, and context switching overhead?
The time quantum (or time slice) is the small unit of CPU time—typically 10 to 100 milliseconds—
allocated to a process before it is preempted and moved to the back of the ready queue. It acts as the defining
parameter for balancing system responsiveness and efficiency.
• Waiting Time: Round Robin (RR) ensures that in a system with $n$ processes, no process waits
more than $(n-1)q$ time units for its next turn. While this provides better response time for
interactive users, the average waiting time is often longer than that of other algorithms.
• Turnaround Time: This metric does not necessarily improve as the quantum increases. Turnaround
time is generally minimized when the quantum is large enough that 80% of CPU bursts are shorter
than the time slice. If the quantum becomes too large, the algorithm effectively becomes First-Come,
First-Served (FCFS).
• Context Switching Overhead: Smaller quanta result in more frequent context switches. Since
context switching is pure overhead where no useful work is performed, the quantum must be large
relative to the context-switch time (typically 10 microseconds) to amortize the cost.
8.
a) What is a process in an operating system? Draw and explain a five-state process
model, describing the purpose of each state and the transitions between them.
A process is an active program in execution. It includes the program code (text section), current activity
with the program counter and registers, a stack for temporary data, a data section for global variables, and a
heap for dynamic memory.
Five-State Model:
A process passes through five states:
• New: The process is being created.
• Ready: It has required resources and waits for CPU scheduling.
• Running: The CPU executes the process instructions.
• Waiting (Blocked): It waits for an external event like I/O completion.
• Terminated: The process has finished execution.
Process Transitions:
The OS controls movement between states:
• Admitted: New → Ready.
• Scheduler Dispatch: Ready → Running.
• Interrupt: Running → Ready when time expires or a higher-priority task appears.
• I/O/Event Wait: Running → Waiting.
• I/O/Event Completion: Waiting → Ready.
• Exit: Running → Terminated.
b) Given the following workload where all processes arrive at time 0. Draw a Gantt
chart illustrating the execution of these jobs using the Priority (preemptive) CPU
scheduling algorithm. Calculate the average waiting time and average turnaround time
for the processes. (Higher number represents higher priority)
In a preemptive priority scheduling algorithm where a higher number represents a higher priority, a newly
arrived process with a higher priority will immediately preempt the currently running process.
Gantt Chart
Time Process Action
0–1 P1 Starts at arrival; Priority 2. Preempted by P2 at T=1.
1–2 P2 Arrives at T=1; Priority 3 (higher than P1). Preempted by P3 at T=2.
2–3 P3 Arrives at T=2; Priority 4 (higher than P2). Finishes at 3.
3–8 P4 Arrives at T=3; Priority 5 (highest). Since P5 (Priority 5) is not higher, P4 completes
its burst. Finishes at 8.
8 – 10 P5 Next highest priority (5) in queue. Finishes at 10.
10 –12 P2 Remaining burst of 2. Finishes at 12.
12 –15 P1 Remaining burst of 3. Finishes at 15.
Metrics Computation
Turnaround Time (Finish Time - Arrival Time):
• P1: 15 – 0 = 15
• P2: 12 – 1 = 11
• P3: 3 – 2 = 1
• P4: 8 – 3 = 5
• P5: 10 – 4 = 6
• Average Turnaround Time: (15 + 11 + 1 + 5 + 6) / 5 = 7.6 units
Waiting Time (Turnaround Time - Burst Time):
• P1: 15 – 4 = 11
• P2: 11 – 3 = 8
• P3: 1 – 1 = 0
• P4: 5 – 5 = 0
• P5: 6 – 2 = 4
• Average Waiting Time: (11 + 8 + 0 + 0 + 4) / 5 = 4.6 units
c) Compare how much the following scheduling algorithms favour short processes.
Analyze the level of discrimination against long processes for:
• FCFS (First-Come, First-Served)
• RR (Round Robin)
• Priority scheduling
Comparison of Scheduling Algorithms
Different algorithms handle process lengths and fairness in distinct ways:
First-Come, First-Served (FCFS)
• Bias: Does not favor short processes; they must wait for all preceding tasks.
• The "Convoy Effect": Short processes get stuck behind a single long-running task, causing system-
wide delays.
• Long Processes: Can monopolize the CPU until they finish or block for I/O.
Round Robin (RR)
• Bias: Favors short processes, which can often complete and exit within one time quantum.
• Fairness: Guarantees every task a fair share ($1/n$) of CPU time.
• Long Processes: Do not lose access to the CPU, but suffer from high turnaround times due to
constant preemption and context switching.
Priority Scheduling
• Bias: Can favor short processes if priority is linked to burst time (like SJF).
• Discrimination: High risk of starvation for long/low-priority processes if new, higher-priority tasks
keep arriving.
• Solution: Aging—a technique that gradually increases a process's priority as it waits, ensuring it
eventually runs.
9.
a) . What is the critical section problem in process synchronization? Discuss the
conditions that any solution to the critical section problem must satisfy to ensure safe
and correct execution.
The critical section problem occurs when multiple processes compete to access a shared resource or variable
in a specific segment of code,. To ensure correct execution and data consistency, only one process can be
active in its critical section at any given time,.
To solve this problem effectively, three conditions must be met:
• Mutual Exclusion: If one process is executing in its critical section, no other process is allowed to
do so,.
• Progress: If no process is currently in a critical section and some want to enter, the selection of the
next process cannot be postponed indefinitely,.
• Bounded Waiting: A limit must exist on the number of times other processes are allowed to enter
their critical sections after a process has made a request, ensuring that request is eventually granted,.
b) What is a semaphore in operating systems? Explain its importance in solving
synchronization issues. Suggest a solution for the bounded buffer problem using
semaphores and describe how semaphores help manage concurrent access.
A semaphore is an integer variable used for process synchronization that is manipulated solely through the
atomic operations wait() and signal(). These tools are critical for coordinating interactions between
concurrent processes to prevent race conditions and ensure data consistency.
To solve the bounded buffer problem, a common solution employs three semaphores:
• mutex: A binary semaphore (initialized to 1) to ensure mutual exclusion for the buffer pool.
• empty: A counting semaphore (initialized to the buffer size $n$) to track available slots.
• full: A counting semaphore (initialized to 0) to track filled slots.
A producer calls wait(empty) and wait(mutex) to add an item, then signals mutex and full when done. A
consumer calls wait(full) and wait(mutex) to remove an item, then signals mutex and empty to indicate
free space. Semaphores control access by blocking processes in a waiting queue until another process signals
that the resource state has changed.
c) Describe how a race condition can occur in a banking system where two functions —
deposit(amount) and withdraw(amount) — are called concurrently by two users
sharing an account. Analyze how this race condition could affect the account balance
and discuss strategies to prevent it.
Race Conditions in Banking
A race condition occurs when multiple processes access shared data concurrently, and the final outcome
depends on the timing of their execution. Simple code like balance += amount is not atomic; at the machine
level, it requires three steps: Load, Modify, and Store.
The "Lost Update" Scenario
Imagine an account with $100:
1. User A (Deposit $50): Loads $100, calculates $150.
2. User B (Withdraw $20): Loads the original $100 (before A saves), calculates $80.
3. User A Saves: Memory now says $150.
4. User B Saves: Overwrites memory with $80.
Result: The $50 deposit is "lost," and the balance is $80 instead of $130.
Prevention Strategies
• Mutual Exclusion: Ensuring only one process enters the "critical section" of the code at a time.
• Locks/Mutexes: A thread must acquire() a lock to access the balance and release() it only when
finished.
• Semaphores: Using a binary semaphore (value 0 or 1) where wait() grants entry and signal() opens
the gate for the next process.
• Atomic Instructions: Using hardware-level commands like compare_and_swap to ensure the update
happens in one uninterruptible step.
10.
a) What is the meaning of the term busy waiting? What other kinds of waiting are there
in an operating system? Can busy waiting be avoided altogether? Explain your answer
Process Waiting Strategies
Busy waiting (or spinning) is when a process loops continuously to check for a condition. While simple, it
wastes CPU cycles that could be used for other tasks.
Alternatives to Busy Waiting
• Blocked/Sleeping: The OS moves the process to a "waiting" queue. The CPU is freed for other tasks
until the required resource becomes available.
• Yielding: The process voluntarily gives up the CPU but remains in the "ready" state, allowing other
processes of the same priority to take over.
How to Avoid Spinning
Busy waiting is typically replaced by interrupts and blocking primitives. Instead of the CPU "asking" if a
task is done, the hardware sends an interrupt signal to "wake up" the sleeping process once the event occurs.
When is Busy Waiting Actually Used?
In multiprocessor systems, "spinlocks" are still common. If the wait time is extremely short, "spinning" on
the CPU is actually faster than the heavy performance cost (overhead) of performing a full context switch to
put the process to sleep.
b) Explain how wait() and signal() semaphore operations can be implemented in a
multiprocessor environment using the Test-and-Set instruction. Why is it important to
minimize busy waiting in such implementations.
In multiprocessor (SMP) systems, atomicity for wait() and signal() cannot be ensured by disabling
interrupts, so the TestAndSet instruction creates a short spinlock to protect the semaphore’s value and
waiting list during updates. This allows only one processor to modify the semaphore at a time.
Busy waiting is minimized because it wastes CPU cycles. It is limited to the brief critical sections inside
wait() and signal(), while processes waiting for a resource are placed in a queue and suspended (block()),
letting the CPU run other tasks until they are awakened.
c) Develop pseudo code for wait() and signal() semaphore operations in a
multiprocessor environment using Test-and-Set. The solution should exhibit minimal
busy waiting.
To provide minimal busy waiting on a multiprocessor, test_and_set is used only as a short-duration
"guard" to protect the semaphore's internal state, while the actual waiting is handled by the operating system.
Data Structure
struct semaphore {
int value;
int guard; // Initialized to 0
struct process *list;
};
Wait Operation
1. while (test_and_set(&[Link])) ; // Busy wait for the short-term guard.
2. [Link]--; // Decrement the actual semaphore value.
3. if ([Link] < 0) { // If no resources are available.
4. add this process to [Link]; // Place process in the waiting queue.
5. [Link] = 0; // Release the guard before sleeping.
6. block(); // Suspend the process via the OS.
7. } else {
8. [Link] = 0; // Release the guard and continue.
9. }
Signal Operation
1. while (test_and_set(&[Link])) ; // Busy wait for the short-term guard.
2. [Link]++; // Increment the semaphore value.
3. if ([Link] <= 0) { // If there are processes waiting.
4. remove a process P from [Link]; // Select a process to wake up.
5. wakeup(P); // Move the process to the ready queue.
6. }
7. [Link] = 0; // Release the guard.
Busy waiting is restricted to the very short duration required to update the value and list, which typically
lasts only a few machine instructions. This prevents the CPU from wasting cycles during the much longer
period while the process is blocked.