CSE2302 Examination Solutions

In the following multiple choice questions, more than one choice may be correct. Circle all correct answers. Full marks will be given where all correct answers are circled. Marks will be deducted within each question for incorrect answers.

Santa Claus sleeps in his shop at the North Pole and can only be wakened by either

all nine reindeer returning from vacation in the South Pacific, or
by some of the elves having difficulties making toys.

To allow Santa to get some sleep, the elves can only wake him when three of them have problems. When three elves are having their problems solved, any other elves wishing to visit Santa must wait for those elves to return.

If Santa wakes up to find three elves waiting at his shop's door, and the last reindeer has returned from the tropics, Santa has decided that the elves must wait until after Christmas, because it is more important to get the sleigh ready. (It is assumed that the reindeer don't want to leave the tropics, and therefore they stay there until the last possible moment.)

The last reindeer to arrive must wake up Santa while the others wait in a warming hut before being harnessed to the sleigh.

Write a suite of synchronized processes that will solve this problem. You may use any programming language you prefer, including pseudo code, and you must show the design and development of your solution. Python solutions will attract a bonus mark. (20+ marks)

Solution

I solved this problem by writing a process skeleton for each active participant type, and then adding the synchronization and mutual exclusion semaphores. Finally the appropriate initializations were added.

Santa Outline: (one only instance) 5 total

while (TRUE) do
    wait(WakeSanta) 1 for loop forever in each process; OR, identification of process set
    if (reindeer at door) then 1 for test on why woken
        1 for handling reindeer
        check that reindeer has rousted other reindeer 
        ready sleigh
        deliver toys
    else 1 for handling elves
        for (each elf) do 1 for remembering there's 3 of them
            solve problem
            send back to work
        end for
    end if
end while

Reindeer Outline: (one instance per reindeer, i.e., nine instances) 5 total

while (TRUE) do see Santa
    while(not Dec. 24 and not tired of South Pacific) do
        vacation in South Pacific
    end while 1 for non-synchronized stuff
    return to North Pole
    if last reindeer to return then 1 for last reindeer test
        for (each reindeer in warming hut) do
            signal(AllReindeerPresent) 1 for rousting other reindeer
        end do
        signal(WakeSanta) 1 for signalling wake up
    else
        # wait in warming hut
        wait(AllReindeerPresent) 1 for handling not last reindeer
    end if
    hook up to sleigh
    fly Santa around world
    return to South Pacific
end while

Elf Outline: (one instance per elf; arbitrarily many) 8 total

while (TRUE) do see Santa
    while (no problem) do 1 for non--synchronized stuff
        build toy
    end while
    wait(mutex); problemElfCount++; signal(mutex) 1 for mutex
    if problemElfCount < 3
        wait(NeedMoreElves)  1 for less than 3 need to wait
    else if problemElfCount >= 3 then
        # gather other 2 elves with problems 
        signal(NeedMoreElves); signal(NeedMoreElves);  1 for gathering 3 elves
        wait(mutex); problemElfCount -= 3; signal(mutex) 1 for mutex
    end if
    # if a group of elves off to see Santa
    #    have your group wait
    wait(ElvesGroupFinished) 1 for only 1 group at a time
    # this group OK to go
    signal(WakeSanta) 1 for signalling wake up
    see Santa
    # On returning, send another group of elves if there is one waiting
    signal(ElvesGroupFinished) 1 for releasing next group
end while

Initialization 2 total

semaphore mutex = 1 1 for correct initializations; OR identification of event set
semaphore WakeSanta = 0
semaphore AllReindeerPresent = 0
semaphore NeedMoreElves = 0
semaphore ElvesGroupFinished = 1 1 for correct semaphores; OR identification of variable set

1 bonus mark if solution presented in Python. Either Exact syntax, or extensive class description (e.g., __init__ and/or run definitions, etc., required for this mark!

Be lenient in the interpretation of these statements. For example, if a student correctly identifies that each of the elves and reindeer processes has a "wakeup Santa" requirement, then award the mark for this, even if not correctly coded.

Explain what reference semantics are, and why programmers of a real operating system might avoid using a language that has reference semantics as its default semantics. (5 marks)

Solution
RS require that objects are identified by a reference to them, rather than their actual value. Usually the term "reference semantics" does not require this regime to be applied to scalar values as well (for efficiency reasons), but this may be the case, particularly for stylised use. RS mean that when objects are passed around by their references, alterations to the object are propogated and seen by other contects also holding a reference to the same object. 1 mark for basic definition, 2 more for depth of discussion OSs are not likely to use RS, since value semantics are usually required anyway, RS requires more sophisticated memory management (garbage collection), and a higher level of run-time support. 1 mark for each argument to a max of 2
Draw a diagram that shows 3 user-level processes labelled U1, U2, U3 running, together with the operating system OS process and a disk controller D, and show on your diagram the control flow transfers when user level process U2 invokes a blocking read from disk D. (5 marks)

Solution
A diagram similar to is required. 2 marks for correct (consistent) diagram, 1 mark for control flow, 1 mark for parallel execution of IO, 1 mark for concurrent (interleaved) flow of process execution.
Draw a diagram of a modern multi-platter disk, and use it to discuss what is meant by the terms read/write arms, read/write heads, tracks, sectors, cylinders, seek time, seek latency, and rotational latency. (5 marks)

Solution
A diagram such as below is required.

read/write arms

label to diagram

read/write heads

label to diagram

tracks

label to diagram

sectors

label to diagram

cylinders

label to diagram

seek time

Time taken to move r/w arm to correct track

seek latency

same as seek time

rotational latency

time taken for correct sector to rotate into position under r/w head

1 mark for correct diagram, 1/2 mark for each correct definition or label.
Consider the following attempt at a critical section algorithm (written in Python).
```
blocked = [false,false]
turn = 0
class P(Thread):
    global blocked,turn
    def __init__(self,id): self.id = id
    while true:
        # entry code
        blocked[self.id] = true
        while turn != self.id:
            while blocked[1-self.id]:
                turn = self.id
        # end entry code

        # critical section

        # exit code
        blocked[self.id] = false
        # end exit code
p0 = P(0); p1 = P(1); 
p0.start(); p1.start();
```
Explain why the algorithm fails. (5 marks)

Solution
Consider p1 starts executing before p0, and reaches the first nested while. turn will be 0, and the condition is true, so the loop runs (1 mark). The body of the loop is a single while, whose condition blocked[0] will be false (1 mark). Hence the inner loop does not execute (1 mark). Nothing changes the condition of the while turn loop, so it continues executing indefinitely (1 mark), and the algorithm fails, since there is no bounded wait on p1 (1 mark).
Alternatively, just give 5 marks for a coherent explanation of all detail

Consider the following set of processes with the arrival for execution at the times indicated and the total required burst times listed.

Process	Arrival Time (mS)	Burst Time (mS)
P1	0	7
P2	2	10
P3	8	5
P4	13	3
P5	18	6

Answer the following questions (using illustrations or tables as necessary) for the two CPU scheduling algorithms:

Round Robin (RR) for time quantum of 4mS,
Non-preemptive Shortest Job First (SJF).

Draw a Gantt chart for each of the scheduling algorithms. (4 marks)

Solution

There is an ambiguity about whether arriving processes get priority over jobs already in the system, hence there are two valid solutions for the Round Robin, depending upon whether processes already in the system have priority (a), or arriving processes have priority (b).

Round Robin (a: resident processes have priority)

0	2	4	8	11	13	15	18	19	22	24	28	29
P1		P1	P1
	P2	P2	P2	P2		P2			P2
			P3			P3		P3			P3
					P4			P4
							P5			P5	P5	P5

Round Robin (b: arriving processes have priority)

0	2	4	8	11	13	15	18	19	22	23	27	29
P1		P1	P1
	P2	P2	P2			P2		P2			P2
			P3	P3		P3			P3
					P4			P4
							P5			P5	P5	P5

2 for correct diagram; 1 for incorrect data points but general structure correct (including correct ordering of processes)

Non-preemptive Shortest Job First

0	2	7	8	13	17	18	20	25
P1
	P2	P2
			P3				P3
				P4	P4
						P5		P5

2 for correct diagram; 1 for incorrect data points but general structure correct (including correct ordering of processes)

Compute the turnaround time of each process for each of the scheduling algorithms. (8 marks)

Solution

Process	RR(a)	RR(b)	SJF
P1	11	11	7
P2	22	27	15
P3	21	15	17
P4	9	9	7
P5	13	13	13

-1/2 for each one wrong

Compute the waiting time of each process for each of the scheduling algorithms. (8 marks)

Solution

Process RR(a) RR(b) SJF

P1 4 4 0

P2 12 17 5

P3 16 10 12

P4 6 6 4

P5 7 7 7

-1/2 for each one wrong

Process	RR(a)	RR(b)	SJF
P1	4	4	0
P2	12	17	5
P3	16	10	12
P4	6	6	4
P5	7	7	7

Consider an operating system MicroHard Doors 2001, which is using a basic paging system (without using demand paging) with a logical address space of 4,096Kbyte and page size of 128Kbyte. The hardware characteristics of the computer system are as follows:

Main memory size = 32 Mbyte (1M = 1024K, 1K = 1024 bytes)
Main memory access time = 75 nS
Smallest addressable unit = 4 bytes (i.e. 1 word)

How many frames are there in the system? Show the format of the logical address (i.e. How many bits for page number? How many bits for page offset?). (6 marks)

Solution
Memory size (physical space) is 8M words (2^23)
Logical space is 1024K words (2^20)
Page size is 32768 words (2^15) Number of frames = physical size/page size = 2^25/2^17 = 2^23/2^15 = 2^8 = 256 2 marks
Number of pages = logical size/page size = 2^22/2^17 = 2^20/2^15 = 2^5 = 32
PPPPPOOOOOOOOOOOOOOO (5 bits for page number, 15 bits for offset, total 20 bits for logical address) 2 marks for each page number, offset. If they fail to allow for 4 bytes per word smallest addressable unit, then 1 mark each (i.e., max 2 for this part of the question)
Assuming the page table is stored in main memory, what is the effective memory access time of this system? (4 marks)

Solution
Effective Access Time is 1 memory cycle to retrieve page table entry, 1 memory access to retrieve datum = 150nS 4 marks
If a translation look-aside buffer (associative register) with an average access time of 15nS is available in the hardware, assuming a hit ratio of 95%, what is the effective memory access time now? (4 marks)

Solution
EAT = h*(15 + 75) + (1-h)*150 = 0.95*90 + 0.05*150 = 85.5+7.5 = 93nS 4 marks
If demand paging was implemented and a process, P, was allocated 4 frames, sometime into the execution of process P, a reference to the virtual address of 0x1a7de68 (hexadecimal) was made. To which page and what offset from the beginning of this page does the virtual address refer? (2 marks)

Solution
The given virtual address is 25 bits long, and is outside the range of valid virtual addresses. The address translation fails. 2 marks. If they assumed that it referred to the real address, and stated this, then they should get an answer of 1101001 111101111001101000 or page 0x69, offset 0x3de68, 1 mark
Assuming an average page fault service time of 30mS and a page fault probability of 0.07%, what is the effective memory access time? (4 marks)

Solution
EAT = 0.9993*(93) + 0.0007*(30000000) = 92.9349 + 21000 = 21.093uS 4 marks
It is worth noting that I (ajh) computed these values by hand. They are not onerous calculations. However, many students found them so:
"Sorry, but my head can't calculate this"
"I need a calculator"
"Please note: due to lack of calculator I did not have time to caltulate exact values."
"Don't have calculator - NOT COOL."
"Something i'd figure out better with/if I had a calculator."
"Not enough time to calculate."
"...you expect them to do that kind of maths without a calculator? What planet are you on ?!"
"grrr.... need a calculator!"

Examination 2001

Solution

Solution

Solution

Solution

Solution

Solution

Solution

Solution

Solution

Solution

Solution

Solution

Solution