Final Solutions and Comments
Part of
materials for 22C:50, Spring 2003
|
Median = 73.4 X
Mean = 70.4 X X X X
X X X X X X
X X X X X X X X X X X X X
_______X___________________X_X_____X_X___X_X_X_X_X_X_X_X_X_X_X_X_X_X_
.24 .28 .32 .36 .40 .44 .48 .52 .56 .60 .64 .68 .72 .76 .80 .84 .88 .
F D C B A
Median = 25.5 X
Mean = 25.2 X
X X
X X X
X X X X X X
X X X X X X X X X X X X
_____________X_X_X___X_X_X_X___X_X_X_X_X_X_X_X_X_X___X_____________
. 8 .10 .12 .14 .16 .18 .20 .22 .24 .26 .28 .30 .32 .34 .36 .38 .40
F D C B A
Median = 9.5 X
X X
X X X X X X
X X X X X X X X X X X X X X X
________X_X_____X_X_____X_X_X_X_X_X_X_X_X_X___X_X_X___X_X__________
. 2 . 3 . 4 . 5 . 6 . 7 . 8 . 9 .10 .11 .12 .13 .14 .15 .16 .17 .
INT SA INT SB SA: SB = #10
A Problem: Assume that the following EAL code is assembled, linked with ext.obj, and loaded. For each line in the following code that actually places a value in memory, identify the component of the programming system that is most likely to fix the final value.
(2.0) EXT SA ______________ 3 had nonblank answers here
EXT SB ______________ 3 had nonblank answers here
SC = 10 ______________ 8 had nonblank answers here
SD: ______________ 6 had nonblank answers here
W SA the loader relocates this external reference
1/3 got this, 2/3 said linker
W SB the linker resolves this external reference
4/5 got this, 1/5 said loader
W SC the assembler handles this absolute value
4/5 got this, 1/5 gave wrong answers
W SD the loader relocates this value
1/2 got this, 1/2 said assembler
W SC+SD the loader relocates this value
1/2 got this, 1/2 said assembler
Part A: Extending the EBNF grammar for MP5sh to support the && feature documented above, we'd have to add just one new rule and one new nonterminal name. Give that rule:
<script> ::= { <line> } <EOF>
<line> ::= # { <anything> } <EOL>
(0.8) <line> ::= <command> { && <command> } <EOL>
1/4 gave good answers, 1/2 left out the curly braces
or made other errors worthy of generous partial credit.
<command> ::= <progname> { <argument> } <EOL>
<progname> ::= <nonblankstring>
<argument> ::= <nonblankstring>
Part B: Obviously, adding support for && to your solution to MP5 requires a slightly more complex parser, because we added a production rule. Does it require changes to the lexical analyzer? If yes, what new lexeme type must be added?
(0.8) we need to recognize && as a lexeme.
over half understood this; another 1/5 had odd answers
worthy of partial credit. One gave C code and several
others gave equally odd answers.
Part C: Write a shell script using this feature that deletes the file f, then deletes the file g, but only if f was successfully deleted. Finally, your script should output success, but only if both deletions worked.
(0.8) rm f && rm g && echo success
1/4 gave essentially this answer, 1/4 missed the echo at
the end, and 1/5 mixed && notation with if-then.
Part D: You've been given the problem of writing an if program that can be called from any Unix shell. You'll have to write an expression evaluator. One major part of the language processing job, however, has already been almost completed by the program that called your program. What is it?
(0.8) lexical analysis
1/6 got this and a few more used the wrong terms but
clearly meant the right thing; 1/2 said parsing for
half credit.
Part E: Write code that outputs equality if 49 times 72 is the same as 56 times 63, using the built-in echo and your if commands, along with the features of the shell discussed in previous parts of this question:
(0.8) if 49 * 72 == 56 * 63 && echo equality
1/4 got this; 1/2 did not use && and clearly did
not understand how the user-written if command would work.
Your boss has just suggested that you write code for OASOS that allows a user program to open a disk file so that the open file becomes a segment of the program's virtual address space.
Part a: Your bosses proposal will work for large (and larger) files. What information do you copy into the page table entries for the segment that represents an open "larger file"?
(1.0) the disk addresses in the i-node become disk addresses
of pages of the segment representing the open file.
1/2 got this, 1/4 got partial credit.
Part b: This proposal has a near fatal flaw if it is applied to small files. What is the root cause of this flaw?
(1.0) the first 8 words of the i-node aren't part of the file,
so the sector holding the i-node can't be mapped into
the virtual address space.
1/4 got this, 1/4 got partial credit.
Part a: Suppose your program opens, as a segment, an object file holding the code for a function. Assume your program then executes a call instruction to the first location in that segment. The result is a complete failure! Your program bombs out with a "bus trap" error message. Why?
(1.0) Object code is not necessarily machine code! it
may need relocation and it may contain header information
that is not intended to be executed!
2 got this, 1/4 did well and 1/4 speculated in interesting
ways that were worth approximately half credit.
Part b: Your program builds a binary tree in a segment it shares with another program. Every time the other program tries to follow a pointer in this tree, it bombs out with a "bus trap" error message. Why?
(1.0) The shared segments must have been at different virtual
addresses in the different address spaces. Had they been
at the same address, at least some attempts to follow
pointers in the tree would have been successful!
1/4 did well, and over 1/4 got at least half credit.
The deallocate(addr,size) system service changes the markings on pages in the addressed range from valid-read-write, valid-read-only or invalid-but-allocated to totally-invalid.
Part a: What part of the system actually allocates page frames to user processes.
(1.0) the page fault handler
1/8 got this, over 1/2 got partial credit, mostly
by saying that the MMU does the allocation (it is
relevant, but generally, the MMU hardware does not
allocate anything!)
Part b: What system data structure does the allocate() service manipulate.
(1.0) the page table, as it marks pages that were totally-invalid
as invalid-but-allocated.
1/4 got this, over 1/2 got partial credit, many for
saying the heap (this allocate service needs no heap,
but yes, on many other systems, that would have been
the right answer).
Part c: The deallocate() service described above does one more thing for each page that was marked valid-read-only or valid-read-write. What thing?
(1.0) it reclaims the deallocated page frames!
1/3 got this and 1/3 got partial credit, mostly for
odd terminology that implied a decent understanding.
Part d: The set of system services given above is incomplete! You can infer that there is one more system service from the given set of states of pages. What must this service do?
(1.0) make_read_only() -- the background mentioned pages
marked valid-read-only but did not mention a service
that gives pages this marking.
1/4 got this, very few gave answers worth partial
credit.
Part a: Show the initial breakdown of the heap for the binary buddy system:
_____________________________________________________________
(1.0) | 2 | 4 | 8 | 16 |1|
|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|
50 60 70 80
1/8 gave this answer (the only correct answer!)
1/4 gave answers with the right block sizes but not
starting at "magic" addresses.
1/4 assumed a 30 word heap (the word inclusive was ignored).
Part b: Show the initial breakdown of the heap for the Fibonacci buddy system:
_____________________________________________________________
(1.0) | 21 | 8 | 2 |
|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|
50 60 70 80
1/4 gave correct answers (there are several).
1/4 created an initial heap with lots of smaller blocks.
1/4 had some blocks that weren't Fibonacci sizes.
Part a: What object is allocated on the heap of the user process?
(1.0) a stream object
1/6 gave this answer, while several confused the
object with its handle; a remarkable 1/3 said an
activation record, an odd answer to say the least.
Part b: How is this connected with an entry in the open file table of the process?
(1.0) it holds the Unix file descriptor, which is the
integer index of an entry in the open file table.
hardly anyone got this; 1/4 said "a pointer",
for partial credit; most described a nonexistant
connection from the open file table to the object
that uses that open file -- there is no connection
in that direction!
Part c: What object is allocated in the operating system kernel's heap?
(1.0) the open file object
1/8 got this; most nonblank answers were very odd.
Part d: How is the open file table entry connected to this kernel object?
(1.0) it contains a pointer to the object
1/4 got this, but there was little partial credit.