I. Introduction

Your boss at the Amazing Computer Company walks into your office one day and says "I'm impressed with the idea of enforced modularity that you've been telling me about, and I wonder whether we can extend the idea to protection of individual modules within a single address space. I've talked to some of the 6.033 staff about this, and developed the following preliminary plan."

The basic idea is to arrange memory as a single address space, which all programs (and the operating system) share. The benefit of this idea is that it makes sharing very easy -- any program can refer to any piece of data, even data in another program. The hard part is providing isolation as well as sharing.

In order to help provide isolation, your boss suggests arranging the single address space as as a set of "segments". Addresses manipulated by programs consist of two parts, a segment number and an offset within the segment. Each segment individually consists of a linear array of bytes. The CPU uses the segment number in an address to index into a segment table with an entry for each segment. The operating system creates and maintains the segment table. Fields in the segment table entries indicate to the hardware which segments the currently executing program is allowed to read, write, and execute.

As a simple example of the benefits of this arrangement, consider what happens when two instances of a program are running. To save space in main memory, both instances should execute the same code; this is easy to arrange by placing the code in its own segment. But each instance should also have its own mutable data (for example, its own heap and stack). Thus each instance should have its own data segment.

As a more complex example of isolation and sharing, consider the relationship of a program and the operating system kernel. On the one hand, the kernel must be isolated against reads and writes from ordinary programs; putting it into its own segment(s) and marking those segments inaccessible takes care of this. On the other hand, the kernel is also a resource shared among the running programs; programs need to be able to make system calls into the kernel, and the kernel must be able to read and write program memory. A well designed segment system should support the notion of a kernel using general-purpose mechanisms.

Your boss asks you to work out a design of a segmented address space for your company's computer hardware and operating system (AmazOS). The computer's instruction set architecture is the same as that of the 6.004 Beta. You can find Beta documentation here. You are allowed to change the instruction set if you need to. You should omit the supervisor bit from the PC, and use your general purpose segment mechanisms instead.

Your job is to design the data structures and algorithms for managing segments. The Beta CPU you'll start with has no virtual memory support; all addresses directly refer to physical memory (a contiguous linear array of bytes). Most of your design will be implemented in a memory management unit (MMU) to be added to the basic Beta computer. Your design will likely involve tables in main memory that the MMU consults.

II. Getting Started

struct SegmentDescriptor {
  int physAddr; // Start of segment's physical memory.
  int length;   // Number of bytes of physical memory.
  int mode;     // 0: invalid; 1: read and write; 2: read only;
                // 3: read and execute only
};

The MMU intercepts the 32-bit virtual addresses that programs generate; these addresses include program counter values for instruction fetch and the targets of LD, ST, JMP, and branch instructions. The MMU treats the upper 8 bits of a virtual address as a segment number and the lower 24 bits as the offset within the segment. The MMU indexes the Segment Table using the Segment Table Address register and the segment number from the virtual address, and fetches the Segment Descriptor. The MMU signals a fault if the kind of access the program is making is not allowed by the mode field. Similarly, the MMU signals a fault if the offset from the virtual address is not less than the segment's length. Otherwise, it generates a physical address by adding the Segment Descriptor's physAddr to the original address' 24 bits of offset, and sends this address to the memory system.

You will find that you have to change and extend the simple design outlined above. For example, your design might add new fields to the SegmentDescriptor, or delete the mode field and replace it with some other protection mechanism, or create new tables that the MMU knows about. The design requirements discussed below will guide the changes you make.

III. Design Guidelines

Your design description must specify the following:

• the algorithm that the MMU uses to translate virtual addresses to physical addresses;
• the format of the tables in memory that the MMU consults;
• any other significant internal state that the MMU maintains (such as registers pointing to tables);
• the interface between the MMU and the CPU; and
• any extensions or changes to the CPU's instruction set architecture that you require.

Your MMU algorithms and data structures must be able to support the program and operating system features listed below. Your paper should outline how your MMU supports each feature. It may be the case that the operating system, the compiler, and/or programs need significant changes to do their part in supporting these features; you do not need to describe these changes in great depth. The point is to argue that your MMU mechanisms are sufficient to make the features possible.

• Multiple programs must be able to share the single address space provided by the CPU. A program must be able to allocate new segments to hold data. A program should be able to indicate whether other programs are allowed to read, write, or execute its segments. It is enough if the MMU supports a few hundred segments in total.
• It must be possible for a program to ensure that no other program can read or write any of its data, or write any of its executable code. That is, your design must be able to enforce modularity. You should present a careful argument that this is the case.
• Multiple instances of single program (e.g. /usr/bin/emacs) must be able to share that program's executable code segment. Each instance must also be able to have its own segment(s) to hold variables and the stack. You must describe how it is that the same executable code segment can refer to different variable segments depending on which instance of the program is running.
• The kernel must be implementable as one or more segments, protected against direct reads and writes by programs. The kernel must be able to read and write all segments.
• Programs must be able to make system calls into the kernel. You should describe the mechanics of system call and return; for example, specify the instructions a program must use to make a system call, the actions the hardware takes when switching into the kernel, and the instructions the kernel uses to return to a program.
• During a system call, the kernel may switch to a different thread, perhaps in a different program. You should describe how (if at all) the kernel must must change the MMU's state or tables as part of such a context switch.
• There must be a way for a running program to start other programs. You should try to make this possible using general-purpose mechanisms; for example, the first step might be for the running program to allocate a segment to hold the executable code of the new program.

• How to allocate physical memory to store segment contents.
• Interrupts or faults. For example, don't worry about how the faults signaled by your MMU are handled.
• Paging or swapping; you can assume that everything fits in main memory.
• Optimizing performance. For example, don't bother adding caches to your design to speed it up; this can be done later when more is known about the design's performance.
• Thread synchronization; you can assume that if multiple threads share a data structure, they take care of their own synchronization.
• Multiple CPUs; you can assume there is only one CPU in the computer.

Where appropriate, you should describe your design using pseudo-code and diagrams of data structures. Remember to indicate explicitly what is executing the pseudo-code (the O/S, the memory management unit, the application, etc.). You may wish to re-read Chapter 2-B of the notes to get presentation ideas; you are designing a system with goals similar to the page-based virtual memory system described in 2-B.

IV. Your report

IV.1. Suggestions on Writing Style

Your paper should be as long as is necessary to explain the problem, your solution, the alternatives you considered, and the reasons for your choices.  It should be no longer than that.  We estimate that a good paper will be 8 to 10 pages in length.

A good paper begins with an abstract.  The abstract is a very short summary of the entire paper.  It is not an outline of the organization of the paper! It states the problem to be addressed (in one sentence).  It states the essential points of your solution, without any detailed justification.  And it announces any conclusions you have drawn. Good abstracts can fit in 100-150 words, at most.

The body of your paper should expand the points made in the abstract. Here you should:

1. Explain the problem and the externally imposed constraints.

    You should explain to your intended audience the background of the problem in terms that the audience can understand.

2. Explain and elaborate your solution.

    Be sure to explain the approach or architecture conceptually before delving into details, components, and mechanics. (Remember, you aren't writing a mystery novel!) Present any analysis clearly and concisely.

3. Show how your solution satisfies the constraints and solves the problem (or how it fails to do so);

    Explain how the properties of your solution that result from choices you have made in your design are reasonable or desirable in the context of the problem statement.  Include analysis of the estimated (or measured, if it applies) performance characteristics of your solution.

4. Describe the alternative approaches that you considered and rejected, and why you rejected them.

    Your paper will be more convincing if you say not just why your idea is good, but why it is better than the alternatives.  (For example, if another approach would meet all of the objectives perfectly, but the cost would be 100 times higher, then you should mention that as a reason for choosing your less general but cheaper approach.)

5. Document your sources, giving a list of all references (including personal communications). The style of your citations (references) and bibliography should be similar to the styles in the technical papers you're reading in this class. In particular, a bibliography at the end and no citations in the text of your paper is insufficient; we'd like to see what specific pieces of information you learned from where as we read your paper.

Write for an audience consisting of colleagues who took 6.033 five years ago. That is, they understand the underlying system and network concepts and have a fair amount of experience applying them in various situations, but they have not thought carefully about the particular problem you are dealing with. Assume that your paper will also be used to convince management that you have a viable design. Finally, give enough detail that they can turn the project over to an implementation team for implementation with some confidence that you won't be surprised by the result.

IV.2. How do we evaluate your report?

When evaluating your report, your instructor will look at both content and writing.

Some content considerations:

• Does your solution actually address the stated problem?
• Do you explain your decisions and the trade-offs?
• How complex is your solution? Simple is better, yet sometimes simple won't do the job. But unnecessary complexity is bad.
• Is your solution a good fit with the goals of the system?
• Is your analysis clear?

• Is the report easy to comprehend?
• Is it well organized and coherent?
• Does it use diagrams where appropriate? (A frequent problem when people use word processors is that they try to express everything in words, either because the word processor doesn't make it easy to include diagrams, or they haven't ever learned how to use the drawing features. Pictures can communicate some ideas far better.)
• Does it use the concepts, models, and terminology introduced in 6.033? If not, does it have a good reason for using a different universe of discourse?
• Does it address the intended audience?
• Is there a good abstract and bibliography?

Phase Two writing considerations

If you are enrolled in the 6.033 writing practicum, you don't need to do anything special; your practicum instructor will explain how the report will get you credit for the Phase II writing requirement. If you are not enrolled in the practicum, and you want us to forward your design project report to the writing program as your phase II writing project, please give us two copies, one of them marked "Phase II". We will forward it to the writing program. Note also that the writing program has a rule that they will accept only reports that earn a B or better from the class in which they originate. Finally, be aware that the second design project will be a team project, and is thus not suitable for Phase II.

V. Collaboration

VI. Schedule