CSC2404 Assignment 2: Operating System Principles and Algorithms

This assignment solution addresses several core concepts in operating systems. Question 1 explores memory management algorithms, comparing first-fit, worst-fit, and best-fit strategies, and then delves into paging mechanisms, including multi-level page tables and TLB performance analysis. Question 2 focuses on process synchronization using monitors and semaphores, presenting code examples for managing shared resources. Question 3 examines a traffic tunnel scenario using monitors to coordinate northbound and southbound vehicles, ensuring safe and efficient passage. Finally, Question 4 tackles concurrency issues in a multi-threaded environment, identifying problems such as race conditions and mutual exclusion, and providing a modified pseudo-code solution using semaphores to ensure data consistency and thread safety. The assignment includes detailed explanations and code snippets to illustrate the concepts.

1
Operating System
OPERATING SYSTEM
By Student's Name
Course Code and Name
Professor’s Name
University Name
City, State
Date of Submission

2
Question 1
a). First-fit algorithm:
212K is put in 500K partition
417K is put in 600K partition
112K is put in 288K partition (new partition 288K = 500K - 212K)
426K must wait
Worst fit algorithm:
212K is put in 600K partition
417K is put in 500K partition
112K is put in 388K partition
426K must wait
Best-fit algorithm:
212K is put in 300K partition
417K is put in 500K partition
112K is put in 200K partition
426K is put in 600K partition
Best-fit makes the most efficient use of memory.

3
b).
i) We utilize the following scheme
P1 P2 d
10 10 12
The 12 least significant digits in this address, allow access for 2 ^12 bytes -4Kb. These are
pointed to by any of the 2 ^10 entries of p2. In total, a second level page table can point to 2 ^
22 bytes -4Mb. Each such page table is pointed to by a first level table entry. In this scenario,
we need four page tables’ pages, a single first level page table (also known as the directory),
that points to level page tables (Han et al, 2015)

4
ii).
iii) i) The physical memory frame is 20 nanoseconds.
There is no TLB
Two accesses of memory: page look up followed by the exact access = 2 x 20 ns= 40
nanoseconds (Levis et al, 2015, pp 9).
ii) There exists a TLB with an access speed of 0.05 nanoseconds
2x 0.05 =0.1

5
0 % x 0.05ns + 100 % x 0.1ns=1ns
iii) 100 % x 0.05 + 0x 0.1=0.05ns
Question 2
Monitor name {
int priority=0;
int waiting=0;
semaphore mutex=1;
semaphore access=0;
REQUESTprocedure ( int pr){
sem_wait(mutex);
while(priority+pr > n) {
waiting++;
sem_signal(mutex);
sem_wait(access);
sem_wait(mutex);
}
priority += pr;
sem_signal(mutex); }

6
RELEASEprocedure (int pr){
int i;
sem_wait(mutex);
priority -= pr;
for (i=0; i < waiting;++i) {
sem_signal(access);
}
waiting = 0;
sem_signal(mutex);
}
//initialization
Main(){
REQUESTprocedure ( int pr);
RELEASEprocedure (int pr);
}
}
Question 3
monitor traffic_tunnel
{
int nbound = 0, sbound = 0; // initializing as no vehicles in north and

7
south side of tunnel
traffic-signal nbound_signal = RED,sbound = RED;
condition busy;
public:
northboundArrival() // called by a vehicle coming from north side
{
if(sbound > 0) busy.wait; // it checks whether there is any vehicle is in
south side and if there is any vehicle, then it wait
nbound++; // increments the number of vehicles in north direction if no
vehicle in south side
nbound_signal = GREEN; // set the traffic light as green in north side
sbound_signal = RED; // set the traffic light as red in south side which
blocks vechiles from south to enter the tunnel
};
southboundArrival() // called by vehicle entering tunnel from south
direction
{
if(nbound > 0) busy.wait; // it checks whether there is any vehicle is in
north side and if there is any vehicle, then it wait
sbound++; // if there is no vehicle in north side,then it increments the
number of vehicle from south direction
sbound_signal = GREEN; // signals the traffic light as green in south

8
direction
northbound_signal = RED; // signals the traffic light to red in north
direction which will block any vehicle entering tunnel from north side
};
depart( Direction exit) // called when a vehicle exists the tunnel
{
if(exit == north) // checking whether the exited vehicle was from north
{
nbound--; // decrementing the count of vehicles in north side
if(nbound == 0)
while(busy.queue) busy.signal;
}
else if(exit == south) // checking whether the exited vehicle was from
south
{
sbound--; //decrementing the count of vehicles in south side
if(sbound == 0)
while(busy.queue) busy.signal;
}
};
}

9
Question 4
part a-:
Problem 1-:Let's suppose thread2 (showFrame () method) runs first then it will try to
dequeuer an element from the empty display Queue because thread1 gets a chance to run
after thread2 (Hoare, 2014, pp 14). Therefore, display Queue is empty. Then garbage value of
Frame will produce inconsistent result. This is one kind of problem (Hansen, 2013, pp7).
Problem 2-: In other case thread1 (GetFrame() method) runs N times. Then N+1th time it will
try to Pop an element from the empty Stack because thread2 did not get a chance to run till
now. Thus, empty Stack is empty and Inconsistent result will be produced. This is second
kind of problem (Gude etal 2018, pp3)
Problem 3 -: Another problem is of mutual exclusion. There is no mutual exclusion.
Part b -:
Here emptyStack[N] and displayQueue[N] data structures are shared among multiple threads
(tid1,tid2).
Critical section -: If multiple threads then that part of code in which any modification
on shared data is performed in any of thread share any data, comes under critical
section.
here operations like enqueue() , dequeue() , push() ,pop() over emptyStack[N] and
displayQueue[N] are part of critical section. If multiple threads wants to execute critical
section at same time then inconsistent result will be produced (Engler & Kaashoek, 2015,
pp13).

10
Critical section is displayed in following image.
Part 3 -: (Modified Pseudo Code)
#define N 100
struct frame *emptyStack[N];
struct frame *displayQueue[N];
Semaphore Nspace /*Counting semaphore initilized with value N in main function*/
Semaphore Nframe /*Counting semaphore initilized with value 0 in main function*/

11
Semaphore mutex /*Binary semaphore to provide mutual exclusion*/
int main() {
/*
** Allocate memory for N frames
** Place the frames' addresses into the empty Stack
*/
sem_init(&Nspace,0,N);
sem_init(&Nframe,0,0);
sem_init(&mutex,0,1);
InitialiseStackMemory();
thread_t tid1, tid2;
thread_create(&tid1, GetFrame);
thread_create(&tid2, ShowFrame);
sleep(300);
}
GetFrame() {
struct frame *frame;
struct frame local;
while (1) {
CameraGrab(&local);
wait(Nspace);
wait(mutex);
frame = Pop();

12
CopyFrame(&local, frame);
Enqueue(frame);
signal(mutex);
signal(Nframe);
}
}
ShowFrame() {
struct frame *frame;
struct frame local;
struct frame filtered;
while (1) {
wait(Nframe);
wait(mutex);
frame=Dequeue();
CopyFrame(frame, &local);
Push(frame);
signal(mutex);
signal(Nspace);
Solarise(&filtered, &local);
VideoDisplay(&filtered);
}
}
Explanation -:

13
1. Problem 1 is solved because if thread2 runs first then it will wait for Nframe semaphore
because initial value of this is 0 so thread2 can't use Dequeue() function till queue is empty.
(Nframe indirectly represent number of elements in the queue). When thread1 signals Nframe
then only thread2 can further make progress (Franchi et al. 2018).
2. Problem 2 is solved because if thread1 runs N+1th time then value of Nspace becomes 0 and
thread1 will wait for Nspace semaphore ,so thread1 can't use Pop() function till stack is
empty (Bach, 2016, pp 12). (Nspace indirectly represent number of elements in the stack).
when thread2 signals Nspace then only thread1 can further make progress (Dunkels et al,
2014).
3. Problem of mutual exclusion is already solved by the mutex semaphore.

14
Reference List
Bach, M.J., 2016. The design of the UNIX operating system (Vol. 5). Englewood Cliffs, NJ:
Prentice-Hall.
Dunkels, A., Gronvall, B. and Voigt, T., 2014, November. Contiki-a lightweight and flexible
operating system for tiny networked sensors. In 29th annual IEEE international conference
on local computer networks (pp. 455-462). IEEE.
Engler, D.R. and Kaashoek, M.F., 2015. Exokernel: An operating system architecture for
application-level resource management (Vol. 29, No. 5, pp. 251-266). ACM.
Franchi, J.F., Franchi and John Franco, 2018. Open architecture casino operating system.
U.S. Patent 5,770,533.
Gude, N., Koponen, T., Pettit, J., Pfaff, B., Casado, M., McKeown, N. and Shenker, S., 2018.
NOX: towards an operating system for networks. ACM SIGCOMM Computer
Communication Review, 38(3), pp.105-110.
Han, C.C., Kumar, R., Shea, R., Kohler, E. and Srivastava, M., 2015, June. A dynamic
operating system for sensor nodes. In Proceedings of the 3rd international conference on
Mobile systems, applications, and services (pp. 163-176). ACM.
Hansen, P.B., 2013. Operating system principles. Prentice-Hall, Inc.
Hoare, C.A.R., 2014. Monitors: An operating system structuring concept. In The origin of
concurrent programming(pp. 272-294). Springer, New York, NY.
Levis, P., Madden, S., Polastre, J., Szewczyk, R., Whitehouse, K., Woo, A., Gay, D., Hill, J.,
Welsh, M., Brewer, E. and Culler, D., 2015. TinyOS: An operating system for sensor
networks. In Ambient intelligence (pp. 115-148). Springer, Berlin, Heidelberg.