CS:3620, Exam 2 Solutions, Spring 2018

The statistics for all grade distributions shown here are based only on those who regularly attended classes, in conformance with the class policies announced at the start of the semester. A total of 10 students missed 10 or more classes and are not counted in the statistics. These 10 students are marked with o in the score histograms here.

Final Exam

Midterm plus Final

Machine Problems

Homework (Top 10 of 12 assignments)

Total Scores

In the above grade distribution, students earning an A generally were able to do well in 5 or more of the 6 machine problems and passed significant functional tests on all of them.

Those earning a B did reasonably on 3 to 5 machine problems and had as many as 2 on which their code did not pass any functional tests.

Those earning a C were unlikely to do well on more than 3 machine problems and typically had from 1 to 4 on which their code did not pass any functional tests.

Solutions and Commentary

Name: ________________________________________________ ID Number: ___________

Please write legibly in the space provided. Illegible and verbose answers will be penalized! The expected answers are short. This exam is open-notes, closed neighbor! This exam is worth 25 points; allocate 4 minutes per point. Each part of each question is worth one point.

Background: Look at the code for fibstub() attached at the end of this exam (feel free to carefully rip that page free from the rest of the exam). This stub allows a C program to call a "function" written as a shell script, for example, the fib script from homework 2 and the midterm. Comments in fibstub() label each line with a letter. Use those letters to answer the following:

A matter of definition: In the following, a line of code is required for some goal if deleting that line would cause that goal not to be satisfied.

This problem is strongly related to MP6; students who have solved that problem should find all of the code at the end of the exam to be familiar.

One puzzle emerged in grading this question: Despite the "line is (lines are)" wording in the questions, intended to invite students to list one or more lines, many students only gave one letter in answer to each line, as if it was a multiple-choice question.

a) Which line(s) of fibstub() is (are) required to transfer control to the fib script?

__p__s_________________________________________________________________

1/7 did well, 1/4 said just s. Popular wrong answers (1/12 each) included e and f. 1/12 earned no credit.

b) Which line is (lines are) required in order to allow fibstub() to regain control after the fib script terminates.

__e__j__k_(t)_u________________________________________________________

Nobody did perfectly, but 1/4 included j in their answer, and 1/5 included e. Popular wrong answers (1/12 each) included g o and i. 1/7 earned no credit.

Note, under normal circumstances, line t is never executed, but it is part of the "programming template" for the fork-join operation coded in C on a Unix/Linux system, so it was allowed as an optional part of the answer. 1/10 included it in their answers.

c) Which line is (lines are) required to pass the value of parm to the fib script?

__l_(p)_q_(r)_s________________________________________________________

1/12 earned full credit. 1/4 listed q and s, critical parts of the answer. 1/10 earned no credit.

The only popular wrong answer was n, given by 1/12, a key part of getting the result back but a line that has nothing to do with passing any parameters.

Note, lines p and r also set elements of argv and arguments can be made for including both or omitting either, so they were optional. Line l is obviously required, since assignment to a non-declared variable doesn't work; nonetheless, this was only granted reduced credit.

d) Which line is (lines are) required get the result of the fib script and return it to the caller of fibstub()?

__b__c__d__f_(g)_h_(i__m)_n_(o__u)_v___________________________________

Nobody earned full credit (the popular pattern of just listing one line clearly paid a part here). 1/12 gave c, 1/12 gave d, 1/6 gave f, 1/3 gave h, 1/8 gave n, and 1/4 gave v.

Lines g, i, m, o and u were not penalized because they naturally go with the creation of the pipe to get the result back, although they are not formally required to get the result from the pipe.

The only popular wrong answer was s, given by 1/12, since the context strongly suggests that the fib script is already being called, and the focus is on getting a result from that call. 1/8 earned no credit.

e) Which line is (lines are) required only to allow fibstub() to be called repeatedly?

__g__i_________________________________________________________________

This was apparently a hard question, nobody earned full credit and only 1/24 earned partial credit, listing either line g or i. Each time the parent process creates a pipe, it uses up 2 slots in its open-file table. If it does not close the corresponding file descriptors, those slots are lost and with repeated use, the entire file descriptor table will be filled.

Among wrong answers, just about every line but p, q, t and u was listed by someone. The most popular were b, e, j and v, listed by 1/10 each. 1/2 earned no credit.

f) Which line is (lines are) required only to avoid stealing resources from the fib script?

__m__o_________________________________________________________________

1/24 earned full credit. 1/10 earned partial credit, listing either line m or o. If the process that calls execve() does not close unneeded file descriptors, those will remain open while the launched application runs, preventing that application from using those slots in its open-file table.

The most popular wrong answers were g, listed by 1/4, i, listed by 1/8 and j, listed by 1/8. The popularity of these is a mystery, since they relate to the parent process and not the child that launches the fib script. 1/4 earned no credit.

g) Which line is (lines are) kernel calls?

__d__e__g__j__m__n__o__s__t____________________________________________

Only 2 earned full credit. Line s was listed by 1/3. Lines e and t were listed by 1/4 each. Lines d and n were listed by 1/5 each. Line j was listed by 1/6. Lines g m and o were listed by 1/8 each. 1/4 earned no credit.

h) Which line is (lines are) only executed if there is an error?

__t____________________________________________________________________

This was probably the easiest question on the entire exam, over 2/3 got full credit.

Background: Again, look at the code for fibstub() from the end of this exam. Excellent answers fit easily in the space provided; therefore answers exceeding this space will be ignored!

a) If line s fails (the fib script didn't exist) what value does fibstub() return and why?

___No data is written to the pipe, so scanf() sees an EOF and__________

___does not change retval, which retains its initial value of -1_______

_______________________________________________________________________

1/16 earned full credit. 1/4 earned half credit by stating that retval retains its initial value without saying why. 1/8 earned some credit by suggesting a return value of EOF, a plausible but wrong hypothesis about the operation of fscanf() when it reads an end-of-file.

Among wrong answers, by far the most popular, given or at least suggested by 1/4, was that the return value was EXIT_FAILURE.

b) If line g is deleted, how would your answer to part a) change?

___fibstub never returns because the open file descriptor on the_______

___input to the pipe means the scanf() waits forever for an EOF________

_______________________________________________________________________

1/16 earned full credit. 1/10 earned partial credit by saying that the code would hang or that it never returns without giving any further explanation. 1/24 earned less, merely suggesting an unspecified effect on the first read.

1/4 of the class suggested that there would be no change in behavior. Over 1/2 of the class earned no credit.

This question was based on problems many students had with MP6, where they suffered exactly the hang described here. The issue was discussed in class at least twice as a result of questions about debugging MP6.

c) What does line n do? Not just what does dup2() do but how does this relate to the function of the entire piece of code.

___This line connects the write end of the pipe to standard output_____

_______________________________________________________________________

_______________________________________________________________________

1/4 got this right. 1/16 earned partial credit by, for example, switching their understanding of the read and write ends of the pipe or by confusing the parent and child. over 1/2 earned no credit.

Background: Look at the fib shell script also listed on the last page of this exam. Assume this script has been called using the shell command fib 8

a) Give the value of argv passed to the execve() kernel call by the shell that launched this script?

___{ "fib", "8", NULL }________________________________________________

_______________________________________________________________________

1/6 earned full credit. 1/6 were docked for missing the NULL at the end. 1/12 just said 8, with no other detail. Another 1/8 earned partial credit with difficult to classify wrong answers. Over 1/7 earned no credit.

b) Give the value of argv passed by execve() to the main() function in /bin/tcsh.

___{ "/bin/tcsh", "fib", "8", NULL }___________________________________

_______________________________________________________________________

1/16 earned full credit. Another 1/8 gave answers identical to the correct answer for part a), earning half credit, 1/7 forgot the null, and 1/16 made both of those errors. 1/4 earned token credit by listing just 8 as an answer. Over 1/6 earned no credit.

This question was based on MP4; it was impossible to do a good job on that machine problem without understanding how the execve() kernel call transforms the argument list as it launches a shell script.

Background: Ultimately, the result of running the fib script is communicated from the echo command in the script to the fscanf() call on line h of fibstub(). Ultimately, /bin/echo probably uses fputc() to output each character, and similarly, fscanf() probably uses fgetc().

a) What kernel calls do fputc() and fgetc() use?

___write()___read()____________________________________________________

1/7 earned full credit, and there was very little partial credit.

b) What kernel object(s) do those kernel calls operate on?

___open file objects representing the two ends of the pipe_____________

Nobody earned full credit. 1/6 said merely open file objects, without connecting them to the concept of a pipe. 1/12 used the term descriptor, confusing the concept of a file object with the concept of a file descriptor, the index of the entry for that object in the open file table of a process. Over half earned no credit, although only 1/16 left the space blank.

c) What is the abstract class of that object (those objects)?

___these are instances of class open file______________________________

Only 1/12 earned full credit. 1/7 earned partial credit for answers that confused file pointers with file objects. This is worse than merely confusing objects with object handles, because the term file pointer has two distinct uses -- it can refer to the position within a file, for example, when referring to the lseek kernel call, or it can refer to the pointer to an open file object. Again, over 1/2 earned no credit, while only 1/10 left the space blank.

Background: To fork a Unix or Linux process on a machine with no memory protection, the system must duplicate the entire memory accessible to that process. Consider a machine with a paged MMU, where the hardware can mark each page as read-only or read-write. The software may make additional annotations on each page table entry for its own use. On such a machine, the fork operation involves creating a new page table for the child process.

a) What is put in the new page table for each read-only page in the old table?

___a copy of the entry from the old page table_________________________

_______________________________________________________________________

_______________________________________________________________________

_______________________________________________________________________

1/4 earned full credit. Common problems among those earning partial credit included confusing pages with page frames or simply describing the format of a read-only page-table entry without indicating that it points to the same page frame as the original. 1/3 earned no credit, with many answers verging on pure BS.

b) What is put in the new page table for each read-write page in the old table?

___a read-write entry referring to a page holding a copy_______________

___of the page referenced by the old page table entry__________________

_______________________________________________________________________

_______________________________________________________________________

Only 1/12 earned full credit. 1/5 lost points for forgetting the use of a pointer or frame number and acting as if the page itself was part of the page table. Another 1/5 forgot to say that the page is copied. Again, 1/3 earned no credit, with many answers verging on pure BS.

c) Suppose decide to defer copying of read write pages until the program actually tries to write them. This way, we never need to copy a page that is never written. To do this, what is put in the new page table for each read-write page in the old table?

___a read-only entry for the page referenced by old table______________

___with auxiliary annotations saying to copy before write______________

_______________________________________________________________________

_______________________________________________________________________

1/10 earned full credit. 1/4 suggested using a mark-bit or clean-dirty bit to track write operations. This is sensible, so it earned partial credit, but it does not solve the problem because tracking writes after the fact will not make copies before the fact.

1/3 earned no credit, with many answers verging on pure BS. For example, more than one suggested major changes to the format of the page table, as if the page-table format was under software control. In fact, it is typically fixed by the MMU hardware and as immutable as the CPU's instruction format.

d) How does the page-table entry for the read-write page in the original page table need to be changed if we use the idea from part c)?

___the same as above, the entry is changed to read-only copy on write__

_______________________________________________________________________

_______________________________________________________________________

_______________________________________________________________________

Only 1/24 earned full credit. As with part c, mark bits were popular, suggested by about 1/5. Among wrong answers, some suggested that read-write page-table entries in the original table needed no speial treatment. Close to 1/2 earned no credit.

e) If we use the idea from parts c and d, what part of the operating system will make copies of read-write pages after a fork kernel call?

___the page fault handler makes the copy when it sees a write__________

___operation on a read-only copy-on-write page_________________________

_______________________________________________________________________

_______________________________________________________________________

1/12 earned full credit. 1/10 gave vague to very vague answers that earned at least some credit. The vaguest such answer was "the memory management software."

Over 1/2 earned no credit. Among those were 1/5 who suggested that the MMU would make the copy.

This question was something of an exploration of student inventiveness. In fact, deferred-post-fork-copy was invented around 1980, 20 years after MMUs and 10 years after the idea of the Unix fork, and is almost universally used on modern Unix/Linux systems. It is among the more obscure features of modern operating systems.

Background: The Unix/Linux nanosleep( interval * req, interval * rem ) causes the calling thread to sleep for the time interval req, unless something else wakes it up prematurely, in which case the remaining fraction of the requested interval is stored in rem. Time intervals are specified as a 2-element structure giving the time delay in seconds and nanoseconds. The simplest implementation of this service rests on real-time clock hardware that gives an interrupt for every clock tick. For this problem, assume that the constant tick is the interval between clock interrupts.

a) What do you need to add to each thread description in order to support this primitive? The answer will be a short list of new fields, with, for each field, a very brief description of its type/class/use.

___wakeup -- the interval until time to wake up the thread_____________

___alarm -- a semaphore to wait on until awakened______________________

___link(s) -- to link this thread into a list of sleeping threads______

_______________________________________________________________________

Nobody earned full credit. Among those earning partial credit, only 1/24 missed the basic need for an interval or deadline for the wake-up operaiton. 1/3 missed the need for some mechanis allowing the sleeping thread to be awakened, and a similar number missed the need to organize some kind of list of sleeping threads.

Most students answers to later parts of this question assumed all of the fields listed above. Careful students ought to have finished their answers to the later parts of this question and then gone back to see what they had assumed and then corrected their answer to this part. Few answers showed evidence of this.

b) Briefly outline what nanosleep() does. A good answer will reference the fields in part a).

___set wakeup to req and link the thread into the list of sleepers_____

___wait for the alarm__________________________________________________

___return remaining value in wakeup as rem_____________________________

_______________________________________________________________________

Again, nobody earned full credit. 1/24 forgot to set the interval or deadline until the wake-up. 1/10 forgot to make a record of the fact that this thread is sleeping. 1/8 forgot to have this thread cease running until awakened, and a similar 1/8 forgot to record the remaining time as the value of rem. Major penalties were assessed to the 1/6 who had answers suggesting some kind of busy waiting for sleeping threads, and for the 1/24 who had solutions that could only work if there was just one sleeping thread at a time.

Over 1/3 earned no credit. In most of these answers, it was extremely difficult to find any evidence of algorithmic thinking or a description of a design for a solution.

c) Briefly outline what the real-time clock interrupt service routine would do to support the nanosleep() kernel call.

___for each thread in the list of sleepers_____________________________

_______decrement that sleeper's interval by one tick___________________

_______if that sleeper's inteval <= 0__________________________________

___________remove it from the sleeper list, signal its alarm__ ________

1/24 earned full credit. 1/7 forgot to hint at searching for sleeping threads, while 1/10 focused on decrementing counters by one tick per interrupt without saying what to do when the count reaches zero. Serious penalties were assessed to the 1/16 who assumed a single sleeper and the one who proposed operations that were impossible within an interrupt service routine. Fully 1/2 earned no credit. Again, it was difficult to find evidence of algorithmic thinking or design in these wrong answers.

d) What do other parts of the system do if they discover that they have to awaken a process that is blocked awaiting the completion of a nanosleep() interval?

___remove it from the sleeper list and signal its alarm________________

_______________________________________________________________________

_______________________________________________________________________

_______________________________________________________________________

1/16 earned full credit. Only 1/24 earned partial credit, either for answers that only worked for a single sleeper or for forgetting to wake up the sleeping process after setting rem. Again, over half earned no credit.

A general remark: Only a very few stayed to the end of the exam period, with many leaving more than 1/2 hour before the end. Most of these would probably have profited by going back and rereading both the questions and answers to see if the answer actually addressed the issues asked by the question. . Judicious use of eras