1. 
(a) -1086586880
(b) -1060896768
(c) -6.125

2.
	mov R2, val
    	mov R1, rt
search:	comp R1, #0
	beq fail
	comp 2(R1), R2
	beq found
	blt right

left:	mov R1, 0(R1)
	jmp search

right:	mov R1, 1(R1)
	jmp search
 	
found:  mov R3, #1
	mov success, R3
	mov match, R1
fail:	halt

rt:	????	; root of BST
val: 	????	; searching value
success:0
match:	????

3.
all semophores are initially 0.

Note: it is very important to signal other processes waiting
for the same semophore, or they can't resume execution.
 
P1:		P2:		P3: 
		wait(P1);	wait(P2);
/* do P1 */	singal(P1);	signal(P2); 
singal(P1);	/* do P2 */	/* do P3*/
		singal(P2);	signal(P3);


p4:		P5: 		P6:
wait(P2);	wait(P1);	wait(P4);
signal(P2);	sihnal(P1);	signal(P4);
/* do P4 */	/* do P5 */	wait(P5);
signal(P4);	signal(P5);	signal(P5);
				/* do P6 */
				signal(P6);


P7: 		P8:
wait(P1);	wait(P3);	
signal(P1);	signal(P3);	
/* do P7 */	wait(P6);	
signal(P7);	signal(P6);
		wait(P7);
		signal(P7);
		/* do P8 */
		signal(P8);

4.
Case I: 1R 4L
               
      |  R  |         
    L         L               
    _         _
      L  |  L 

after first wait, there are two possibilities:

        |R  |          either R or L1 will grab the other chopstick
    L         |L1
             
     |L    |L


         R  |          R is waiting, so L1 can grab the other cchopstick

    |L        |L1

      |L   |L


Case II: 2R 3L
case 1
      R  |  R       
    -        -
   L          L1

      |  L  |

After the first wait
      R   |R       
    ?         -     either R or L1 will grab the other chopstick.
   L          L1
              -
        |L

case 2:
      L1 |  L       
    -        -
   R1         R

      |  L  |

After the first wait
      L1|   L       If R1 doesn't grab, L1 can grab the other chopstick.
    -        ?      If R1 grab the chopstick, either R1 or L1 can grab 
   R1         R       the other chopstick.

     ?   L  |


Other cases are symetric to the above two cases, so there
will not be deadlock if we have at least one RHP and one LHP.

5.
34: 1536 = 600 => page 3
 9: 2048 = 800 => page 4
65: 3584 = E00 => page 7
10: 4608 =1200 => page 9

a) 
page  Frame
0      
:      
:      
9      4
10     9
:     
:      
34     3
:
:
65     7
:

b) 
page  Frame
0      
:      
:      
9      4
10     9
:     
12     3
:      
:
49     0	
:
65     7
:

c)
4608 = 1200 => 800 = 2048
5119 = 13FF => 9FF = 2559
5120 = 1400 =>1200 = 4608
33300= 8214 => E14 = 3604

6
a) FIFO

Faults=10 :
P|  5  3  7  5  2  8  5  3  5  2  8  7  2  8
============================================
0|  5  5  5  5  5  8  8  8  8  8  8  8  2  2
1|     3  3  3  3  3  5  5  5  5  5  5  5  8
2|        7  7  7  7  7  3  3  3  3  3  3  3
3|              2  2  2  2  2  2  2  7  7  7
============================================
F|  x  x  x     x  x  x  x           x  x  x


b) optimal

Faults=6 :
P|  5  3  7  5  2  8  5  3  5  2  8  7  2  8
============================================
0|  5  5  5  5  5  5  5  5  5  5  5  5  5  5  
1|     3  3  3  3  3  3  3  3  3  3  7  7  7  
2|        7  7  7  8  8  8  8  8  8  8  8  8  
3|              2  2  2  2  2  2  2  2  2  2  
============================================
F|  x  x  x     x  x                 x


c) LRU
Faults=7 :
P|  5  3  7  5  2  8  5  3  5  2  8  7  2  8
============================================
0|  5  5  5  5  5  5  5  5  5  5  5  5  5  5
1|     3  3  3  3  8  8  8  8  8  8  8  8  8
2|        7  7  7  7  7  3  3  3  3  7  7  7
3|              2  2  2  2  2  2  2  2  2  2
============================================
F|  x  x  x     x  x     x           x


d) Second-Chance
Key: - = Second-chance bit set
     < = Next pointer

Faults=7 :
P|  5  3  7  5  2   8  5  3  5  2   8   7  2   8
===============================================
0|  5  5  5  5- 5-< 5  5- 5- 5- 5-  5-  5  5   5
1|   < 3  3  3  3   8  8  8  8  8   8-  8  8   8-
2|      < 7  7  7   7< 7< 3  3  3   3   7  7   7
3|         <  < 2   2  2  2< 2< 2-< 2-< 2< 2-< 2-<
===============================================
F|  x  x  x     x   x     x             x