soln9-14.txt

operating system concepts sixth edition windows XP updat 操作系统课后答案

Review Questions:

Question 9.5:
  Given memory partitions of 100K, 500K, 200K, 300K, and 600K (in
  order), how would each of the First-fit, Best-fit, and Worst-fit
  algorithms place processes of 212K, 417K, 112K, and 426K (in order)?
  
  Which algorithm makes the most efficient use of memory? 

Answer:
	a. First-fit: 
	b. 212K is put in 500K partition 
	c. 417K is put in 600K partition 
	d. 112K is put in 288K partition (new partition 288K = 500K - 212K) 
	e. 426K must wait 
	f. Best-fit: 
	g. 212K is put in 300K partition
	h. 417K is put in 500K partition 
	i. 112K is put in 200K partition 
	j. 426K is put in 600K partition 
	k. Worst-fit: 
	l.  212K is put in 600K partition
	m. 417K is put in 500K partition 
	n. 112K is put in 388K partition 
	o. 426K must wait 

  In this example, Best-fit turns out to be the best.

Question 9.7: 
   Why are page sizes always powers of 2? 

Answer: Recall that paging is implemented by breaking up an address into
  a page and offset number. It is most efficient to break the address
  into X page bits and Y offset bits, rather than perform arithmetic on
  the address to calculate the page number and offset. Because each bit
  position represents a power of 2, splitting an address between bits
  results in a page size that is a power of 2.

Question 9.8:
  Consider a logical address space of eight pages of 1024 words each,
  mapped onto a physi-cal memory of 32 frames. 
    a. How many bits are there in the logical address? 
    b. How many bits are there in the physical address?

Answer: 
  a. Logical address: 13 bits 
  b. Physical address: 15 bits

Question 9.10:
  Consider a paging system with the page table stored in memory. 
    a. If a memory reference takes 200 nanoseconds, how long does a 
       paged memory refer-ence take? 

    b. If we add associative registers, and 75 percent of all
       page-table references are found in the associative registers, 
       what is the effective memory reference time? (Assume that 
       finding a page-table entry in the associative registers takes 
       zero time, if the entry is there.) 

Answer:
  a. 400 nanoseconds; 200 nanoseconds to access the page table and 200
     nanoseconds to access the word in memory. 
  b. Effective access time = 0.75
     (200 nanoseconds) + 0.25   (400 nanoseconds) = 250 nanoseconds.
  
Question 9.16 
  Consider the following segment table: 
    Segment Base Length 
       0     219  600 
       1    2300   14 
       2      90  100 
       3    1327  580 
       4    1952   96 

  What are the physical addresses for the following logical addresses? 

    a. 0,430 
    b. 1,10 
    c. 2,500 
    d. 3,400 
    e. 4,112 

Answer: 
  a. 219 + 430 = 649 
  b. 2300 + 10 = 2310 
  c. illegal reference, trap to operating system 
  d. 1327 + 400 = 1727 
  e. illegal reference, trap to operating system

Question 9.17:
  Consider the Intel address translation scheme shown in Figure 9.20. 

    a. Describe all the steps that the Intel 80386 takes in translating
       a logical address into a physical address.

    b. What are the advantages to the operating system of hardware that
       provides such complicated memory translation hardware?

    c. Are there any disadvantages to this address translation system? 

Answer:
  a. The selector is an index into the segment descriptor table. The
     segment descriptor result plus the original offset is used to produce
     a linear address with a dir, page, and offset. The dir is an index
     into a page directory. The entry from the page directory selects the
     page table, and the page field is an index into the page table. The
     entry from the page table, plus the offset, is the physical address.

  b. Such a page translation mechanism offers the flexibility to allow
     most operating sys-tems to implement their memory scheme in hardware,
     instead of having to imple-ment some parts in hardware and some in
     software. Because it can be done in hard-ware, it is more efficient
     (and the kernel is simpler).

  c. Address translation can take longer due to the multiple table lookups
     it can invoke. Caches help, but there will still be cache misses.

Question 10.1:
  Under what circumstances do page faults occur? Describe the actions
  taken by the oper-ating system when a page fault occurs.

Answer: 
  A page fault occurs when an access to a page that has not been brought
  into main memory takes place. The operating system verifies the memory
  access, aborting the program if it is invalid. If it is valid, a free
  frame is located and I/Ois requested to read the needed page into the
  free frame.  Upon completion of I/O, the process table and page table
  are updated and the instruction is restarted.

Question 10.3:
  A certain computer provides its users with a virtual-memory space of
  2^32 bytes. The computer has 2^18 bytes of physical memory. The virtual
  memory is implemented by paging, and the page size is 4096 bytes. A
  user process generates the virtual address 11123456. Explain how the
  system establishes the corresponding physical location. Distinguish
  be-tween software and hardware operations.

Answer: 
  The virtual address in binary form is 
       0001 0001 0001 0010 0011 0100 0101 0110 

  Since the page size is 2^12, the page table size is 2^20 . Therefore
  the low-order 12 bits  0100 0101 0110  are used as the displacement
  into the page, while the remaining 20 bits  0001 0001 0001 0010 0011
  are used as the displacement in the page table.

Question 10.5:
  Assume we have a demand-paged memory. The page table is held in
  registers. It takes 8 milliseconds to service a page fault if an
  empty page is available or the replaced page is not modified, and 20
  milliseconds if the replaced page is modified. Memory access time is
  100 nanoseconds.  Assume that the page to be replaced is modified 70
  percent of the time.  What is the maxi-mum acceptable page-fault rate
  for an effective access time of no more than 200 nanoseconds?

Answer: 
  0.2 usec = (1 - P) X 0.1usec + (0.3P) X 8 msec + (0.7P) X 20 msec
  0.1      = -0.1P + 2400 P + 14000P
  0.1     ~= 16,400 P
  P       ~= 0.000006

Question 10.6:
  Consider the following page-replacement algorithms. Rank these
  algorithms on a five-point scale from  bad  to  perfect  according
  to their page-fault rate. Separate those al-gorithms that suffer from
  Belady s anomaly from those that do not.

    a. LRU replacement 
    b. FIFO replacement 
    c.  Optimal replacement 
    d. Second-chance replacement 

Answer: 
         Rank     Algorithm "Suffer from Belady's anomaly"
          1        Optimal             no 
          2          LRU               no 
          3      Second-chance        yes 
          4         FIFO              yes

Question 10.10 Consider the two-dimensional array A: 

  int A[][] = new int[100][100];

  where A[0][0] is at location 200, in a paged system with pages of
  size 200.  A small process is in page 0 (locations 0 to 199) for
  manipulating the matrix; thus, every instruction fetch will be from
  page 0. For three page frames, how many page faults are generated
  by the following array initialization loops, using LRU replacement,
  and assuming page frame 1 has the process in it, and the other two
  are initially empty:

    a. for (int j = 0; j < 100; j++) 
         for (int i = 0; i < 100; i++) 
           A[i][j] = 0; 
  
    b. for (int i = 0; i < 100; i++) 
         for (int j = 0; j < 100; j++) 
           A[i][j] = 0; 

Answer: 
  Assume an int is 2 bytes and each page has length 200 bytes.  Then one
  row fits in a page.  
  A. 100
  B. 100 * 100 = 10,000

Question 10.18:
  Consider a demand-paged computer system where the degree of
  multiprogramming is currently fixed at four. The system was recently
  measured to determine utilization of CPU and the paging disk. The
  results are one of the following alternatives.  For each case, what
  is happening?  Can the degree of multiprogramming be increased to
  increase the CPU utilization? Is the paging helping?

    a. CPU utilization 13 percent; disk utilization 97 percent 
    b. CPU utilization 87 percent; disk utilization 3 percent 
    c. CPU utilization 13 percent; disk utilization 3 percent 
  
Answer:
  a. Thrashing is occurring. 
  b. CPU utilization is sufficiently high to leave things alone, an increase 
     degree of multiprogramming. 
  c. Increase the degree of multiprogramming.

Question 11.1:
  Consider a file system where a file can be deleted and its disk space
  reclaimed while links to that file still exist. What problems may
  occur if a new file is created in the same storage area or with the
  same absolute path name? How can these problems be avoided?

Answer: 
  Let F1 be the old file and F2 be the new file. A user wishing to access
  F1 through an existing link will actually access F2. Note that the
  access protection for file F1 is used rather than the one associated
  with F2. This problem can be avoided by ensuring that all links to a
  deleted file are deleted also. This can be accomplished in several ways:

    a. Maintain a list of all links to a file, removing each of them when
       the file is deleted. 
    b. Retain the links, removing them when an attempt is made to 
       access a deleted file. 
    c. Maintain a file reference list (or counter), deleting the file 
       only after all links or ref-erences to that file have been deleted.

Question 11.3:
  Why do some systems keep track of the type of a file, while others leave
  it to the user or simply do not implement multiple file types? Which
  system is  better?

Answer: