Chapter 1

Project Introduction

1. Introduction

The course project is the design and implementation of a simple operating system for a simple hypothetical machine: the Z502 computer. You are given a simulator for the Z502 machine, along with a number of test programs that exercise the required features of your operating system. You are required to write your version of the OS502 operating system and, optionally, any special test programs that you desire.

The remainder of this document gradually introduces the components of the project and the minimum requirements of each project part of your operating system. In order to finish each project part, it is only necessary to read this document as far as the assignment for that phase, along with related reading from the course textbook, lecture notes, and the appendices of this document. You may, however, find it interesting to read through the entire document to get a perspective on the whole project, and to plan ahead for later phases.

2. Project Goals

The two project parts cover the following general areas:

  1. The basics of an interrupt system in relation to a multiprocess, non-virtual-memory environment and familiarization with the simulator and with programming.
  2. Virtual memory support; page fetch, replacement algorithms and shared memory; disk driver support.

Throughout the project you will have considerable flexibility in designing your own algorithms and data structures. There are also many interesting ways in which the minimum project requirements can be extended, and you are welcome to explore in any direction that interests you. When making design decisions, you will often find yourself making efficiency tradeoffs (for example, between the time required to perform an operation and the space required for the associated data structures). You should explain such decisions in your documentation. In some cases, you may be able to imagine an extremely efficient and sophisticated design that would be rather complicated to implement. You should avoid such solutions unless you have first implemented and debugged a straightforward solution. The amount of work required to design, implement and debug a straightforward solution is already considerable, and you are not required to go beyond the basic requirements. In blunt terms, please resolve efficiency/simplicity tradeoffs in favor of simplicity, even if you are aware that such a choice would not be acceptable in a real operating system. If you wish, and if time and resources allow, you may consider implementing more complex designs after the minimum project is complete. This method of development should also enhance the modularity of your operating system, as once your system is working, you should be able to substitute an easy but inefficient algorithm for a more complicated design without endangering other components of your code.

3. The Z502 Machine

Your operating system will be written for the Z502 computer, a hypothetical machine designed for use in this Computer Systems course. The Z502 machine is a 32bit/word minicomputer. Its advanced multi-register CPU sports numerous instructions, virtual memory support, and a multi-level interrupt scheme.

The Z502's advanced architecture has several features that are of particular interest to Operating System designers: (For the details of the Z502 machine, including registers, instruction set, and memory management support, see Appendix A.)

  1. The CPU may operate in one of two modes: user and kernel. In user mode, the machine executes the C (or other ) language and user system calls as defined in Appendix C. In kernel mode, the C (or other) code that you write and link with the simulator is executed. In addition, programs running in kernel mode are able to manipulate the machine in privileged ways that programs running in user mode cannot (e.g. issue I/O instructions, change address translation tables, etc.). Specialized instructions exist in both modes to switch from one mode to another, and in kernel mode from one program to another. Since a program in kernel mode is given control of the machine, it is the logical choice for most of an operating system.
  2. The Z502 includes the hardware and CPU features necessary to support two types of memory system: identity translation, and full page translation. Thus, the system can be configured for many applications. With the identity translation, programs are non-relocatable and statically loaded. With page translation, a full virtual memory operating system is possible. All references to memory addresses are interpreted as virtual addresses and are translated to physical addresses before each memory access takes place. The conversion from virtual to physical addresses is performed automatically by the hardware via a Page Table that is completely under the control of the operating system.
  3. To allow control of processor allocation and measurement of resource consumption, the Z502 has both a timer and a clock. The timer allows the operating system to gain control after a certain period has elapsed, while the clock allows the operating system to provide time-of-day functions as well as the time-stamping of events.
  4. The Z502 comes with a disk drive and a clock. Device integrity is protected by only allowing transactions with the devices in kernel mode, thus placing them under the control of the operating system. I/O transfers proceed in parallel with the central processor to achieve maximum processor use. Communication from the devices to the CPU is implemented via an interrupt system and specialized registers.

Because the Z502 is intended as a general purpose machine, it is available in several configuration options. The amount of memory, address translation scheme, and number of disks can all be varied. An operating system for the Z502 should be tailored for the address translation scheme, but should, of course, run with any number of disks and amount of memory.

4. The Development Environment

To aid your development of an operating system we provide a simulator (not hypothetical, we hope) for the Z502 machine on your "real" machine OS. The combination of Your "Real" Machine Operating System (YRMOS) and the simulator constitutes the environment for your development effort.

The Z502 simulator is a program that provides a thorough simulation of our hypothetical Z502 computer. As shown in Figure 1.1, your operating system will run under the control of the simulator, while the simulator runs under the control of YRMOS. The simulator simulates privileged instructions, Z502 devices, and interrupts. Upon system startup, i.e., when the simulator is first invoked from YRMOS, the simulator performs necessary initialization (i.e., simulating hardware bootstrap) and transfers control to the entry point of the operating system (i.e., the function os_init() in the operating system). From the point of view of your operating system, the behavior of the simulator is virtually identical to that of the Z502 machine described in the previous subsection and detailed in Appendix A.

The development environment comes with test programs designed to measure your success in implementing OS502. (described in Appendix B).

5. Unrealistic Aspects of the Project

The unrealistic aspects of the project fall into two categories: hardware simplifications in the Z502 that remove certain complexities that occur in real systems, and unrealistically simple requirements for the operating system functionality.

5.1 Hardware

  1. The Z502 interrupt system guarantees that no interrupts will be missed or lost. In a real system lost interrupts are possible if the software is not properly designed and the latency associated with responding to an interrupt has the potential for being too long.
  2. The Z502 hardware is completely error-free (we hope). In real operating systems, a large part of the code is concerned with error recovery and diagnostics.
  3. The very small page sizes of the Z502 family are unusual, but were chosen so that small amounts of memory would be required on your real machine.
  4. In the Z502 kernel mode (i.e. from the point of view of your code), the amount of memory available for operating system data structures can be considered to be unlimited. In a real operating system, much design is concerned with the allocation of space for operating system data areas. Operating system performance is usually strongly affected by the amount of space it consumes. In systems that do not page the kernel, less is better.

5.2 Functionality

  1. You are allowed to assume a non-hostile user environment. This allows protection and security issues to be largely ignored.
  2. You are allowed to assume that all processes require a fixed, statically allocated amount of virtual memory. If processes dynamically allocate and free space, it is from within a fixed area allocated at compile time. You may assume that the process makes no memory allocation requests to the operating system at run time. Thus, no dynamic virtual memory allocation issues need be addressed.
  3. You are not required to support a general inter-process communication mechanism, that is included in most real operating systems. Support of system calls that give a subset of inter-process communication is a part of Project 1.
  4. In order to be portable, the Z502 assumes the underlying YRMOS is uniprocess and unitask. Given this, it's real tough building a multiprocess system. In a real system, an exception can happen any time; here it will occur only while you're making a hardware request or when using the "CALL" macro. To give the "illusion" of multiprocess, you must do two things:
    1. References to all subroutines within your OS must use the CALL mechanism explained in Appendix C. NOTE that you should use "ZCALL" when calling a hardware routine and "CALL" when referencing one of your OS502 routines.
    2. Follow these simple rules: ALWAYS just "return" from an interrupt; NEVER return from a fault, but ultimately cause a context switch, starting a different process.