CS5348-Operating Systems: Homework 2 Solved

Implement a monitor solution for the bakery problem. Assume that you have N salesmen and customers arrive at arbitrary times. The code for customers and salesmen external to the monitor is given as follows.
customer  { get_service ();    receive the service    release_service ();

}

salesman

{ prepare_service();    provide the service    complete_service();

}

Discuss the steps for implementing the Monitor construct using integer semaphores. Consider letting the signalee continue after condition signaling. You need to consider all steps in the implementation and give more implementation details than those shown in lecture slides (which are incomplete).
Given the system state, follow Banker’s algorithm to determine whether to grant or deny the requests. You need to compute the “Needed” matrix (numbers of resources the processes still need) and the “Available” vector (the available resources currently in the system) first. Then you need to pretend to allocate and perform the safety analysis. You need to show your work for all the steps.
 

                                  Total         Allocated          MaxReq              Needed         Available 

                                                     𝑃 𝑃 𝑃 𝑃        𝑃 𝑃 𝑃 𝑃                 𝑃 𝑃 𝑃 𝑃           

𝑅     3          1   0    0   0        1   1    2   2         𝑅         6         1   1    0   1        2   2    2   1        

                        𝑅           4           0   0    1   1        2   1    1   2        

 

      Requested         𝑃 𝑃 𝑃 𝑃

𝑅  0   1   0   1  

𝑅  0   0   0   0

𝑅  1   1   0   0

Given the current system state, follow the deadlock detection algorithm to check whether there is a deadlock. You need to show your work clearly. If there is deadlock, you should also indicate which processes are involved in the deadlock.
 

                                  Total       Allocated   Requested 

                                                  𝑃 𝑃 𝑃         𝑃 𝑃 𝑃                

𝑅     1          1   0   0             0   0   1   𝑅        1         0   1   0             1   0   0  

                        𝑅           1           0   0   0       0   1   1       

                        𝑅           1           0   0   1       1   0   0  

Consider a memory system with 1GB space (=1024MB). Currently the memory free list contains ((128MB, 64MB), (320MB, 8MB), (512MB, 16MB), (768MB, 256MB)) where each item (x, y) in the list represents the starting location x and length y of a free partition. Four jobs 𝐽 , 𝐽 , 𝐽 , and 𝐽 of sizes 14MB, 20MB, 160MB, and 64MB, respectively, are to be loaded to the memory. Consider the first fit allocation policy and answer the following questions.Consider each job 𝐽 , 1  𝑖  4. When 𝐽 is running, what would be the value for the base register and bound register?
Now 𝐽 is running and it accesses the logical address 0x04213a0c. Compute the corresponding physical address. Also, check and determine whether this causes access violation.
Now 𝐽 is running and it accesses the logical address 0x02f3f12c. Compute the corresponding physical address. Also, check and determine whether this causes access violation.
Consider a 1GB memory system using buddy scheme. The system loads jobs 𝐽 , 𝐽 , 𝐽 , 𝐽 , and 𝐽 of size 40MB, 20MB, 160MB, 64MB, and 100MB, respectively.Compute the starting addresses of each job.
What is the total internal fragmentation?
Consider a 256MB memory system using simple paging scheme. Each page is of size 16KB. The memory is byte addressable. The page table for Process P is as follows. Process P’s address space is only 5 pages. The numbers in the table are all in decimal.
 

11
25
40
3
13
0

1

2

3

4

 

How many bits are required to address the entire memory?
How many bits are required to address the offset within each page?
What is the maximal possible internal fragmentation P can have?
Given a logical address 0x0000ef5b, compute the corresponding physical address. Also, check and determine whether this causes access violation.
Given a logical address 0x00017f5b, compute the corresponding physical address. Also, check and determine whether this causes access violation.
 

Consider a virtual memory system with cache, main memory, and disk. The cache size is 256KB and has an access time 15ns. The cache hit ratio is 90% (which is considered low). The main memory is 256MB and has an access time 150ns. 99.99% of the memory accesses would find the demanded pages in the main memory and 0.01% of them would generate page faults. The disk size is 20GB and has an access time 1ms. Compute the average memory access time.
Consider a virtual memory system using 32-bit addressing. The physical memory is of size 4GB. Each page is of size 8KB. Assume that each entry of the page table fits in one word. A two-level page table is used and the root level contains 1K entries. A process P has the following page table.
Root level page table             Level 2 page table               Level 2 page table               Level 2 page table                  start at 0x00000000            start at 0x00000100            start at 0x00001000

                     0x00001000                        frame 150                           frame 33                           frame 160

0x00000100 frame 21 disk frame 512 null disk frame 120 ……

                            ……                                   ……                                   ……                                        

                                                                 

How many bits are required to address the root page table?
How many bits are required to address each second level page table?
Convert the logical address 0000 0000 0100 0000 0101 0000 1111 0101 (binary) to physical address.