Question 1
Answer the following questions:
a. Given five memory partitions of 100 KiB, 500 KiB, 200 KiB, 300 KiB, and 600 KiB (in order), how would each of the first-fit, best-fit, and worst-fit algorithms place processes of 212 KiB, 417 KiB, 112 KiB, and 426 KiB (in order)? 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 the pro-gram 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, also explain your reasoning.)
(ii) Describe the lookup steps within the page tables 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?
Don't answer with just a number, also explain your reasoning.
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 int main() {
M.RequestAccess();
/* Access file: open, read, close, etc. */ M. FinishedAccess ( ) ;
1
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-comming cars in the tunnel. Note, due to the length of the tunnel, at most only 3 cars 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 north2 south 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 north2 south ( ) is similar to south2north 0
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:
/* in global memory area accessible by threads */ #define N 100
struct frame *emptyStack[N];
struct frame *displayQueue[N];
int main() {
/*
** Allocate memory for N frames
** Place the frames' addresses into the empty Stack
*/ InitialiseStackMemory();
thread t tidl, tid2;
thread create(&tid1, GetFrame); thread create(&tid2, ShowFrame);
sleep(300);
GetFrame () {
struct frame *frame; struct frame local;
while (1) {
CameraGrab(&local); /* get a frame from the camera */
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) ; VideoDisplay ( &filtered) ;
}
}
This program creates two threads, one calls GetFrame 0 , which continually grabs frames from a camera, and the other calls ShowFrame 0 , which continually displays them (after modifying the frame). 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 0 are maintaining the list of frame addresses on the empty stack. Pop 0 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 0 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 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 ensure that problems will not occur.
Hint : this is a variation on the Producer-Consumer problem and will require similar semaphores.