Midterm II

Solutions and Commentary

Part of materials for 22C:50, Summer 2004
by Douglas W. Jones
THE UNIVERSITY OF IOWA Department of Computer Science

Grade Distributions


Median = 5.9
Mean   = 5.79         X
                      X               X
       1 . 2 . 3 . 4 . 5 . 6 . 7 . 8 . 9 . 10

Composite Exams

Median = 11.9
Mean   = 11.95            X
                          X   X   X
       0 . 2 . 4 . 6 . 8 . 10. 12. 14. 16. 18. 20
Grade Scale           D     C     B     A   

Homework Scores

Median = 26.7
Mean   = 25.49
                                             X     X
      10. 12. 14. 16. 18. 20. 22. 24. 26. 28. 30. 32

Machine Problem Scores

Median = 13.7
Mean   = 12.45                        X
                              X       X
       0 . 2 . 4 . 6 . 8 . 10. 12. 14. 16. 18. 20

Overall Scores

Median = 52.9
Mean   = 49.90
      28. 32. 36. 40. 44. 48. 52. 56. 60. 64. 68.
Grade Scale     F     D     C     B     A   

Exam Solutions

  1. Consider these two very artificial fragments of EAL code: (2 points)
         ; file1.a                         ; file2.a
            EXT A                             INT A
            INT B                             EXT B
            W   A                             W   A
         B: W   B                             W   B
            W   C                          C: W   C
         C  =   #200                       A  =   #300

    Assume that these have been assembled and that a linking loader is used to link first file1 and then file2 and load them into memory starting at address 30016. Show the resulting contents of memory as consecutive words:

       location      value                 location      value
         0300     __0300______               030A     __030A______ hardest
         0302     __0302______               030C     ____________
         0304     __0200______ hard          030E     ____________
         0306     __0300______               0310     ____________
         0308     __0302______               0312     ____________

    4 did perfect work. It is clear that dealing with C was the most difficult. This is a local symbol in each file, neither defined as internal nor external, so the linker never sees it.

  2. Which of the following shell commands must be built-in to the shell and not merely the names of executables. For each that must be built-in, why? (1 point)

    a) exit <status>

    This must be built in because the exit from an application cannot force the shell that launched that application to terminate.

    8 did well here, the rest gave odd reasons.

    b) cd <filename>

    This must be built in because changes to the environment, including changes to the current working directory done within an applicaton have an effect only on that appliction, not on the shell that launched it.

    6 did well here, two gave odd reasons, and 2 incorrectly concluded this could be done by an application.

  3. You have been asked to write an new suite of applications, callable from any Unix shell. The primary application in this suite is a program called if that executes the applicaton named by argv[1] and passes, as parameters, argv[2] and up. If the executed application terminates successfully, if exits normally. Otherwise, it reads standard input up to and including a line starting with the single keyword else or endif. If it finds end-of-file on this scan, it reports an error.

    a) The suite also includes an application called else. What does this do? (1 point)

    Else, if executed, should scan standard input up to and including a line containing endif. It should complain if reaches the hend of file.

    5 did well here, 2 missed the end of file error, and the remainder were confused, which is odd because this bears such a close resemblance to the last machine problem.

    b) What other application programs must you write as part of this suite, and what do they do? (1 point)

    Endif, if executed, should do nothing.

    Few students gave a good answer here, one listed endif, with no explanation of what it does while the remainder earned no credit.

  4. There was a time in the early PC era when external disk drives were sold that could be connected to the serial port of a computer. Typically, these had a command to set the disk address, one to write a sector's worth of data to a one-sector buffer inside the drive electronics, one to read the contents of that buffer, and one to read or write between the specified disk address and the internal buffer. Assume commands are one byte, disk addresses are 4 bytes, and sectors have 512 bytes.

    a) Assuming a fast serial port, is disk scheduling still relevant? (1 point)

    Yes. If the serial port is fast enough, seek times will still delay the next read or write if it is not in a close-enough cylinder to the previous one.

    8 gave good answers here, 3 somehow concluded that scheduling was irrelevant.

    b) How many interrupts it would take to complete one disk transfer to or from this device? (1 point)

    Assuming one interrupt per character transferred, typical of serial ports, there is 1 for the command to move the data, 512 for the data bytes, 1 for the command to set the disk address, 4 for the bytes of the disk address, and 1 for the command to read or write between disk and buffer, for a total of 519 interrupts.

    1 gave this answer. The popular answers were 4, 3 and 2 interrupts. The answer 4 was given half credit because it would have been reasonable if the serial port had a DMA interface.

  5. Assume you are given a disk spinning at 100 revolutions per second, and with 100 sectors per track, and with 1000 bytes per sector, including intersector gap and header information, which take up 100 bytes (these numbers are round so you won't need a calculator).

    a) How many bytes per second does the interface for this disk process? (0.5 points)

    100 revs/second × sectors/rev 100 × 1000 bytes/sector
    = 10,000,000 bytes/second

    9 did well here (this was a pretty obvious one), while 2 had odd errors that suggested either no time or serious conceptual problems.

    b) How many microseconds pass during reading the header on one sector? (0.5 points)

    100 bytes/header / 10,000,000 bytes/second = 1/100,000 seconds/header
    = 10 microseconds/header

    6 got this right, 5 gave odd answers.

    c) Given that the disk interrupt service routine takes 2 microseconds, what is the minimum interleaving factor that will work for this disk, ignoring the count of sectors per track? (0.5 points)

    2 microseconds is less than 10 microseconds, so the interrupt service routine will return sometime in the middle of reading the header for the next sector. We can conclude that this is too late for no interleaving, so it will have to skip one sector. This implies that 2-way interleaving will work.

    5 did well here, taking into account correct inferences from wrong answers in part b. 6 gave odd answers, sometimes with complex and inexplicable arithmetic to back them up.

    d) Given the number of sectors per track, what interleaving factor will be likely to be used? (0.5 points)

    The interleaving factor should not have any common factors with the number of sectors per track, so we must go up from 2-way to 3-way, using every third sector.

    6 did well here, working from the answer they gave to part c. 5 did poorly, with many either giving wild numbers or giving numbers that had common factors with 100 (10-way interleaving anyone?).

  6. Large sectors allow more efficient input/output for large files, but if a whole sector is allocated for each small file, this can lead to significant waste. One option, used by the Reiser File System under Linux, is to store "file tails" (the final fractional sector of a large file, or a whole small file) packed together into sectors.

    a) What information would you need to add to a classical UNIX i-node to allow the tail of a file to be packed together with other file tails in a single disk sector? (0.5 points)

    The i-node would clearly need to contain the offset into the sector holding the tail of the tail.

    It would make sense to put the sector number of the tail sector in the i-node, treating the tail of the file specially instead of having this sector number stored deep in some index node.

    There is no need for the size of the tail, since we just need to take the file size mod the sector size to find the tail size.

    One did well here, 2 got a bit over half credit for the offset into the tail sector of the tail data, and 3 got a bit under half credit for making a special case of the sector number of the sector holding the tail.

    b) What file operations would be significantly slower with this scheme? (0.5 points)

    Reading the tail of a file and writing the tail of a file will be slower. Reading or writing other sectors of the file should be no different than before.

    4 said read and write were slower; this was worth under half credit. 3 emphasized something about the tail, earning over half credit, but nobody did really well here.