CSE 120: Homework #1 Solutions

Fall 2023
  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.

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

  2. You may have written programs that call exit, or return from main with some value, and wondered what happens to that value. The value can be returned to a parent process when the parent calls wait on the child: if the child calls exit(0) then the value 0 can be returned to the parent via wait. Why have this functionality, why might it be useful?

    The status value that the child process passes to exit allows the child to indicate to the parent what happened when it executed — in its most basic form, the status value allows the child to indicate to the parent whether the child was successful or not. From this perspective, you can think of the child process as a large, coarse-grained procedure. The parent "invokes" the child as a process, and the child calls exit to pass a return value back to the parent.

    Shell scripts frequently take advantage of this functionality, such as when a shell script wants to take a different action depending on whether a command was successful or not. The man pages for command line tools typically end by describing their exit status values and their interpretations. For instance, here is the list from man ls on ieng6:

       Exit status:
           0      if OK,
    
           1      if minor problems (e.g., cannot access subdirectory),
    
           2      if serious trouble (e.g., cannot access command-line argument).
          
  3. Which of the following instructions should be privileged? (Also 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 monitor 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. For each of the following system calls, give a condition that causes it to fail: open, read, fork, exec, unlink.

    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 a spreadsheet); 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. On Unix, two signals that cannot be caught and handled by an application are SIGKILL and SIGSTOP.

    a) SIGKILL immediately terminates a process. What is a scenario that motivates having the OS make it impossible for an application to handle SIGKILL?

    One scenario is a buggy program with an infinite loop. If a program with an infinite loop can handle SIGKILL but has a bug, then it may not be possible to ever terminate the process without rebooting.

    Another scenario is if the process is malware. If malware applications could handle SIGKILL then they could prevent users from terminating them.

    b) SIGSTOP immediately pauses a process (which can later be resumed with SIGCONT). Why is it safe (in terms of application correctness) for an application to be arbitrarily paused using SIGSTOP?

    It is safe in terms of correctness because applications are already written assuming that they can be paused/suspended at any time. The effect of SIGSTOP is the same as if a process were paused by the OS as a result of a timer interrupt. The difference is that the OS would automatically schedule the process to run again in the future with a timer interrupt, whereas with SIGSTOP a process is paused until it receives a SIGCONT.

  6. Suppose the hardware interval timer only counts down to zero before signalling an interrupt. 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.

  7. Suppose you have to implement an operating system on hardware that supports interrupts and exceptions but does not have a trap instruction. Can you devise a satisfactory substitute for traps using interrupts and/or exceptions? If so, explain how. If not, explain why.

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

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

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

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

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

    41 (first process)
    41 -> 42 (fork in the if predicate)
          41 -> 43 (fork in the if clause)
    42 -> 44 (fork in the else 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.