CLO # 4 - Understand synchronization and deadlocks. Implement synchronization using Mutex/Semaphores.

Q1. [15 marks] Instruction: Write answers as bullets points.

a) Consider a tcke booking sysem where he available number o tckes or
each program mus be mainained. A person who wishes o book a tcke calls
he bookTicke() uncton, which checks i tckes are available and hen
decreases he available tckes coun by one. This is illusraed in he code
shown. Now explain how a race conditon is possible in his siuaton. Also,
show a Phread library-based C program ha avoids race conditon using a muex. [1 + 3]

Race condition is possible as follows:

• This function code has no mutual exclusion.
• Threads, running on multiple cores, will update the variable “availableTickets” – which is a single memory
location – in random order resulting in race condition.
• *** full program needs to be written transforming given bookTicket() function given.
• No marks if semaphores are used. 1.5 marks if syntax is 100% correct + 1.5 marks if 100% logic is correct.

b) Explain synchronizaton issue(s) in producer and consumer codes in a producer-consumer problem. Wrie and explain
C code snippes ha use wo ypes o semaphores as a soluton or his problem. [2+2]

• Both have the same synchronization issue: i.e. ensuring that the producer and consumer access the shared
buffer in a mutually exclusive manner, and
• coordinating their activities so that the buffer does not overflow or underflow.
• 1 wt. for correct code and 1wt. for explanation of code.

Page 1 of 6
c) Wrie answers o he ollowing questons:
i. Why hardware aomic insructons are necessary in he implemenaton o locking primitves? [1]
These instructions ensure mutual exclusion even if threads run on different cores in parallel.
ii. How do wo hreads become deadlocked while accessing resources? Wrie C code snippe using semaphores and
a sep-by-sep explanaton or any scenario. [1.5+1.5]

• 1.5 wt. will be awarded only if out-of-order pairs of waits are used in
the code.
• Textual answer will get no awards.
• 1.5 wt. will be awarded if step-by-step explanation given.

Page 2 of 6
d) How busy waitng is implemened during synchronizaton? Wrie wo C code snippes showing wo dieren mehods.
Also, explain he working o any one snippe using a dry run wih variable values. Assume wo processes where one
is executng in is critcal secton and oher is waitng [2 + 1].

2 wt.
• The busy term (a.k.a spinning) is used as waiting involves a loop that
continuously checks the condition, consuming CPU cycles until the
condition is met.
• Two Option A and Option B (or similar) is given with dry run.

1wt.
• Only if explicit dry run done by the student.

CLO # 5 - Understand virtual memory and its management.

Q2. [15 marks] Instruction: Write answers as bullets points. Make suitable assumptions, if needed.

a) Explain exernal ragmenaton in main memory using a labeled diagram. Wha causes inernal ragmenaton in a
page? Explain wih an example. [2 + 1]

2wt.

1 wt.
Internal fragmentation occurs when memory allocated for a process is slightly larger than what the process
requires. This "extra" allocated memory within a fixed-size block (page) is wasted because it cannot be used by
other processes. Suppose total size of executable code is 3.5k and page allocated to text segment of the process
will always be 4k in a system where page size is fixed to 4k. Therefore, 0.5k is waster due to internal
fragmentation.

b) Page auls are critcal in a virual memory sysem.

i. Explain Page aul processing using a labelled diagram. [2]

See diagram.

ii. In a compuer sysem, memory access tme is 40 nanoseconds

and hard disk access tme is 1.25 milliseconds. Calculae
eectve memory access tme i page aul probabiliy is
0.000025. [2]

effective access time = (1 − p) × (40) + p (1.25 milliseconds)

= (1 − p) × 40 + p × 1,250,000
= 40 + 1249960 × p
= 40 + 1249960 (0.000025)
= 40 + 31.249 ➔ 71.249

Page 3 of 6
c) LRU is one o he many page replacemen algorihms. Explain is wo
implemenatons as ollows:
i. Use a labelled diagram and sepwise hins o describe clock (second
chance) algorihm. Show i does approximae LRU unctonaliy. [2]
ii. Now, enhance he above algorihm o ensure ha diry victm pages
are ushed o memory beore reuse. [2]

• The reference bits are used to approximate the LRU policy.

• Pages that are used frequently will have their reference bit set
to 1, giving them a second chance and making it less likely for
them to be replaced immediately, much like how LRU would
prefer recently used pages over those used a long time ago.

d) Suppose a program is accessing main memory in a virual memory sysem having a page size o 2K.
i. Sae he dierence beween paged and demand paged memory sysem? [1]

Paged Memory System Demand Paged Memory System

All pages that are part of process are loaded into Pages are loaded only when accessed. Pages are
available frames at execution start. loaded on page fault occurrence

ii. Show a labelled diagram which shows how a virual memory address generaed by a program is ranslaed ino a
physical address. Now, in your diagram, assume suiable values or page number and page ose and show how he
processor calculaes he physical address. [3]

• Virtual address (logical address) is generated by the

executing program.
• Page table lookup is done to read the frame number.
• Displacement within page/frame remains same.
• ----
• Suppose page number is 26 and offset is 87 so the logical
address is 2687. The page table lookup for page number
26 resulted in a frame number 890. So the physical
address becomes 89087.

CLO # 1 - Describe, discuss, and analyze, services provided by the modern Operating Systems.

Q3. [6 marks] Instruction: Avoid unnecessary details in your answers.

Page 4 of 6
a) Creae a diagram illusratng he inerrup handling process in a ypical operatng sysem. Wha is he purpose o
tmer in operatng sysems and how i is relaed o inerrups. [1+2]

1 wt. for diagram and 2wt. for the answer below.

• OS needs to be reminded to perform periodic tasks.

• This can be done using a time, which when reaches a pre-set value, it generates a
hardware interrupt known as a timer interrupt.
• This is used system wide to facilitate process scheduling, time-sharing, and
system resource management.
• For example, a timed interrupt (say 5 milliseconds) in process scheduling
preempts the currently executing process and brings in new one (known as
context switching) thus allowing fair CPU allocation.

b) Describe executon seps o a (generic) sysem call using wo modes in a modern operatng sysem wih he help o
a labelled diagram. [2]
• When a system call is executed, it is treated as a software interruption.
• Control is transferred through the interrupt vector to a
service routine in the operating system.
• Switching the mode to kernel mode.
• The kernel identifies the system call type and retrieves
necessary parameters, which may be passed via
registers, stack, or memory.
• After verifying the parameters, the kernel executes the request and returns control to the user program.

Wha problems do you expec i OS execues his sysem call in user mode only? Explain. [1]
• Privileged instructions (switching to kernel mode, I/O control, and timer management.) can only be executed
in kernel mode. These facilitate managing resources that are kept private from users. The dual mode of
operation protects the operating system and users from errant actions by designating certain harmful
instructions as privileged.
• If privilege mode instructions are allowed in user mode (i.e. there is only one mode of operation) a bug in the
user program will crash the whole OS.
• Multitasking and Multiprogramming will be difficult as in old DISK Operating System (DOS).

CLO # 2 - Understand, design, and implement solutions employing concepts of Processes and Threads

Q4. [6 marks]
a) Consider Google’s Chrome browser as a mult-process archiecure. Wha bene would his implemenaton provide
o he user? [2]
• If each tab is a separate process, then this provides protection and security as each process memory will be
sperate and unaccusable by other processes. can be accessed by other processes.
• Each process can be scheduled on a different core of the processes. Thus, response time will be improved.

b) Show how many processors are needed o gain a 3.5 tmes speedup i he serial porton is 20%. [2]

speedup = 1 / (serial portion + (parallel portion /N) where N is number of processors. Putting values
3.5 = 1 / (0.2 + (0.8/N))
3.5 (0.2 + (0.8/N)) = 1 ➔ 0.7 + (2.8/N) = 1 ➔ 2.8 / N = 0.3 ➔ N = 2.8 / 0.3 ➔ N = 9.33 ~ 10 processors.

c) Explain dieren ypes o mapping beween user-level and kernel-level hreads. [2]
• One-to-One: True parallelism as each user threads gets its own kernel threads which can be scheduled
independently.
• Many-to-One: Thread library (like Pthread) can manage user threads and maps then to a single kernel
thread.
• Many-to-Many: Flexible mapping where many user threads are mapped equal number and less kernel threads.
Page 5 of 6
CLO # 3 – Understand mechanisms for scheduling of tasks in modern operating systems.

Q5. [8 marks] Instruction: Write answers as bullets points.

a) Consider Linux Compleely Fair Scheduler. Explain: i) he compuatons done o akes scheduling decisions, and ii)
give a diagram o show how CFS ecienly compues he nex runnable ask. [2+2]

b) Assume an Operatng Sysem uses FCFS scheduler. Suppose here are only wo processes: rs is running wih fy
hreads o compue he value o Pi using 5000K ieratons, and he second process is an Inerne browser where a
single ab is shown o he user. Explain how you change he code o he frs process such ha he FCFS scheduler
run boh processes alernatvely i.e. beore nishing he rs process. Write precise answer in 2-3 lines only [2].

Cooperative or non-preemptive scheduling. FCFS is non-preemptive, so once it starts execution of the first
process the 2nd process must wait till the completion of the 1st.

2wt. To achieve alternating execution with an FCFS scheduler, the programming has to code either sleep () or
other system calls to relinquish the CPU within each thread's computation loop. This allows the second process
(the Internet browser) to run.

c) Compare and conras pre-emptve and non-preemptve scheduling [2].

Pre-emptive Scheduling Non-preemptive Scheduling

OS can interrupt processes at any time Processes run until they voluntarily relinquish or finish
Overhead due to frequent context switches Lower due to minimal context switches
More complex to implement and manage Simple (process must relinquish CPU)
Fair CPU utilization May lead to starvation
Highly responsive Depend upon

Page 6 of 6