Exam 1: MidtermComments and Solutions
Part of
the homework for 22C:112, Spring 2009
|
Mean = 4.30
Median = 4.0 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____________________________
0 . 1 . 2 . 3 . 4 . 5 . 6 . 7 . 8 . 9 . 10. 11. 12. 13. 14. 15
bad | typical | good
1 #!/bin/tcsh 2 # examscript -- a shell script for the exam 3 @ number = 1 4 @ argc = $#argv 5 while ( $number <= $argc ) 6 echo \$argv\[$number\] = $argv[$number] 7 @ number = $number + 1 8 end
a) Which line or lines in this shell script probably involve the shell launching some application.
Line 6, the echo command. All the others are builtins. To the shell, line 1 is a comment. To the execve() that launched the shell, line 1 means something, but that is irrelevant to this question.
18 did well here. 4 referred to line 1 only, earning no credit.
b) Noting that the backslash character suppresses special interpretation of the following character during command line parsing and is not included in the argument, what output do you expect from the command
./examscript parameter list
$argv[1] = parameter $argv[2] = list8 did well here, 6 got most of the credit but failed to understand the effect of backslash quoting. 13 more got some credit for understanding that the words parameter and list would be output in some form.
c) Why is it "@ number" on the left-hand side of this shell's assignment operator but "$number" on the right. Wouldn't it have been nicer if the shell allowed "$number=$number?" Your answer should use what you know about the internal mechanisms of the shell to explain what forced the authors into the awkward notation.
To the shell, @ is a command. Its first argument is the text of a variable name, its second argument is a mandatory equals sign, and its arguments after that are component symbols of an expression to be evaluated. In contrast, the $, wherever it occurs, causes the immediately folloing string to be used as a variable name and replaced with the textual representation of that variable name, even before the command is identified.
A programmer may, of course, imagine that the @ signifies something like what programming language theorists sometimes call an lvalue while the $ signifies an rvalue but this is merely a syntactic observation and has nothing to do with the mechanisms inside the shell that lead to the use of this notation.
4 students came close to the core elements of the above answer, without quite getting there, earning more than half credit. The majority made no reference to the internal mechanisms of the shell but earned a bit of credit for discussing some variant of the lvalue vs rvalue distinction.
Note that the C language confuses arrays with pointers to arrays, but an assembly language programmer would know that the parameters are actually pointers to the arrays and not the arrays themselves.
Note, independently of the above, that programs running on Unix-like systems typically have three data segments, a code segment that is, if possible, protected so that only read and execute operations are legal on code, plus a read-write static segment for statically allocated global variables, plus a read-write stack segment for activation records containing local variables. In some computer architectures, it would be quite sensible to allocate one index register to point to the base of each of these segments.
a) Explain why execve() must copy the arrays pointed to by argv and envp, as well as all of the strings pointed to by both arrays.
The stack and static segments provided by the caller of execve() are discarded or overwritten as the result of the call, so anything in variables in those segments will be lost unless it is copied.
1 did well. 2 got more than half credit for suggesting that they were copied to preserve them from damage, but failed to disclose the threat. 4 earned a bit of credit for saying that they needed to be preserved during fork(), even though the question (to this point) had nothing to do with forking.
b) Where should execve() put the copy it makes?
Given that there are 3 segments (stack, static and code), we can use a process of elimination. First, the code is constant and cannot change from one use of a program to the next. Therefore, these copies cannot go there. Second, the data structures to be copied are variable sized. Therefore, they cannot go into any fixed-size space in the static segment. They must therefore go into a variable-sized slot somewhere. The one obvious slot is the base of the stack, under the activation record for the main program. This works. The other slot, less obvious because we have yet to discuss the mechanisms, is on the heap. This works too.
6 suggested the base of the stack and 2 more suggested the heap. 3 earned half credit for saying that the copies go before the first location used by execve(), with no hint about which memory segment.
c) When a program does a fork() operation, one or more memory segments must be copied. Assume intelligent use of indexing, so that copying is minimized. Which segments must be copied?
Intelligent use of indexing lets us do something like assign one index register to point to the base of the static segment and another to point to the base of the code segment, so all "static" memory references from within the code are indexed off these registers. As a result, there is no need to change the code segment for the child of the fork. Therefore, the only segments that must be copied are those containing varialbes, the static segment and the stack segment.
8 suggested both the static and stack segment. 4 got half credit for mentioning only the stack segment, 1 got half credit for mentioning only the static segment, and 4 got half credit for saying that all segments needed to be copied. 3 more had vague answers that seemed worthy of half credit.
To link two object files using this object code, the contents of the two files are simply concatenated.
a) While loading the code of a program in the code segment, a machine instruction is loaded that uses direct addressing to reference a variable in the static segment. Explain why loading this instruction is likely to take two load records in the above scheme.
An instruction directly addressing a variable in the static segment will need two load records, one for the opcode (an absolute value, that is, with a base of zero and an offset that is the opcode's value), and one for the operand (the base is the address of the start of the static segment and the offset is the displacement into the static segment).
2 did well here, 2 explained the opcode only, 2 explained the operand only. Many students wrote at length about a completely different division, that between base and offset, but both of these were defined as components of the loaded values, and each load record is defined to contain a load value, which implies that each load record has both components in a single record. Many students wrote at length about the fetch-execute cycle, explaining how the load instruciton works instead of explaining how an instruction is loaded in memory.
b) Some key features are missing from the above description of the object code. Linking object files by concatenation requires one missing feature, using the loader to initialize initial values of variables in the static segment requires another missing feature. Identify the missing features.
Key feature 1: Linking by concatenation requires some way to change the relocation base at the start of each successive object file that is concatenated.
Key feature 2: Initializing variables in the statis segment requires a way to change the loader's location counter so it loads the next load record in the static segment. The same or a similar mechanism is needed to switch back to the code segment after doing the initialization.
Nobody gave both parts of this answer. 4 got full credit and 2 more got partial credit for changing the relocation base, while 1 got partial credit for changing the location counter.
For this question, consider two cases, first, the device is one of several asynchronous serial devices such as keyboard or mouse. Second, consider a file, where that file is implemented on one of several disk drives. Our focus here is on the data structures that sit between the user program and the device.
a) The parameter fd is a small integer. Describe how the read() system call uses fd to call the appropriate top-level device-dependent routine operating on an open-file data structure.
/* C */ read(int fd, char * buf, int len) { (fdtable[fd]->read)(fdtable[fd], buf, len) } // C++ -- exactly equivalent to the above read(int fd, char * buf, int len) { fdtable[fd].read(buf, len) }In other words, the file descriptor fd is an index into a table of pointers to open file data structures. One field of this data structure, called read above, is a pointer to the code for reading from that specific file. This is called with the file data structure as a parameter.
3 did well here, 10 got partial credit for saying true things that were were not convincing proof of understanding.
b) In the case of asynchronous serial devices, the open-file data structure probably contains a reference to a device data structure. What information would you place in the device data structure for one of a number of similar serial devices?
We are given that there are several identical asynchronous device interfaces. Because they are identical, they can use identically the same code, which is to say, they are the same class. The device data structure must contain everything needed to distinguish one such device from another, for example, the device register addresses for the specific device and pointers to the queues used by that device.
2 did well here, 13 earned partial credit by giving at least one part of the answer. A surprising number of students discussed the internal structure of device registers, earning no credit.
c) In the case of the disk file, the open file data structure probably contains additional information in addition to a reference to a device data structure. Describe this additional information.
We need to know the file position, and we need to know where this file is on disk. In a Unix like system, the were information is all encoded in an i-node.
17 students got half credit for listing one correct piece of information, in most cases, they listed file size, but a few listed file position.
void enqueue(queue * q, char ch) {
q->buffer[q->tail] = ch;
q->tail = q->tail + 1;
if (q->tail >= q->size) q->tail = 0;
}
char dequeue(queue * q) {
int ch = q->buffer[q->head];
q->head = q->head + 1;
if (q->head >= q->size) q->head = 0;
return ch;
}
a) Given a queue pointer q, give boolean expressions for the queue full and queue empty conditions that are compatible with the above code.
empty = q->tail == q->head; full = (q->tail + 1 == q->head) % q->size; full = (q->tail + 1 == q->head) || ( (q->head == 0) && (q->tail + 1 == q->size) );Two solutions for the full condition are given because the mod operator may be slow, which might be why the original code avoided using it.
4 did well, 1 more gave just the full condition, and 3 more gave just the empty condition. 9 faced penalties for forgetting about the mod operation (or its equivalent).
1 student noticed that the code contained an error, corrected above. (queue was used in the code where q should have been used.) This seems to have had no impact on anyone else.
b) Are there any critical sections in this code where interrupts should be disabled in order to prevent trougle? If so, identify them. If not, explain why not.
The code given contains no critical sections, if we assume a single-threaded application.
4 got this correct. The remainder did not.
c) When should the interrupt handler turn off the device interrupt enable bit?
Note that this question refers to the device interrupt enable bit, not the global interrupt enable bit. The device interrupt enable bit should be turned off when the input queue fills up -- that is, after enqueue, it is full.
3 got this right. 4 got partial credit for correct answers for an output device (the example from class). 7 got partial credit for incorrect answers that correctly described how interrupts need to be globally disable during the interrupt service routine until the interrupt request has been retracted in order to prevent infinite loops in the interrupt mechanism.
d) When should the user-side routine of the driver turn on the device interrupt enable bit?
Note that this question refers to the device interrupt enable bit, not the global interrupt enable bit. The user side should re-enable the interrupts after every dequeue from the input queue, since the dequeue guarantees that there is now space for at least one character in the queue.
5 got this right. 5 more earned at least half for essentially correct answers that were somewhat confused, and 2 more reversed the directio of input/output but were correct for an output operation. Too many students seem to have thought that parts b) c) and d) were all different facets of the same question.