© DL at UTA, 1997

CSE 5306 Name______________________________________

Operating Systems Student ID Number_________________________

Exam 2, Summer 1997

Please read this:

This is a closed book, closed notes exam.

Use a dark ink and print answers on the test paper following the question.

Please try to keep answers together on the test page and avoid writing on the

back of the sheets of paper.

Turn in all pages of the test. Write your answers legibly. Unreadable answers

will be counted wrong. Make sure you have all pages of the test.

Read each question carefully and be sure your answer addresses the question.

Overly general (non-specific) answers will be counted wrong.

Point values are given for each question. The exam has a total of 100 points.

1. [ pts]

The "Eldorado 4" computer has a single machine instruction that does:

function trylock(var x: boolean): boolean;

begin trylock := x; x := TRUE; end;

The following is a part of a (user) program: (assume comments are

accurate, line numbers are not part of program)

1. /* Non critical section */

2. t := y * h;

3. /* Critical section */

4. write( fh, t );

5. /* End of critical section (remainder section)*/

6. temp := t - 1;

a. Can the instruction "trylock" be used to implement mutual-exclusion in

the above program code? If so, show how (where changes would go) if not

explain why not and show what changes (to the machine instruction and-

or program) would be necessary (if possible).

b. What problems or disadvantages, if any, does using the instruction

trylock to implement mutual-exclusion have above? Please explain.

c. If semaphores could be used to implement mutual exclusion, how and where would they

be done to change the program above?

The inhabitants of the planet Mars have launched a planatary probe (space

ship) to explore Earth. They have disguised the exploration module to look

like a chicken, thinking that the robot chicken could walk around freely on

the planet Earth (based on information from earth TV shows). The chicken,

named MAX (Mars Advanced eXplorer), has a computer system described as follows:

MAX has the following hardware configuration: The CPU has 26 address lines and

32 data lines, seperate address I/O space, is 8-bit addressable, is a CISC

architecture, all instructions are 16 bits, has an 16 K byte instruction cache,

and a 32 K byte data cache, with 2 Megabytes of main memory (MAXs head is

small). Main memory access takes 8 nanosecs, cache access takes .5 nanosecs.

MAX has 2 disks, each with its own disk controller. MAX has a soft real-time

OS (OSOS - Outer Space OS) which supports virtual memory with page sizes

selectable at system generation time (system "hatch") of either: 256 bytes or

4 K Bytes and reading a page takes 4 ms, writing a page takes 8 ms for either

page size.

2. [ pts]

For MAX:

a.) 1. What is the range (size) of physical addresses?

2. What is the range (size) of logical addresses?

b.) 1. What is the size of the page table?

2. How many page frames are there?

c.) Assuming that on average 10 percent of pages have been modified (dirty),

and the (maximum) page fault rate is 5 per 1,000,000

What is the overhead of VM? (Show calculations):

d.) Show (bitwise) how VM addressing works for OSOS (show address to address

translation, which bits of which address map to what)

e.) Which algorithm for VM page replacement is appropriate for MAX? What

extra hardware (if any) is necessary to implement it?

f.) A process deadlock would be a disaster on OSOS (who would reboot MAX?)

so other than ignoring it, what could be done? Give 2 possible solutions

and explain how they may be implemented.

3. [ pts]

The following are references to pages for processes that occur in

the given order. Where: P2.3 means process 2 needs "its" page 3.

If we have 4 page frames show those frames after EACH page reference:

P1.1, P2.1, P1.2, P2.2, P1.1, P1.3, P3.1, P2.1

FIFO replacement:

----------------------------------------------------------------

1.1 1.1 1.1

----------------------------------------------------------------

2.1 2.1

----------------------------------------------------------------

1.2

----------------------------------------------------------------

How many page faults occur (don't count first 3):_____________

LRU replacement:

----------------------------------------------------------------

1.1 1.1 1.1

----------------------------------------------------------------

2.1 2.1

----------------------------------------------------------------

1.2

----------------------------------------------------------------

How many page faults occur (don't count first 3):_____________

How many page faults would occur with OPTIMUM?:_____________

4. [ pts]

The following are memory partitions, in order, in memory. Memory partitions

may not be combined. Assume that the following processess arrive, in order.

Show how each algorithm would place processess in memory partitions:

Process Sizes: 100, 50, 300, 450, 150 (in order)

Partition Size: First Fit Best Fit Worst Fit

-------------------------------------------------------------------------

500

-------------------------------------------------------------------------

300

-------------------------------------------------------------------------

200

-------------------------------------------------------------------------

In the preceeding, what is internal fragmentation? (Describe or show)

In the preceeding, what is external fragmentation?