Question )Deadlock prevention algorithms prevent deadlocks by restraining how requests can be made. A different method for avoiding deadlocks is to require additional information about how resources are to be requested.
For example, consider the following snapshot.
a. How many resources are there of type (A, B, C)?
b. What are the contents of the Need matrix?
c. Is this system currently in a safe state? Justify your answer.
d. If a request from P3 reaches for (1, 0, 0 ), can the request be
safely granted immediately?
Answer)
a. (3,14,11) resources = total + avail
b. Need = Max - Allocation.
A B C
P0 0 0 0
P1 0 7 5
P2 1 0 0
P3 0 0 2
c.Yes, because the processes can be implemented and processed in the order P0, P2, P1, P3.
d.
Question )Consider a system in which memory contains the following hole size in memory direction order:
20K, 10K, 18K, 9K, 12K and 15K.
Which hole is taken for successive segment request of
a. 6 KB
b. 10 KB
c. 12 KB
d. 9 KB
for the First fit, Best Fit, and Worst Fit. Clearly show the memory allocation using a diagram. Which algorithm makes the most efficient use of memory?
Answer)
First fit: (a) 20K (b) remainder of 20K (c) 18K (d) 10K
Best fit: (a) 9K (b) 10K (c) 12K (d) 15K
Worst fit: (a) 20K (b) 18K (c) 15K (d) remainder of 20K
Question) Suppose two processes enter the ready queue with the following properties: Process 1 has a total of 8 units of work to perform, but after every 2 units of work, it must perform 1 unit of I/O (so the minimum completion time of this process is 12 units). Assume that there is no work to be done following the last I/O operation. Process 2 has a total of 20 units of work to perform. This process arrives just behind P1. Show the resultant schedule for the shortest-job-first (preemptive) and the round-robin algorithms. Assume a time slice of 4 units of RR. What is the completion time of each process under each algorithm?
Answer)
SJF:
Completion time of process p1 = 12 unit
Completion time of process p2 = 28 unit
Round- robin (R R) algorithm:
Completion time of process p1 = 20 unit
Completion time of process p2 = 28 unit
Question) A data of 700GB is to be stored in disks of 200GB each.
a. How many such disks are required if the following RAID structures are implemented? Justify your answers with explanation and diagrams.
i. RAID 1
ii. RAID 0
iii. RAID 6
iv. RAID 5
b.If the system implements RAID 4, how many I/O operations are required for a write operation?
Answer)
a)1) 8 disks 2) 4 disks 3) 4+2=6 disks 4) 4+1= 5 disks
(with explanation and diagrams)
b)5 I/o operations
Question) Consider a system with a 90% hit ratio, 40 nano-seconds times to search the associative registers, 600 nano-seconds times to access memory. Find the time to access a page :
a. When the page number is in associative memory?
b. When the time to access a page when not in associative memory?
c. Find the effective memory access time?
Answer)
(a) The time needed is 40 nano seconds to fetch the page from the associative memory and 600 nano seconds to read the preferred word from memory.
Time = 40+600 = 640 nano seconds
(b)The time when the page is not in associative memory
Time=40+600+600=1240 nano seconds
One memory access extra is required to read the page table from memory.
(c)Effective memory access time = page number in associative memory + page number, not in associative memory.
Page number in associative memory = 0.9x640
Page number not in associative memory=0.1x1240
Effective memory access time = 0.9 x 640 + 0.1 x 1240 = 700 nano seconds
Question) Consider a physical memory of size 264 KB which is managed by buddies’ scheme. Suppose a set of five processes namely P1, P2, P3, P4 and P5demand memory requirement of size 2028KB, 112KB, 288 KB, 598KB and 25KB respectively. What would be the size of the memory blocks allocated to these four programs? Is it a fair allocation? Justify.
Answer)
As Buddy system allocates contiguous blocks of fixed size memory this is the power factor of 2. Therefore, if a process request memory which doesn’t fit into the appropriately sized units, the next highest power of 2 sizes of memory is allocated. In our case, allocated block size are as follows,
Process P1 which request 2028KB, the nearest power of 2 is 2048KB (211KB) which could satisfy the request. Therefore, the buddy scheme allocates a contiguous memory block of size 211 KB. Similarly, the process P2 gets memory block of size 27 KB, process P3 gets memory block of size 29 KB and process p4 gets memory block of size 210 KB and P5 gets 25.
Justification: The serious drawback of this approach is that it is extremely inefficient in terms of memory utilization. The reason is that this scheme services all the requests by always allocating memory which must be rounded up to a power of 2. This results in the substantial amount of internal fragmentation, since, on an average, it allocates almost double the size of requested memory which is simply a waste on the part of memory usage that often summarily leads to nearly half of the memory remained unutilized. However, the distinct advantage of this scheme is, that deallocation is quite fast, and subsequent coalescing of released memory to form a larger free contiguous memory block for subsequent use can be carried out at much faster speed than its other competitors.
Question) Linux’s security model is closely related to typical UNIX security mechanisms. Linux performs access control by assigning objects a protection mask that specifies which access modes are to be granted to processes. Give any four examples of file protection modes with allowed file accesses.
Answer) Any four with an explanation
Question) Consider a logical address space of eight pages of 1024 bytes each, mapped onto a physical memory of 32 frames.
a. How many bits are there in the logical address? Identify in the logical address the bits used as an offset and the bits used as the page number.
b. How many bits are there in the physical address? Identify in the physical address the bits used as an offset and the bits used as the frame number.
Answer)
(a) Logical address: 13 bits (8 pages X 1024 bytes/page = 8196 bytes – requires 213 addresses). Bits for offset: Bits 0 to 9 (10 bits for offset into 1024, 210 byte page), 3 bits identify page number (23= 8 pages)
(b) Physical address: 15 bits (32 frames X 1024 byes/frame = 32768 bytes, requires 215 addresses). Bits for offset: Bits 0 to 9 (10 bits for offset into 1024, 210 byte frame), 5 bits identify frame number (25= 32 frames)
Question) What are the differences between user-level threads and kernel level threads?
Answer)
(1) User-level threads are unidentified by the kernel, whereas the kernel is conscious of kernel threads.
(2) On systems with either M:1 or M:N mapping, user threads are organized and planned by the thread library and the kernel plans kernel threads.
(3) Kernel threads may not be associated with a process, however, every single user thread fits a specific process. Kernel threads are usually more costly to be maintained than user threads as they need to be denoted with a kernel data structure.
Question) Describe the actions taken by a kernel to context-switch between kernel-level threads.
Answer)
Context switching between kernel threads typically requires saving the value of the CPU registers from the thread being switched out and restoring the CPU registers of the new thread being scheduled
Question) In demand paging, a victim frame is selected using the page replacement algorithm, if there is no free frame in the memory. In general, the page replacement algorithm with the lowest page fault rate is selected as the scheme. Consider the following page-reference string in a 3-frames system
1 2 3 2 1 5 2 1 6 2 5 6 3 1 3 6 1 2 4 3
a. How many page faults would occur with FIFO page replacement?
b.How many page faults would occur with LRU page replacement?
c.How many page faults would occur with OPT page replacement?
d.Check for Belady’s anomaly considering 4 frames for FIFO.
Answer)
FIFO -14 9 Page faults
LRU – 11 9 Page faults
OPTIMAL – 9 Page faults
Checking for Belady’s anomaly
Question) Given the following queue 95, 180, 34, 119, 11, 123, 62, 64 with the Read-Write head initially at the track 50 and the tail track being at 199. Apply the following algorithms and find the total head movements. Which algorithm results in lesser head movement so as to achieve a faster seek time?
a.First Come-First Serve (FCFS)
b.Shortest Seek Time First (SSTF)
c.Elevator (SCAN)
d.Circular SCAN (C-SCAN)
e.C-LOOK
Answer)
(a)FCFS - For this case, it went from 50 to 95 to 180 and so on. From 50 to 95 it moved 45 tracks. In this example, it had a total head movement of 640 tracks.
(b)SSTF- In this case request is serviced according to next shortest distance. Starting at 50, the following shortest distance would be 62 and not 34 since it is merely 12 tracks far from 62 and 16 tracks far from 34. The process would continue until all the process is taken care of. For instance, the subsequent case would be to move from 62 to 64 and not 34 since there are only 2 tracks among them and not even 18 if it were to go the other way around.
50, 62, 64, 34, 11, 95, 119, 123, 180
Total Head movements - 236 tracks
(c)SCAN - This approach works like an elevator does. It tests down to the closest end and then when it hits the bottommost it tests up examining the requests that it didn't get while going down. If a request arises in when it is scanned it will not be serviced up until the process originates back down or moves back up.
50, 34, 11, 0, 62, 64, 95, 119, 123, 180
Total Head movements - 230 tracks
(d)C-SCAN - Circular scanning works just like the elevator to some extent. It begins its scan toward the closest end and works it all the way to the final end of the system. Once it hits the bottom or top it jumps to the other end and moves in the same direction. Keep in mind that the huge jump doesn't count as a head movement.
The total head movement for this algorithm -187 track
50, 34, 11, 0, 180, 123, 119, 95, 64, 62
(e)C-LOOK - This is just an enhanced version of C-SCAN. In this, the scanning doesn't go past the last request in the direction that it is moving. It too jumps to the other end but not all the way to the end. Just to the furthest request.
C-LOOK total head movements - 157 tracks.
50, 34, 11, 180, 123, 119, 95, 64, 62
