- 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 ifend 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 Pacificend 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 groupend while
Initialization 2 total
semaphore mutex = 1 1 for correct initializations; OR identification of event setsemaphore WakeSanta = 0semaphore AllReindeerPresent = 0semaphore NeedMoreElves = 0semaphore ElvesGroupFinished = 1 1 for correct semaphores; OR identification of variable set1 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
- Consider the following attempt at a critical section algorithm (written in Python).
blocked = [false,false]turn = 0class 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 codep0 = 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 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 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)
2 for correct diagram; 1 for incorrect data points but general structure correct (including correct ordering of processes)0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 P1 P1 P1 P2 P2 P2 P2 P2 P2 P3 P3 P3 P3 P4 P4 P5 P5 P5 P5 Non-preemptive Shortest Job First
2 for correct diagram; 1 for incorrect data points but general structure correct (including correct ordering of processes)0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 P1 P2 P2 P3 P3 P4 P4 P5 P5 - Compute the turnaround time of each process for each of the scheduling algorithms. (8 marks)
Solution
-1/2 for each one wrongProcess 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 - Compute the waiting time of each process for each of the scheduling algorithms. (8 marks)
Solution
-1/2 for each one wrongProcess 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
If the word is in the cache, it takes the lookup time plus the memory time to retrieve, i.e., 15+75=90nS. If it is not, then we need two memory cycles (page table and target word) plus the TLB lookup time, i.e., 15+75+75=165nS
EAT = h*(15 + 75) + (1-h)*(15+75+75) = 0.95*90 + 0.05*165 = 85.5+8.25 = 93.75nS 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 marksIt 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!"
