CSE 451 - Winter 1999 (2024)

Sample Solutions, Quiz 2

Chapter 3, Silberschatz and Galvin, 5th edition

The five major activities of the operating system with regard toprocess management are:
- The creation and deletion of both user and system processes
- The suspension and resumption of processes
- The provision of mechanisms for process synchronization
- The provision of mechanisms for process communication
- The provision of mechanisms for deadlock handling
The three major activities of the operating system with regard tomemory management are:
- Keeping track of which parts of memory are currently being used and by whom
- Deciding which processes are to be loaded into memory when memory space becomes available
- Allocating and deallocating memory space as needed
The three major activities of the operating system with regard tosecondary storage management are:
- Free space management
- Storage allocation
- Disk scheduling
The five major activities of the operating system with regard tofile management are:
- The creation and deletion of files
- The creation and deletion of directories
- The support of primitives for manipulating files and directories
- The mapping of files onto secondary storage
- The backup of files on stable (nonvolatile) storage media
The purpose of the command interpreter (or shell) is to provide aconvenient interface between the user and the operating system. Oneexcellent reason to keep the command interpreter separate from thekernel is that it's easier to have many different commandinterpreters, leaving the user free to select the interface he or sheis most comfortable with. (If you want to run mysh as your commandinterpreter, for instance, you can.) Another reason is that the shelldoesn't need to be part of the OS, and a lot of people think it's goodfor the OS to be as lightweight as possible. This is a designdecision.
Five services provided by the operating system and theconveniences they provide:
- Program execution. This service allows the user to request that a program be loaded into memory and run. In some sense, user programs can do this themselves. If you squint right at a multi-threaded user program, you can think of it as a program loader, but it is not as flexible as the OS.
- I/O operations. This OS service allows the user to request that data be read from or written to a disk, the mouse, the keyboard, the screen, or any other device. While a user program could do this by itself (if it were allowed), it is much more convenient and safe to have the OS provide a common interface to these devices, so that their use may be multiplexed among users, and so that only valid data is passed to devices.
- File system manipulation. This service allows the user to request that data be stored into or retrieved from the file system. Again, a user program is free to set up its own file system if it so chooses, but it may be difficult for that program to share with other user programs, and if the data is to be kept in stable storage (disk), then the user program will probably want direct access to that storage. Again, much more convenient and safe to allow the OS to provide a shared file system to all user processes.
- Communications. There are two service groups under this heading: inter-process communication (IPC) and remote procedure call (RPC) or message passing. For the purposes of this question, RPC seems to be just another form of I/O, so the answer above covers it. IPC is a little different; it allows two processes on the same machine to communicate. This communication can be accomplished in a number of ways: through the file system, through pipes, through shared memory, and it seems to me there's a fourth way I ought to be thinking of but it's escaped me for now. Anyway, some of these methods of communication are easier for the user process to accomplish on its own than others. Communicating through the file system requires no more intervention by the OS than you already had for having the file system itself. Setting up pipes or shared memory is impossible without OS help, though.
- Error detection. This OS service allows the user program to be oblivious to the possibility of CPU, memory, or device error. The OS takes care of all of the sanity checking on all of these things, leaving a clean, abstract layer for user programs to build on. As in most of these examples, user programs could do this by themselves, but it makes much more sense to factor out this boring work and let the OS take care of it for us.
You may have sensed a recurring theme in the above answers: a lot ofthe conveniences provided by the OS could technically be accomplishedin userland if necessary. However, since these are resources that alluser programs will want to have, it makes more sense to take care ofthem once and for all in the OS. The OS does things that users aretoo lazy, too careless, or too malicious to be allowed to dothemselves.
The purpose of system calls is to provide an interface for userprograms to request operating system services.
The purpose of system programs is to make the system useful.Imagine that you have a UNIX workstation on your desk, but that all ithas is the operating system. It doesn't have ls or cat or cc or emacsor even vi. It's a fully working system, but you have no way offinding out what's in the file system, editing a file, or compilingit, so it's hard even to bootstrap your way to a useful system bywriting all of your own programs.
The layered approach to system design can make the process ofimplementing a very complex system cleaner and easier to think about.Each layer can take for granted that the layer below it will provideit with the interface it exports, and build from there.
OS designers like virtual machine architectures because they candevelop new OS techniques more safely and easily: since they are onlyworking on a virtual machine and not a real one, system operation neednot be interrupted for kernel hacking. (Normal kernel hacking makesthe entire machine unstable and very unfriendly to other users.)Users like the virtual machine architecture because it provides themwith the illusion of a whole machine all to themselves, identical to areal machine, even when there aren't enough real machines to goaround. (NOTE: while the virtual machine concept is an intriguingone, it isn't considered a key concept of this course.)
We like to separate mechanism and policy so that the system isflexible and can adapt to different workloads and users. Ideally, themechanism should support a wide range of policies.
See the email archive for this question. Again, this is notconsidered a key concept of this course, so if it's a little fuzzy, noworries.

Chapter 4, Silberschatz and Galvin, 5th edition

Concurrent programming introduces all sorts of interesting new issues: How should the different processes share resources such as the CPU and devices? How should they be laid out in memory? How should processes be created and deleted? Where should their state be stored when they are not running? What facilities should be provided for cooperation and synchronization?
The short-term scheduler selects from processes currently ready to run. It runs on the order of every 100 milliseconds. The medium-term scheduler is in charge of reducing the degree of multiprogramming in the system when necessary, by swapping some processes out. It runs only when necessary. The long-term scheduler really only exists on batch systems: it selects processes from a pool of jobs in mass storage and runs them one by one.
A normal context switch requires the PC, the stack pointer, and the registers to be reloaded with the new process' state. The DECSYSTEM-20, which has multiple register sets, presumably needs only the PC and the stack pointer to be updated (unless there are separate PCs and SPs in each register set?) and for the active register set to be changed. If all register sets are in use, then one register set must be written to memory while the desired set is copied in from memory.
Threads have two advantages over multiple processes: they share an address space, so communication is easier; and they are much lighter weight and easier to create and destroy quickly. However, if any thread makes a system call, then all user threads are stopped while the request is serviced. A web server might benefit from the use of threads so that it can handle many requests. A program to find large prime numbers, which is very compute intensive and does little I/O, might not.
Threads require their own PC's, register sets, and stack. Processes require all of those things plus their own address space,open files, and signal handlers.
To switch contexts between two threads, only the PC, thestack pointer, and the registers need to be updated. Processcontext switch requires all of those things, plus it requiresOS intervention for scheduling, placing the old process on the ready (or waiting) queue and selecting the next one, andpossibly mapping some memory.
User-level threads are managed by the user process and areinvisible to the kernel. However, they must either useasynchronous I/O or all block if any thread needs to do I/O.Kernel threads are managed by the OS. They take a lot longerto switch between, but they don't suffer the I/O problems ofuser threads.

Producer:

repeat ... produce an item in nextp ... while (in = out) && (last_to_go = producer) do no-op; buffer[in] := nextp; last_to_go := producer; in := in+1 mod n;until false;

Consumer:

repeat while (in = out) && (last_to_go = consumer) do no-op; nextc := buffer[out]; last_to_go := consumer; out := out+1 mod n; ... consume the item in nextc ...until false;

Consider the mailbox IPC scheme.
```
receive(A, message1); receive(B, message2); 
```
If it turns out that A takes a long time to come and B comes right away, then it will be inefficient, but it will still be correct.
b. The process might execute:
See Also
Process State in OS - Scaler Topics
```
thread_fork(&Wait_for_message, A);thread_fork(&Wait_for_message, B);/* go to sleep until signaled */Wait_for_message(Mailbox X) { receive(X, message); /* wake up main thread */} 
```
c. Not possible. What you really want is a "peek" operation that tells you if there are any messages, but you don't want to remove any messages you find (which the receive operation will do) and you don't want to add any messages that weren't there already (which the send operation will do). Since both of the primitive operations (send and receive) have adverse affects, there's no way to find out the state of the box without perturbing the system.
IPC, or interprocess communication, is handy when you want multiple processes on the same machine to work together. For instance, you may want to connect up some processes with a pipe on the command line: "grep foobar *.h | less". Or, in perhaps a more familiar example, you may want to drag a piece of a spreadsheet in Excel into your Word document. These are examples of IPC.
RPC, or remote procedure call, allows for a local process to request that some work be done by a process on some other machine. RPC can "make it look like" a remote procedure call is just a regular procedure call, except maybe not quite as reliable. Inside the guts of an RPC call, the arguments to the remote procedure are "marshalled," or bundled into a safe form for transmission over a network, and sent as a message to some remote process. The remote process (or the RPC handling layer under it) unmarshalls them, executes the procedure, and then sends back the result. This makes some client-server operations much less painful. There may be more on this if we make it to the distributed systems chapter.