CSC2404 Programming Assignment 2: Concurrency and Memory Management

This document presents solutions for CSC2404 Assignment 2, addressing various aspects of operating systems and programming. The first question explores memory allocation algorithms, comparing first-fit, best-fit, and worst-fit strategies, and delves into the lookup steps within page tables, including scenarios with and without a Translation Lookaside Buffer (TLB). The second question provides a solution for a monitor-based problem using semaphores for synchronization. The third question presents a monitor-based solution for managing traffic flow in a tunnel, handling northbound and southbound traffic. The final question analyzes and resolves concurrency issues in a multi-threaded program, identifying critical sections, and providing modified pseudo-code to solve the problems using semaphores for synchronization and mutual exclusion, including explanations for the solutions. References to related publications are also included.

Programming 1
PROGRAMMING
By Student's Name
Course Code and Name
Professor’s Name
University Name
City, State
Date of Submission

Programming 2
Question 1
a). Using 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
ii). Using 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
iii). Using Worst-fit Algorithm
212K is put in 600K partition
417K is put in 500K partition
112K is put in 388K partition
426K must wait
It turns out that Best-fit Algorithm makes the most efficient use of the memory (Liu et al,
2016, pp17).

Programming 3
Question 1
b).
(ii) Describe the lookup steps within the page tables to find
the physical address of the logical address 0x00403004.

Programming 4
(iii There is no TLB?
Access time = 3*20 =40nsec 2 access for finding physical address and 1 to access
data
i. There is a TLB, with an access speed of 0.05 nanoseconds, but the TLB does not
contain information on the required page (Dourish, 2016, pp13)?
With TLB with an access speed of 0.05 nanosecond
0.05 + 2*20 +20= 60.05nanoseconds
ii. iii. There is a TLB, with an access speed of 0.05 nanoseconds, and the TLB
contains information on this page (Savitch, 2017, pp 18)?
if the TLB contains the information
Question 2
Solutions
Monitor FileMonitor {
/* monitor variables here */
int count = 0;
semaphore cond; //semaphore variable to lock
void RequestAccess() {
/* Code here */
while(count >= 5){
cond.wait();
}
assert(count < 5);

Programming 5
count++;
}
void FinishedAccess() {
/* Code here */
count--;
cond.notify();
}
}
Question Three
Solution
monitor traffic_tunnel
{
int nbound = 0, sbound = 0; // initializing as no vehicles in north and
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

Programming 6
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
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
{

Programming 7
sbound--; //decrementing the count of vehicles in south side
if(sbound == 0)
while(busy.queue) busy.signal;
}
};
}
Question Four
Solution
part a-:
Problem 1-:Let us suppose thread2 (showFrame () method) runs first. Then it will try to
dequeue a element from the empty displayQueue. Because thread1 gets a chance to run after
thread2. Therefore, displayQueue is empty. Then garbage value of Frame will produce
inconsistent result. This is one kind of problem (Hoffman & Stroustrup, 2016, pp10).
Problem 2-:In other case thread1(GetFrame() method) runs N times. Then N+1th time it will
try to Pop a element from the empty emptyStack. Because thread2 did not get a chance to run
until now. So, emptyStack is empty and Inconsistent result will be produced. This is second
kind of problem.
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) (Awais, 2016, pp17).
Critical section -: If multiple threads share any data (Dey, 2016, pp12). Then that part of code
in which any modification on shared data is performed in any of thread, comes under critical
section.

Programming 8
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 inconsistant result will be produced.
Critical section is displayed in following image .
Part c -: (Modified Pseudo Code)
#define N 100
struct frame *emptyStack[N];
struct frame *displayQueue[N];

Programming 9
Semaphore Nspace /*Counting semaphore initilized with value N in main function*/
Semaphore Nframe /*Counting semaphore initilized with value 0 in main function*/
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);

Programming 10
frame = Pop();
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 -:

Programming 11
1. Problem 1 is solved because if thread2 runs first then it will wait for N frame 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.
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.(Nspace indirectly represent number of elements in the stack) (Al-Yatama et al, 2017,
pp5006). When thread2 signals N space then only thread1 can further make progress.
3. Problem of mutual exclusion is already solved by the mutex semaphore.

Programming 12
References
Al-Yatama, A., Ahmad, I. and Al-Dabbous, N., 2017. Memory allocation algorithm for cloud
services. The Journal of Supercomputing, 73(11), pp.5006-5033.
Awais, M.A., 2016. Memory management: Challenges and techniques for traditional memory
allocation algorithms in relation with today's real time needs. Advances in Computer Science:
an International Journal, 5(2), pp.22-27.
Dey, A., 2016. Machine learning algorithms: a review. International Journal of Computer
Science and Information Technologies, 7(3), pp.1174-1179.
Dourish, P., 2016. Algorithms and their others: Algorithmic culture in context. Big Data &
Society, 3(2), p.2053951716665128.
Hoffman, S. and Stroustrup, B., 2016. C++: A Smart Way to Learn C++ Programming and
Javascript (c plus plus, C++ for beginners, JAVA, programming computer, hacking, hacking
exposed). CreateSpace Independent Publishing Platform.
Liu, C., Wang, C. and Wang, J., 2016, July. A bandwidth adaptive pseudo-code tracking loop
design for BD/INS integrated navigation. In 2016 2nd International Conference on Control
Science and Systems Engineering (ICCSSE) (pp. 46-49). IEEE.
Savitch, W., 2017. Problem Solving with C++, Student Value Edition Plus
MyProgrammingLab with Pearson eText-Access Card Package. pearson.