OPERATING SYSTEMS

(Fall 2023)
Solution by (CH MUZAMMIL) & (MISS HARAM)

Q1. Answer the following short questions:

(A) Difference between long-term scheduler and medium-term
scheduler
Long-term Scheduler Medium-term Scheduler
Decides which processes are admitted into Manages processes by swapping them in and out
the system. of memory.
Works less frequently. Works more frequently.
Controls the degree of multiprogramming Manages the suspension and resumption of
(number of processes in the system). processes.
Selects processes from the job pool (new Deals with processes that are already in the
state) to the ready state. ready queue, and can swap them out.
Affects the system’s memory usage and
Affects the overall load and number of
performance by controlling which processes are
processes in the system.
in memory.

(B) What are the disadvantages of using Semaphores?

1. Complex to Manage: Incorrect use of semaphores can cause difficult-to-debug errors like
deadlocks or race conditions.
2. Deadlock Risk: Poor management can lead to deadlocks where processes are stuck waiting
for each other.
3. Ordering Issues: Semaphores don’t easily control the order of process execution, which can
lead to confusion.
4. Priority Inversion: A low-priority process can block a high-priority one, causing delays.
5. Manual Control: The programmer must carefully manage wait() and signal(), which increases
the risk of errors.
6. Inefficiency: In some cases, semaphores are less efficient than other synchronization tools
like mutexes or condition variables.

(C) Write the solution of Bounded-Buffer (Producer-Consumer)

Problem using Semaphores
The bounded-buffer problem can be solved using three semaphores:
semaphore full = 0;
semaphore empty = N;
semaphore mutex = 1;

// Producer Process
while (true) {
wait(empty);
wait(mutex);
// Add item to buffer
signal(mutex);
signal(full);
}

// Consumer Process
while (true) {
wait(full);
wait(mutex);
// Remove item from buffer
signal(mutex);
signal(empty);
}

(D) What are Zombie Processes? When are these created and
terminated?
Zombie Processes: These are processes that have completed execution but still occupy an entry
in the process table. They occur when a child process ends, but its parent has not yet collected
its exit status using wait().
• Creation: A zombie process is created when a process ends, but its parent hasn’t collected
the exit status using the wait() system call.
• Termination: Zombie processes are removed when the parent process calls wait() to
get the exit status. If the parent doesn’t do this, the zombie process will stay in the process
table until the parent itself finishes, at which point the system will clean up the zombie.

(E) What is difference between Ordinary Pipes and Named Pipes?

Ordinary Pipes Named Pipes (FIFOs)
Unidirectional communication between Bidirectional communication between unrelated
related processes. processes.
Typically used between a parent and its Can be used by unrelated processes on the same
child process. system.
Temporary; exists only while processes Persistent; exists in the filesystem until explicitly
are running. deleted.
Created using system calls like pipe(). Created using mkfifo command or mknod() system
Ordinary Pipes Named Pipes (FIFOs)
call, with a unique name in the filesystem.
Accessible only by related processes (no Accessible by any process with the pipe's name in
independent name in filesystem). the filesystem.
Typically bidirectional (two-way communication
Unidirectional (one-way).
possible).
(F) Consider a logical address space of 32 pages of 1024 bytes each,
mapped onto a physical memory of 16 frames.
• a. How many bits are there in the logical address?
• b. How many bits are there in the physical address?
• c. How many bits are needed for offset?
Given:
• Logical address space: 32 pages of 1024 bytes each
• Physical memory: 16 frames
a. Logical Address Bits:
Since there are 32 pages, we need log2(32)=5 bits for the page number. Each page has
1024 bytes, so log2(1024) =10 bits for the offset.
Total Logical Address Bits = 5+10 = 15 bits
b. Physical Address Bits:
There are 16 frames, so we need log2(16)=4 bits for the frame number. Offset remains
10 bits.
Total Physical Address Bits=4+10=14 bits
c. Offset Bits:
Offset bits are determined by page size, which is 1024 bytes, so log2(1024)=10 bits.

LONG QUESTIONS
(A) Consider a system with a 6-bit virtual address space and a size
of frames/pages of 16 bytes. The page table provides a mapping
from logical to physical memory:
Page # Frame #
0 8
1 3
2 11
3 1
Translate the following virtual addresses to physical addresses (all addresses are in decimal):
Virtual address Physical address

20
40

25

15

35

32

Answer:
Given a 6-bit virtual address space and a 16-byte page size, we use a 2-bit offset for each
address (since log2(16) = 4).

Calculate the physical addresses:

Steps:
1. Split the virtual address into page number and offset.
2. Map the page number to the frame number using the table.
3. Calculate the physical address by shifting frame number and adding the offset.
Virtual Address: 20
• Page number: 20÷16 = 1 (Page 1)
• Offset: 20 mod 16 = 4
• Mapped frame: Frame 3 (from the page table for Page 1)
• Physical address: Frame 3×16+4 = 48+4 = 52

Virtual Address: 40
• Page number: 40÷16 = 2 (Page 2)
• Offset: 40 mod 16 = 8
• Mapped frame: Frame 11 (from the page table for Page 2)
• Physical address: Frame 11×16+8 = 176+8 = 184

Virtual Address: 25
• Page number: 25÷16 = 1 (Page 1)
• Offset: 25 mod 16 =9
• Mapped frame: Frame 3 (from the page table for Page 1)
• Physical address: Frame 3×16+9 = 48+9 =57

Virtual Address: 15
• Page number: 15÷16 = 0 (Page 0)
• Offset: 15 mod 16=15
• Mapped frame: Frame 8 (from the page table for Page 0)
• Physical address: Frame 8×16+15 = 128+15 = 143
Virtual Address: 35
• Page number: 35÷16 = 2 (Page 2)
• Offset: 35 mod 16 =335
• Mapped frame: Frame 11 (from the page table for Page 2)
• Physical address: Frame 11×16+3 = 176+3 = 179

Virtual Address: 32
• Page number: 32÷16 = 2 (Page 2)
• Offset: 32 mod 16 =0
• Mapped frame: Frame 11 (from the page table for Page 2)
• Physical address: Frame 11×16+0 = 176+0 =176

Using the page table provided:

Physical
Virtual Address Page # Frame #
Address
20 1 3 52
40 2 11 176
25 1 3 57
15 0 8 143
35 2 11 179
32 2 11 176

(B) Assume there are 5 processes (P0 through P4) and 4 types of
resources (A, B, C, and D). At T0, the allocation and maximum demand
are provided in tables.
Allocation Max

A B C D A B C D

P0 0 1 1 0 0 2 1 0

P1 1 2 3 1 1 6 5 2

P2 1 3 6 5 2 3 6 6

P3 0 6 3 2 0 6 5 2

P4 0 0 1 4 0 6 5 6

If the system has one instance of A, five instances of B, and two instances of C in hand,
determine if the system is in a safe state. If yes, provide the safe sequence.

Answer:

Step 1: Calculate the Need matrix

The Need matrix is calculated as:
Need = Max − Allocation

Step 2: Check if the system is in a safe state

1. Available Resources:
○ A=1
○ B=5
○ C=2
○ D=0
2. Work vector: Initialize Work as the Available resources vector:
Work={1,5,2,0}
3. Finish vector: Initialize Finish as a vector of false values indicating no process has
finished yet:
Finish={false, false,false, false,false}
4. Find processes that can proceed:
○ Check each process in sequence to see if its Need can be satisfied with the Work
vector. If so, "finish" the process, update the Work vector, and mark the process
as finished.

Checking each process:

P0:
○ Need = {0, 1, 0, 0}
○ Work = {1, 5, 2, 0}
○ P0's need can be satisfied (0 ≤ 1, 1 ≤ 5, 0 ≤ 2, 0 ≤ 0).
○ After P0 finishes, update Work:
Work = Work + Allocation (P0) = {1+0, 5+1, 2+1, 0+0} = {1, 6, 3, 0}.
○ Mark P0 as finished: Finish = {true, false, false, false, false}.
P3:
○ Need = {0, 0, 2, 0}
○ Work = {1, 6, 3, 0}
○ P3's need can be satisfied (0 ≤ 1, 0 ≤ 6, 2 ≤ 3, 0 ≤ 0).
○ After P3 finishes, update Work:
Work = Work + Allocation (P3) = {1+0, 6+6, 3+3, 0+2} = {1, 12, 6, 2}.
○ Mark P3 as finished: Finish = {true, false, false, true, false}.
P1:
○ Need = {0, 4, 2, 1}
○ Work = {1, 12, 6, 2}
○ P1's need can be satisfied (0 ≤ 1, 4 ≤ 12, 2 ≤ 6, 1 ≤ 2).
○ After P1 finishes, update Work:
Work = Work + Allocation (P1) = {1+1, 12+2, 6+3, 2+1} = {2, 14, 9, 3}.
○ Mark P1 as finished: Finish = {true, true, false, true, false}.
P2:
○ Need = {1, 0, 0, 1}
○ Work = {2, 14, 9, 3}
○ P2's need can be satisfied (1 ≤ 2, 0 ≤ 14, 0 ≤ 9, 1 ≤ 3).
○ After P2 finishes, update Work:
Work = Work + Allocation (P2) = {2+1, 14+3, 9+6, 3+5} = {3, 17, 15, 8}.
○ Mark P2 as finished: Finish = {true, true, true, true, false}.
P4:
○ Need = {0, 6, 4, 2}
○ Work = {3, 17, 15, 8}
○ P4's need can be satisfied (0 ≤ 3, 6 ≤ 17, 4 ≤ 15, 2 ≤ 8).
○ After P4 finishes, update Work:
Work = Work + Allocation (P4) = {3+0, 17+0, 15+1, 8+4} = {3, 17, 16, 12}.
○ Mark P4 as finished: Finish = {true, true, true, true, true}.

Step 3: Conclusion
All processes can finish, so the system is in a safe state. The safe sequence is:
P0 → P3 → P1 → P2 → P4.

(C) Which function is used to create user-level threads using the

pthread library? Provide one example to show the creation and
execution of 4 threads.
To create user-level threads using the pthread library, the function used is pthread_create().
Example to create and execute 4 threads:
#include <pthread.h>
#include <stdio.h>

// Function to be executed by threads

void* thread_function(void* arg) {
int thread_id = *(int*)arg;
printf("Thread %d is executing\n", thread_id);
return NULL;
int main() {
}

pthread_t threads[4]; // Array to store thread IDs

int thread_ids[4] = {1, 2, 3, 4}; // Thread identifiers

// Create 4 threads
for (int i = 0; i < 4; i++) {
pthread_create(&threads[i], NULL, thread_function, &thread_ids[i]);
}

// Wait for all threads to finish

for (int i = 0; i < 4; i++) {
pthread_join(threads[i], NULL);
}
return 0;
}

Explanation:
1. pthread_create() is used to create each thread, passing the function thread_function to be
executed by each thread.
2. pthread_join() ensures that the main program waits for all threads to finish before it ends.

--------------------------------------------------------------------------------------------------------------------

Remember in Your Prayer