CSE 120: Homework #1 Solutions

Spring 2025
  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 (i.e., hardware) 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 handler. 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. [Anderson 2.1] For each of the three mechanisms that supports dual-mode operation — privileged instructions, memory protection, and timer interrupts — explain what might go wrong without that mechanism, assuming the system only had the other two. (In other words, if we just had memory protection and timer interrupts but not privileged instructions, what could go wrong; if we just had privileged instructions and timer interrupts, what could go wrong, etc.)

    Without privileged instructions: Without privileged instructions, any process could execute any instruction (e.g., instructions for interacting with I/O devices, masking interrupts, manipulating virtual memory state, etc.). As a result, a buggy or malicious process could violate memory protection (access data in the address space of another process or the operating system), I/O protection (issue requests to disk for someone else's data), fairness (turning off interrupts to gain full control over the CPU), etc.

    Without memory protection: Similar to above, without memory protection any process can potentially access the data of any other process (of any user), as well as the data maintained by the operating system. [Early personal computers lacked such memory protection, and any application could potentially disrupt other applications or the operating system with stray pointers.]

    Without timer interrupts: Fundamentally, the timer interrupt is the essential mechanism that enables the operating system to regain control over the CPU on a regular basis. Without timer interrupts, a buggy or malicious process could run indefinitely on the CPU and deny the CPU to other processes and the operating system (e.g., an infinite loop).

  3. [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 a trap instruction to invoke system calls in the operating system (e.g., INT or SYSCALL). 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.

  4. [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) Clear memory
    d) Turn off interrupts
    e) Switch from user to 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.

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

    Switch from user to kernel 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.

  5. An important feature of the process abstraction is that the operating system has complete control over when a process executes, and the OS can arbitrarily suspend or resume a process at its discretion. As a result, applications are generally implemented to be independent of the passage of real time. However, many applications want to know about the passage of real time to implement various features, even as simple as a cursor that blinks every second. To support such functionality, OSes provide an interface to inform applications of the passage of real time. OSes typically use the same mechanism as with exceptions (e.g., divide-by-zero) to interrupt and notify a process as time passes.

    Below is a small C program that prints the passage of time in seconds using the simple Unix alarm interface (see man 2 alarm on ieng6):

    #include <unistd.h>
    #include <signal.h>
    #include <stdio.h>
    
    volatile int seconds;
    
    void handler (int signum) {
        seconds++;
        alarm (1);   // schedule next SIGALRM
    }
    
    int main (int argc, char *argv[]) {
        int last = seconds = 0;
        signal (SIGALRM, handler);  // SIGALRM is the timer signal
        alarm (1);   // schedule SIGALRM handler callback, arg is # of seconds
    
        while (1) {  // normally we would do useful work instead of spinning
      if (last != seconds) {
          printf ("%d sec\n", seconds);
          last = seconds;
      }
      if (last == 5) return 0;
        }
    }
    

    a) What is the output of this program? To verify your answer, you can compile and execute the program on ieng6:

    $ cc file.c          [assuming you put the program contents into file.c]
    $ ./a.out
    
    a) The output is:
    1 sec
    2 sec
    3 sec
    4 sec
    5 sec      
    

    b) Generally it is not possible to predict how long a program will take to execute by inspecting its code. However, for this program we can. Approximately how long does it take to execute? (You can run it on ieng6 with time ./a.out.)

    b) Approximately 5 seconds

  6. [GNU C Library manual] The use of mechanisms like Unix signals introduces a source of non-determinism and concurrency in the execution of a process, even for single-threaded applications. Consider the following C program:
    #include <unistd.h>
    #include <signal.h>
    #include <stdio.h>
    
    volatile struct data { long int one, two; } value;
    
    void handler (int signum) {
        if (value.one != value.two)
          printf ("%ld != %ld\n", value.one, value.two);
        alarm (1);   // schedule next SIGALRM
    }
    
    int main (int argc, char *argv[]) {
        static struct data zeros = { 0, 0 }, ones = { 1, 1 };
        signal (SIGALRM, handler);  // SIGALRM is the timer signal
        alarm (1);   // schedule SIGALRM handler callback, arg is # of seconds
    
        while (1) {
          value = ones;
          value = zeros;
        }
    }
    

    The program is a tight loop assigning ones and zeroes to value. Is it possible for the program to ever print out the != message in handler? Briefly explain why or why not. (Again you can compile the program and experiment with it.)

    Yes, it is possible for the program to print out the != message in handler. The alarm signal behaves like an interrupt, and interrupts can occur between the execution of any two CPU instructions. While the code for assigning ones or zeros to value is a single line of C code, the compiler will generate multiple instructions to update both fields of the value struct. As a result, it is possible for the timer to interrupt the process between the assignment of field one and the assignment of field two. When this happens, the signal handler will find that the two fields have different values. While it might seem that the probability is low for the interrupt to occur precisely between the two instructions that write to the fields of value, if you compile and run it you will see that it can and does happen.

  7. [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.

  8. 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, see man 3 exec for all possibilities.) You do not need to provide an explanation.

    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.