Roll Number: _____________ Name______________ Group________________

THAPAR INSTITUTE OF ENGINEERING &TECHNOLOGY, PATIALA

Department of Computer Science & Engineering
Operating System (UCS303) – End Semester Examination Solution
Date: 18/12/2024 & Time: 2:00PM MM: 60 & MT: 180 Min
Faculty Name: Dr. Garima, Dr. Shashank Sheshar Singh, Dr. Rahul Nijhawan, Dr. Javed Imran Dr. Vaibhav Pandey,
Dr. Sumit Varshney, Ms. Shivani Goswami, Dr. Payal
Note: Attempt any three questions Completely. Attempt/Answer all sub-parts like (a), (b), (c) (d) for each
question in one place. Do mention Page No. of your attempt on the front page.
Ques. No Questions Mark

Q1. (a). At a particular instance, the main memory has 4 empty slots of size 4K, 8K, 20K, and 2K. Processes J1-J8 are 4
arriving simultaneously at t=0 with their request size. Evaluate the completion time of the process J7 with the
values given in the table below if the requests are fulfilled in the same sequence. Consider the Best Fit approach
and measure the time in ns.

3 Marks for the table (Process) and 1 mark for the correct answer (19).

(b) In a microkernel architecture, consider the following services: application programs, inter-process communication 4
(IPC), file system, memory management, device drivers and CPU scheduling. Create a table that categorizes each
service as residing in either user space or kernel space.
Sol:
Service Execution Space Marks

Application Program User Space .5

File System User Space 1

Device Driver User Space .5

IPC Kernel Space 1

Memory Management Kernel Space .5

CPU Scheduling Kernel Space .5

(c). Define the Access Matrix, explain the roles of Copy, Owner, and Control operations, and discuss strategies for 4
its implementation with examples.

Access Matrix: 1
An Access Matrix is a table used in computer security to define which users (subjects) have permission to perform
specific actions on resources (objects) in a system. Each cell in the matrix specifies the permissions a user has for
a resource, such as read, write, execute, or delete.
For example:

Here, User 1 can read File A and write to File B, while User 2 can only write to File A.

Roles of Operations:
1.5
1. Copy:
Allows a user to give their permission to another user.

Example: If User 1 has the "Read" permission for File A with a "Copy" flag, they can grant "Read"
permission to User 2.

2. Owner:
Grants full control over an object, including modifying permissions for other users.
Example: If User 1 is the owner of File A, they can allow or restrict others to read or write to the file.

3. Control:
Enables a user to control the permissions of other users for an object without being its owner.
Example: A manager (not the owner) can allow employees to access certain documents.

Implementation Strategies:
1.5
1. Access Control Lists (ACLs):

For each object, maintain a list of users and their permissions.

Example:

File A → User 1: Read, User 2: Write

2. Capability Lists:

For each user, maintain a list of objects and their permissions.

Example:
User 1 → File A: Read, File B: Write

3. Hybrid Approach:

Combine ACLs and Capability Lists for optimized performance.

(d). A single-core system is required to 8
schedule the following processes.
Simulate the scheduling of these Process Arrival Burst Priority
Time (ms) Time (1=Highest)
processes using the following algorithms:
a. RR Scheduling with a time (ms)
quantum of 4 ms, and
P1 0 8 2
b. Preemptive Priority Scheduling.
P2 1 4 1

P3 2 9 3

P4 3 5 2

Compare the average waiting time and average turnaround time for above two scheduling algorithms and find
out which one will perform best.

a)Round Robin Scheduling (Quantum = 4 ms)

Average Waiting Time: 2 marks

Average Turnaround Time: 2 marks

b)Scheduling (Preemptive)
 Average Waiting Time: 2 marks

Average Turnaround Time: 2 marks

Q2. (a). Consider the given resource allocation graph of a system consisting five processes and three resource types. 4
Determine the state of the system under the following scenarios.
1. If the system is in a deadlock state or not. If it is not, identify a possible execution sequence (To break the tie
select the process with the smaller ID first.) (2 Marks)
2. If process P2 makes an additional request for one instance of resource type R3, can we grant this request
immediately if not then identify the deadlocked process. (2 Marks)

1. First we need to calculate the resource allocation matrix from the given graph, that is as follows:
Sol.
Now we need to apply the following deadlock detection algorithm:

After applying the algorithm, we find that the system is not in a deadlock state and execution sequence of
processes is as follows:
< P0 → P2 → P1 → P3 → P4>

The detailed answer is as follows:

2. Now that process P2 makes one additional request for an instance of type R3. The
Request matrix is modified as follows:
 Conclusion:

The system is now in a deadlock state after P2 makes an additional request

for one instance of type R3. The processes involved in the deadlock are P1,
P2, P3, and P4.

(b). Illustrate a scenario where two threads increment a shared counter (counter=0) without proper synchronization. 6
Describe step by step how a race condition occurs, and explain the final value of the counter if both threads run
concurrently. Additionally, define the hardware-based solutions available to resolve the critical section problem.

Sol 2
 The final value of the counter is incorrectly 1 instead of 2. (another variant also possible).

Test-and-Set 2

An operating system implements a single level paging. This system uses Translation Look aside Buffer (TLB)
and Physical Address Cache (PAC) to improve effective memory access time of Page Table and Main Memory
(c). respectively. TLB has a hit ratio 90%. PAC has a miss ratio of 20%. Main memory access time, TLB access time
and PAC access time are 1000 ns, 200 ns and 400 ns respectively. Assuming that all the pages of the process are
in main memory, the effective memory access time.

Effective memory access time (EMAT) =

=90/100[200+(80/100)*400+(20/100)*(400+1000)]+10/100[200+1000+(80/100)*400+(20/100)*(400+1000)]
Sol. =0.9[200+320+280]+0.1[1200+320+280] =0.9[800]+0.1[1800] =720+180 = 900 ns 5

(d). Consider the given code segment for two process P1 and P2 to analyse the two critical section conditions: mutual 5
exclusion and progress. Pre-emption can occur while executing the given code. Assume, initially S1=1 and S2=0
and all instructions are atomic. Show that if above mentioned synchronization conditions are satisfied or not, with
proper explanation.

P1: while (S1 = = S2);

Critical Section:
 S1=S2;

P2: while (S1 != S2);

Critical Section:

S1=! (S2);

It can be easily observed that the Mutual Exclusion requirement is satisfied by the above solution,
P1 can enter the critical section only if S1 is not equal to S2, and P2 can enter the critical section
only if S1 is equal to S2.

Progress Requirement is not satisfied. Let us first see the definition of Progress Requirement.

Progress Requirement: If no process is executing in its critical section and there exist some
processes that wish to enter their critical section, then the selection of the processes that will enter
the critical section next cannot be postponed indefinitely.

If P1 or P2 want to re-enter the critical section, then they cannot, even if there is other process is
not running in critical section.
3. (a)
Consider a system where a process is allocated 3 frames in the main memory. The process needs to execute
with the following page reference sequence: [5, 0, 1, 0, 2, 3, 0, 2, 4, 3, 3, 2, 0, 2, 1, 2, 7, 0, 1, 1, 0]. Using an
appropriate step-by-step diagram, calculate the page faults that occur when employing the Most
Frequently Used (MFU) and Optimal Page Replacement (OPR) algorithms. To break tie situations use
FIFO.

Sol: Input Details

• Number of frames: 3

• Page reference sequence: [5, 0, 1, 0, 2, 3, 0, 2, 4, 3, 3, 2, 0, 2, 1, 2, 7, 0, 1, 1, 0]

• Tie-breaking rule: FIFO

Step 1: Most Frequently Used (MFU) [2.5 Marks]

Algorithm Overview:

• MFU replaces the page that has been accessed the most frequently.

• If there is a tie (pages with the same frequency), the FIFO rule is used.

Total Page Faults (MFU):11 page faults

 Step 2: Optimal Page Replacement (OPR) [2.5 Marks]

Algorithm Overview:

• Optimal Page Replacement replaces the page that will not be used for the longest time in the future.

• This minimizes page faults by looking ahead in the reference sequence.

Step-by-Step Execution:

Total Page Faults (OPR):9 page faults

(b) Suppose you have given the following disk scheduling scenario: The disk has 1000 tracks, numbered from
0 to 999. The disk arm starts at track 500. The disk request queue is: [299, 40, 123, 650, 200, 370, 900, 40,
600, 100, 800, 499, 1000, 201]. The disk arm is initially moving towards the lower numbered tracks (left).
The seek time is 6 ms/cylinder. Compute the total seek time, for the following disk arm scheduling
algorithms

i) SSTF [2 marks] ii) LOOK Scheduling [2 marks] iii) C-SCAN Scheduling [2marks]

If Students consider tracks ranging from 0 to 1000, we adjust the calculations to include valid requests
within this range. Request 1000 is now valid and should be considered during processing.
 Discuss the producer and consumer problem and provide a solution using semaphores.

Producer-Consumer Problem: (2 Marks)

The Producer-Consumer Problem is a classic synchronization problem in operating systems, where two types of
processes share a common buffer:

• Producer: Generates data and places it into a shared buffer.

• Consumer: Consumes data from the shared buffer.

The challenge is to ensure that:

1. The producer does not add data to a full buffer.

2. The consumer does not remove data from an empty buffer.

3. Both processes access the buffer in a synchronized manner to avoid race conditions.

c).
Semaphore empty = N // Number of empty slots (buffer size is N)

Semaphore full = 0 // Number of filled slots

Semaphore mutex = 1 // Ensures mutual exclusion

Buffer[N] // Shared buffer

 Producer: [2 Marks]

Consumer [2 Marks]

Consider a file system where each physical block is 256 bytes. An index block contains pointers to 127 file blocks
along with one additional pointer to the next index block of the file. Assume that the last accessed physical block
(100) and all relevant directory entries are already loaded into main memory. If the desired block to be read is
block 600, calculate the total number of physical blocks that must be accessed (including block 600) for
contiguous allocation, linked allocation and indexed allocation strategies. (1+1+1)

Contiguous Allocation: 1 block: Only block 600 needs to be accessed, as the directory and starting block are
already in memory.

Linked Allocation: Traverse from block 100 to block 600: Blocks accessed = 600 - 100 = 500.

Indexed Allocation: Accesses Required:

1. Access the first 4 index blocks to traverse the chain.

2. Access the 5th index block to locate block 600.
3. Access block 600.

Total Accesses: 4 (index blocks) + 1 (final index block) + 1 (block 600) = 6

d)
Q4. (a). Discuss the segmentation using a diagram to map logical address to physical address. Further, to implement 5
segmented paging, non-contiguous allocation method paging is applied to segment table as well as segment both,
due to large segment table and segment size to store in the main memory. Consider a system using a segmented
paging architecture. The segment is divided into 8k pages each of size 2k words. The segment table is divided
into 256k pages each of size 512 words. The frame number requires 22 bits, and then calculate the number of bits
to represent the logical address (LA). Assume that the Word size is 1 Byte.

Sol. A process is divided into Segments. The chunks that a program is divided into which are not necessarily all
[2.5]
of the exact sizes are called segments. Segmentation gives the user’s view of the process which paging does
not provide. Here the user’s view is mapped to physical memory.

[2.5]
(b). Identify the correct security concept (Integrity, Firewall, Authentication, Authorization, Confidentiality) for each 5
of the following real-life scenarios: 1. Logging into a banking application using a password, 2. Restricting a guest
Wi-Fi network from accessing internal servers, 3. Encrypting emails before transmission. 4. Verifying a
downloaded file using a checksum, and 5. Blocking traffic from suspicious IP addresses using a router.
(1+1+1+1+1)

,
(c). Given a 16 KB file stored on a RAID 1+0 system with 4 drives and a block size of 2 KB, determine the number
of blocks required to store the file. Additionally, provide a clear and well-labelled diagram to illustrate the data
distribution across the drives assuming block-level striping is implemented.

Sol File Size: 16 KB

Block Size: 2 KB
RAID Configuration: 1+0 (4 drives with mirroring and striping).
Steps to Determine Blocks and Distribution:
1. Number of Blocks Required for File:
Number of blocks = File Size/Block Size = 16 KB/2 KB = 8 blocks (1 Mark)
(3 Mark) 4
 Consider a system using a multilevel paging scheme. The page size is 16 KB. The memory is byte-addressable
(d). and the virtual address is 48 bits long. The page table entry size is 4 bytes.
1. How many bits are required to specify a physical address?
2. What will be the size of the inner page table? 6
3. Illustrate the above-mentioned multilevel paging scheme by a diagram.

Sol
Page table entry size = 4 bytes = 32 bits
1.
Thus, Number of bits in frame number = 32 bits

Number of frames in main memory = 2 32 frames

Size of main memory = Total number of frames x Frame size

= 232 x 16 KB = 246 B = 64 TB

Thus, Number of bits in physical address = 46 bits (2 Marks)

2. Number of bits in virtual address = 48 bits

Thus, Process size = 248 bytes = 256 TB

Number of pages the process is divided = Process size / Page size

= 248 B / 16 KB

= 248 B / 214 B

= 234 pages

Inner page table size = Number of entries in inner page table x Page table entry size

= Number of pages the process is divided x Page table entry size

= 234 x 4 bytes = 236 bytes = 64 GB (2 Marks)

3.

(2 Marks)