CSE 120: Homework #1 Solutions

Spring 2023
  1. How do hardware and the OS work together to handle interrupts? When an interrupt happens, what tasks are handled by the hardware and what tasks are handled by the OS?

    When an interrupt happens (e.g., a network device receives a packet), the CPU stops current operation, switches to kernel mode, and saves machine state on the kernel stack. The CPU then reads an address from the interrupt table, indexed by the interrupt number, and jumps to the address of the interrupt handle. The OS handles the interrupt (by running the interrupt handler function). Upon completion, the CPU restores the saved state from the stack and returns to user mode. The application that got interrupted (when the interrupt happened) continues from where it stopped.

  2. [Silberschatz] Some computer systems do not provide a privileged mode of operation in hardware. Is it possible to construct a secure operating system for these computers? Give arguments both that it is and that it is not possible. (By a secure operating system, we mean that a user program is not able to corrupt the kernel, prevent it from running, crash the system, violate memory protection, etc.)

    There are several possible approaches for implementing a secure operating system. One is to write a emulator for a dual-mode processor (one with a privileged mode) and to run the operating system on top of this emulator. A slight variant of this is to run user code only in an emulator; this is the approach you use in Nachos.

    Another is to rely upon safe languages. Only executing user programs written in a safe language such as Java will work, since the language properties guarantee that arbitrary writes to memory aren't allowed and the instruction set is limited. Note here that the user doesn't get to choose arbitrary machine code to run—the code run is the result of just-in-time compiling the Java code. Similar to this is only running code which has been produced by a trusted compiler which is known to check memory addresses and not output privileged instructions.

    It is not enough to have the kernel scan the user code for bad instructions before executing it, if the code may have been produced by an arbitrary compiler. First, bad instructions may not be easy to identify—for example, they might be a write instruction which happens to overwrite critical data, but which is not easily identified as such. Directly executing user code is also dangerous because the user code may do something indirect such as overwriting its code or writing out new code to a new page of memory and then jumping to it, and this code would then not be checked for security.

    Similarly, asking the processor to check with the OS before executing each instruction doesn't quite work. I don't know of a processor which has a mode quite like this. Even if one did, that would essentially amount to having a mode bit—there has to be some way for the processor to know to check user code but not the operating system code itself. To make this work, you can use a full emulator (as described earlier).

  3. [Silberschatz] Which of the following instructions should be privileged? Give a one-sentence explanation for why.

    a) Set value of timer
    b) Read the clock
    c) Set memory content to zero
    d) Turn off interrupts
    e) Switch from user to monitor (kernel) mode

    Set value of timer: Yes, otherwise the user program can manipulate it such that the OS never gains control.

    Read the Clock: No, as a user can't really do anything harmful by simply reading the clock.

    Clear Memory: Yes, since a user program shouldn't be able to clear arbitrary memory. (Exception: No, if interpreted as simply clearing memory belonging to the process.)

    Turn off interrupts: Yes, same reasoning as for setting the value of the timer.

    Switch from user to monitor mode: Yes, since otherwise a user program could simply switch to kernel mode to execute instructions it wouldn't otherwise be able to, and defeat security.

  4. [Tanenbaum] For each of the following Unix system calls, give a condition that causes it to fail: open, read, fork, exec, unlink (delete a file). (Hint: We discussed some in lecture, and you can also explore the error semantics of these system calls using man on ieng6, e.g., man 2 fork.)

    open: File does not exist.

    read: Invalid file descriptor.

    fork: No more processes (OS out of memory).

    exec: Program file does not exist; file exists, but does not represent a valid executable file (e.g., it is an image); file exists, but the user does not have permission to execute it (e.g., the file does not have the exec bit set, or the user does not have permission to execute the file).

    unlink: File does not exist; user does not have permission to access the file.

  5. [Anderson 2.13] Suppose you have to implement an operating system on hardware that supports interrupts and exceptions but does not have an explicit syscall instruction. Can you devise a satisfactory substitute for syscalls using interrupts and/or exceptions? If so, explain how. If not, explain why. (In this context, the syscall instruction is the instruction used by a user-level process to invoke a system call in the operating system.)

    (Background) Processes execute the trap instruction to invoke system calls in the operating system. The trap instruction ensures a controlled and protected transition from user-level to kernel-level, enabling user-level processes to execute code in the operating system on their behalf.

    Exceptions like divide by zero or invalid instruction also cause a controlled and protected transition from user-level to kernel-level. If the underlying hardware does not provide a trap instruction, an operating can use exceptions instead as a hack. For example, an operating system can have the convention that executing an invalid instruction will take the place of a trap instruction since executing an invalid instruction will cause an exception that immediately transfers control to the operating system.

    Additional details (not needed in an answer) are how to specify which system call to invoke and how to pass arguments. By convention, for instance, the system call number and arguments can be placed on the process stack. In verifying all arguments, the operating system can also distinguish between using an invalid instruction for a system call and the process actually executing an invalid instruction unintentionally.

  6. Consider the following C program:
    #include <stdlib.h>
    int main (int argc, char *arg[])
        fork ();
        if (fork ()) {
    	fork ();
        } else {
            char *argv[2] = {"/bin/ls", NULL};
            execv (argv[0], argv);
            fork ();

    a. How many total processes are created (including the first process running the program)? (Note that execv is just one of multiple ways of invoking exec.)

    b. How many times does the /bin/ls program execute?

    [Hint: You can always add debugging code, compile it, and run the program to experiment with what happens.]

    a. 6 processes are created, including the first process. The process tree looks like:

    41 (first process)
    41 -> 42 (fork before the if predicate)
          42 -> 43 (fork in the if predicate of the first forked process)
                42 -> 44 (fork in the if clause)
    41 -> 45 (fork in the if predicate of the first process)
          41 -> 46 (fork in the if clause)

    Note that exec does not create a new process, it overwrites the currently running process with a new program. As a result, the branch in the program that calls exec will not call fork after the exec.

    b. The /bin/ls program executes twice.

  7. [Crowley] Suppose the hardware interval timer only counts down to zero before signalling an interupt. How could an OS use the interval timer to keep track of the time of day?

    The operating system can program the interval timer to go off after some short time interval, say 10 ms. Each time the timer interrupt fires, the OS resets the timer, and increments a counter. By multiplying the counter by the timer interval, the operating system can measure the amount of time which has progressed. If the operating system knows what time it booted (say it has a clock which can tell it this, or it asks the user, or checks the network), it can determine the exact time of day.

    It is not sufficient to simply program the timer to a large value and check to see the amount of time remaining, since the operating system will also need to use the timer for other purposes, such as interrupting user programs for context switching.