联系方式

  • QQ:99515681
  • 邮箱:99515681@qq.com
  • 工作时间:8:00-23:00
  • 微信:codinghelp

您当前位置:首页 >> Java编程Java编程

日期:2019-12-11 09:43

1.[10 points] Deadlock

1.1.Does starvation imply deadlock? Please justify your answer. (2 points).


1.2.Consider the following code snippet (3 points)


If (a > 3)

   wait(s1);

else

   wait(s2);

b++;

wait(s3);

If (b < 0 && a <= 1)

   wait(s1);

else if (b >= 0 && a > 1)

   wait(s2);

else

   wait(s4);

a++;

signal(s4);

signal(s3);

signal(s2);

signal(s1);


s1, s2, s3 and s4 are binary semaphores with initial value 1. All variables are local variables for each thread. Consider two threads running this snippet of code simultaneously. Can there be a deadlock? Please use a concrete example to justify your answer. (3 points)

1.3.Consider the following snapshot of a system (5 points)

                      Allocation                  Max                    Available

         A B C D                       A B C D                        A B C D

          P0 1 1 0 1 2 2 3 6    1 0 5 2

          P1 1 2 0 1 2 7 1 1

          P2 3 2 1 1 4 4 5 3

          P3 2 4 1 1 4 4 5 2

          P4 1 0 0 0 1 0 4 2

             

Please answer the following questions (1 point each)

a)(2 points) Use the banker’s algorithm to determine whether the current system is safe or not. If yes, please demonstrate an order in which all the processes may complete.


b)(2 points) If a request from process P3 arrives for (2, 1, 0, 1), can this be granted immediately? If yes, show an execution order.


c)(2 points) If a request from process P3 arrives for (1, 0, 0, 0), can this be granted immediately? If yes, show an execution order.


d)(2 points) If a request from process P2 arrives for (0, 0, 0, 2), can this be granted immediately? If yes, show an execution order.

2. [25 points] Memory Management

2.1.What is address binding? Please briefly describe three ways of address binding? (4 points)

2.2.A computer system has a 16-bit virtual address space for a total of 64 Kbytes. Suppose the page size is 8 Kbytes, and thus the virtual address space of a process consists of 8 pages. A page table entry (PTE) has a 9-bit frame number, a valid bit, and a writable bit (11 bits in total).  (6 points)


a)What is the maximum size of the physical memory? (2 points)


b)Consider the following page table.

PageValidFrameWritable

0Yes0x005No

1Yes0x012Yes

2Yes0x02ENo

3NoN/ANo

4NoN/ANo

5NoN/ANo

6Yes0x003Yes

7Yes0x004No


Translate three virtual addresses by filling in the following table. (4 points)

Virtual AddressValid (yes/no)Physical Address in Hexadecimals (if valid)Writable (yes/no)

0x1234

0x4321

0x8848


2.3.Consider a virtual address given below, in which the first 10 bits are used as an index into the first-level page table and the next 10 bits are used as an index into a second-level page table, which performs address translation. Suppose each page table entry (PTE) size (in both first- and second-level page tables) is 4 bytes, please answer the following questions. (7 points)


page   numberpage offset

10-bit10-bit12-bit


a)What is the page size in such a system? (1 point)


b)What is the size of the virtual address space? (1 point)

c)How much memory does the first-level page table occupy? (1 points)

d)How much memory do all of the second-level page tables occupy? (2 points)

e)How much space is needed by the second-level page tables for a process that requires a memory space of 16 MB? (2 points)


2.4.What is swapping, and what is the main benefit of using swapping? (2 points)


2.5.Consider the following segment table (6 points)

SegmentBaseLength

0120189

12155596

252580

3165064

4846378


What are the physical addresses for the following logical addresses (segment number, offset)?

a)0, 227

b)2, 63

c)3, 45


What are the logical addresses for the following physical addresses?

d)247

e)1450

f)1043


3. [25 points] Virtual Memory


3.1.Consider a two-dimensional array A:

  char A[][] = new char[100][100];


where A[0][0] is at location 200 in a paged memory system with pages of size 200 bytes. A process that manipulates the matrix resides in page 0 (i.e., the program resides in locations 0 to 199). Thus, every instruction fetch will be from page 0. Suppose that three frames are allocated to this process and LRU replacement is used, how many page faults are generated by the following array-initialization loops? (4 points) Hint: frame 1 always contains the program and the other two used for the array are initially empty.


a.for (int j = 0; j < 100; j++) ??  

  for (int i = 0; i < 100; i++) ??      

     A[i][j] = 0;


Answer:


b.for (int i = 0; i < 100; i++) ??  

  for (int j = 0; j < 100; j++) ??      

     A[i][j] = 0;

Answer:


3.2. Consider the following sequence of page references in term of page numbers:

1, 3, 2, 2, 3, 4, 1, 4, 3, 2, 4, 1

Suppose there are 3 frames allocated for this process, please illustrate the contents of the frames under 3 different page replacement algorithms and compute the number of page faults for each algorithm. (9 points)

Number of page faults:


3.3.One crucial requirement for demand paging is the ability to restart any instruction after a page fault. A major difficulty arises when one instruction may modify several different memory locations. For instance, consider the IBM System 360/370 MVC (move character) instruction, which can move up to 256 bytes from one location to another (possibly overlapping) location. If either block (source or destination) crosses a page boundary, a page fault might occur after the move is partially done. In addition, if the source and destination blocks overlap, the source block may have been modified, in which case we cannot simply restart the instruction. Can you think of a way to resolve this problem? (3 points)

3.4.The figure below illustrates how CPU utilization changes with the increases of the degree of multiprogramming. Please briefly explain the behavior in the two ranges. (3 points)

3.5.We have only discussed demand paging in the lectures. Demand segmentation is similar to demand paging, with the only difference of using variable-sized “pages.” However, this can significantly complicate the replacement algorithms. Please briefly sketch two segment-replacement algorithms, one based on the FIFO page-replacement scheme and the other based on the LRU page-replacement scheme. Notice that since segments are not of the same size, a segment that is selected for replacement may be too small to make sufficient room for the new segment. In this case, multiple segments need to be selected and replaced. In addition, the OS has to keep track of any leftover (free holes) after the replacement. Assume that segments can be relocated freely anywhere inside the memory. (6 points)

4.[10 points] The secondary storage system

4.1.A RAID level 0 disk array usually performs better that a RAID level 1 disk array due to block stripping. Is it possible that in some cases, a RAID level 1 achieves better performance for some read requests than a RAID level 0? Please justify your answer (2 points)


4.2.Please briefly describe the three advantages of using NVM (non-volatile memory) devices over HDDs as the secondary storage. (2 points)


4.3.Suppose that a disk drive has 6000 cylinders, numbered 0 to 5999. The drive is currently serving a request at cylinder 2000, and the previous request was at cylinder 1200. The queue of pending requests, in FIFO order, is:

3000, 2500, 100, 200, 600, 3500, 1000, 4900

Starting from the current head position (2000), what is the total distance (in cylinders) that the disk arm moves to satisfy all the pending requests for each of the following disk-scheduling algorithms? (6 points)

a)FCFS

b)SSTF

c)SCAN

d)C-SCAN

e)LOOK

f)C-LOOK

Answer:


5. [10 points] File Systems

5.1.File systems provide mechanism to track the free disk space, usually in term of disk blocks. What is the advantage and disadvantage in bit map and linked-list? (4 points)


5.2.We have discussed three file allocation strategies, namely contiguous, linked, and indexed allocation. In practice, what criteria should be used in deciding which strategy is best utilized for a particular file? (3 points)


5.3.Consider a Unix file system that uses inodes to represent files. Each disk block size is 4KB. The disk address is 32 bits. This file system has 7 direct disk blocks, 2 indirect, one double indirect, and one triple indirect disk block.  What is the maximum size of a file that can be stored in this file system? (3 points) (You only need to obtain an approximation)


6.[10 points] Security and Protection


6.1.What is the principle of least privilege?  What is the purpose of this with respect to the security protection? (3 points)


6.2.What is the advantage of protection rings over the two modes of operations? What is the main limitation of protection rings? (3 points)


6.3.Compare and contrast different access matrix implementation, including global table, access list, capability list and lock-key mechanism. (4 points)


7.[10 points] Synchronization


7.1.The operating systems provide different locking mechanisms depending on application needs. Windows and Linux implement multiple locking mechanisms including spinlocks, mutex locks, semaphores, and condition variables. Please briefly explain under what scenario each mechanism is needed. (3 points)


7.2.Suppose there are 2N H atoms and N O atoms dynamically arrive over time. A program is written to facilitate the chemical reaction to form water, which is invoked when two H atoms and one O atom are present. The atoms are threads. Each H atom invokes a function hReady when it is ready to react, and each O atom invokes a function oReady when it is ready. For this problem, you are to write the code for hReady and oReady. The functions must delay execution until there are at least two H atoms and one O atom present, and then one of the threads must call the function makeWater (which just prints out a message that water was made). After the makeWater call, two instances of hReady and one instance of oReady should return. The solution should avoid starvation and busy-waiting.


Given the following two implementations, justify whether each implementation either (1) works, (2) doesn’t work, or (3) is dangerous -- that is, sometimes it works and sometimes it doesn’t. If the implementation does not work or is dangerous, explain why and show how to fix it so it does work.


You may assume that the semaphore implementation enforces FIFO order for wakeups — the thread waiting longest in wait() is always the next thread woken up by a call to signal(). (7 points)

(a)Implementaion-1 (3 points)


Semaphore h_wait = 0;

Semaphore o_wait = 0;

int count = 0;


hReady() {

 count++;

 if (count % 2 == 1) {

   wait(h_wait);

 } else {

signal(o_wait);

wait(h_wait);

 }

}oReady() {

 wait(o_wait);

 makeWater();

 signal(h_wait);

 signal(h_wait);

}

(b)Implementaion-2 (4 points)


Semaphore h_wait = 0;

Semaphore o_wait = 0;


hReady() {

 signal(o_wait);

 wait(h_wait);

}oReady() {

 wait(o_wait);

 wait(o_wait);

 makeWater();

 signal(h_wait);

 signal(h_wait);

}



版权所有:留学生编程辅导网 2020 All Rights Reserved 联系方式:QQ:99515681 微信:codinghelp 电子信箱:99515681@qq.com
免责声明:本站部分内容从网络整理而来,只供参考!如有版权问题可联系本站删除。 站长地图

python代写
微信客服:codinghelp