CSE 451 - Winter 1999

Chapter 1, Silberschatz and Galvin, 5th edition

1. One set of three main purposes of the operating system is:
   • provide an environment in which a user can execute programs
   • make the computer system convenient to use
   • use the computer hardware in an efficient manner
   Another set is:
   • schedule computational activities to ensure good performance of the computing system,
   • provide a convenient environment for the development and execution of programs,
   • and put system resources to optimal use
   They amount to much the same thing; either answer was OK.

2. The four steps to running a program on a completely dedicated machine were:
   • Load the program manually into memory, from the front panel switches (one instruction at a time), from paper tape, or from punched cards.
   • Push the appropriate buttons to set the starting address and to start the execution of the program
   • As the program runs, monitor its execution by the display lights on the console. If errors are discovered, halt the program, examine the contents of memory and registers, and debug the proram directly from the console.
   • Get output from printer or from punched paper tape or cards.

3. The advantages to staging a tape onto disk are that the tape is sequential-access while the disk is random-access, so average seek time for a piece of data on the disk is much shorter. Then, while the first tape's data is being processed, another tape may be staged at the same time, so that the data is pipelined.

4. In a multiprogramming and time-sharing environment, there are new security issues.
   a. Two examples of security problems: first, one user may interfere with the execution of another user's program unless the system expressly prevents it. Second, one user may read or write to files belonging to another user unless, again, the system expressly prevents it.
   b. Realistically, no. In a dedicated system, the OS must be protected from the user's process. In a time-shared machine, the OS must be protected from many users' procesess, and each user process must be protected from the others. This increases the complexity of the system. A dedicated system has a single set of security permissions while a time sharing system has multiple sets of security permissions, and the ability to switch between levels. The time-sharing system can not know with absolute certainty who is sitting behind the keyboard.
   

5. Multiprogramming allows more efficient use of the CPU and I/O devices by interleaving user's requests. The the goal of multiprogramming is always to have code for the CPU to be executing.

6. In the past, the difference between mainframe and PC operating systems was that mainframes needed sophisticated OS's capable of juggling the demands of many users and protecting those users from each other. Personal computers did not need as much sophistication; for instance, if only one user has files in the filesystem, why bother to have file access protections? Over the last decade, however, as personal computers have become more integrated into business settings and as PC users themselves have become more sophisticated and demanding, PC operating systems have caught up or surpassed mainframe OS's in complexity.

7. The essential properties of the following types of OS's are:
   a. Batch: In the basic batch system, one program runs at a time. A human or software monitor is required for program scheduling and loading. In advanced batch systems, CPU and I/O operations may be overlapped. Spooling to allow the I/O of one job to overlap the computation of another. Multiprogrammed batch systems allowed more than one program to run "at the same time," and had job scheduling and CPU scheduling to support that.
   b. Interactive: Provides on-line communication between the user and the system, with response times on the order of a second or shorter.
   c. Time-sharing (aka multi-tasking): Probably has a file system. Each running program is a process. Advanced time-sharing systems have virtual memory to support the large amount of data required by multiple users.
   d. Real-time: Has rigid time requirements on the operation of a processor or the flow of data. Hard real-time systems guarantee that critical tasks complete on time. Soft real-time systems allow critical tasks to get priority over other tasks and retain that priority until they complete.
   e. Distributed: Has multiple processors in the system which typically do not share the same memory or clock. Processors communicate via some sort of network, for the purposes of resource sharing, computation speedup, reliability, and data exchange.
   

8. Two of the purposes of the operating system are to make the computer efficient and convenient to use. Sometimes, these two purposes are in contradiction with one another. It may be appropriate to "waste" resources in order to support convenience. Convenience for the programmer or user may save far more time than efficient operation under the covers. For example, the operating system is responsible for managing the virtual memory allocated to a process. The programmer may know more about her program's data access patterns, and may be able to judge better than the operating system how to manage the virtual memory for her process, resulting in more efficient operation of the computer system. However, by giving the operating system responsibility for managing virtual memory, several good results are achieved: (a) The programmer can still write the program, even if she doesn't know all the architectural details of the computer system she is using. (b) The programmer can write one program that may be compiled for a number of different platforms, leaving the system-dependent details of the VM system up to the operating system. (c) The program is much faster and cleaner to write.

9. (For the purposes of this question, assume the personal computer and single-user workstation are not multi-tasking -- probably a silly assumption in today's environment.) A user may be better off using a time-sharing system rather than a personal computer or a single-user workstation if that user wants to run multiple programs simultaneously. Then he can overlap the I/O and computation of more than one of his own processes. In addition, he may want to share the file system on that time-sharing system with some other user. Finally, the time-sharing system is likely to be less expensive per user.

10. In a symmetric multiprocessing system, each processor runs its own copy of the OS, and the copies communicate with each other as needed. In an asymmetric multiprocessing system, one master processor assigns tasks to each of the other slave processors. Multiprocessors have the advantage that they have increased throughput than a single processor, and they may cost less to operate than having n separate single- processor machines because they can share physical resources. They may also be more reliable, since the failure of one processor may not bring the entire machine to a halt. However, the speedup ratio for an n-processor machine is not n because there is overhead in orchestrating the use of all of the processors.

11. Distributed systems are desirable because they allow us to share resources, speed up computation, increase reliability, and exchange data among systems.

12. The main difficulty in writing a real-time operating system is in meeting time constraints reliably. Hard real-time systems are considered a difficult problem, but soft real-time systems are now very common.

Chapter 2, Silberschatz and Galvin, 5th edition

1. This buffering scheme is exactly the same as spooling but on a much finer grain, in terms of the time scale and the amount of data processed at a time. The spooling scheme reads all of the program data at one time and must have space for all of it. The buffering scheme reads only part of the program data at one time, while the previous part is still being processed. If the balancing act can be maintained, the buffering scheme is much more space-efficient.

2. The monitor bit allows for a very coarse security system. However, since there is only one bit of information, there is only one level of protection: is accessing this address allowed or not? Despite this coarseness, the monitor bit does provide the important function of letting user code accidentally or maliciously damage kernel data structures.

3. The terms trap, exception, and interrupt are often used imprecisely or loosely, but according to Brian, these are the definitions we will be using in this class:
   • Trap: synchronous entry into the OS kernel generally as a result of a specific TRAP instruction (i.e. a syscall)
   • Exception: synchronous entry into the OS kernel generally as a result of some exceptional software condition
   • Interrupt: asynchronous entry into the OS kernel generally as a result of some external hardware event

4. DMA, or direct memory access, is useful when a peripheral device and main memory need to transfer data between them and the CPU's assistance is not required. DMA allows the data transfer to occur without the CPU's intervention, allowing more useful computation to get done instead.

5. Which should be privileged?
   a. Set value of timer: PRIVILEGED. The timer controls scheduling: if a user program runs until the timer goes off without voluntarily ceding control, it is forced to yield by the OS. If a user program could set the value of the timer, then it could hog the CPU.
   b. Read the clock: NOT PRIVILEGED. Reading the clock can't interfere with the kernel or other user programs.
   c. Clear memory: PRIVILEGED. The OS must check that the process wanting to clear memory controls the piece of memory in question before complying with the request.
   d. Turn off interrupts: PRIVILEGED. Only the OS should be in charge of setting the flow of control between the kernel and the user processes (except in the case of voluntary yielding).
   e. Switch from user to monitor mode: PRIVILEGED. If user programs could switch to monitor mode, they could do whatever they wanted. Instead, they must request a switch to monitor mode and then yield control to the kernel by making a system call.
   

6. A secure operating system running on an architecture that does not supply a privileged mode might operate by providing a virtual machine interface to the user program and checking each instruction as it is run. That is, the user's program never gets to run on the "bare hardware," because the OS must check each instruction and do one of three things with it: run it as is, run it with some modification to make it safe, or reject it.

   This scheme works, but is extremely slow. If the idea is to build a completely secure OS without a privileged mode and without checking each instruction, then I don't think it can be done, because one of those unchecked instructions may access memory or devices in a damaging way.

7. The operating system has a lot of data structures inside it: open file tables, virtual memory maps, process control blocks, and so forth. These data structures really need to change all the time, so the model proposed in the question implies that you need to do without them or else you need to put them in the unprotected memory segment. If you do without them, then the range of services you can provide is severely curtailed, but if you put them outside the unprotected memory segment, they are not secure from user damage.

8. Which of the instructions listed absolutely must be protected? In my answers, OK means that users may call the instruction.
   a. Change to user mode. OK. Assuming that a change to user mode when already in user mode is a no-op, users may call "change to user mode" without doing any harm.
   b. Change to monitor mode. OK. In fact, I'm not sure why they claim that this is usually protected; this was not the model we saw in class. Typically the change to monitor mode is a machine instruction which always results in a jump into the system call handler, so it is safe to let any process call it.
   c. Read from monitor memory. NOT OK from the security standpoint, PROBABLY OK from the correctness standpoint. The security argument: the kernel throws around a lot of sensitive data; for example, if a user reads a file from disk, pieces of that file probably sit around in kernel buffers at some point during the read. Arbitrary other users should not be allowed to circumvent file system security by reading monitor memory.
   From the correctness standpoint, there isn't too much mischief that a user program can get into by reading monitor memory. By correctness, I mean that the OS is correct if it can properly carry out the task of sharing limited resources among multiple users and processes in a fair manner. Technically, a user process may be able to exploit "inside info" from the kernel to squeeze more compute power or device usage out of the OS, but it would probably have to be actively malicious.
   d. Write into monitor memory. NOT OK. Enough said.
   e. Fetch an instruction from monitor memory. OK, with the same caveats as the part (c). If the instruction itself is protected, presumably that will still be blocked since the problem only says fetch, not execute. However, it's still not too cool for the user program to be reading monitor memory, whether that memory happens to contain data or instructions.
   f. Turn on timer interrupt. IRRELEVANT. I can't think of a time when a user process would be running and timer interrupts would be off, so it doesn't seem that this would ever come up.
   g. Turn off timer interrupt. NOT OK. If a user process can turn off the timer, then the kernel can't properly implement time slicing.

9. Caches are useful when you have two types of storage: fast, small, expensive storage (the cache) and slow, large, cheap storage (the backing store). The cache contains elements from the store that are seen as useful in some way, or likely to be needed soon. A cache is useful because it makes access to those useful data quicker. However, having a cache introduces the problem of cache consistency: making sure that the same data item in the cache and the store always match, or at least that they always match when it really matters (like when your system goes down). The reason caches are smaller than their backing stores is because they are made out of more expensive stuff. If they were just as cheap to make than the backing store then we'd ditch the store and just use the cache. Another reason is that the two storage devices may have different qualities; for instance, DRAM loses its values when you pull the plug, but a disk keeps them.

10. Hardware aids for OS security include:
    • the monitor bit, which prevents users from accessing kernel memory
    • the timer, which helps the OS do time-slicing, thereby preventing malicious or accidental CPU-hogging
    • privileged instructions, which prevent the user from running machine instructions they shouldn't