CHAPTER 5: CPU SCHEDULING
ANSWERS TO PROBLEMS 3, 4, 7, 8.

5.3 ANSWER

a.
The Gantt charts are

 Time ->
 0   1   2   3   4   5   6   7   8   9  10  11  12  13  14  15  16  17  18  19
 _____________________________________________________________________________
 |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   | 
 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 2 | 3 | 3 | 4 | 5 | 5 | 5 | 5 | 5 | FCFS
 | 1 | 2 | 3 | 4 | 5 | 1 | 3 | 5 | 1 | 5 | 1 | 5 | 1 | 5 | 1 | 1 | 1 | 1 | 1 | RR
 | 2 | 4 | 3 | 3 | 5 | 5 | 5 | 5 | 5 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | SJF
 | 2 | 5 | 5 | 5 | 5 | 5 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 3 | 3 | 4 | SJF
 -----------------------------------------------------------------------------


b.
Turnaround time

          FCFS   RR    SJF   Priority
    P1    10     19    19     16
    P2    11      2     1      1
    P3    13      7     4     18
    P4    14      4     2     19
    P5    19     14     9      6

c.
Waiting time (turnaround time minus burst time)
                 FCFS       RR      SJF      Priority
        P1          0       9       9        6
        P2         10       1       0        0
        P3         11       5       2        16
        P4         13       3       1        18
        PS         14       9       4        1
d.
Shortest job First

5.4 ANSWER
a. 10.53
b.  9.53
c.  6.86

Remember that turnaround time is finishing time minus arrival time, so you
have to subtract the arrival times to compute the turnaround times.
FCFS is 11 if you forget to subtract arrival time.


5.7 ANSWER
a. FCFS
b. LIFO Premptive

5.8 Answer
a. The shortest job has the highest priority.
b. The lowest level of MLFQ is FCFS.
c. FCFS gives the highest priority to the job that has waited the longest.
d. None



CHAPTER 7: DEADLOCKS
ANSWERS TO PROBLEMS 5, 8, 9, 13

7.5 ANSWER
There are many examples. This is only one, and not the simplest.

Consider the following snapshot of the system.
    
              Allocation        Max   Available
                 ABCD          ABCD    ABCD

        PO       0012          0012    1520
        P,       1000          1750
        P2       1354          2356
        P3       0632          0652
        P4       0014          0656
    
By allowing P1 to finish and return its resources to the Available list,
we can then service the request of P3. When P3 returns its resources,
Available contains (2 8 8 6), thus allowing the rest of the processes
to finish in any order.

7.8 ANSWER.
Suppose the system is deadlocked. This implies that each process is holding one
resource and is waiting for one more. Since there are three processes and
four resources, one process must be able to obtain two resources. This process
requires no more resources and therefore it will return its resources when done.

7.9 ANSWER
Using the terminology of Section 7.6.2 we have:

 (a)  Max_1 + Max_2 + ... + Max_n < m + n

 (b)  Max_i >= 1  for all i
      Proof: Need_i = Max_i - Allocation_i
      If there exists a deadlock state then:
 
 (c)  Allocation_1 + Allocation_2 + ... + Allocation_n = m

 Use a to get: (Need_1 +...+ Need_n) + (Allocation_1 +...+ Allocation_n)
                = (Max_1 +...+ Max_n)
                < m + n

 Use c to get: (Need_1 +...+ Need_n) + m < m + n 
 Rewrite to get: (Need_1 +...+ Need_n) < n 

This implies that there exists a process Pi such that Need_i = 0.
Since Max_i >= 1 it follows that Pi has at least one resource that
it can release. Hence the system cannot be in a deadlock state.

7.13 ANSWER
a.
Since Need = Max - Allocation, the content of Need is
                          ABCD
                          0000
                          0750
                          1002
                          0020
                          0642
b.
Yes, the sequence  satisfies the safety requirement.

c.
Yes. Since
    i. (0,4,2,0) <= Available = (1,5,2,0)
   ii. (0,4,2,0) <= Max_i = (1,7,5,0)
  iii. The new system state after the allocation is made is
    
              Allocation       Max      Need         Available
        P0       0012          0012     0000          1100
        P1       1420          1750     0330
        P2       1354          2356     1002
        P3       0632          06.52    0020
        P4       0014          0656     0642
and the sequence < P0, P2, P1, P3, P4 > satisfies the safety requirement.


CHAPTER 8: MEMORY MANAGEMENT
ANSWERS TO PROBLEMS 8, 9, 10, 16

8.8 Answer.
a. Logical address: 13 bits

b. Physical address: 15 bits

8.9 ANSWER
An address on a paging system is a logical page number and an offset. The
physical page is found by searching a table based on the logical page number
to produce a physical page number. Because the operating system controls
the contents of this table, it can limit a process to accessing only those
physical pages allocated to the process. There is no way for a process to
refer to a page it does not own because the page will not be in the page table.
To allow such access, an operating system simply needs to allow entries for
non-process memory to be added to the process' page table. This is useful
when two or more processes need to exchange data - they just read and write
to the same physical addresses (which may be at varying logical addresses).
This makes for very efficient interprocess communication.

8.10 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 x (200 nanoseconds) + 0.25 x (400 nanoseconds)
                      = 250 nanoseconds.


8.16 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


CHAPTER 9: VIRTUAL MEMORY
ANSWERS TO PROBLEMS 4, 5, 8, 10, 11, 16

9.4 ANSWER.

a. Stack - good.
b. Hashed symbol table - not good.
c. Sequential search - good.
d. Binary search - not good
e. Purecode - good.
f. Vector operations - good.
g. Indirection - not good.

9.5 ANSWER

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

9.8 ANSWER

effective access time  = 0.99 x (1 usec + 0.008 x 2 usec)
                         + 0.002 x (10,000 usec + 1,000 usec)
                         + 0.001 x (10,000 usec + 1,000 usec)
                         (0.99 + 0.016 + 22.0 + 11.0) usec
                         34.0 usec

9.10 ANSWER
The array is stored row-major; that is, the first data page contains A[1,1],
A[1,2], ..., A[2,100], the second page contains A[3,1], A[3,2], ..., A[4,100]
and so on.

a.
The page reference string is
   0, 1, 0, 2, 0,..., 0, 49, 0, 1, 0, 2, 0,..., 0, 49, ...
and thus there will be 5000 page faults.

b.
The page reference string is
   0,1,0,2,0,...,0,49
and thus there will be 50 page faults.

9.11 ANSWER
         Number of frames  LRU     FIFO  Optimal
               1           20      20    20
               2           18      18    15
               3           15      16    11
               4           10      14     8
               5            8      10     7
               6            7      10     7
               7            7       7     7


9.16 ANSWER.
a.
Define a page-replacement algorithm addressing the problems of:
    i. Initial value of the counters - 0.
   ii. Counters are increased - whenever a new page is associated
       with that frame.
  iii. Counters are decreased - whenever one of the pages associated
       with that frame is no longer required.
   iv. How the page to be replaced is selected - find a frame with
       the smallest counter. Use FIFO for breaking ties.

b.
14 page faults

c.
11 page faults

9.17 ANSWER
    
 effective access time =  (0.8) x (1 usec)
                           + (0.1) x (2 usec) + (0.1) x (5002 usec)
                       =  501.2 usec
                       =  0.5 msec



CHAPTER 10: FILE SYSTEM INTERFACE
ANSWERS TO PROBLEMS 11

10.11 ANSWER

a.
One piece of information kept in a directory entry is file location.
If a user could modify this location, then he could access other files,
defeating the access-protection scheme.

b.
Do not allow the user to directly write onto the subdirectory. Rather
provide system operations to do so.



CHAPTER 11: FILE-SYSTEM IMPLEMENTATION
ANSWERS TO PROBLEMS 1, 6
11.1 ANSWER

                    Contiguous  Linked  Indexed
                a.   201         1         1
                b.   101        52         1
                c.     1         3         1
                d.   198         1         0
                e.    98        52         0
                f.     0       100         0
   

11.6 ANSWER
Let Z be the starting file address (block number).

a.
Contiguous. Divide the logical address by 512 with X and Y the resulting
quotient and remainder respectively.

  i. Add X to Z to obtain the physical block number.
     Y is the displacement into that block.
 ii. 1

b.
Linked. Divide the logical physical address bv 511 with X and Y the
resulting quotient and remainder respectively.

  i. Chase down the linked list (getting X + 1 blocks).
     Y + 1 is the displacement into the last physical block.

 ii. 4

c.
Indexed. Divide the logical address by 512 with X and Y the resulting
quotient and remainder respectively.

  i. Get the index block into memory. Physical block address is contained
     in the index block at location X.
     Y is the displacement into the desired physical block.

 ii. 2


CHAPTER 13: IO DEVICES
ANSWERS TO PROBLEMS 1, 11, 12

13.1 ANSWER
a.
New requests for the track over which the head currently resides can
theoretically arrive as quickly as these requests are being serviced.

b.
All requests older than some predetermined age could be "forced" to the top of
the queue and an assocaited bit for each could be set to indicate that no new
request could be moved ahead of these requests. For SSTF, the rest of the queue
would have to be reorganized with respect to the last of these "old" requests.

c.
To prevent unusually long response times.


13.11 ANSWER

Rotational latency is usually not considered in disk scheduling because the
scheduler would need to know the number of the sector that would be underneath
the head at the time of I/O service. This information would have to come
immediately before servicing the I/O request in order to be accurate.
And this would require extra communication with the peripheral, which would
take time, cancelling some of the benefit.

13.12 ANSWER

There is no seek time nor latency on a RAM disk, so those factors can be ignored.
In fact, there is no need to schedule RAM disk accesses because they ll occur at
the same speed, no matter what has happened previously.