CS:3620, Exam 1 Solutions, Spring 2018

Note: The midterm exam grade distribution includes all students who took the exam. The remaining distributions exclude the few students who missed more half or more of the times that attendance was taken in this class. The midterm grade scale is a bit harsh in order to give ample warning to those in need of warnings.

Background: Here is a shell script from the solution distributed to Homework 2:

#!/bin/tcsh
# fib i  -- outputs the i'th Fibonacci number
if ($1 < 2) then
    echo $1
else
    @ iminus1 = $1 - 1
    @ iminus2 = $1 - 2
    @ result = `fib $iminus1` + `fib $iminus2`
    echo $result
endif

a) What Unix/Linux/MacOS kernel call interprets the first line of this script?

__execve()_____________________________________________________________

1/7 got this right, 1/5 earned partial credit for suggesting tcsh which is not a kernel call but is at least relevant to the first line. 1/16 earned even less credit for suggesting bash which is a different shell, but at least relevant to the concept that the first line names a shell.

Among wrong answers, the most popular was getenv(), mentioned by 1/11. The only other wrong answers mentioned by more than one student were fgets() and the word compiler. None of these are kernel calls, and the lack of a pattern in the wrong answers suggested wild guessing.

By way of explanation, on Unix or Linux, whether you launch a program from within your own application or from within a shell, the actual launch is done by execve(), and this interprets the first bytes of the file to to see if it should loads and runs an object file or launch an interpreter. The magic number at the head of the file determines which. In this case, the "#!" is the magic number telling execve() to read the first line of the file as the file name of the interpreter it should load and run.

b) What do the back-quotes in `fib $iminus1` do?

__the quoted text is treated as a shell command________________________

__and the output of that command replaces the text and quote marks_____

1/22 got this right. 2/7 earned half credit for saying that the quote marks cause the quoted material to be interpreted as a shell command, without saying anything about where the output goes.

3/8 earned a little credit for saying something involving a recursive call. These students were distracted by the larger context and failed to focus on the role of the notation itself.

c) What can you conclude about the user's $PATH from the fact that the script reads `fib $iminus1` instead of `./fib $iminus1`?

__$PATH ended with :. or $PATH included the directory holding fib______

1/2 earned full credit. This was a relatively easy question.

Wrong answers frequently involved strangely garbled terminology, for example, the suggestion that fib was itself part of the path, or that the path is itself in some directory. The oddest wrong answers asserted that the shell somehow knew the name of the file it was reading and made a special case for recursive shell scripts.

Background: Here is part of the Makefile for mush from the posted solution MP3:

getcommand.o:   getcommand.c globals.h
	cc -c getcommand.c

a) This says that you need to remake getcommand.o if what files have changed since getcommand.o was last updated?

__getcommand.c or globals.h_____(from line 1 of what's given above)____

5/8 got this. 1/7 omitted globals.h, 1/22 omitted getcommand.h. A few added extra file names to the list or said something about variables being changed instead of focusing on the file names. Few earned no credit.

b) If getcommand.o needs to be remade, what shell command is run?

__cc -c getcommand.c____________(from line 2 of what's given above)____

4/7 got this. 1/11 earned partial credit for answers that were similar to the shell command that is in the make file, but with inexplicable differences such as using gcc instead of the cc that is explicitly given. Another category of strange answer earning just a bit of credit was some variant on make; yes, there is implicit recursion in the way make works, but a makefile is full of explicit shell commands and the recursion in make is unlikely to extend to the point of issuing shell commands to call itself when it can just as easily do recursive calls internally in its own code.

Very few earned no credit.

Background: Here is some code from launch() in the solution distributed for MP2

/* built-in commands */
if (argv[0] == NULL) {
	/* we need this to prevent strcmp() from segmentation fault */
	return;
}
if (!strcmp( argv[0], "exit" )) {
	/* this could get exit succes/failure code from argv[1] */
	exit( EXIT_SUCCESS );
}

a) What input to mush could you type to causes argv[0] to be null?

__A blank or empty input line__________________________________________

_______________________________________________________________________

4/9 got this. 1/7 earned strong partial credit for saying space, without saying "nothing but spaces" or some qualifier to indicate that it's not just a leading space or an embedded space in a line that creates this condition. Vague answers such as "any control character like newline" earned some credit for another 1/22.

b) As written, mush does not support comments. What code would you add to the above to make it support shell comments starting with #?

__if (argv[0][0] == '#') return;_______________________________________

_______________________________________________________________________

_______________________________________________________________________

2/9 got this.

There were numerous normal programming errors leading to small deductions. 1/5 used strcmp() to recognize the string "#". This would require a space after the pound sign introducing a comment. 1/6 forgot the second subscript [0]. 1/8 used "#" when they should have used '#'.

More serious errors included the 1/11 who used a while loop instead of an if statement, even more seriously 1/3 who wrote bizarre code instead of the return statement. In many cases, this turned the comment into some kind of echo command. In other cases, it seemed to involve bulk editing of argv for unclear purposes.

Background: In homework 4, this code was discussed in the context of the putcom(cp,c) function of a crude serial-port driver:

while ((inp( cp->comstatus ) & TxDE) == 0) /* empty loop body */;
outp( cp->comdata, c );

a) What sets the TxDE bit in the device status register?

__The device sets it when it's done transmitting the previous byte_____

_______________________________________________________________________

1/8 got this. A very few students flipped parts a) and b) for a little credit, and one earned partial credit for a vague answer. The rest earned no credit.

By way of explanation, the TxDE bit means "Transmitter Data register is Empty" and this bit was discussed in our lecture and the readings on polling for simple low-performance I/O.

b) What resets the TxDE bit in the device status register?

__The act of putting a new character in the device data register:______

__outp( cp->comdata, ... );____________________________________________

1/4 got this. 1/11 gave vague answers that hinted at this, while 1/6 said just outp(), possibly referring to the line above but with no mention of the comdata devie register, and therefore earning only a small amount of credit.

Both parts of this question were essentially asking about device interface hardware and how it interacts with software. Most offerings of introductory computer architecture courses have at least some discussion of this.

Background: Consider a disk with 8 cylinders numbered 0 to 7. While it was finishing a number of I/O requests on cylinder 0, requests arrived for I/O to cylinders 3, 4, 0, 6, 5, 6 and 4, in that order.

a) If the disk driver is written to serve the I/O requests in FIFO order, how far will the disk heads travel radially to serve these I/O requests. (Moving from cylinder 0 to 1 is a distance of one step).

__18___from the sequence 0 3 4 0 6 5 6 4_______________________________

2/5 got this and an additional 1/11 made clerical errors that earned partial credit.

I had great difficulty finding any patterns in the wrong answers, but most of them involved dumbers that were at least twice the answer given here. Perhaps they were counting disk revolutions or something like that.

b) If the disk driver is written to serve the I/O requests in elevator order, how far will the disk heads travel radially to serve these I/O requests.

__6____from the sequence 0 0 3 4 4 5 6 6_______________________________

1/2 did well here, and an additional 1/11 made clerical errors for partial credit.

Background: The interrupt service routine for a serial communications input port (without echo) might look like this written in C:

void com1isr() {
        int stat = inp( COM1LSR );
	if (stat & RxRDY)
		enqueue( com1inqueue, inp( COM1DATA ) );
	if (full( com1inqueue ))
		outp( COM1IER, inp( COM1IER ) & ~RxIE );    ***
}

a) The code that inputs and outputs the COM1IER device register above is a critical section, yet nothing in this code protects it. Why is it OK in this context to write unprotected critical sections?

__It is in an interrupt service routine where interrupts are___________

__disabled throughout, so it is already protected by its context.______

1/7 did well, and an additional 1/16 gave vague answers that earned partial credit.

Wrong answers generally indicated no understanding of what a critical section was or no understanding of the fact that the question referenced just one line of code above (marked with *** here). That line is a critical section because it reads, modifies and then writes the interrupt enable register.

Another problem was that it appears that many students did not understand the idiom for setting and clearing bits. This idiom is common to C, C++, Java and Python. Whenever you want to set or clear individual bits in a variable in these languages, you use some variant on this:

v = v & ~bits; clears all bits in v that are set in bits.

v = v | bits; sets all bits in v that are set in bits.

Usually, bits is a constant, but if you want to set or clear bit number n, you use (1<<n) for bits.

b) What code is responsible for undoing the changes made to the COM1IER device register made by the second if statement above?

__Every time the user dequeus from com1inqueue,________________________

__the RxIE bit is set to re-enable input interrupts____________________

1/8 got this and just one student earned partial credit.

It is clear that interrupts, queues, and I/O driver structure are new and difficult material!

Background: The array disk[DISKS] is an array of disk device interfaces, each holding SECTORS disk sectors numbered from 0 to SECTORS-1. The operations on disk device interface d are put(d,buf,sector) and get(d,buf,sector), where buf is a buffer in RAM and sector is a sector number on device d.

Here is partial code for a virtual device put() that outputs to device d that converts this array of disk devices into one big virtual device:

put(disk_device d, void * buf, int sector) {
	int n = 
	int s = 
        put( disk[n], buf, s )
}

a) Give the code for computing n and s

__n = sector / SECTORS_________________________________________________

__s = sector % SECTORS_________________________________________________

1/11 got this right. 3/8 gave nonsense answers for finding the physical disk number n while earning partial credit by giving s as some function of sector. Of these, most omitted the % SECTORS.

It is clear that most of the class did not understand the whole idea of the question, taking a large number of physical disks and using them to make one big virtual disk. Some of the wrong answers involved very strange code, things like loops even.

b) If we want to allow the possibility of multipple virtual disks constructed like this, where should the array disk[] be stored?

__put disk[] as a field of the disk_device data structure______________

_______________________________________________________________________

Only a few students earned even partial credit. A number of answers suggested strange multidimensional arrays, or just blow-off answers such as "in RAM". Of course the array is in RAM. That is where all data structures go, by default. Other answers seemed desparate to connect this discussion with file systems by somehow putting some kind of directory structure on disk.

Exam 1: Midterm

Solutions and Commentary

Grade Distributions

Midterm Exam

Machine Problems 1 — 3

Homeworks 1 — 6

Overall Scores

Solutions and Commentary