Reference no: EM132361081

Question 1

Answer the following questions:

a. Given five memory partitions (in order) of 100 KiB, 500 KiB, 200 KiB, 300 KiB, and 600 KiB, how would each of the first- fit, best-fit, and worst-fit algorithms place processes (in or- der) of 212 KiB, 417 KiB, 112 KiB, and 426 KiB? Which algorithm makes the most efficient use of memory?
b. Assume a 32 bit system, with a 2-level page table, with a page size of 4KiB (p1=10bits, p2=10bits, offset=12bits).
(i) A program on this system requires 16MiB in total: the program text segment uses 4MiB, the program data re- quires 2MiB, the program dynamically allocates 8MiB on the heap, and the stack utilises 2MiB.
How many page-table pages are required for this pro- cess? (Don't answer with just a number, explain your reasoning. Without your reasoning we cannot award part marks if your answer is incorrect.)
(ii) Describe the lookup steps within the page tables to find the physical address of the logical address 0x00403004.
(iii) If the reference time to access the physical memory frame is 20 nanoseconds. Assume that all required pages are in memory. How long does a paged memory reference take, if-
i. There is no TLB?
ii. There is a TLB, with an access speed of 0.05 nanosec- onds, but the TLB does not contain information on the required page?
iii. There is a TLB, with an access speed of 0.05 nanosec- onds, and the TLB contains information on this page?
(Do not answer with just a number, explain your rea- soning. Without your reasoning we cannot award part marks if your answer is incorrect.)

Question 2

A file is to be shared among different processes. The file can be accessed simultaneously by more than one process, up to a maxi- mum of 5 processes. In pseudo-code write a monitor to coordinate access to the file. For example:
FileMonitor M;

int main() {
...
M.RequestAccess();
/* Access file: open, read, close, etc. */ M.FinishedAccess();
...

}

Monitor FileMonitor {

/* monitor variables here */

void RequestAccess() { /* Code here */ } void FinishedAccess() { /* Code here */ }

}
The monitor pseudo-code needs to define monitor variables and the monitor functions.

Notes
• This is pseudo-code and not meant to be compiled and run. You will need to check the logic though.
• This is a monitor so mutual-exclusion is assured and does not need to be incorporated in the code.
• Assume that the monitor uses Mesa condition variables.
• As a starting point study Figure 5.19 (ed. 8, Figure 6.20) from the text book (Operating System Concepts, Silberschatz et el.).

Question 3

A two-way north-south highway through the mountains must pass through a narrow tunnel with only one lane. A south-bound or north-bound car can pass through the tunnel only if, when it ar- rives, there are no on-coming cars in the tunnel. Note, due to the length of the tunnel, at most 5 cars only are allowed in the tun- nel at one time-provided that they are all heading in the same direction.

In pseudo-code write the two processes north2south and south2north that allows cars to use the tunnel safely. As a starting point use the code below.

Hint: This is similar to the readers-writers problem except it is symmetric-north2south() is similar to south2north();
Remember: All Semaphores and variables must be initialised.
/* Shared Data between all processes */ Semaphore tunnel_mutex;
/* Shared Data between south2north processes */

Semaphore north_mutex; Semaphore going_north_max; int number_going_north;

south2north()
{

/* Add Synchronisation code here */ DriveNorthThroughTunnel();
/* Add Synchronisation code here */
}

/* Shared Data between north2south processes */

Semaphore south_mutex; Semaphore going_south_max; int number_going_south;

north2south()
{
/* Add Synchronisation code here */ DriveSouthThroughTunnel();
/* Add Synchronisation code here */
}

Question 4

Consider the following pseudo-code:
/* Global memory area accessible by threads */ #define N 100
struct frame *emptyStack[N]; struct frame *displayQueue[N];

int main() {
/*
** Initialise by allocating the memory for N frames
** And place the N frame addresses into the
** empty Stack array
*/ Initialise();

thread_t tid1, tid2;

threadCreate(&tid1, GetFrame); threadCreate(&tid2, ShowFrame);

sleep(300);

}

GetFrame() {
struct frame *frame; struct frame local;

while (1) {
CameraGrab(&local); /* get a frame from the camera
store it in local */
frame = Pop(); /* pop an empty-frame address from the empty stack */
CopyFrame(&local, frame); /* copy data from the local
frame to the frame address */
Enqueue(frame); /* push the frame address to
} the display queue */
}

ShowFrame() {
struct frame *frame; struct frame local; struct frame filtered;

while (1) {
frame=Dequeue(); /* pop the leading full frame
from the full queue */ CopyFrame(frame, &local); /* copy data to the local frame */

Push(frame); /* push the frame address to the empty stack */
Solarise(&filtered, &local); /* Modify the image */ VideoDisplay(&filtered); /* display the image */
}
}
This program creates two threads, one calls GetFrame(), which continually grabs frames from a camera, and the other thread calls ShowFrame(), which continually displays the frames (after modi- fication). When the program starts the emptyStack contains the addresses of N empty frames in memory.
The process runs for 5 minutes displaying the contents from the camera.

The procedures Pop() and Push() are maintaining the list of frame addresses on the empty stack. Pop() removes a frame memory address from the empty stack, and Push() adds a memory address to the empty stack.

The procedures Dequeue() and Enqueue() are maintaining the list of frame memory addresses in the display queue in display order. Dequeue() removes the memory address of the next frame to display from the display queue, and Enqueue() adds a memory address to the end of the display queue.

The stack and the queue are the same size, and are large enough to contain all available frame memory addresses.

a. Without including synchronisation code problems will occur.

Discuss what could potentially go wrong?

b. Identify the critical sections in the above pseudo-code.

c. Modify the above pseudo-code using semaphores only, to en- sure that problems will not occur.

Hint: this is a variation on the Producer-Consumer problem and will require similar semaphores.