| 6.033 - Computer System Engineering (Spring 2003) | Handout 13 - March 7, 2003 |
The motes are designed to be scattered throughout an environment (such as a factory floor, animal habitat, etc) and dynamically form a network of sensors. These "sensor networks" are an active field of research in the systems community ( [TinyOS] [TinyOS2] [DARPA SENSIT] [ACM Sensor Networks Conference]). The job of the motes is to work as a group to efficiently collect data and relay it periodically to a collection site. The motes run until their batteries die at which time they are thrown away and replaced by a fresh mote.
This particular configuration of motes will be deployed throughout an academic building and be used as a test-bed for developing new sensor network software. Researchers will write small programs (1K to 4K of object code and data) and upload them to the motes. A copy of each program will be run on every mote. Each program is annotated with the amount of space it should initially be allocated. These programs will perform duties such as collecting sensor information (room temperature, stress on the building, etc.) and communicating with other nodes. Researchers may also remove programs from the motes (to upload a new version or to free up space for other programs).
We are uncertain about how the programs will behave. You should state what expectations you have for the program behavior (i.e. how often it accesses main memory, how much computation it does) and how a program that behaves differently would perform under your design.
Importantly, the researchers are from different Universities and the programs are independently developed: you must ensure that one program is not able to damage another by overwriting any part of another program's memory space (i.e. an application should not be able to perform a STORE to a piece of memory belonging to another application). You should protect against accidental damage from another program; malicious programs are beyond the scope of this assignment. You are only concerned with interactions between programs; You do not have to worry about fine-grained protection within a programs address space (e.g. read-only text segments, etc).
While the operating system provides scheduling and networking support, it does not enforce memory protection. Your job is to design the system which protects programs from one another. Your system will interact with both the hardware of the mote and its operating system. You need to supply the design of a memory management unit to the CPU implementors; the operating system implementors want to know what you need them to do on a context switch and how to allocate and deallocate protection domains.
The hardware team wants your thoughts on an MMU: A system for translating the virtual address which will be produced by programs into physical addresses which can be understood by the memory system. In the figure below, your job is to fill in what goes in the bold box labeled MMU.
Your design need not necessarily require hardware changes, however. You may assume that your system can inspect and modify the programs before they are sent to the motes: it may be possible to design a software only protection system this way.
You will need to implement several small parts of the operating system which interact with loading programs safely. These calls use a PID datatype. PIDs are unique identifiers that the operating system assigns to each process. Assume that the OS assigns each process a PID when it is first uploaded.
The operating system implementors have provided you with a "hook"
for performing memory management tasks on a context switch. You should
provide them with a description of how the following function should
be implemented (in the following function definitions [in] denotes a read-only parameter and [out] denotes a read-write parameter):
on_switch ([in]PID current_pid, [in]PID new_pid);
on_switch will be called whenever by the operating system's scheduler whenever the currently running process is about to be changed. You should take whatever action is necessary to make sure the new process can access its memory (and only its memory). This action may involve manipulating the state of the CPU or accessing/altering in-memory data structures.
The operating system will also handle receiving new programs via the packet radio. When a new program is received the operating system will call
bool new_protection_domain ([in]int req_size, [in]PID id,
[out]mem_region[] regions)
struct mem_region {
ADDRESS start;
int length
};
new_protection_domain returns a list of regions of memory whose total size is at least req_size bytes. If req_size bytes of memory are not available new_protection_domain should return false indicating a failure. new_protection_domain returns a list of regions (instead of a single, contiguous block) since some memory protection schemes may patch together discontiguous regions of physical memory into a virtual address space. From an implementor's perspective (that's you), new_protection_domain should do what is necessary to create a new protection domain of the indicated size and, for each region, return the address of the start of the region in physical memory and its size. The id parameter will be used by the operating system to identify the domain in the future (e.g. in calls to on_switch).
Note that the operating system does not provide any sort of memory isolation for programs. It will blindly load the program at the location you specify and will not check any references made by the program for validity.
A corresponding call deallocates the memory associated with a process when it is removed from the mote.
void destroy_protection_domain ([in]PID id);
This call should make all memory owned by PID available for reuse. It is not necessary to zero or blank the memory in any way.
Note that all solutions to this problem are required to report protection faults to the operating system. Since some designs may require the operating system to handle additional faults (hint (for some designs): TLB miss), specifying the API of the fault handler is part of your assignment. In implementing the fault handler you may include additional changes to the operating system and/or the CPUs ISA (assume the ISA includes no calls related to memory protection).
Programs are annotated with an initial memory size. However, a program can increase the amount of memory it uses dynamically by calling into the operating system. To allow this behavior, you should implement the following call:
bool grow_protection_domain ([in]PID id, [in]int size,
[out]mem_region[] regions)
This call attempts to increase the size of the protection domain PID by size bytes. If size bytes are not available, the call should return false, indicating failure. The frequency with which grow_protection_domain is invoked will affect your design. In your report, spell out how often you expect this routine to be invoked and why that estimate is realistic (e.g. the routine will not be invoked often because we require programs to be annotated with their maximum possible size). The output parameter (regions) should contain a list of all of the memory allocated to the program after the call (i.e. any memory previously allocated to the program and any new memory you allocate in grow_protection_domain.
The design space is not limited to designs which utilize all of the flexibility provided by hardware and the operating system; your design could require no action on a contect switch (for example) or require no additional hardware and still be correct.
Because the mote is so small, it has very strict resource limitations in terms of energy. Your design will have to cope with the tradeoffs (against performance, simplicity, etc.) introduced by these limitations. The energy costs for different components of the mote are given in the following table:
Energy costs (mA)
In addition to current draw you should also consider several other design criteria. Your design should efficiently utilize memory. Quantify how many programs you expect to be able to fit into the mote's 32K of memory and how much memory is wasted. Your design should provide protection as well as efficient access to memory. Quantify the overhead of your system: how many main memory accesses (on average) are required per LOAD/STORE operation. Your design should not require excessive hardware. Specify exactly what additional components you have added and justify their added cost (example: adding 8,000 registers to cache protection bits for each word of memory is not justifiable).
When discussing your design you should compare your design to other possible designs with respect to the criteria above and argue why the tradeoffs you made are appropriate.
Your design should meet the following requirements:
You should complete the following tasks:
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 (single spaced).
Who is the audience for this 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.
Following are some tips on the organization of a design report. You can find other helpful suggestions on writing this kind of report in the M.I.T. Writing Program's on-line guide to writing Design and Feasibility Reports. You may also want to look at the Mayfield Handbook's explanation of IEEE documentation style. A very good book on writing style is: "The Elements of Style," by William Strunk Jr. and E. B. White, Third Ed., MacMillan Publishing Co., New York, NY, 1979. (An older version is also available online or from the MIT libraries.)
Title
Give your design report a title that reflects the subject and scope of your project.
Abstract
A good paper begins with an abstract. The abstract is a 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. Abstracts are normally about 150 words or ½ page. Write the
abstract after you have written your report.
1.0 Report Introduction
Explain the rationale for the project. Provide a problem statement and
a statement of purpose. You may assume that the reader has read the
DP1 assignment: you do not need to restate the problem in detail.
2.0 Design Overview
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.0 Design Description
Explain and elaborate your solution. 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. (Some writers add a separate section to their report that specifically addresses performance analysis.)
4.0 Feasibility
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.)
References
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.
IV.2. How do we evaluate your report?
When evaluating your report, your instructor will look at both content and writing.
Some content considerations:
Some writing considerations:
Phase Two writing considerations (Juniors and Seniors)
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.
CIM Considerations (Sophomores) Your design report will constitute your writing grade for the Communication Intensive requirement.
| Go to 6.033 Home Page | Questions or Comments: 6.033-tas@mit.edu |