OS Lab End-Semester Exam Guide

Operating Systems Lab [CSS_2211] — MIT Manipal 2025–26

[Link] CSE & Allied Streams | Fourth Semester

11 40% 2 hrsC/C++
LABS COVEREDEND SEM WEIGHT DURATION LANGUAGE

This guide covers: Theory · Programs · Commands · Viva Q&A · Statement Questions

Labs 4–11 carry HIGH weightage in the end-semester exam

Table of Contents

Lab 1 — UNIX Shell Commands Basic Navigation, Files, Wildcards, Piping

Lab 2 — Advanced UNIX Shell Commands grep, sort, wc, cut, sed, tr, chmod

Lab 3 — Shell Scripting Variables, Arithmetic, Control Structures

★ Lab 4 — Process & Thread Management fork(), exec(), wait(), Pthreads

★ Lab 5 — CPU Scheduling Algorithms FCFS, SJF, SRTF, Priority, Round Robin

★ Lab 6 — Interprocess Communication Pipes, Message Queues, Shared Memory, FIFO

★ Lab 7 — Process Synchronization Semaphores, Mutex, Producer-Consumer

★ Lab 8 — Deadlock Management Banker's Algorithm, Deadlock Detection

★ Lab 9 — Memory Management I First Fit, Best Fit, Worst Fit, Paging, Segmentation

★ Lab 10 — Memory Management II FIFO, Optimal, LRU Page Replacement

★ Lab 11 — Disk Scheduling FCFS, SSTF, SCAN, C-SCAN, LOOK, C-LOOK

 UNIX Shell Commands
Basic navigation, file operations, wildcards, piping and redirection
Low Weightage Theory + Demo

1. Concept Explanation

What is a Shell?
A shell is a program that acts as an interface between the user and the OS kernel. You type commands → shell
interprets them → OS executes them. It is also a scripting environment.

The prompt $ (Bourne-type) or % (C-type) is issued by the shell, waiting for your command.

Shell Types (Write in Exam)

Shell Prompt Family Notes

sh (Bourne Shell) $ Bourne Original UNIX shell

bash (Bourne Again) $ Bourne Most common on Linux

ksh (Korn Shell) $ Bourne Enhanced Bourne

csh (C Shell) % C-type C-like syntax

tcsh % C-type Enhanced C Shell

Special Characters

Character Meaning Example

* Matches 0 or more characters ls *.txt

? Matches exactly 1 character ls file?.txt

[a-z] Matches any char in set/range ls [abc]*

~ Home directory cd ~

.. Parent directory cd ..

> Redirect output (overwrite) ls > [Link]

>> Redirect output (append) echo hi >> [Link]

| Pipe output to next command ls | sort

; Run multiple commands in sequence cd /tmp; ls

& Run command in background ./prog &

⌨ 2. Important Commands

Command Usage What it does

pwd pwd Print current (working) directory

cd cd /home/user Change directory

ls ls -la List files (-l=long format, -a=hidden files)

touch touch [Link] Create empty file / update timestamp

cat cat [Link] Display file contents

head head -5 [Link] Show first N lines

tail tail -5 [Link] Show last N lines

cp cp [Link] /tmp/ Copy file/directory

mv mv [Link] [Link] Move or rename file

 rm rm -r dir/ Delete file or directory (-r=recursive)

mkdir mkdir mydir Create directory

rmdir rmdir mydir Remove empty directory

find find . -name "*.c" Search for files

man man ls Show manual page for command

chmod chmod 755 prog Change file permissions

which which grep Show full path of command

Piping & Redirection Examples

ls -l | sort # List files and sort alphabetically

ls -l | grep ".txt" # List only .txt files
wc -l [Link] # Count lines in file
ls > [Link] # Save ls output to file (overwrite)
echo "hello" >> [Link] # Append text to file
cat [Link] | head -10 # Show first 10 lines
ls | sort | uniq # List unique sorted filenames

5. Statement-Based Questions & How to Answer

"List all files in the current directory with details."

Answer: ls -l or ls -la to include hidden files. Explain each column: permissions, links, owner, size, date, name.

"Demonstrate piping and redirection in UNIX."

Answer: ls -l | grep ".txt" > [Link] — explain that | sends output of ls to grep, then > saves to file.

"Display only files with .txt extension."

Answer: ls *.txt (wildcard) or find . -name "*.txt"

6. Viva Questions

Q1: What is a shell and what are its types?

A shell is a command-line interpreter between user and OS kernel. Types: Bourne (sh, bash, ksh) with prompt $ and C
Shell (csh, tcsh) with prompt %.

Q2: Difference between > and >>?

> redirects output to a file, overwriting existing content. >> appends output to the end of an existing file without
deleting its contents.

Q3: What is piping in UNIX?

Piping (|) connects the standard output of one command to the standard input of another. Example: ls -l | grep ".c"
lists only .c files.

Q4: What does chmod 755 mean?

7=rwx for owner, 5=r-x for group, 5=r-x for others. Owner has full access; group and others can read and execute but
not write.

Q5: What is the shebang line?

#!/bin/bash is the first line of a shell script, telling the kernel which interpreter to use to execute the script.
 Advanced UNIX Shell Commands
grep, sort, wc, cut, sed, tr — data extraction, filtering, process management
Low Weightage Commands + Output

⌨ 2. Key Commands

grep — Search for Patterns

grep searches plain-text data for lines matching a pattern (regular expression).

grep "apple" [Link] # Find "apple" in file (case-sensitive)

grep -i "apple" [Link] # Case-insensitive search
grep -v "apple" [Link] # Lines NOT matching (invert)
grep -n "apple" [Link] # Show line numbers
grep -x "apple" [Link] # Match WHOLE line exactly
grep -c "apple" [Link] # Count matching lines only
grep -E "^p" [Link] # Lines starting with 'p' (regex)
grep -E "e$" [Link] # Lines ending with 'e'
grep -r "word" ./folder/ # Recursive search in folder

sort — Sort File Content

sort [Link] # Alphabetical sort

sort -r [Link] # Reverse sort
sort -n [Link] # Numeric sort
sort -o [Link] file # Save sorted output to file
sort -u [Link] # Sort and remove duplicates

wc — Word Count

wc [Link] # Shows: lines words bytes filename

wc -l [Link] # Only line count
wc -w [Link] # Only word count
wc -c [Link] # Only byte count
wc * # Count for all files in directory

cut — Extract Columns

cut -c1-3 [Link] # Characters 1 to 3 per line

cut -c1,4,7 [Link] # Characters 1, 4, and 7
cut -f1,3 [Link] # Fields 1 and 3 (tab-separated)
cut -d':' -f1 /etc/passwd # Field 1, using ':' as delimiter
ls -l | tr -s ' ' | cut -d' ' -f5 # Get file size column

sed — Stream Editor (Search & Replace)

sed 's/old/new/' [Link] # Replace first occurrence per line

sed 's/old/new/g' [Link] # Replace ALL occurrences (g = global)
sed -i 's/old/new/g' [Link] # Edit file in-place (modify original)
sed '/^#/d' [Link] # Delete lines starting with #
sed -n '/^d/p' # Print only lines starting with 'd'
sed -e '11,$ d' [Link] # Delete all lines after line 10
sed '/word/a "new line"' file # Append new line after matching line

tr — Translate / Replace Characters

tr 'a-z' 'A-Z' < [Link] # Convert lowercase to uppercase

tr 'A-Z' 'a-z' < [Link] # Convert uppercase to lowercase
tr -d '\r' # Delete carriage return characters
tr -s ' ' # Squeeze multiple spaces to one
tr -cd '[:alnum:]' # Remove all non-alphanumeric chars

chmod — File Permission Numbers

Number Permission Symbol

7 Read + Write + Execute rwx

6 Read + Write rw-

5 Read + Execute r-x

4 Read only r--

3 Write + Execute -wx

2 Write only -w-

1 Execute only --x

0 No permission ---

chmod 755 [Link] # owner=rwx, group=r-x, others=r-x

chmod 664 [Link] # owner=rw, group=rw, others=r
chmod a+x [Link] # Add execute permission for ALL
chmod u+rw,g=r [Link] # Symbolic mode: owner rw, group r only
chmod -R 755 directory/ # Recursive: apply to dir and contents

Process Management Commands

ps # Show running processes (PID, TTY, TIME, CMD)

ps -aux # Show all processes with details
kill 1234 # Send SIGTERM to process 1234 (graceful stop)
kill -9 1234 # Send SIGKILL to process 1234 (force kill)
kill -15 1234 # Same as kill 1234 (SIGTERM = signal 15)
bg # Resume stopped job in background
fg # Bring background job to foreground

5. Statement-Based Questions

"Find all lines starting with uppercase letter in a file."

Answer: grep -E "^[A-Z]" [Link]

"Replace all occurrences of 'IT' with 'Information Technology' and save."

Answer: sed 's/IT/Information Technology/g' [Link] > [Link] or use sed -i to edit in place.

"Count number of students in ICT department."

Answer: grep "ICT" [Link] | wc -l

6. Viva Questions

Q1: Difference between grep -v and grep -x?

-v prints lines that do NOT match the pattern. -x matches only lines that are an EXACT whole-line match.

Q2: What does 'sed s/a/b/g' do?

It replaces ALL occurrences of 'a' with 'b' in each line. Without 'g', only the first occurrence per line is replaced.

Q3: What is SIGKILL (kill -9)?

SIGKILL (signal 9) forcefully terminates a process immediately. It cannot be caught, blocked, or ignored by the process.
Use SIGTERM (kill -15) first for graceful termination.

Q4: What is the difference between sort and sort -n?

sort does lexicographic (alphabetical) sorting. sort -n does numeric sorting. Example: 2, 10, 20 sorted alphabetically =
10, 2, 20; sorted numerically = 2, 10, 20.
 UNIX Shell Programming (Shell Scripting)
Variables, arithmetic, control structures, functions and script execution
Medium Weightage Scripting Programs

1. Concept Explanation

A shell script is a group of commands stored in a file that the shell can execute. Scripts are interpreted (not
compiled), and run top to bottom.

Shbang Line — First line of EVERY script

#!/bin/bash # Tells OS to use bash interpreter

#!/bin/sh # Use default Bourne shell

The shbang line MUST be the very first line. Without it, the script may not execute correctly.

Variables

name="Alice" # Assign (NO spaces around = sign!)

x=10
echo $name # Access value with $ prefix
echo "Hello $name" # Variables inside double quotes are expanded
echo 'Hello $name' # Single quotes: $name printed literally

read a # Read one value from user

read a b c # Read multiple values (space-separated)

⌨ 2. Arithmetic Methods — All 4 Must Know

Method Syntax Notes

expr result=`expr $a + $b` Spaces required between operators and operands. Integer only.

$(( )) result=$((a + b)) No spaces needed. No $ for variables inside. Best for integers.

[ ] test [ $a -gt $b ] Used for comparisons, not arithmetic. Returns 0 (true) or 1 (false).

bc result=$(echo "scale=2; $a/$b" | bc) Floating point support. Use scale=N for decimal places.

Comparison Operators

Operator Meaning Operator Meaning

-eq equal to -ne not equal to

-gt greater than -lt less than

-ge greater or equal -le less or equal

-f file is regular file -d file is directory

-e file file exists -z str string is empty

3. Standard Programs

Program 1: if-else with comparison

#!/bin/bash
echo "Enter two numbers:"
read a b
if [ $a -gt $b ]; then
echo "$a is greater than $b"
elif [ $a -lt $b ]; then
echo "$b is greater than $a"
else
echo "Both are equal"
fi
Program 2: Calculator with floating point (bc)

#!/bin/bash
echo "Enter two numbers:"
read a b
echo "Enter operator (+, -, *, /):"
read op
result=$(echo "scale=2; $a $op $b" | bc)
echo "Result: $result"

Program 3: for loop (C-style)

#!/bin/bash
read n
for (( i=1; i<=n; i++ )); do
echo -n "$i "
done
echo ""

Program 4: while loop

#!/bin/bash
read n
i=1
while (( i <= n )); do
echo -n "$i "
((i++))
done
echo ""

Program 5: case statement

#!/bin/bash
echo "Enter 1, 2, or 3:"
read choice
case $choice in
1) echo "You chose one." ;;
2) echo "You chose two." ;;
3) echo "You chose three." ;;
*) echo "Invalid choice." ;;
esac

Program 6: Check if file is directory or regular file

#!/bin/bash
echo "Enter filename:"
read fname
if [ -d "$fname" ]; then
echo "$fname is a DIRECTORY"
elif [ -f "$fname" ]; then
echo "$fname is a REGULAR FILE"
else
echo "$fname does not exist"
fi

How to Run a Shell Script

chmod +x [Link] # Give execute permission (do this once)

./[Link] # Run the script
# OR
bash [Link] # Run directly without execute permission

5. Statement-Based Questions

"Write a shell script to find whether a given file is a directory or regular file."
Use -d and -f flags with if-else. Show Program 6 above.

"Write a shell script to calculate gross salary. GS = Basic + TA + 10% of Basic."

Use bc for floating point: result=$(echo "scale=2; $basic + $ta + $basic*0.1" | bc)

"Write a shell script to delete all even numbered lines in a text file."
Use sed: sed -n '1~2p' [Link] (print only odd lines = delete evens)
 6. Viva Questions

Q1: What is the shbang line? Why is it needed?

#!/bin/bash is the shbang line — it tells the kernel which interpreter to use for the script. Without it, the default shell may
not interpret the script correctly.

Q2: How do you perform floating point arithmetic in bash?

Bash does not support floating point natively. Use the 'bc' command: result=$(echo "scale=2; 5/3" | bc)

Q3: Difference between local and global (environment) variables?

Local variables are only available in the current shell session and go out of scope when the script ends.
Global/environment variables are created with 'export' and are available to all child processes spawned from that shell.

Q4: What does [ $a -eq $b ] return?

It returns exit status 0 (true/success) if a equals b, or 1 (false/failure) otherwise. Used in if/while conditions.
 Process & Thread Management
fork(), exec(), wait(), exit(), getpid(), getppid(), Pthreads — most important lab!
★ HIGH WEIGHTAGE Must Know Programs

1. Concept Explanation

fork() — Create a New Process

fork() creates an exact copy (child process) of the calling (parent) process. Both processes continue executing from
the same point in the code, but differ based on the return value of fork().

Who receives the return value Value returned by fork()

Parent process PID of the child (positive integer)

Child process 0

Error (failed) -1

KEY POINT: fork() is called ONCE but returns TWICE — once in the parent, once in the child. The return value is what
distinguishes them.

exec() — Replace Process Image

exec() does NOT create a new process. It replaces the current process's code and data with a new program. The PID
does not change. Usually called inside the child process after fork().

Variant Args Format Uses PATH? When to use

execl list (known at compile time) No (need full path) Fixed known args

execv array No (need full path) Dynamic args as array

execlp list Yes Fixed args, command name only

execvp array Yes Dynamic args, command name only

execle list + custom env No Need custom environment

execve array + custom env No Need custom environment

wait() — Parent Waits for Child

wait() suspends the parent until one of its child processes terminates. Returns the child's PID. Prevents zombie
processes. Always use wait() or waitpid() in parent process.

exit() — Terminate a Process

exit(0) = successful termination. exit(non-zero) = error. The exit status is returned to the parent through wait().

Zombie vs Orphan Processes

Process Type When it occurs What happens

Zombie Child calls exit() but parent never calls Child entry stays in process table, shown as <defunct>
(defunct) wait() in ps

Orphan Parent exits before child finishes Child is adopted by init process (PID=1)

Pthreads — POSIX Thread Functions

Function Syntax Purpose

pthread_create pthread_create(&tid, NULL, func, arg) Create new thread to run func(arg)

pthread_join pthread_join(tid, &retval) Wait for thread to finish (like wait() for processes)

pthread_exit pthread_exit(retval) Terminate calling thread

3. Programs (VERY IMPORTANT)

Program 1: fork() — Parent and Child with PID display + wait()

/* fork_basic.c
Compile: gcc fork_basic.c -o fork_prog
Run: ./fork_prog */
#include <sys/types.h>
#include <unistd.h>
#include <stdio.h>
#include <stdlib.h>
#include <sys/wait.h>

int main() {
pid_t pid;

printf("Before fork: PID = %d\n", getpid());

pid = fork(); /* fork() called ONCE, returns TWICE */

if (pid == -1) { /* Error */

perror("fork failed");
exit(1);
}
else if (pid == 0) { /* CHILD: fork() returned 0 */
printf("I am the CHILD\n");
printf(" Child PID = %d\n", getpid());
printf(" Parent PID = %d\n", getppid());
exit(0);
}
else { /* PARENT: fork() returned child's PID */
wait(NULL); /* Wait for child to finish */
printf("I am the PARENT\n");
printf(" Parent PID = %d\n", getpid());
printf(" Child PID = %d\n", pid);
}
return 0;
}

Program 2: fork() + exec() — Child runs a different program

/* fork_exec.c
Compile: gcc fork_exec.c -o fork_exec
Run: ./fork_exec */
#include <sys/types.h>
#include <stdio.h>
#include <unistd.h>
#include <sys/wait.h>
#include <stdlib.h>

int main() {
pid_t pid = fork();

if (pid < 0) {
fprintf(stderr, "Fork Failed\n");
return -1;
}
else if (pid == 0) { /* CHILD: replace with ls program */
execlp("/bin/ls", "ls", "-l", NULL);
/* If exec succeeds, code below is NEVER reached */
perror("exec failed");
exit(1);
}
else { /* PARENT: wait for child */
wait(NULL);
printf("Child Complete. Parent exiting.\n");
}
return 0;
}

Program 3: Zombie Process (for demonstration)

/* zombie.c — child exits but parent sleeps (no wait)

Compile: gcc zombie.c -o zombie
Run: ./zombie & then run: ps -aux | grep zombie */
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>

int main() {
pid_t pid = fork();
 if (pid == 0) {
printf("Child (PID=%d) exiting now.\n", getpid());
exit(0); /* Child exits immediately */
} else {
printf("Parent (PID=%d) sleeping for 30 sec...\n", getpid());
sleep(30); /* Parent sleeps — does NOT call wait() */
/* During this 30s, child is a ZOMBIE (defunct) */
}
return 0;
}

Program 4: Pthreads — Two threads with data passing

/* threads.c
Compile: gcc threads.c -lpthread -o threads
Run: ./threads */
#include <pthread.h>
#include <stdio.h>
#include <stdlib.h>

void* thread_func(void* param) {

int id = (int)(long)param;
printf("Hello from Thread %d (TID=%lu)\n", id, pthread_self());
return (void*)(long)(id * 10); /* Return id*10 as result */
}

int main() {
pthread_t t[3];
int retval[3];

for (int i = 0; i < 3; i++) {

pthread_create(&t[i], NULL, thread_func, (void*)(long)i);
}
for (int i = 0; i < 3; i++) {
pthread_join(t[i], (void**)&retval[i]);
printf("Thread %d returned: %d\n", i, retval[i]);
}
printf("Main thread done.\n");
return 0;
}

Program 5: Fibonacci using Pthreads (Classic Exam Question)

/* fib_thread.c
Compile: gcc fib_thread.c -lpthread -o fib
Run: ./fib (enter n when prompted) */
#include <pthread.h>
#include <stdio.h>
#include <stdlib.h>

int n;
int fib[50]; /* Shared array — main thread reads after join */

void* calc_fib(void* arg) {

fib[0] = 0; fib[1] = 1;
for (int i = 2; i < n; i++)
fib[i] = fib[i-1] + fib[i-2];
return NULL;
}

int main() {
printf("Enter number of Fibonacci terms: ");
scanf("%d", &n);

pthread_t tid;
pthread_create(&tid, NULL, calc_fib, NULL);
pthread_join(tid, NULL); /* Wait for child thread */

printf("Fibonacci series: ");

for (int i = 0; i < n; i++) printf("%d ", fib[i]);
printf("\n");
return 0;
}

▶ 4. Compile and Run Commands

# Regular C programs:
gcc program.c -o program
./program

# Programs using pthreads (MUST add -lpthread):

gcc threads.c -lpthread -o threads
./threads

# Run as background process:

./zombie &
ps -aux | grep zombie # To see the zombie process

5. Statement-Based Questions & How to Answer

"Demonstrate fork() system call."

Write Program 1. Explain: fork() creates child, returns 0 to child and child's PID to parent. Use if/else to separate behavior.
Show sample output with PIDs.

"Create a zombie (defunct) child process."

Write Program 3. Child calls exit() immediately. Parent sleeps with no wait(). Run with & in background, then ps -aux to
show <defunct> child.

"Load a binary executable in a child process using exec system call."

Write Program 2. fork() creates child, child calls execlp to replace itself with ls. Parent waits.

"Write a multithreaded program to generate Fibonacci series."

Write Program 5. Main creates child thread via pthread_create, child computes into shared array, main calls pthread_join
then prints.

6. Viva Questions

Q1: What is the return value of fork() in parent and child?

In the parent, fork() returns the PID of the child (positive integer). In the child, fork() returns 0. On error, it returns -1 and
sets errno.

Q2: What is the difference between fork() and exec()?

fork() creates a NEW process (child) that is an exact copy of the parent — two processes run simultaneously. exec()
replaces the CURRENT process's code and data with a new program — no new process is created, the PID stays the
same.

Q3: What is a zombie process?

A child process that has finished execution (called exit()) but whose exit status has not yet been collected by the parent
(parent hasn't called wait()). It remains in the process table as <defunct> until the parent collects it.

Q4: What is the difference between process and thread?

A process is an independent program with its own memory space, PCB, and resources. Threads are lightweight units of
execution within a process that share the same memory space. Threads are faster to create/communicate; processes are
more isolated.

Q5: Why do we use pthread_join()?

pthread_join() makes the calling thread wait for the specified thread to finish. It also retrieves the thread's return value
and frees its resources. Without it, the main thread may exit before child threads finish.

⚡ M US T REMEM BER — LAB 4

fork() returns: 0 to child | child's PID to parent | -1 on error

exec() does NOT create new process — replaces current process image
execlp/execvp use PATH to find command; execl/execv need full path
Always use wait(NULL) in parent to avoid zombie processes
Compile pthreads with -lpthread flag: gcc file.c -lpthread -o prog
pthread_create() parameters: &tid, NULL, function, argument
Zombie = child exits, parent doesn't wait | Orphan = parent dies first
 CPU Scheduling Algorithms
FCFS, SJF, SRTF, Priority, Round Robin — compute WT, TT, draw Gantt chart
★ HIGH WEIGHTAGE Programs + Gantt Chart

1. Concept Explanation

Key Definitions (Write ALL of these in exam)

Term Definition Exam Goal

Turnaround Time (TT) Total time from process submission to completion Minimize

Waiting Time (WT) Time spent waiting in the ready queue Minimize

Response Time Time from submission to first CPU response Minimize

CPU Utilization Percentage of time CPU is busy doing useful work Maximize

Throughput Number of processes completed per unit time Maximize

Burst Time (BT) CPU time required by the process Given

Arrival Time (AT) Time at which process enters the ready queue Given

Completion Time (CT) Time at which process finishes execution Calculated

Turnaround Time (TT) = Completion Time (CT) − Arrival Time (AT)

Waiting Time (WT) = Turnaround Time (TT) − Burst Time (BT)

Average WT = Sum of all WT / Number of processes

Scheduling Algorithms Summary

Algorithm Selection Policy Preemptive? Problem

FCFS First arrived, first served No Convoy effect (long jobs block short ones)

SJF Shortest burst time gets CPU first No Starvation of long jobs

SRTF Preemptive SJF — shortest REMAINING time Yes High overhead, starvation

Priority Highest priority process runs first Both versions Starvation of low-priority jobs

Round Each process gets a time quantum, then Yes High context-switch overhead if quantum too
Robin rotates small

3. Programs

Program 1: FCFS Scheduling

/* fcfs.c — First Come First Served

Compile: gcc fcfs.c -o fcfs | Run: ./fcfs */
#include <stdio.h>

int main() {
int n, i;
printf("Enter number of processes: ");
scanf("%d", &n);
int pid[n], bt[n], at[n], ct[n], tat[n], wt[n];

for (i = 0; i < n; i++) {

pid[i] = i + 1;
printf("Enter Arrival Time and Burst Time for P%d: ", i+1);
scanf("%d %d", &at[i], &bt[i]);
}

/* Calculate Completion Times */

ct[0] = at[0] + bt[0];
for (i = 1; i < n; i++) {
if (ct[i-1] < at[i]) /* CPU was idle */
 ct[i] = at[i] + bt[i];
else
ct[i] = ct[i-1] + bt[i];
}

float avgWT = 0, avgTAT = 0;

printf("\nP\tAT\tBT\tCT\tTAT\tWT\n");
for (i = 0; i < n; i++) {
tat[i] = ct[i] - at[i]; /* Turnaround Time */
wt[i] = tat[i] - bt[i]; /* Waiting Time */
printf("P%d\t%d\t%d\t%d\t%d\t%d\n",
pid[i], at[i], bt[i], ct[i], tat[i], wt[i]);
avgWT += wt[i];
avgTAT += tat[i];
}
printf("Average WT = %.2f\n", avgWT / n);
printf("Average TAT = %.2f\n", avgTAT / n);
return 0;
}

Program 2: Round Robin Scheduling

/* round_robin.c
Compile: gcc round_robin.c -o rr | Run: ./rr */
#include <stdio.h>
#include <string.h>

int main() {
int n, quantum, i;
printf("Enter number of processes: "); scanf("%d", &n);
printf("Enter time quantum: "); scanf("%d", &quantum);

int bt[n], at[n], remaining[n], wt[n], tat[n], ct[n];

for (i = 0; i < n; i++) {
printf("Enter AT and BT for P%d: ", i+1);
scanf("%d %d", &at[i], &bt[i]);
remaining[i] = bt[i];
}

int time = 0, done = 0;

memset(wt, 0, sizeof(wt));

while (done < n) {

int progress = 0;
for (i = 0; i < n; i++) {
if (remaining[i] > 0 && at[i] <= time) {
progress = 1;
if (remaining[i] > quantum) {
time += quantum;
remaining[i] -= quantum;
} else {
time += remaining[i];
ct[i] = time;
remaining[i] = 0;
done++;
}
}
}
if (!progress) time++; /* CPU idle — advance time */
}

float avgWT = 0, avgTAT = 0;

printf("\nP\tAT\tBT\tCT\tTAT\tWT\n");
for (i = 0; i < n; i++) {
tat[i] = ct[i] - at[i];
wt[i] = tat[i] - bt[i];
printf("P%d\t%d\t%d\t%d\t%d\t%d\n", i+1, at[i], bt[i], ct[i], tat[i], wt[i]);
avgWT += wt[i]; avgTAT += tat[i];
}
printf("Avg WT=%.2f, Avg TAT=%.2f\n", avgWT/n, avgTAT/n);
return 0;
}

▶ 4. Worked Example with Gantt Chart

Given: P1(AT=0,BT=60), P2(AT=3,BT=30), P3(AT=4,BT=40), P4(AT=9,BT=10)

FCFS — Gantt Chart:

P1 (0→60) P2 (60→90) P3 (90→130) P4

 P1 (0→60) P2 (60→90) P3 (90→130) P4
(130→140)

Process AT BT CT TT = CT−AT WT = TT−BT

P1 0 60 60 60 0

P2 3 30 90 87 57

P3 4 40 130 126 86

P4 9 10 140 131 121

Avg WT = (0 + 57 + 86 + 121) / 4 = 264 / 4 = 66

Avg TT = (60 + 87 + 126 + 131) / 4 = 404 / 4 = 101

Round Robin (quantum=10) — Gantt Chart:

P1(0-10) P2(10-20) P3(20-30) P1(30-40) P4(40-50) P2(50-60) P3(60-70) P1(70-80) P3(80-90) P1(90-100)

5. Statement-Based Questions

"Implement CPU scheduling algorithm — FCFS/Round Robin/SRTF."

Write the appropriate program. Input: n processes with AT and BT. Output: Gantt chart, individual WT and TT, average WT
and TT.

"Compute waiting time and turnaround time for each process."

Use formulas: TT = CT − AT, WT = TT − BT. Always show your calculations step by step.

6. Viva Questions

Q1: Difference between SJF and SRTF?

SJF (non-preemptive): Once a process starts running, it runs to completion. SRTF (preemptive SJF): If a new process
arrives with shorter remaining burst time than current process, the current is preempted.

Q2: What is starvation and aging?

Starvation is when a process waits indefinitely because higher-priority processes keep arriving. Aging is the solution —
gradually increase the priority of waiting processes over time.

Q3: What is the convoy effect in FCFS?

When a long CPU-bound process holds the CPU, all short processes behind it must wait — like a convoy of fast cars stuck
behind a slow truck. SJF and RR avoid this.

Q4: What is the optimal time quantum for Round Robin?

Quantum should be larger than most CPU burst times (to avoid too many context switches) but small enough to provide
good response time. Usually 10–100ms.

⚡ M US T REMEM BER — LAB 5

TT = CT − AT | WT = TT − BT | Avg = Sum / n
FCFS: non-preemptive, arrival order, suffers convoy effect
SJF: optimal average WT (non-preemptive) | SRTF: preemptive version
Priority: smaller number = higher priority (in this manual)
Round Robin: preemptive FCFS with time quantum, no starvation
ALWAYS draw Gantt chart in exam for full marks
For menu-driven program: use switch-case with FCFS/SJF/RR/Priority options
 Interprocess Communication (IPC)
Pipes, Named Pipes (FIFOs), Message Queues, Shared Memory

★ HIGH WEIGHTAGE Programs + Concepts

1. Concept Explanation

IPC (Interprocess Communication) is a mechanism that allows processes to communicate and share data with
each other. Linux supports: Pipes, Named Pipes (FIFOs), Message Queues, and Shared Memory.

IPC Method Direction Related Processes? Key Use

Pipe Unidirectional Yes (parent-child Simple data stream between related processes
only)

FIFO (Named Unidirectional No (any processes) Unrelated processes communicating via filesystem name
Pipe)

Message Queue Both No Structured messages with type; non-FCFS retrieval

directions possible

Shared Memory Both No Fastest IPC; direct memory access; needs synchronization
directions

Pipe System Calls

A pipe has two ends: fd[0] = read end, fd[1] = write end. Data flows one way only.

Function Syntax Purpose

pipe() pipe(int fd[2]) Create pipe. fd[0]=read, fd[1]=write. Returns 0 on success.

write() write(fd[1], buf, len) Write data to pipe

read() read(fd[0], buf, len) Read data from pipe

close() close(fd[0]) or close(fd[1]) Close unused pipe ends (IMPORTANT!)

Message Queue System Calls

Function Purpose

msgget(key, flags) Create or access a message queue; returns msqid

msgsnd(msqid, msg_ptr, size, flags) Send message to queue

msgrcv(msqid, msg_ptr, size, type, flags) Receive message from queue

msgctl(msqid, IPC_RMID, 0) Delete/control message queue

Shared Memory System Calls

Function Purpose

shmget(key, size, flags) Create shared memory segment; returns shmid

shmat(shmid, NULL, 0) Attach (map) into process address space; returns pointer

shmdt(ptr) Detach shared memory from process

shmctl(shmid, IPC_RMID, 0) Delete shared memory segment

3. Programs

Program 1: Pipe — Parent writes, Child reads

/* pipe_comm.c
Compile: gcc pipe_comm.c -o pipe_prog | Run: ./pipe_prog */
#include <stdio.h>
#include <unistd.h>
#include <string.h>
 #include <sys/wait.h>

int main() {
int fd[2];
char buf[100];
char *msg = "Hello from Parent to Child via Pipe!";

if (pipe(fd) == -1) { perror("pipe failed"); return 1; }

pid_t pid = fork();

if (pid == 0) { /* CHILD: reads from pipe */
close(fd[1]); /* Close WRITE end — not needed by child */
int n = read(fd[0], buf, sizeof(buf));
buf[n] = '\0';
printf("Child received: %s\n", buf);
close(fd[0]);
} else { /* PARENT: writes to pipe */
close(fd[0]); /* Close READ end — not needed by parent */
write(fd[1], msg, strlen(msg));
close(fd[1]); /* Close write end — signals EOF to child */
wait(NULL);
}
return 0;
}

Program 2: Message Queue — Send number, check palindrome

/* msg_sender.c — Run this first */

#include <stdio.h>
#include <stdlib.h>
#include <sys/msg.h>

struct msg_buf { long mtype; int num; };

int main() {
int msqid = msgget((key_t)1234, 0666 | IPC_CREAT);
struct msg_buf msg;
[Link] = 1;
printf("Enter a number: "); scanf("%d", &[Link]);
msgsnd(msqid, &msg, sizeof(int), 0);
printf("Sent: %d\n", [Link]);
return 0;
}

/* msg_receiver.c — Run this after sender */

#include <stdio.h>
#include <stdlib.h>
#include <sys/msg.h>

struct msg_buf { long mtype; int num; };

int isPalindrome(int n) {
int rev = 0, orig = n;
while (n > 0) { rev = rev * 10 + n % 10; n /= 10; }
return rev == orig;
}

int main() {
int msqid = msgget((key_t)1234, 0666 | IPC_CREAT);
struct msg_buf msg;
msgrcv(msqid, &msg, sizeof(int), 1, 0);
printf("Received: %d\n", [Link]);
printf("%d is %sa palindrome\n", [Link], isPalindrome([Link]) ? "" : "NOT ");
msgctl(msqid, IPC_RMID, 0);
return 0;
}

Program 3: Shared Memory — Parent sends char, Child replies with next char

/* shm_comm.c — Parent and child share memory

Compile: gcc shm_comm.c -o shm_prog | Run: ./shm_prog */
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <sys/shm.h>
#include <sys/wait.h>

struct shared_data { int flag; char ch; };

int main() {
 int shmid = shmget((key_t)1234, sizeof(struct shared_data), 0666 | IPC_CREAT);
struct shared_data *shm = (struct shared_data*) shmat(shmid, NULL, 0);
shm->flag = 0;

pid_t pid = fork();

if (pid == 0) { /* CHILD: wait for parent, then reply */
while (shm->flag == 0); /* Wait until parent writes */
printf("Child received: %c\n", shm->ch);
shm->ch = shm->ch + 1; /* Next character */
shm->flag = 2; /* Signal parent */
shmdt(shm);
} else { /* PARENT: write a character */
shm->ch = 'A';
shm->flag = 1; /* Signal child */
while (shm->flag != 2); /* Wait for child's reply */
printf("Parent received reply: %c\n", shm->ch);
shmdt(shm);
shmctl(shmid, IPC_RMID, 0); /* Delete shared memory */
wait(NULL);
}
return 0;
}

5. Statement-Based Questions

"Demonstrate creation, writing to and reading from a pipe."

Show Program 1. Explain fd[0]=read end, fd[1]=write end. Why close unused ends.

"Process A wants to send a number to Process B via message queue. B checks if it's a palindrome."
Show Programs in Program 2 — sender and receiver. Explain msgget, msgsnd, msgrcv, msgctl/IPC_RMID.

"Parent sends English alphabet to child using shared memory. Child responds with next alphabet."
Show Program 3. Explain shmget, shmat, shmdt, shmctl. Use a flag variable for synchronization.

6. Viva Questions

Q1: What is a pipe? What are its limitations?

A pipe is a unidirectional byte stream channel. Limitations: (1) Only between related (parent-child) processes, (2)
Unidirectional, (3) No persistence. FIFOs overcome limitation 1.

Q2: Why must unused pipe ends be closed?

If the write end is not closed by the reader, the reader will block indefinitely waiting for more data — it will never see
EOF. Closing unused ends ensures proper EOF signaling and prevents resource leaks.

Q3: What is the difference between pipe and FIFO?

Pipe is unnamed, exists only in memory, usable only between parent-child processes. FIFO (named pipe) has a filesystem
name (created with mkfifo), accessible by any unrelated processes knowing the name.

Q4: What is the fastest IPC method and why?

Shared memory is the fastest IPC. Processes directly read/write the same memory region — no kernel involvement for
data transfer. However, it requires synchronization (semaphores/mutex) to avoid race conditions.

⚡ M US T REMEM BER — LAB 6

Pipe: fd[0]=read end, fd[1]=write end — unidirectional, parent-child only

Always close unused pipe ends after fork()
Message queue key: use (key_t)1234 consistently between sender and receiver
msgtype=0 in msgrcv retrieves any message; msgtype=N retrieves type N only
Shared memory: shmget → shmat → use → shmdt → shmctl(IPC_RMID)
Shared memory is fastest IPC but needs synchronization
 Process Synchronization
Data races, Mutex, Semaphores, Producer-Consumer, Readers-Writers, Dining Philosophers

★ HIGH WEIGHTAGE Classic Problems

1. Concept Explanation

Data Race
A data race occurs when two or more threads access the same shared variable simultaneously, and at least one is
writing to it. This leads to unpredictable, incorrect results.

Mutex (Mutual Exclusion Lock)

A mutex is a binary lock — only one thread can hold it at a time. Other threads trying to lock it will block until
released. Used to protect a critical section.

Function Purpose

pthread_mutex_init(&m, NULL) Initialize mutex (or use PTHREAD_MUTEX_INITIALIZER)

pthread_mutex_lock(&m) Acquire lock — blocks if another thread holds it

pthread_mutex_unlock(&m) Release lock

pthread_mutex_destroy(&m) Free mutex resources

Semaphore
A semaphore is a counting variable that controls access to shared resources. Supports P() (wait/down) and V()
(signal/up) operations.

Function Effect Also called

sem_init(&s, 0, N) Initialize with value N. 0=process-private, 1=shared between processes -

sem_wait(&s) Decrement. If result is negative, thread BLOCKS until > 0 P() or down()

sem_post(&s) Increment. If threads are waiting, one is unblocked V() or up()

sem_destroy(&s) Free semaphore resources -

Producer-Consumer Problem (Bounded Buffer)

Producer adds items to a buffer. Consumer removes items. Buffer has fixed size N.

Semaphore Initial Value Purpose

mutex 1 Mutual exclusion for buffer access (critical section)

full 0 Count of filled slots (items available for consumer)

empty N (buffer size) Count of empty slots (space available for producer)

Readers-Writers Problem
Multiple readers can read simultaneously — no problem
A writer needs exclusive access — no other reader or writer can operate
First R-W Problem: Readers have priority (no reader waits if only readers are reading)
Second R-W Problem: Writers have priority (no new reader starts if a writer is waiting)

3. Programs

Program 1: Mutex — Protecting shared counter

/* mutex_counter.c
Compile: gcc mutex_counter.c -lpthread -o mutex_prog | Run: ./mutex_prog */
#include <pthread.h>
#include <stdio.h>

pthread_mutex_t mutex;
volatile int counter = 0;
 void* increment(void* param) {
for (int i = 0; i < 1000; i++) {
pthread_mutex_lock(&mutex); /* LOCK — enter critical section */
counter++;
pthread_mutex_unlock(&mutex); /* UNLOCK — leave critical section */
}
return NULL;
}

int main() {
pthread_t t1, t2;
pthread_mutex_init(&mutex, NULL);
pthread_create(&t1, NULL, increment, NULL);
pthread_create(&t2, NULL, increment, NULL);
pthread_join(t1, NULL);
pthread_join(t2, NULL);
pthread_mutex_destroy(&mutex);
printf("Final counter = %d (should be 2000)\n", counter);
return 0;
}

Program 2: Producer-Consumer using Semaphores

/* prod_cons.c
Compile: gcc prod_cons.c -lpthread -lrt -o pc | Run: ./pc */
#include <stdio.h>
#include <pthread.h>
#include <semaphore.h>
#include <unistd.h>

#define BUFFER_SIZE 5
int buf[BUFFER_SIZE];
int in = 0, out = 0;
sem_t mutex, full, empty;

void* producer(void* arg) {

for (int i = 0; i < 10; i++) {
sem_wait(&empty); /* Wait if buffer is full */
sem_wait(&mutex); /* Enter critical section */
buf[in] = i; /* Produce item i */
printf("Produced: %d | Buffer[%d] = %d\n", i, in, buf[in]);
in = (in + 1) % BUFFER_SIZE;
sem_post(&mutex); /* Leave critical section */
sem_post(&full); /* Signal: one more item available */
sleep(1);
}
return NULL;
}

void* consumer(void* arg) {

for (int i = 0; i < 10; i++) {
sem_wait(&full); /* Wait if buffer is empty */
sem_wait(&mutex); /* Enter critical section */
int item = buf[out];
printf("Consumed: %d | From Buffer[%d]\n", item, out);
out = (out + 1) % BUFFER_SIZE;
sem_post(&mutex); /* Leave critical section */
sem_post(&empty); /* Signal: one more space available */
sleep(2);
}
return NULL;
}

int main() {
sem_init(&mutex, 0, 1); /* mutex = 1 (binary semaphore) */
sem_init(&full, 0, 0); /* full = 0 (no items initially) */
sem_init(&empty, 0, BUFFER_SIZE); /* empty = 5 (all slots free) */

pthread_t tid1, tid2;

pthread_create(&tid1, NULL, producer, NULL);
pthread_create(&tid2, NULL, consumer, NULL);
pthread_join(tid1, NULL);
pthread_join(tid2, NULL);

sem_destroy(&mutex);
sem_destroy(&full);
sem_destroy(&empty);
return 0;
}
Program 3: Semaphore ordering — Thread 1 before Thread 2

/* sem_order.c — Guarantee Thread1 prints before Thread2

Compile: gcc sem_order.c -lpthread -lrt -o sem_order */
#include <pthread.h>
#include <stdio.h>
#include <semaphore.h>

sem_t semaphore;

void* func1(void* param) {

printf("Thread 1 executing\n");
sem_post(&semaphore); /* Signal Thread 2 to proceed */
return NULL;
}

void* func2(void* param) {

sem_wait(&semaphore); /* Wait until Thread 1 signals */
printf("Thread 2 executing (after Thread 1)\n");
return NULL;
}

int main() {
pthread_t t1, t2;
sem_init(&semaphore, 0, 0); /* Start at 0 — Thread 2 will wait */
pthread_create(&t1, NULL, func1, NULL);
pthread_create(&t2, NULL, func2, NULL);
pthread_join(t1, NULL);
pthread_join(t2, NULL);
sem_destroy(&semaphore);
return 0;
}

5. Statement-Based Questions

"Implement Producer-Consumer problem using semaphores."

Show Program 2. Explain 3 semaphores: mutex=1 (critical section), full=0 (items), empty=N (spaces). Producer:
wait(empty)→wait(mutex)→produce→post(mutex)→post(full). Consumer:
wait(full)→wait(mutex)→consume→post(mutex)→post(empty).

"Demonstrate use of mutex to prevent data race."

Show Program 1. Without mutex, final counter will be less than 2000 due to race condition. With mutex, it is always
exactly 2000.

6. Viva Questions

Q1: Difference between mutex and semaphore?

Mutex is a binary lock (only 0 or 1) — ONLY the thread that locked it can unlock it. Semaphore is a counting mechanism
(0 to N) — any thread can call sem_wait/sem_post. Mutex is for mutual exclusion; semaphore is for signaling and
counting.

Q2: What are sem_wait() and sem_post()?

sem_wait() = P() = down(): decrements semaphore. If it becomes 0 or negative, the calling thread blocks. sem_post() =
V() = up(): increments semaphore, potentially unblocking a waiting thread.

Q3: In Producer-Consumer, what do the 3 semaphores represent?

full = count of items in buffer (starts at 0). empty = count of free slots (starts at BUFFER_SIZE). mutex = binary
semaphore ensuring only one thread accesses the buffer at a time (starts at 1).

Q4: What is a critical section?

A section of code that accesses shared resources (variables, files, hardware) and must not be executed by more than one
thread/process simultaneously. Protected using mutex or semaphore.

⚡ M US T REMEM BER — LAB 7

sem_wait() = P() = down() | sem_post() = V() = up()

Mutex is binary semaphore; initialized to 1
Producer-Consumer: mutex=1, full=0, empty=N (buffer size)
Order in Producer: ALWAYS sem_wait(empty) BEFORE sem_wait(mutex)
Order in Consumer: ALWAYS sem_wait(full) BEFORE sem_wait(mutex)
Compile: gcc file.c -lpthread -lrt -o prog
 Deadlock Management Algorithms
Banker's Algorithm (Avoidance), Deadlock Detection Algorithm

★ HIGH WEIGHTAGE Algorithm + Program

1. Concept Explanation

What is a Deadlock?
A deadlock is a situation where a set of processes are permanently blocked — each waiting for a resource held by
another process in the same set. It's a circular dependency.

Four Necessary Conditions (ALL must be true simultaneously)

# Condition Meaning

1 Mutual Exclusion At least one resource must be held in non-sharable mode

2 Hold and Wait A process holds resources while waiting for more

3 No Preemption Resources cannot be forcefully taken from a process

4 Circular Wait A cycle exists: P1→R1→P2→R2→P1

Banker's Algorithm — Data Structures

For n processes and m resource types:

Name Size Meaning How to get

Available m Number of available instances of each resource type Given

Max n×m Maximum instances each process may ever request Given

Allocation n×m Currently allocated to each process Given

Need n×m Still needed by each process to complete Need = Max − Allocation

Need[i][j] = Max[i][j] − Allocation[i][j]

Safety Algorithm (checks if system is in safe state)

A state is safe if there exists a safe sequence where each process can eventually complete using available +
released resources.

1. Initialize: Work = Available; Finish[i] = false for all i

2. Find process i such that: Finish[i]=false AND Need[i] ≤ Work
3. Work = Work + Allocation[i]; Finish[i] = true; go back to step 2
4. If ALL Finish[i] = true → SAFE STATE. Otherwise → UNSAFE (possible deadlock)

Resource Request Algorithm

1. If Request[i] > Need[i] → ERROR (exceeded max claim)
2. If Request[i] > Available → WAIT (not enough resources)
3. Tentatively allocate: Available -= Request; Allocation[i] += Request; Need[i] -= Request
4. Run safety algorithm. If SAFE → grant request. If UNSAFE → rollback and make process wait.

3. Banker's Algorithm Program

Worked Example (from Lab Manual):

Resources: A=10, B=5, C=7 | 5 processes

Process Alloc (A,B,C) Max (A,B,C) Need (A,B,C)

P0 0,1,0 7,5,3 7,4,3

P1 2,0,0 3,2,2 1,2,2

P2 3,0,2 9,0,2 6,0,0

 P3 2,1,1 2,2,2 0,1,1

P4 0,0,2 4,3,3 4,3,1

Available = (3,3,2). Safe sequence: P1 → P3 → P4 → P0 → P2

/* banker.c — Banker's Algorithm

Compile: gcc banker.c -o banker | Run: ./banker */
#include <stdio.h>
#include <stdbool.h>

int n, m; /* n=processes, m=resources */

int alloc[10][10], need[10][10], avail[10];

bool isSafe() {
int work[10];
bool finish[10];
for (int i=0; i<m; i++) work[i] = avail[i];
for (int i=0; i<n; i++) finish[i] = false;

int safeSeq[10], count = 0;

while (count < n) {
bool found = false;
for (int i=0; i<n; i++) {
if (!finish[i]) {
bool ok = true;
for (int j=0; j<m; j++)
if (need[i][j] > work[j]) { ok = false; break; }
if (ok) {
for (int j=0; j<m; j++) work[j] += alloc[i][j];
safeSeq[count++] = i;
finish[i] = true;
found = true;
}
}
}
if (!found) { printf("UNSAFE STATE! Deadlock possible.\n"); return false; }
}
printf("SAFE STATE. Safe sequence: ");
for (int i=0; i<n; i++) printf("P%d ", safeSeq[i]);
printf("\n");
return true;
}

void resourceRequest(int pid, int req[]) {

printf("\nRequest from P%d: ", pid);
for (int j=0; j<m; j++) printf("%d ", req[j]);
printf("\n");

/* Step 1: Check Request <= Need */

for (int j=0; j<m; j++)
if (req[j] > need[pid][j]) { printf("Error: exceeded max claim\n"); return; }
/* Step 2: Check Request <= Available */
for (int j=0; j<m; j++)
if (req[j] > avail[j]) { printf("P%d must wait: resources unavailable\n", pid); return; }
/* Step 3: Tentatively allocate */
for (int j=0; j<m; j++) {
avail[j] -= req[j];
alloc[pid][j] += req[j];
need[pid][j] -= req[j];
}
/* Step 4: Safety check */
if (!isSafe()) {
printf("Request DENIED (unsafe). Rolling back.\n");
for (int j=0; j<m; j++) { avail[j] += req[j]; alloc[pid][j] -= req[j]; need[pid][j] += req[j]; }
} else {
printf("Request GRANTED.\n");
}
}

int main() {
printf("Enter number of processes and resources: "); scanf("%d %d", &n, &m);
printf("Enter Allocation matrix (%dx%d):\n", n, m);
for (int i=0; i<n; i++) for (int j=0; j<m; j++) scanf("%d", &alloc[i][j]);
printf("Enter Max matrix (%dx%d):\n", n, m);
int max[10][10];
for (int i=0; i<n; i++) for (int j=0; j<m; j++) { scanf("%d", &max[i][j]); need[i][j] = max[i][j] - alloc[i][j]; }
printf("Enter Available resources (%d values):\n", m);
for (int j=0; j<m; j++) scanf("%d", &avail[j]);

printf("\nNeed matrix:\n");
 for (int i=0; i<n; i++) { printf("P%d: ", i); for (int j=0; j<m; j++) printf("%d ", need[i][j]); printf("\n"); }

isSafe();

int pid, req[10];

printf("\nEnter process number for resource request: "); scanf("%d", &pid);
printf("Enter request (%d values): ", m);
for (int j=0; j<m; j++) scanf("%d", &req[j]);
resourceRequest(pid, req);
return 0;
}

5. Statement-Based Questions

"Implement Banker's algorithm for deadlock avoidance."

Show the program. Input the example from the manual. Show Need matrix computation, safety check with safe sequence
output, then test a request.

"Determine if the system is in a safe state. Can request (1,0,2) from P1 be granted?"
Compute Need = Max − Allocation. Run safety algorithm — show safe sequence. For the request: check Request ≤ Need,
Request ≤ Available, tentatively allocate, re-run safety algorithm.

6. Viva Questions

Q1: What are the 4 necessary conditions for deadlock?

(1) Mutual Exclusion, (2) Hold and Wait, (3) No Preemption, (4) Circular Wait. ALL four must be present simultaneously for
deadlock to occur.

Q2: What is a safe state?

A system is in a safe state if there exists at least one safe sequence of processes — each process can eventually get all
the resources it needs using currently available resources plus resources released by earlier processes in the sequence.

Q3: Deadlock avoidance vs. detection?

Avoidance (Banker's Algorithm): Proactively check before each allocation to ensure system stays safe — never enters
deadlock. Detection: Allow deadlock to occur, periodically check if it occurred, then recover by killing processes or
preempting resources.

Q4: Why is it called the Banker's Algorithm?

It's analogous to a bank — the OS (bank) only allocates resources (loans) if it can still satisfy all potential future requests.
Like a bank maintaining enough reserve to handle all customer withdrawals.

⚡ M US T REMEM BER — LAB 8

ALWAYS compute Need = Max − Allocation first

Safety check: Work=Available, find process where Need≤Work, add its Allocation to Work, mark done.
Repeat.
If ALL processes can finish → safe. If stuck → unsafe.
Resource Request: check ≤Need, check ≤Available, tentatively allocate, run safety check
Safe sequence may not be unique — any valid sequence is acceptable
4 deadlock conditions must ALL be true simultaneously
 Memory Management I
First Fit, Best Fit, Worst Fit allocation + Paging + Segmentation
★ HIGH WEIGHTAGE Simulation Programs

1. Concept Explanation

Memory Allocation Strategies (Contiguous Allocation)

Strategy How It Works Advantage Disadvantage

First Fit Allocate the FIRST hole that is big enough. Stop Fastest allocation May leave unusable fragments
searching once found. at start

Best Fit Allocate the SMALLEST hole that is big enough. Smallest leftover fragment Slowest (full scan); small
Must scan entire list. fragments unusable

Worst Allocate the LARGEST hole. Must scan entire Largest leftover hole (may Wastes large holes
Fit list. be reusable)

Fragmentation
External Fragmentation: Enough total memory exists, but not contiguous. First Fit and Best Fit both suffer
from this. Solution: Compaction (shuffle memory to merge free holes).
Internal Fragmentation: Allocated memory is slightly larger than requested. Waste is inside the partition.

Paging
Paging divides physical memory into fixed-size frames and logical memory into same-size pages. A page table
maps page numbers to frame numbers. Eliminates external fragmentation; may have internal fragmentation.

Page Number (p) = Logical Address ÷ Page Size

Page Offset (d) = Logical Address mod Page Size

Physical Address = (Frame Number × Page Size) + Offset

Segmentation
Segmentation divides memory into variable-size logical segments (code, stack, heap, data). Each segment has a
base address and limit (size). Supports the user's view of memory. May have external fragmentation.

Physical Address = Segment Base + Offset (only if Offset < Segment Limit)

3. Program — First Fit, Best Fit, Worst Fit

/* memory_alloc.c
Compile: gcc memory_alloc.c -o mem | Run: ./mem */
#include <stdio.h>
#include <string.h>

#define MAX 10

int main() {
int nb, np;
int bsize[MAX], psize[MAX];

printf("Enter number of memory blocks: "); scanf("%d", &nb);

printf("Enter sizes of blocks: ");
for (int i=0; i<nb; i++) scanf("%d", &bsize[i]);

printf("Enter number of processes: "); scanf("%d", &np);

printf("Enter sizes of processes: ");
for (int i=0; i<np; i++) scanf("%d", &psize[i]);

int avail[MAX], alloc[MAX];

/* ========== FIRST FIT ========== */

memcpy(avail, bsize, nb * sizeof(int));
memset(alloc, -1, sizeof(alloc));
 printf("\n=== FIRST FIT ===\n");
printf("%-12s%-12s%-12s%-12s\n", "Process", "Size", "Block No", "Fragment");
for (int i=0; i<np; i++) {
for (int j=0; j<nb; j++) {
if (avail[j] >= psize[i]) {
alloc[i] = j;
printf("P%-11d%-12d%-12d%-12d\n", i+1, psize[i], j+1, avail[j]-psize[i]);
avail[j] -= psize[i];
break;
}
}
if (alloc[i] == -1) printf("P%-11d%-12d%-12s\n", i+1, psize[i], "Not Allocated");
}

/* ========== BEST FIT ========== */

memcpy(avail, bsize, nb * sizeof(int));
memset(alloc, -1, sizeof(alloc));
printf("\n=== BEST FIT ===\n");
printf("%-12s%-12s%-12s%-12s\n", "Process", "Size", "Block No", "Fragment");
for (int i=0; i<np; i++) {
int best = -1, minFrag = 999999;
for (int j=0; j<nb; j++) {
if (avail[j] >= psize[i] && (avail[j] - psize[i]) < minFrag) {
minFrag = avail[j] - psize[i];
best = j;
}
}
if (best != -1) {
alloc[i] = best;
printf("P%-11d%-12d%-12d%-12d\n", i+1, psize[i], best+1, avail[best]-psize[i]);
avail[best] -= psize[i];
} else {
printf("P%-11d%-12d%-12s\n", i+1, psize[i], "Not Allocated");
}
}

/* ========== WORST FIT ========== */

memcpy(avail, bsize, nb * sizeof(int));
memset(alloc, -1, sizeof(alloc));
printf("\n=== WORST FIT ===\n");
printf("%-12s%-12s%-12s%-12s\n", "Process", "Size", "Block No", "Fragment");
for (int i=0; i<np; i++) {
int worst = -1, maxFrag = -1;
for (int j=0; j<nb; j++) {
if (avail[j] >= psize[i] && avail[j] > maxFrag) {
maxFrag = avail[j];
worst = j;
}
}
if (worst != -1) {
alloc[i] = worst;
printf("P%-11d%-12d%-12d%-12d\n", i+1, psize[i], worst+1, avail[worst]-psize[i]);
avail[worst] -= psize[i];
} else {
printf("P%-11d%-12d%-12s\n", i+1, psize[i], "Not Allocated");
}
}
return 0;
}

Manual Example (from Lab Manual):

Blocks: 100K, 500K, 200K, 300K, 600K | Processes: 212K, 417K, 112K, 426K

Process Size First Fit Block Best Fit Block Worst Fit Block

P1 212K Block 2 (500K) Block 4 (300K) Block 5 (600K)

P2 417K Block 5 (600K) Block 2 (500K) Block 2 (500K)

P3 112K Block 2 (288K rem) Block 1 (100K) — FAIL Block 4 (300K)

P4 426K Not Allocated Not Allocated Not Allocated

5. Statement-Based Questions

"Simulate First-Fit, Best-Fit and Worst-Fit strategies."

Show the program. Run with given input. Display allocation table with block number and internal fragmentation for each
strategy. State which makes most efficient use of memory.
"Assuming page size of 32 bytes, display page number and offset for logical address 204."
Page No = 204 / 32 = 6. Offset = 204 mod 32 = 12. Answer: Page 6, Offset 12.

6. Viva Questions

Q1: Which memory allocation strategy is the best?

First Fit is fastest. Best Fit produces smallest remaining hole. Worst Fit produces largest remaining hole. Simulations show
First Fit and Best Fit are generally better than Worst Fit in practice.

Q2: Difference between paging and segmentation?

Paging: fixed-size pages/frames, no external fragmentation, may have internal. Segmentation: variable-size segments, no
internal fragmentation, may have external. Paging is hardware-transparent; segmentation matches programmer's logical
view.

Q3: What is compaction?

Compaction rearranges memory contents to consolidate all free holes into one large contiguous free block, eliminating
external fragmentation. It is time-consuming and requires relocation of processes.

⚡ M US T REMEM BER — LAB 9

First Fit: stop at first hole big enough | Best Fit: scan all, pick smallest fitting | Worst Fit: scan all, pick largest
External fragmentation: free space exists but not contiguous — solved by compaction or paging
Internal fragmentation: allocated block bigger than needed — inherent in paging
Paging formulas: page# = addr / pageSize, offset = addr mod pageSize
Physical address = frameNumber × pageSize + offset
 Memory Management II — Page Replacement
FIFO, Optimal, LRU page replacement — count page faults, compute hit ratio

★ HIGH WEIGHTAGE Simulation + Trace Table

1. Concept Explanation

Page Fault and Page Replacement

A page fault occurs when a referenced page is NOT in physical memory (frames). The OS must load it from disk,
possibly replacing an existing page. The algorithm for deciding which page to replace is the page replacement
algorithm.

Page Replacement Algorithms

Algorithm Replace Which Page? Implementation Belady's Anomaly?

FIFO The OLDEST page (first brought Queue — remove from front YES (more frames can mean
in) more faults!)

Optimal Page not needed for LONGEST Requires future knowledge — No

(OPT) future time theoretical only

LRU LEAST RECENTLY USED page Track last-access time for each No
frame

Hit Ratio = (Total References − Page Faults) / Total References × 100%

Miss Ratio = Page Faults / Total References × 100%

Example — Reference String: 7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1 | Frames = 3

FIFO: 15 page faults | Optimal: 9 page faults | LRU: 12 page faults

3. Programs

Program 1: FIFO Page Replacement

/* fifo_page.c
Compile: gcc fifo_page.c -o fifo | Run: ./fifo */
#include <stdio.h>
#include <stdbool.h>
#include <string.h>

int main() {
int frames, n;
printf("Enter number of frames: "); scanf("%d", &frames);
printf("Enter number of page references: "); scanf("%d", &n);
int pages[n];
printf("Enter page reference string: ");
for (int i=0; i<n; i++) scanf("%d", &pages[i]);

int frame[frames];
memset(frame, -1, sizeof(frame));
int head = 0, faults = 0;

printf("\n%-8s", "Page");
for (int i=0; i<frames; i++) printf("F%-5d", i+1);
printf("Status\n");
printf("--------------------------------------------------------\n");

for (int i=0; i<n; i++) {

bool found = false;
for (int j=0; j<frames; j++)
if (frame[j] == pages[i]) { found = true; break; }

if (!found) { /* PAGE FAULT */

frame[head] = pages[i];
head = (head + 1) % frames; /* FIFO circular pointer */
faults++;
}
 printf("%-8d", pages[i]);
for (int j=0; j<frames; j++) {
if (frame[j] == -1) printf("%-6s", "-");
else printf("%-6d", frame[j]);
}
printf("%s\n", found ? "HIT" : "FAULT");
}

printf("\nTotal Page Faults = %d\n", faults);

printf("Total Page Hits = %d\n", n - faults);
printf("Hit Ratio = %.2f%%\n", (float)(n-faults)/n*100);
return 0;
}

Program 2: LRU Page Replacement

/* lru_page.c
Compile: gcc lru_page.c -o lru | Run: ./lru */
#include <stdio.h>
#include <stdbool.h>
#include <string.h>
#include <limits.h>

int main() {
int frames, n;
printf("Enter number of frames: "); scanf("%d", &frames);
printf("Enter number of page references: "); scanf("%d", &n);
int pages[n];
printf("Enter page reference string: ");
for (int i=0; i<n; i++) scanf("%d", &pages[i]);

int frame[frames], last_used[frames];

memset(frame, -1, sizeof(frame));
memset(last_used, -1, sizeof(last_used));
int faults = 0, filled = 0;

printf("\n%-8s", "Page");
for (int i=0; i<frames; i++) printf("F%-5d", i+1);
printf("Status\n");
printf("--------------------------------------------------\n");

for (int i=0; i<n; i++) {

bool found = false;
int hit_idx = -1;
for (int j=0; j<frames; j++)
if (frame[j] == pages[i]) { found = true; hit_idx = j; break; }

if (!found) { /* PAGE FAULT */

faults++;
int replace;
if (filled < frames) { /* Empty slot available */
replace = filled++;
} else { /* Find LRU frame (smallest last_used) */
int min_time = INT_MAX, min_idx = 0;
for (int j=0; j<frames; j++)
if (last_used[j] < min_time) { min_time = last_used[j]; min_idx = j; }
replace = min_idx;
}
frame[replace] = pages[i];
last_used[replace] = i;
} else {
last_used[hit_idx] = i; /* Update last used time on hit */
}

printf("%-8d", pages[i]);
for (int j=0; j<frames; j++) {
if (frame[j] == -1) printf("%-6s", "-");
else printf("%-6d", frame[j]);
}
printf("%s\n", found ? "HIT" : "FAULT");
}

printf("\nTotal Page Faults = %d\n", faults);

printf("Hit Ratio = %.2f%%\n", (float)(n-faults)/n*100);
return 0;
}

Optimal Page Replacement — Core Logic

/* In optimal, for each page fault, replace the page

 that will NOT be used for the LONGEST future time */
int findOptimal(int frame[], int frames, int pages[], int curr, int n) {
int farthest = -1, replace = 0;
for (int j=0; j<frames; j++) {
int k;
for (k=curr+1; k<n; k++)
if (pages[k] == frame[j]) break;
if (k == n) return j; /* This page never used again — replace it */
if (k > farthest) { farthest = k; replace = j; }
}
return replace;
}

▶ 4. Trace Table Example — FIFO (3 Frames)

Reference string: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5

Page F1 F2 F3 Status

1 1 - - FAULT

2 1 2 - FAULT

3 1 2 3 FAULT

4 4 2 3 FAULT (replace 1)

1 4 1 3 FAULT (replace 2)

2 4 1 2 FAULT (replace 3)

5 5 1 2 FAULT (replace 4)

1 5 1 2 HIT

2 5 1 2 HIT

3 5 3 2 FAULT (replace 1)

4 5 3 4 FAULT (replace 2)

5 5 3 4 HIT

Page Faults = 9 | Hits = 3 | Hit Ratio = 3/12 × 100 = 25%

5. Statement-Based Questions

"Simulate page replacement algorithms FIFO and Optimal."

Show both programs. Run with the given reference string. Display the trace table, total page faults, and hit ratio for each
algorithm.

"Simulate LRU page replacement and compute hit ratio."

Show LRU program. In LRU, track the time each frame was last accessed. On page fault, replace the one with the oldest
access time (smallest last_used value).

6. Viva Questions

Q1: Which page replacement algorithm is optimal?

The Optimal (OPT) algorithm gives the minimum page fault rate. However, it requires future knowledge of the reference
string so it cannot be implemented in practice — it's used only as a theoretical benchmark to compare other algorithms.

Q2: What is Belady's Anomaly?

In FIFO page replacement, increasing the number of frames can sometimes INCREASE the number of page faults. This
counterintuitive behavior is Belady's Anomaly. It does NOT occur in LRU or Optimal algorithms.

Q3: Why is LRU better than FIFO?

LRU exploits temporal locality — recently used pages are likely to be used again soon. FIFO just replaces the oldest page
regardless of usage pattern, which may evict frequently-used pages.

Q4: What is the difference between page fault and page hit?
Page hit: the referenced page IS in memory (frames) — no disk access needed, fast. Page fault: the referenced page is
NOT in memory — OS must load it from disk, causes delay. More faults = slower performance.

⚡ M US T REMEM BER — LAB 10

Page Fault = page not in memory → load from disk | Hit = page in memory
FIFO: replace oldest page (use circular pointer); suffers Belady's Anomaly
Optimal: replace page not used for longest future time (theoretical only)
LRU: replace page not used for longest past time (track last_used time)
Hit Ratio = (n − faults) / n × 100%
FIFO has Belady's Anomaly; LRU and Optimal do NOT
Optimal always gives minimum faults; LRU is the best implementable algorithm
 Disk Scheduling Algorithms
FCFS, SSTF, SCAN, C-SCAN, LOOK, C-LOOK — minimize total head movement

★ HIGH WEIGHTAGE THM Calculation + Program

1. Concept Explanation

Key Terms

Term Definition

Seek Time Time for disk arm to move to the target track/cylinder

Cylinder Set of tracks at one arm position across all platters

THM (Total Head Movement) Sum of all cylinder-to-cylinder distances traveled

Disk Scheduling Selecting the order to service pending I/O requests to minimize seek time

Disk Scheduling Algorithms

THM
Algorithm Rule Key Feature
(example)

FCFS Service requests in arrival order 640 Simple, fair, but poor performance

SSTF Service nearest cylinder first (minimum seek 236 Better than FCFS; may cause
time) starvation

SCAN Move one direction servicing all, then reverse at 236 Like elevator — fair, uniform service
(Elevator) end

C-SCAN One direction to end, jump to start, service 183 More uniform wait time than SCAN
again

LOOK Like SCAN but only goes to last request, not end 208 Avoids unnecessary travel to disk
ends

C-LOOK Like C-SCAN but jumps to first request, not 153 Best performance in the example
cylinder 0

Example Setup (from Lab Manual)

Disk: 0–199 cylinders | Current head position: 53 | Previous position: 125 (for direction)

Pending queue: 98, 183, 37, 122, 14, 124, 65, 67

FCFS Calculation — Serve in arrival order

Order: 53 → 98 → 183 → 37 → 122 → 14 → 124 → 65 → 67

THM = |98-53| + |183-98| + |37-183| + |122-37| + |14-122| + |124-14| + |65-124| + |67-65|

= 45 + 85 + 146 + 85 + 108 + 110 + 59 + 2 = 640 cylinders

SSTF Calculation — Always pick nearest

From 53: nearest=65, then 67, then 37, then 14, then 98, then 122, then 124, then 183

THM = |65-53| + |67-65| + |37-67| + |14-37| + |98-14| + |122-98| + |124-122| + |183-124|

= 12 + 2 + 30 + 23 + 84 + 24 + 2 + 59 = 236 cylinders

SCAN Calculation — Move toward 0 first (given previous was 125, so going toward 0)
Going toward 0: 53 → 37 → 14 → 0, then reverse toward 199: 0 → 65 → 67 → 98 → 122 → 124 → 183

THM = |53-37| + |37-14| + |14-0| + |0-65| + |67-65| + |98-67| + |122-98| + |124-122| + |183-124|

= 16 + 23 + 14 + 65 + 2 + 31 + 24 + 2 + 59 = 236 cylinders

C-SCAN Calculation — One direction (0→199), then jump to 0, continue

65 → 67 → 98 → 122 → 124 → 183 → 199 (jump to 0 — NOT counted) → 14 → 37
 THM = |65-53| + |67-65| + |98-67| + |122-98| + |124-122| + |183-124| + |199-183| + |14-0| + |37-14|

= 12 + 2 + 31 + 24 + 2 + 59 + 16 + 14 + 23 = 183 cylinders

Note: The jump from 199 back to 0 in C-SCAN is NOT counted in THM.

LOOK Calculation — Like SCAN but stops at last request

Going toward 0: 53 → 37 → 14 (stop here, no need to go to 0). Then reverse: 14 → 65 → 67 → 98 → 122 → 124 → 183

THM = |37-53| + |14-37| + |65-14| + |67-65| + |98-67| + |122-98| + |124-122| + |183-124|

= 16 + 23 + 51 + 2 + 31 + 24 + 2 + 59 = 208 cylinders

C-LOOK Calculation — Like C-SCAN but jump to first request, not cylinder 0
65 → 67 → 98 → 122 → 124 → 183 (jump to 14 — first request in other direction) → 14 → 37

THM = |65-53| + |67-65| + |98-67| + |122-98| + |124-122| + |183-124| + |37-14|

= 12 + 2 + 31 + 24 + 2 + 59 + 23 = 153 cylinders (jump 183→14 NOT counted)

3. Programs

Program: Disk Scheduling — FCFS, SSTF, SCAN, C-SCAN

/* disk_sched.c
Compile: gcc disk_sched.c -o disk | Run: ./disk */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>

#define MAX 100

int ABS(int x) { return x < 0 ? -x : x; }

void fcfs(int req[], int n, int head) {

int thm = 0, cur = head;
printf("\nFCFS Order: %d", cur);
for (int i=0; i<n; i++) { thm += ABS(req[i]-cur); cur = req[i]; printf(" -> %d", cur); }
printf("\nFCFS Total Head Movement = %d cylinders\n", thm);
}

void sstf(int req[], int n, int head) {

int r[MAX], visited[MAX], thm = 0, cur = head;
memcpy(r, req, n*sizeof(int));
memset(visited, 0, sizeof(visited));
printf("\nSSTF Order: %d", cur);
for (int count=0; count<n; count++) {
int minD=99999, idx=-1;
for (int i=0; i<n; i++)
if (!visited[i] && ABS(r[i]-cur) < minD) { minD=ABS(r[i]-cur); idx=i; }
visited[idx]=1; thm+=minD; cur=r[idx];
printf(" -> %d", cur);
}
printf("\nSSTF Total Head Movement = %d cylinders\n", thm);
}

void scan(int req[], int n, int head, int disk_size) {

int r[MAX+1], cnt = n;
memcpy(r, req, n*sizeof(int));
/* Sort requests */
for (int i=0; i<cnt-1; i++) for (int j=0; j<cnt-1-i; j++)
if (r[j]>r[j+1]) { int t=r[j]; r[j]=r[j+1]; r[j+1]=t; }

int thm = 0, cur = head;

printf("\nSCAN Order: %d", cur);
/* Move toward 0 first */
for (int i=cnt-1; i>=0; i--) if (r[i]<=head) { thm+=ABS(r[i]-cur); cur=r[i]; printf(" -> %d", cur); }
/* Go to 0 */
thm += cur; cur = 0; printf(" -> 0");
/* Move toward max */
for (int i=0; i<cnt; i++) if (r[i]>head) { thm+=ABS(r[i]-cur); cur=r[i]; printf(" -> %d", cur); }
printf("\nSCAN Total Head Movement = %d cylinders\n", thm);
}

int main() {
 int n, head, disk_size;
printf("Enter disk size: "); scanf("%d", &disk_size);
printf("Enter initial head position: "); scanf("%d", &head);
printf("Enter number of requests: "); scanf("%d", &n);
int req[n];
printf("Enter requests: ");
for (int i=0; i<n; i++) scanf("%d", &req[i]);

fcfs(req, n, head);
sstf(req, n, head);
scan(req, n, head, disk_size);
return 0;
}

5. Statement-Based Questions

"Simulate disk scheduling algorithms FCFS, SSTF, SCAN, C-SCAN and find total head movements."
Show program. Use the given example: head=53, queue=98,183,37,122,14,124,65,67. Show order of service and THM for
each algorithm.

"Which disk scheduling algorithm is most efficient for the given request queue?"
Compare THM values: FCFS=640, SSTF=236, SCAN=236, C-SCAN=183, LOOK=208, C-LOOK=153. C-LOOK gives minimum
THM. But SSTF can cause starvation. SCAN/C-SCAN give good balance.

6. Viva Questions

Q1: What is seek time and how do scheduling algorithms reduce it?
Seek time is the time for the disk arm to move to the desired track. Algorithms like SSTF, SCAN, and C-SCAN minimize
total head movement (THM), directly reducing average seek time compared to FCFS.

Q2: Difference between SCAN and LOOK?

SCAN moves the head all the way to the end of the disk (cylinder 0 or max) before reversing, even if no requests are
there. LOOK only goes as far as the last pending request in each direction — more efficient.

Q3: Advantage of C-SCAN over SCAN?

C-SCAN provides more uniform wait time. In SCAN, requests near the reversal point get served twice quickly while
requests in the middle wait longer. C-SCAN treats the disk as circular — more fair distribution.

Q4: Why is SSTF not always the best?

SSTF can cause starvation — requests far from the current head position may wait indefinitely if closer requests keep
arriving. It's locally optimal (next best) but not globally optimal.

Q5: Why is the C-SCAN/C-LOOK jump not counted in THM?

The jump from the high end back to cylinder 0 (or first request) is a seek but we only count the actual servicing
movements. The return jump is a reset without any reads/writes, so it is excluded by convention.

⚡ M US T REMEM BER — LAB 11

THM = sum of |current_pos - next_pos| for each serviced request

FCFS: arrival order — simple but high THM (640 in example)
SSTF: nearest first — good THM but starvation possible
SCAN: go to disk end, reverse, service all — like elevator algorithm
C-SCAN: one direction only, jump to start — more uniform wait
LOOK/C-LOOK: like SCAN/C-SCAN but stop at last request, not disk end
C-SCAN/C-LOOK: jump back is NOT counted in THM
C-LOOK has minimum THM (153) in the manual example