Homework 1 solution key 1.1 a) Two problems: A single user could run programs in such as a way as to consume more than their share of resources, and users might be able to access each other's private files. b) You'll never assure the same degree of security (especially if each user has physical access to the machine), but you can come pretty close if you structure the operating system to explicitly enforce this goal. The key is removing or controlling access to shared resources (e.g. have separate filesystems rather than permissions in a single filesystem) 1.4 a) Batch programming is kind of the bread and butter of some realtime operating systems (especially ones that run factory machines where they execute a series of established processes). It's probably pointless for handheld systems, where the applications are usually interactive with the user. b) Virtual memory The real distinction is not between handheld and realtime operating systems, but in the hardware their targeted for. There exist some handheld devices and some embedded controllers (running realtime OSs) that have only one level of memory, and so don't need VM support, but others that have multiple levels, and do need the support. c) Time sharing Time-sharing is splitting the CPU in such as way as to simultaneously support two or more interactive processes. Some handheld devices (like the early Palms) only ran one app at a time, but others try to look like a little desktop computer, and you can switch around between applications, so the necessity of time-sharing is not so clear. Realtime systems, on the other hand, are almost by definition time-sharing (it would be pointless to have all that infrastructure for scheduling and meeting deadlines if there wasn't time-critical CPU sharing). 1.6 Multiprocessor systems share more resources (e.g. main memory, peripherals, etc.) between the processors than clustered systems, since multiprocessors are usually in the same machine case. Communcation between processors and assorted resources is also faster in a multiprocessor system. Clustered machines need some communications infrastructure (like a network) and software designed to allow them to cooperate (the software must be aware it is running on a cluster). To implement a specifically a highly-available service, the software must also be able to adapt to the loss of one of the cluster machines (i.e. it must be able to shift work to the other machines). 1.11 a) The interface is the same (a device driver notifies the device controller). The driver just gets out of way afterwards. b) A single interrupt is generated when the transfer is complete c) Obviously the program waiting on the DMA transfer cannot execute, even though the CPU is free. Potentially, of course, the DMA could stomp on memory being used by the programs, but in practice there is strict enforcement of what parts of memory are written to. 1.x First, the fact that the system is single-user shouldn't change things: computing has gone from several people with one job each sharing the same computer to a single user with many jobs (think of all the applications you run). The problem remains roughly the same: how do I split the resources of the machine among these clients? Second, while processors have become faster and memory larger, programs have increased in complexity (or at least resource requirements) as well. Even if you argue that computer advancement has outpaced software, we have new resources (like network bandwidth) that we probably all agree there's not enough of and thus requires efficient management. 2.2 For some examples: 1) Supporting multiprogramming of the CPU. This would be (nearly) impossible to do at the user level, requiring explicit cooperation between processes (and there would be no enforcement) 2) Providing a single point of configuration for devices. Recall that this used to be done at user level (e.g. each program had its own printer configuration), but its much more convenient to have it all in one place. 3) User interface. Each program could have its own, but providing a user interface at the OS level allows programs to share the same screen at the same time) and provide a consistent look-and-feel (so users don't have to learn multiple UIs) 4) Protection and security. Absent an operating system, protection would rely on cooperation. Obviously this won't be effective in any situation where we would actually need protection, since in those cases at least one person isn't cooperating. 5) Communication stacks. Each program can provide it's own (there are many user-level implementations of network stacks), but it saves a lot of programming and configuration effort to put it in the OS. 2.9 Separting the two is necessary because policies often change. If we were to integrate the two, a new policy would require a new mechanism. This would increase programming effort and provide another source of potential error. 2.12 Microkernels make it easier to extend the operating system (a change is just a new module) and are better from a software engineering perspective (modularity is always a good goal). However, they require that a "user" program (in the traditional sense of the word) interact with a system service (also at the user-level) by passing messages in and out of the kernel. This leads to more kernel/user crossings (an expensive operation) and thus performance is degraded. 2.14 An operating-system designer can use virtual machines to ease development, by allowing a test OS to be run on the same machine it is developed on, and shortening boot time by bypassing the physical hardware. Users can run programs without thought of the underlying hardware or OS, useful if they want to run a program developed for Linux simultaneously with one developed for Windows. 3.1 The long-term scheduler decides which processes to accept into the job pool to maintain an appropriate level of multiprogramming. The short-term scheduler select the next job to run on the CPU out of this pool when the CPU is freed. The medium-term scheduler monitors the job pool and makes changes by swapping out processes to maintain the multiprogramming level or mix. 3.2 After some notification of a process switch (an interrupt, say), the CPU must save the PCB of the outgoing process, execute the short-term scheduler to determine the next job to run, load the PCB of the incoming process, and start execution at the saved program counter. It may also need to invalidate cache entries or other miscellaneous tasks. 3.5 a) Synchronous communication is easier to program and more natural to think about (ask for response, wait for response). However, we can't get other work done while blocked on messages, which might waste productive time. b) Explicit buffering is basically synchronous communication (as automatic corresponds to asynchronous), so the same tradeoffs from a) apply. Additionally, automatic buffering requires more implementation at the system level (i.e. you actually have to write all that buffering code). c) Send by copy is a more natural model of programming (you don't have to worry about who might have a copy of a particular variable) and can be more secure (the receiver can't affect the sender's data), but can be inefficient for large data structures, both because you have to make a copy to pass, and because changes cannot be made directly but instead relayed back through the sender. d) Fixed-size messages are easier to implement (e.g. since you can assume a particular message size, it makes it easier to allocate memory). However, they can waste resources (if you send a message smaller than the fixed size, you waste the rest of the message space; if you send one larger than the size, you may be paying extra overhead by having to split it into multiple messages), which is not the case using variable-size messages. If the program has to interface with the fixed-sized message system, there can also be programming overhead associated with splitting messages.