Exam 1: Midterm

Solutions and C

Part of the homework for 22C:112, Spring 2011
by Douglas W. Jones
THE UNIVERSITY OF IOWA Department of Computer Science

Grade Distributions

Exam

mean   = 6.67
median = 7.2                     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

Homeworks 1 to 5

mean   = 11.35
median = 12.2                    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

Machine Problem 1

             X
             X
             X
             X         Mean   = 2.89
             X         Median = 2.5
             X
             X
             X
             X
             X
             X
             X
             X
   X         X     X
___X_________X_____X_X_X_
  0 . 1 . 2 . 3 . 4 . 5

Overall

                                     X
mean   = 20.00                       X
median = 19.3                        X           X
                                     X X         X   X X
_________X_____________X_X_________X_X_X_X_______X_X_X_X_X_X_____
  0 . 2 . 4 . 6 . 8 . 10. 12. 14. 16. 18. 20. 22. 24. 26. 28. 30
         F             D D

Solutions

Background: Consider this shell script:
```
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
```
Also consider this partial alternative.
```
5    mywhile ( $number <= $argc ) <<end
6            echo \$argv\[$number\] = $argv[$number]
7            @ number = $number + 1
8    end
```
The mywhile program is relatively straightforward, given that you can evaluate the expression passed as command line arguments. The <<end makes the shell pass everything up to the line containing end as standard input to mywhile. Then, mywhile repeatedly passes this standard input to tcsh until the expression is false.
a) What prevents the mywhile version of this script from working, ever, despite the fact that mywhile itself works perfectly.

The terminating condition, ( $number <= $argc ) has dollar-sign substitution applied just once, before the mywhile application is launched. As a result, mywhile never can see any changes to the value of the terminating expression.
Also, it is impossible for the loop body, executing in a subshell, to have side effects that change environment variables in the shell that contains the while loop.
5 gave one or another good reason. 13 gave reasons that suggested major misunderstandings. Partial credit was rare.

b) Why do we need an @ command? For example, why would it be more difficult to write a shell that allowed this:
```
7            $number = $number + 1
```
In the Unix shells, dollar-sign substitution is done first, before the command name or arguments are examined to see what to do with the line. As a result, the suggested "more civilized" form of the line might end up looking like 5 = 5 + 1 by the time the shell looked at the syntax to see that it was an assignment.
Only 1 gave a really good answer, and 8 earned partial credit. The rest did poorly, giving answers that either made no sense or made sense in an alternate universe where shell scripts were evaluated by something akin to a real compiler.

c) Why so many spaces? For example, why not write the following:
```
5    while   ($number<=$argc)
```
The shell uses spaces to delimit elements of the argument vector, argv, and the while command takes advantage of this so that it doesn't need to do any difficult work parsing its argument. With the spaces removed, the while command sees the entire argument as one lump.
12 did well here, and 4 more earned partial credit. Among those who earned no credit, an alarming number suggested that the reason for the spaces had something to do with programming style, holding that they were there for readability.
Background: Programs running on Unix-like systems typically have three segments: a read-execute only code segment, a read-write static segment and a read-write stack segment. Consider the following code:
```
#include <stdio.h>
char * s = "Hello world!\n"

int main() {
        char ch;
        for (;;) {
                ch = *s;
                if (ch == '\0') break;
                putchar(s[i]);
        }
}
```
a) The identifiers in the above code are s, main and ch. For each identifier, what segment ends up holding the associated value. For full credit, identify the tricky some of these raise.
s is a global variable, therefore in the static segment.
main names a piece of code, therefore in the code segment.
ch is a local variable, therefore in the stack segment.
Tricky issues: s refers to a string that could be in the code segment (it is constant), but s is a variable. main can legally be implemented as a pointer to the code, and as such, it could be a pointer in the static segment.
6 did perfectly. 13 more had serious problems with s, 3 more had serious problems with main and 6 more had serious problems with ch. Everyone got at least some credit here.
Just for fun, to illustrate how horrible C really is, here is a legal C program that actually works unless you pass more than about 20 command line arguments to it:
```
#include 
#include 
void main(int j) {
  printf("%d\n", j);
  (main + (exit - main)*(j/20))(j+1);
}
```
b) The constants in the above code are "Hello world!\n", and '\0' For each constant, what segment ends up holding the value. Clearly describe any tricky issues that arise.
"Hello world!\n" can be stored in the static segment or in the code segment depending on the compiler. '\0' may be stored in the static segment or the code segment, but an optimizing compiler is likely to use immediate operands in machine instructions or even just test the Z condition code instead of explicitly storing this constant anywhere.
11 did well, 4 earned no credit.

c) Which of the addresses of variables or constants in this code might require relocation when the object file holding this code is linked with other object files to make the executable. The right answer depends on how you answered a and b.

Any items stored in the static or code segments will have their load addresses shifted depending on what else is linked into those segments. Storage in the stack segment is allocated at run-time and is therefore not subject to relocation by the linker.
7 did well, 4 earned no credit.
Background: Consider the path take by data output to a printer.
1. A C program calls fputc( ch, stdout )
2. which calls write( 1, &ch, 1 )
3. which calls enqueue( print_q, ch )
4. which leads to calling out( ch, print_data_reg )
a) What system layer contains the implementation of each function called above?

fputc is midleware.
write is an operating system interface.
enqueue is in the user side of the I/O driver.
out is the interface to the device hardware.
8 did well, 5 earned no credit.

b) What system layer calls each of the above functions?

fputc is called by the applicaiton.
write is called by middleware (but applications may call it).
enqueue is called by the system or by user-side driver code.
out is called by the driver's interrupt service routine.
7 did well here, 6 earned no credit.
Background: Consider a computer system with no memory protection, but with the Unix system call model for input/output. read(fd,buf,len) uses fd to locate the device to be used. Eventually, the user's call to read() leads to a call to a system routine read_devclass(dev,buf,len), where dev=open_file_table[fd].ofile. Note that read_devclass is specific to a specific device class and applied to a specific device.
a) Each entry in open_file_table has several fields. One of them is ofile, the pointer to an open file data structure. What other field would be needed in each entry?

Access permissions (read or write) definitely go here. There is no good reason to put anything else here, although you could put the device type here without doing harm.
Nobody did perfectly here, and 15 earned no credit. Partial credit was offered to those who put harmless information in the table. In some cases, the problem appears to have been a serious misunderstanding of the difference between "accessible from the table by following the pointer to the open file object" and "directly included in the table". I am beginning to believe that many students do not understand pointers.

b) Where would the read() function look to find out which read_devclass() subroutine to call?
The data structure pointed to by the ofile field, which is also the local variable dev inside the read routine.
4 did well, 9 earned no credit. The most popular answer earning partial credit involved storing the file type in the open file table.
Here is what could be the entire code for read():
```
int read( int fd, char * buf, int len ) {
        struct open_file * dev = open_file_table[fd].ofile;
        if (open_file_table[fd].rights & O_RDONLY) {
                return (dev->read_method)( dev, buf, len );
        } else {
                errno = EBADF;
                return -1;
        }
}
```
c) Suppose fd refers to an open disk file on a system using classic Unix-style i-nodes. Obviously, when the file is opened, the i-node is read into main memory. Where, in relation to the different data structures described above, would the i-node be stored.

The i-node would be read into the open file object or into memory pointed to by the open file object.
8 did well here, 9 earned no credit. Answers such as "in RAM" were given no credit, since that much was given (assuming that RAM and main memory are synonyms). Answers such as "in the i-table" were given no credit since the i-table is on disk, by definition, and the problem statement already said that it was copied into main memory somewhere.
Background: Consider the following code implementing a disk queue request queue. There may be several small errors here, but they are not the subject of this question.
```
 1 void enqueue(diskqueue * q, request * r) { /* called by user code */
 2         cylinderqueue * c = q->a[r->cylinder];
 3         r->next = NULL;
 4         if (c == NULL) {
 5                 c = newcylinderequeue();
 6                 c->head = r;
 7                 c->tail = r;
 8                 q->a[r->cylinder] = c;
 9         } else {
10                 c->tail->next = r;
11                 c->tail = r;
12         }
13 }
14 request * dequeue(diskqueue * q) { /* called from an int. svc. routine */
15         cylinderqueue * c = q->currentqueue;
16         request * r;
17         if (c == NULL) {
18                 int cyl = q->current;
19                 do {
20                         cyl = cyl + 1
21                         if (cyl > q->maxcyls) cyl = 0;
22                         c = q->a[r->cylinder];
23                 } while ((c == NULL) && (cyl != q->current));
24                 q->a[r->cylinder] = NULL;
25                 if (c == NULL) return NULL;
26                 q->currentqueue = c;
27                 q->current = cyl;
28         }
29         r = c->head;
30         c->head = r->next;
31         if (c->head == NULL) {
32                disposecylinderequeue( c );
33                q->currentqueue = NULL;
34         }
35         return r;
36 }
```
a) What scheduling policy does this code implement, with respect to disk cylindeers? Briefly, what line or lines allowed you to identify the policy?

Lines 19 to 23 search q->a[] for a non-null entry. This searh is done by incrementing the index (line 20) and wrapping back to zero when it reaches its maximum (line 21). Therefore, it is the unidirectional elevator algorithm.
7 did well here. 11 earned no credit. There was little partial credit. It is noteworthy that the queueing discipline within each cylinder in the code given is FIFO, but partial credit for this observation was only given if the answer clearly indicated that this applied only within one cylinder.
b) There is a critical section between lines 2 and 8. What line or lines of code must not interrupt this critical section? The problem lines are those that assign to data structures examined in the critical section. Assignments to local variables are harmless. If we ignore multithreaded user code, this leaves lines 24 and 30. Full credit was given for this much. 5 did well. 8 earned no credit. Partial credit was given for non-focused answers that included the lines in question. c) The interrupt handler should turn off the device interrupt enable bit in response to the value returned by dequeue. What value does dequeue return to tell the handler to do this? A return value of NULL. 12 did well here, 4 earned no credit. d) One part of the dequeue routine given here would not be desirable in an interrupt service routine. Identify it and explain why. The search loop in the dequeue routine could take a long time, and the general rule is that interrupt service routines should be very brief. 5 did well. 13 earned no credit.