2.1 Bankers Algorithm (Safety Algorithm)

			Available Resource
	Current Allocaton	Maximum Need	A B C	Need to Complete
	A B C	A B C	2 3 1	A B C
P0	1 2 4	6 3 4
P1	1 0 0	6 5 3
P2	1 2 1	1 4 2
P3	2 1 1	3 5 2
P4	3 3 3	4 6 4

Fill in the Need to Complete column

Analyze whether there is a sequence that allows all processes to acquire resources and complete

If there is a sequence to complete list it here: Multiple, starts with P3, P2 either P0, P1

If there is no sequence to complete, explain why not

2.2 Disk Scheduling: using Shortest Seek-Time First, R/W head starts at track 50.

Sequence is 10, 50, 36, 21, 74, 28, 19, 35, 80, 70, 84, 32

Draw a line diagram with the track requests indicated like the powerpoint slide

Add arrows moving the R/W head to the next track using SSTF scheduling

Count the total head movement.

Page 3:

Analyze the performance of two scheduling mechanisms: Exponential Averaging, and true ShortestBurstFirst. Calculate the Average Completion Time AND count the number of context switches. The workload consists of the following:

P1: 11(3,4,4); P2: 7(2,5); P3: 17(2,4,5,6). I/O between bursts for 4 time quantums. Exp Ave default =2, alpha=0.6

Processes are executed in FIFO order within each queue.

Executing (initial pred=2, alpha =0.6)

Time

0

Exec

Ready

1,2,3

P1

2

P2

2

P3

2

I/O:4

Ave completion time = Context switches=

True SJF: (shortest CPU-burst first)

Time

0

Executing

ReadyQ

1,2,3

I/O:4

Completion time ave = Context switches =

Page 4 :

Mini-Cache

32 bytes of memory. 16 bytes of fully set-associative cache, where blocks can go anywhere within the set. Block is 4 bytes, set in cache is two blocks. Populate memory starting with 0-9, then upper case letters.

Hint- with full associativity in the set: each block has its own set of Tag bits. Memory is not organized by sets but by blocks, though blocks are assigned to sets and load in the cache in the correct set.

The following address requests will load the cache:

00111

00001

10000

10111

The CPU then generates address 10010. If this address is in the cache, respond with the requested byte.

Pages 5 & 6: Instruction Set Analysis and CPU Architecture in two parts

We need to develop an instruction set, formats, and CPU architecture to support the following operations:

R3 R1 OP R2: 32 instructions

R1 R1 OP R2: 32 instructions

MEM R1: 32 instructions

R2 R1 OP MEM: 16 instructions

MEM R1 OP R2: 16 instructions

The machine has 8 general purpose registers, each 16 bits in size. Memory is accessed by a base plus displacement of 16 bits.

Page 5: Analysis. & Instruction Formats.

Page 6 CPU internal design.

Page 7

For a process that has a parallel fraction (alpha) of 99.2%:

7a) Calculate the break-even point.

7b) Calculate the theoretical speedup at the break-even number of processors.

7d) Calculate the theoretical speedup if 2000 processors can be used (are available in the architecture).

7e) Explain what is meant-by CSMA-CD?

7f) Why is the Ethernet (original) frame size set to 576 bits?

7g) Explain the difference between a connection-oriented and connectionless packet transport strategy. With TCP/IP, what protocol is connectionless and what protocol is connection-oriented?

7h) Explain the theoretical basis behind caching effectiveness.

7i) List and explain the three problem areas that limit the realizable speedup from the use of pipelines.

7j) Explain why modern processors use a RISC design as opposed to the other CISC design.

Page 8 Gate Circuit Design Problem

Solve the following problem: represent as a truth table, extract a function, minimize the function, and implement in gates:

You are part of an engineering team to build an appliance, your job is involved with the digital logic controlling the heating of an automatic electric coffee/tea pot. A fail-safe circuit protects the pot and heating element from overheating based on a number of True/False conditions. The heating element should only be able to be energized when: the device is turned-on, the timer is above zero (it is counting down), the pot is on the heating surface (determined by the weight of the pot resting on the heating surface), and there is water in the pot (determined by weight above that of the pot),