Java程序辅导

Monash University
Semester Two 2010 Examination Period
Faculty of Information Technology
EXAM CODES: FIT2022
TITLE OF PAPER: FIT2022 Computer Systems 2
EXAM DURATION: 3 hours writing time
READING TIME: 10 minutes
THIS PAPER IS FOR STUDENTS STUDYING AT: Clayton, Malaysia
INSTRUCTIONS FOR CANDIDATES
During an exam, you must not have in your possession, a book, notes, paper, calculator, pencil case, mobile
phone or other material/item which has not been authorised for the exam or specifically permitted as noted
below. Any material or item on your desk, chair or person will be deemed to be in your possession. You are
reminded that possession of unauthorised materials in an exam is a discipline offence under Monash Statute
4.1.
No examination papers are to be removed from the room.
Answer all questions in SECTION A, and any 4 questions from SECTION B.
AUTHORISED MATERIALS
CALCULATORS: NO
OPEN BOOK: NO
SPECIFICALLY PERMITTED ITEMS: NO
Candidates must complete this section
STUDENT ID DESK NUMBER
Page 1 of 18
SECTION A: Tutorial Questions: Answer ALL questions in this section. (20 marks total)
Each question in this section is worth 2 marks.
1) A new computer architecture is proposed which contains an instruction to exchange the contents of two
registers. Would this instruction be suitable to implement mutual exclusion? Why (not)?
Answer:
No. It cannot be used in the style of the exchange register and memory instruction,
because the lock value in one of the registers must be loaded from memory first. Be-
tween the load of the register and the exchange instruction, an interrupt may occur, thus
potentially altering the lock value in memory, without updating the register.
Comment: Not well done. Too many candidates focussed on the (mistaken) concept that
the registers were somehow each associated with the processes in contention, indicating
that they did not understand the crucial (correct) issue that it is the atomicity of the
operation that is at stake.
[2 marks]
2) When an application program calls a system function to carry out some operation, should the system
operation be executed in user space, system space, or in kernel space? Why?
Answer:
It depends. Some system calls can execute in user space (e.g. read from buffer), others in
system space (buffer copy), while others must execute in kernel space (I/O data transfer).
(1 mark for answer, 1 mark for explanation)
Comment: Any of the alternatives were accepted, as long as they were accompanied by
a consistent explanation.
[2 marks]
3) One approach to the design of an operating system is to build the components of the system in layers,
where components in each layer m depend upon the resources and operations provided by components
at the next lower level m-1. The hardware is then regarded as layer 0. What advantages can you think
of for this approach?
Answer:
Separation of concerns - each layer responsible for adding specific, limited functionality.
Simplifies design, and eases maintenance. (1 mark for each advantage, max 2)
Comment: straightforward bookwork. Most candidates coped with this question.
[2 marks]
4) Should operating systems always make the most efficient use of the computing hardware? Under what
circumstances might this paradigm be broken?
Answer:
Not necessarily. Issues such as minimizing response time may preclude efficient hardware
use. (1 mark for answer, 1 mark for example)
Comment: also straightforward.
[2 marks]
Page 2 of 18
5) A disk system has sectors contain 256 bytes. Identify 2 different ways of representing a file across a set
of disk blocks. For each method, how might byte a48 of the file be accessed?
Answer:
sequential (starting address+a4816); random (lookup address of block number a16 in file
inode/dictionary/table and read byte 4816 from that block). (0.5 for each method, 0.5 for
each algorithm)
Comment: Not well done. Most had some idea of the variety of file structures, but were
unable to explain how they distributed over disk blocks. Given that this was straight out
of lab 3, it makes one wonder at how the lab learning experience is assimilated. When it
came to specifying how to compute the address of byte a4816, only a handful of candidates
were able to do this.
[2 marks]
6) Explain the difference between dynamic linking and dynamic loading.
Answer:
Linking is the process of resolving inter-module references (e.g., to library routines), load-
ing is the process of adding executable code to memory. The ’dynamic’ prefix simply
means that these are done as required during the execution of a process, rather than
beforehand (’static’). (1 mark each definition, including ’dynamic’ explanation)
Comment: Also not well done. Not only is this bookwork, but it is bookwork covered
in FIT1001 as well as FIT2022!
[2 marks]
7) Explain how a two-level page table scheme improves the basic paging memory management strategy by
reducing the memory demands of the logical to physical address mapping process. If two-level paging
schemes are useful in this respect, would a two level segmentation scheme give any advantage over a
one-level paging scheme? Why (not)?
Answer:
A one-level page table requires one entry for every (logical) page in the address space.
All entries must be resident in memory. A two-level page table only requires the top-level
page table to be resident, and this only requires sqrt(number of logical pages) of entries
(assuming top and bottom level tables equal in size). Yes, although not having fixed page
sizes would complicate things to the point of impracticality.
Comment: Better. Many students commented on the square root attribute, but did not
explain it correctly. In a two-level table, the number of entries in the top level table is the
square root of the number of entries in a one-level table. Second-level tables however must
have the same number of entries (in total) as a one level table, because that is defined
by the number of virtual pages. Two level tables thus require more virtual memory than
one-level tables, but their big advantage is that only the single top-level table must be in
physical memory.
[2 marks]
8) You need to arrange a meeting between yourself and two friends as soon as possible. Describe a protocol
for using the telephone (with no conference call facility) to arrange such a meeting. What relevance
does this problem have to I/O systems?
Page 3 of 18
Answer:
I/O device telephone
I/O device X free? ring address X
no, abort no answer, ring later
yes, set up transfer yes, say hello and introduce yourselves
perform I/O have conversation
complete transfer say goodbye
reset device hangup
For n friends (not counting originator), 2n − 3 instances of this protocol are required in
the worst case.
Comment: Given the attention given to this problem in tutorials, most were able to
collect at least one mark here.
[2 marks]
9) Why is it difficult to protect a system in which users are allowed to do their own I/O?
Answer:
Consider the disk subsystem, particularly the disk boot sector. If users could do their
own I/O, they could write a new boot sector, and then on the next reboot, their program
would obtain control of the entire system. (Other examples are possible.)
Comment: Nearly all candidates could give a coherent explanation to this.
[2 marks]
10) Consider the following attempt at a critical section algorithm.
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.
Answer:
The while loop while turn != self.id: must terminate at some stage. However, if
the inner loop condition blocked[1-self.id] is initially false, the outer loop will have a
null body, and it will loop forever, since nothing will act to change the condition turn !=
self.id
Comment: This one surprised me. After the poor showing on this question in 2008, I
thought it worth running this question again. Nearly everyone was able to point to the
circumstances causing the infinite loop, although the explanations were at times muddy.
[2 marks]
Page 4 of 18
SECTION B: Answer any FOUR questions in this section (80 marks total)
1)
a) Consider a concurrent program with two processes p and q, defined as follows. A, B, C, D and E
are arbitrary atomic (indivisible) statements. Assume that the main program (not shown) does
a parbegin (parallel execution) of the two processes.
def p():
A
B
def q():
C
D
E
Show all 10 possible interleavings of the execution of the two processes (show this by giving
execution “traces” in terms of the atomic statements).
Answer:
i) A, B, C, D, E
ii) A, C, B, D, E
iii) A, C, D, B, E
iv) A, C, D, E, B
v) C, A, B, D, E
vi) C, A, D, B, E
vii) C, A, D, E, B
viii) C, D, A, B, E
ix) C, D, A, E, B
x) C, D, E, A, B
Half mark for each
[5 marks]
Page 5 of 18
b) The famous Carrickarede rope bridge in Northern Ireland is wide enough for only one person. It
is suspended 30 metres above the rocks below and is not for the faint-hearted! Explain the four
conditions of deadlock, and show how they can apply in this situation.
Answer: Assume there is a person at each end of bridge, and both proceed onto the
bridge.
i) mutual exclusion: only one person proceed across the bridge - it is not
wide enough for two people to pass.
ii) hold and wait: each person is holding the section of bridge that the other
person needs to complete the crossing.
iii) no preemption: once on the bridge, it is too scary to turn back!
iv) circular wait: each person is waiting on the other to turn back.
(1 mark for each condition, plus 1 for explanation(s))
[8 marks]
Page 6 of 18
c) Consider the following solution to the bounded buffer problem:
Data:
int n,in,out;
ItemType buffer[n],nextp,nextc;
Producer:
do {
...
produce(nextp);
...
while ((in+1) % n == out) {noop;}
buffer[in] = nextp;
in = (in+1) % n;
} until 0;
Consumer:
do {
while (in==out) {noop;}
nextc = buffer[out];
out = (out+1) % n;
...
consume(nextc);
...
} until 0;
i) This is a valid solution to the problem, but is inefficient in that it only uses n-1 slots of
the buffer. Explain why.
Answer: Assume that the buffer is initialized with in=out=0. Next assume
that no items are removed from the buffer, so that out=0, while items are
added by the producer. The number of items added will thus be equal to in.
The condition for the buffer being full is (in+1)\%n == out, which, since
out=0, reduces to (in+1)\%n=0. But if in hasn’t wrapped around, this is
in+1=n, or in=n-1. Since nothing has been removed, this means that the
number of items added, in or n-1, is the maximum capacity of the buffer.
QED.
[1 mark]
ii) It also uses busy waiting. Explain what this is, and why it is inefficient.
Answer: The busy wait occurs in the while () {noop;} code fragments. It
involves repeated testing of a condition, waiting for it to become false. The
repeated execution consumes CPU cycles to no real purpose and is wasteful.
[1 mark]
Page 7 of 18
iii) Rewrite the bounded-buffer solution, so that it uses all n slots of the buffer, and uses
semaphores to avoid the busy waiting.
Answer:
Data:
int n,in,out,count=0;
ItemType buffer[n],nextp,nextc;
semaphore notempty,notfull; /*initialized to 0,1*/
Producer:
do {
...
produce(nextp);
...
if (count=n) {wait(notfull);}
buffer[in] = nextp;
in = (in+1) % n; count++;
signal(notempty);
} until 0;
Consumer:
do {
if (count==0) {wait(notempty);}
nextc = buffer[out];
out = (out+1) % n; count--;
signal(notfull);
...
consume(nextc);
...
} until 0;
1 mark for declaring appropriate semaphores
1 mark for count variable
1 mark for correct increment/decrement of count
1 mark for correct wait operation and placement on notfull,notempty
1 mark for correct signal operation and placement on notfull,notempty
[5 marks]
Page 8 of 18
2)
a) The buddy system is a memory management scheme that uses variable sized partitions. Assume
a computer with a memory size of 256K, initially empty. Requests are received for blocks of
memory of 5K, 25K, 35K and 20K.
i) Explain the basic principle behind the buddy system.
Answer: If a free block of size 2i ≥ requested size < 2i−1 exists, allocate that,
otherwise split the next largest block into 2 and repeat the process. 1 mark
for splitting in half, 1 mark for correct power of 2.
[2 marks]
ii) Show how the buddy system would deal with each request, showing the memory layout at
each stage.
Answer:
[4 marks]
iii) After allocating all the processes, what would be the effect of the 25K process terminating
and returning its memory?
Answer:
[2 marks]
b) A particular computer has 0.5GB (Gigabytes) of real memory and the operating system on this
computer uses a maximum of 4TB (Terabytes) of virtual memory for each user process, and 4096
bytes for a page size.
Answer: 0.5Gb is 229. 4TB is 242.
i) How many pages in a process memory space are there?
Answer: 242 ÷ 4096 = 242−12 = 230 (or 1073741824 - a power of 2 suffices)
[2 marks]
ii) What is the maximum number of entries in a page table?
Answer: 229 ÷ 4096 = 229−12 = 217 (or 135168 - a power of 2 suffices)
[2 marks]
iii) How many bits are necessary for a page frame number?
Answer: 17 (from the previous question)
[2 marks]
(Show your calculations.)
c) What is the difference between long-tem scheduling and short-term scheduling?
Answer:
Long term scheduling adds jobs to the ready queue from the job queue
Short term scheduling dispatches jobs from the ready queue to the running state.
2 marks each for these statements or (succint) variants thereof. Lose 1 mark if they
omit the words (or notion of) job and ready queues, 1 mark if distinction between
job and ready queues is not made adequately.
[4 marks]
d) What are the system indications for adding more jobs to the ready queue? For removing jobs
from the ready queue?
Page 9 of 18
Answer:
Adding jobs:
• CPU utilization falls
• many processes in blocked state, few in ready queue
• ...
Removing jobs:
• thrashing
• lack of memory
• termination
• ...
0.5 marks for each valid point up to a total of 2
[2 marks]
Page 10 of 18
3) The Cigarette Smokers Problem. Consider a system with three smoker processes and one agent process.
Each smoker continuously rolls a cigarette and then smokes it. But to roll and smoke a cigarette, the
smoker needs three ingredients: tobacco, paper, and matches. Each smoker has a supply of exactly
one of these ingredients: one has tobacco, the next paper, and the third matches. The agent has a
supply of all three ingredients, and on each cycle places two arbitrarily chosen ingredients on the table.
The smoker who has the third ingredient then makes and smokes a cigarette, signalling the agent on
completion, who then puts out two more arbitrarily chosen ingredients, and the cycle repeats.
Write a program to synchronize the agent and the smokers. You may use any programming language
you choose to write the code. (A bonus of 1 mark applies if you use Python!) Pseudo-code is acceptable.
Use the next page for your rough working, then include your final version on this page.
Answer:
Key Variables
agent=Semaphore(1)
ingredient=[Semaphore(0) for i in range(2)]
(in what follows, we use wait and signal, but the Python Semaphore object uses acquire
and release respectively.)
Agent Process
class Agent(Thread):
def __init__(self):
pass
def run():
while True:
agent.wait();
i = choose_ingredient_to_omit();
ingredient[i].signal();
Smoker Process (parameterized by missing ingredient i)
class Smoker(Thread):
def __init__(self,num):
self.num=num
def run(self):
while True:
ingredient[self.num].wait();
smoke_cigarette();
agent.signal();
Main Process
agent=Agent()
agent.start()
smokers=[Smoker(i) for i in range(3)]
for i in range(3):
smokers[i].start()
Page 11 of 18
Answer: 4 marks were allocated to each of the following concepts evidenced by the student’s
answer.
a) semaphores (correct declaration and initialization)
b) inter-process communication (correct placement of wait and signal calls)
c) data structures (correct declaration and use)
d) code (readable, properly structured)
e) processes (declaration, initialization and instantiation)
Comment: There were a surprising number of students who made no attempt at defining
concurrency in their program. Maybe the question was slightly ambiguous in this respect,
but to not use concurrency in this question would indicate that the student was asleep for
most of the semester.
Several otherwise perfect answers made a fatal flaw in attempting to make each smoker
do serial waits upon their needed two ingedients. A moment’s reflection should convince
the reader that no ordering of the (circular) dependencies upon missing ingredients will
avoid the possibility of deadlock when using this algorithm. The key to a correct solution
is to wait upon the smoker’s held ingedient being not supplied.
[20 marks]
Page 12 of 18
4)
a) In Laboratory session 5, you saw how to model various scheduling algorithms as a vehicle for
simulating the multiprogramming behaviour of processes within a job mix.
That simulation used the following set of events to determine key transitions in
the simulation.
create A process is created. The event defines the process number of the process that is
created. We also define the total running time of the process, which determines
how long the process will execute before it reaches the terminate state. Since
the process may also generate I/O which will in turn generate a rescheduling,
we model this with a (very simple) model of defining how many time intervals
before it issues an I/O operation. If this value is zero, no I/O will take place.
Other information attached to the process is not used in FCFS, and so can be
set to zero. The event record will look like this:
[event time] create [process no] [run time] [I/O time]
admit A specified process is admitted to the ready queue. No other information re-
quired.
[event time] admit [process no] 0 0 0
dispatch this event will be generated by the scheduler, when it determines which process
to make ready. There should be no input event records for dispatch.
iowait this event will be generated by the scheduler, from information in the create
input record. There is no input event record for iowait itself.
iocomplete this event needs to be generated by the scheduler, whenever a process goes into
the iowait state. For the moment, we will adopt a simple approach, and assume
that the length of time a process spends in iowait is fixed, and this time is specified
as the value of a class variable IOWaitTime. There is no corresponding input
record.
exit this event will also be generated by the scheduler, when the total execution time
of the process (p.time) has been used up. There is no input event record for
exit.
That implementation used the simple 5-state model of process states, which only has a single
wait or blocked state. Consider what would be needed to alter the simulation if the Unix-style
suspend state is introduced, where a process may be suspended (removed from memory) to make
room for additional processes.
i) Draw a state diagram for processes in this new context.
Answer: 5 state model, plus 2 new states suspend.ready, suspend.waiting (2
marks for each state and associated edges)
[4 marks]
ii) Explain how the event model must change.
Answer: need to add edges: suspend (from ready to suspend.ready, run-
ning to suspend.ready, and waiting to suspend.waiting), restore (from sus-
pend.ready to ready and suspend.waiting to waiting), and IOEvent (from
suspend.waiting to suspend.ready).
[4 marks]
iii) Define the new events that must be added to the list above. Include any necessary param-
eters.
Answer: as defined above. IOEvent must have as parameter the event that
occurred.
[4 marks]
b) Calculate how much disk space (in sectors, tracks and surfaces) will be required to store 336,000
140-byte logical records if the disk is fixed sector with 1024 bytes/sector, with 96 sectors/track,
Page 13 of 18
100 tracks per surface, and 8 usable surfaces. Ignore any file header record(s) and track indices,
and assume that records cannot span two sectors.
Answer: Each sector can hold 7 logical records (7 x 140 = 980 bytes). The required
number of sectors is 336,000/7 = 48,000 sectors. This requires 48,000/96 = 500
tracks, which in turn requires 500/100 = 5 surfaces.
[4 marks]
c) Consider the same disk system as in the previous question, and assume that the disk rotates at
360rpm. A processor reads one sector from disk using interrupt-driven I/O, with one interrupt
per byte. If it takes 1.0µs to process each interrupt, what percentage of the time will the processor
spend handling I/O (disregard seek time)?
Answer:
There are 1024 bytes/sector. Since each byte generates an interrupt, there are 1024
interrupts. Total interrupt processing time = 1.0 × 1024 = 1024µs. The time to
read one sector is:
(60sec/min)/(360rev/min)/(96sectors/track) = 0.001736sec = 1736µs
Percentage of time processor spends handling I/O:
(100)× (1024/1736) = 59%
[4 marks]
Page 14 of 18
5)
a) Write a short program fragment (in any language) that defines the semantics (meaning) of the
Test and Set instruction.
Answer:
def TestAndSet(v):
ret = v.value
if (ret == 0): v.value = 1
return ret
2 marks for returning old value, 1 mark for setting variable, 2 marks for identifying
that parameter must be pass-by-reference. Note that the if is not essential, but is
included by analogy with the Compare and Swap implementation.
[5 marks]
b) Why can’t you use a Test and Set instruction in place of a binary semaphore? Explain what
additional semantics are required.
Answer: A binary semaphore requires either a busy wait (deprecated) or a blocking
wait, semantics not provided directly in the Test and Set. (The advantage of a
binary semaphore is that it does not require an arbitrary length queue of processes
waiting on the semaphore.)
(5 marks for blocking wait or explanation of why busy wait is deprecated, 3 marks
for just busy wait. 1 bonus mark for explanation of binary semaphore.)
[5 marks]
c) Write a short program fragment (in any language) that defines the semantics of the unblocking
signal(semaphore) operation, and calls the test and set operation defined in part a) above. You
may assume a primitive instruction “block” or “ready” that blocks/readies a given process.
Answer:
mutex=0
def signal(semaphore):
if semaphore.value == 0: return
while TestAndSet(mutex) == 0: pass
ready(semaphore.this_process)
semaphore.value=0
mutex=0
(1 mark for the semaphore parameter, 1 mark for identifying null semaphore, 1
mark for the mutex with TestAndSet conditional, 1 mark for readying the blocked
process, 1 mark releasing the semaphore.
[5 marks]
d) What is the difference between deadlock prevention, deadlock avoidance, and deadlock detection?
Answer: prevention: Ensuring that at least one of the four conditions for deadlock
never holds; (2 marks)
avoidance: Ensuring that processes never enter the “unsafe” regions of resource
allocation; (2 marks)
detection: Allowing deadlock to occur, and then recovering from the deadlock. (1
mark)
[5 marks]
Page 15 of 18
6)
a) Assuming that passwords are selected from four-character combinations of 26 alphabetic charac-
ters. Assume that an adversary is able to attempt passwords at a rate of one a second.
i) Assuming no feedback to the adversary until each attempt has been completed, what is
the expected time to discover the password?
Answer: T = 26
4
2 seconds = 63.5 hours
[3 marks]
ii) Assuming feedback to the adversary flagging an error as each incorrect character is entered,
what is the expected time to discover the correct password?
Answer: Expect 13 tries for each digit. T = 13 4 = 52 seconds.
[3 marks]
iii) Assuming that the username is a one to eight character alphabetic string, unknown to the
adversary, and that no feedback is given until both username and password are entered,
what is the expected time to discover a correct combination?
Answer:
∑8
n=1 26
n × 2642 = 217180147132 × 228488 ≈ 5 × 1016 seconds ≈
1.5 billion years! Note that approximate answers (to at least correct order of
magnitude) are accepted.
[3 marks]
iv) What inference do you draw from these calculations?
Answer: Keeping user names hidden (as much as possible) greatly improves
username/password security.
[3 marks]
Page 16 of 18
b) UNIX treats file directories in the same fashion as files; that is, both are defined by the same
type of file structure, called an i-node. As with files, directories include a 9-bit protection string.
i) Explain the interpretation of the 9-bit protection string, for both files and directories.
Answer: There are three groups of three bits, where the groups are user (owner
of file/directory), group (user is member of a group), all (all users in the sys-
tem). In each group, the bits mean read permission (search for directories),
write permission, and execute permission (lookup for directories)
[3 marks]
ii) Explain the meaning of the octal protection string of 644 for a file, and 730 for a directory.
Answer: The file can be read or written by the user, but only read by group
members or other users. The directory can be searched, written and looked
up by the user, but only written or looked up by group members. Other
users have no access.
[3 marks]
iii) In this example, how might the contents of the file be compromised from the user’s point
of view?
Answer: Suppose that the directory d and the file f have the same owner and
group and that f contains the text something. Disregarding the superuser,
no one besides the owner of f can change its contents can change its contents,
because only the owner has write permission. However, anyone in the owner’s
group has write permission for d, so that any such person can remove f from
d and install a different version, which for most purposes is the equivalent of
being able to modify f.
[2 marks]
END OF EXAMINATION QUESTIONS
Page 17 of 18