Requirement Specification

The basic requirements are divided into a number of categories, each detailing a certain area of OS functionality.

Process Handling

The operating system should provide the concept of processes that run pseudo-parallel to each other by sharing time on the single processor in the system.

PH1: Process States

• Processes should be possible to block.
• A blocked process should not be able to run until it is unblocked.
• It should be possible to delay a process for a specified amount of time.
• When a process is delayed, it should not be able to execute any code.

PH2: Process Priorities

• Each process should have a priority.
• The number of priority levels should be at least 5.
• Priorities should be specified at process start.
• Priorities might be changeable at run-time.

PH3: Process Scheduling

Scheduling should be highest-priority first, with preemption. In particular:

• A higher-priority process should be scheduled in preference to a lower-priority process.
• Between processes of the same priority, round-robin scheduling should be used.
• Higher-priority processes should be able to preempt lower-priority processes.
• There should be a recurring regular check for which process to run, unrelated to whether a particular task has finished its work.

PH4: Process Identities

• Each process should have a unique ID that can be used to address the process and perform operations on it.

PH5: Process Creation

• Processes should be able to create new processes.
• Processes are created by a spawn operation that starts a new process with a given code to run.
• The spawn operation should return the ID of the created process.
• If the process spawning fails for some reason, an error should be reported.

PH6: Process Termination

• Processes should be able to terminate themselves.
• Processes should be able to terminate other processes.
• The operating system should be able to terminate processes.

PH7: Process Information

• A process should be able to obtain information about another process.
• The information should include priority and other relevant information.

PH8: Resource Recycling

• When a process is terminated, all resources that it has allocated should be reclaimed.
• The operating system should never "leak" memory, if there are dynamically allocated or assigned resources.

PH9: Process Limitations

• There can be a fixed upper limit on the number of processes allowed in a system.
• Process IDs may be reused.
• Any fixed upper limits must be easy to modify, using a #define or similar C construct.

Message Passing

Processes in the operating system should communicate using asynchronous message passing.

MP1: Messages

• Messages are unicast, going from one process to precisely one other process.
• The messages should be able to contain some user data.
• Messages should be tagged with sender and receiver process identities.
• Messages should have a type or priority field for filtering by the receiver.
• It should be possible to pass process identities using messages.

MP2: Message Queues

• Each process should have a single message queue for incoming messages.
• The message queue can have a fixed upper bound on the number of messages stored.

MP3: Sending Messages

• Processes should be able to send messages to other processes.
• The send should not depend on the state of the other process.
• The send operation should report an error if the message queue of the receiving process is full.
• The send operation should never block the sending process.

MP4: Receiving Messages

• Processes should be able to receive messages from their message queue.
• The receive operation should be able to filter messages based on the type or priority of the message.
• The user-defined data specified in the message should be readable by the receiver.
• The receive operation should block the receiving process if the message queue is empty.
• It should be possible to specify a time-out for a receive operation, after which a process will resume operation even if no message arrives, and report an error.

Input and Output

The system has to provide some kind of input and output facility to do interesting work.

IO1: Text Consoles

• The system should provide at least one text console for input and output.

IO2: Interrupt-Driven IO

• Text input and output shall be implemented using interrupt-driven IO on the serial port of the system.

IO3: Text Output

• It should be possible for processes to send text to a console.
• It should be possible to send coherent messages, i.e. a process should be able to send a text message that is printed uninterrupted on a text console.

IO4: Text Input

• It should be possible for a process to request the user to input text.

Other

There are some other requirements that do not fit conveniently under the headings above.

O1: Clock Service

• There should be a clock service in the operating system.
• The clock service should provide the current time and date to processes.
• It should be possible to set and read the current time and date.

O2: No Shared Memory

• Processes should never use shared variables or memory to communicate.
• It is not necessary for the operating system to rigorously enforce this condition.

O3: Reentrancy

It should be possible to execute multiple instances of the same processes concurrently. In particular, this means that:

• A program cannot use "static" variables in C or global variables.
• Any attempts at using names to identify processes has to allow for the dynamic creation of names.

User Programs

The system would be no fun without a set of programs to run on it. For demonstration purposes, you should implement a set of simple user programs.

UP1: Command Shell

The system should have a command shell that can do at least the following:

• Start processes. For example, it shall be possible to start another interpreter.
• Read from and write to the system clock.
• Change priority of processes.
• Obtain information about present processes.
• Terminate processes.
• It should be possible to have more than one shell running simultaneously.
• The command shell should not be special-treated by the operating system in any way.

UP2: Ring

This demonstrates process communication.

• A program should start a set of other processes, P1 to Pn.
• The processes should be set up in a communications ring, where P1 sends messages to P2, etc. on to Pn.
• The demonstration should send some messages around the ring and show that they visit all processes along the way.
• The user should only need to start a single process to start the ring demo: the main program should start the other processes involved.

UP3: Dining Philosophers

This demonstrates process synchronization (you will need to work out how to synchronize processes given the message passing paradigm). The dining philosophers program is a program solving a problem with resource sharing as follows. A group of philosophers are sitting around a dining table (formed as a circle). Between each pair of philosophers is one fork. Occasionally, one philosopher wants to eat and to do that he needs two forks. This means that two philosophers sitting next to each other can not eat at the same time. You should implement this with the following in mind:

• Each philosopher is a process of its own with a behavior that is similar to the following:

  think(random())
  get one fork
  get other fork
  eat(random()) 
  drop forks
  restart

• Like UP3, the entire setup should be started by a single process.

UP4: Text Scroller

There should be a scroller background process that scrolls text on the Malta board LCD display.

• The text can be varied or fixed, depending on the level of ambition.
• The process should provide for smooth scrolling even on a highly loaded system.

EC1: Activate the MMU

In the basic assignment, you do not need to use the MMU of the processor. In this extra credit, you should activate it to provide some basic memory protection. In particular, you need to provide the following functionality:

• The operating system data and code should not be neither readable nor overwritable by applications.
• The data for each appplication should not be readable or writeable to other applications.
• An application should only be able to read or write memory assigned to it.
• Attempts to write or read erroneous locations should result in termination of the misbehaving program.
• A demo application and "application note" should document and demonstrate how your implementation protects the program and operating system from each other.

EC2: Provide Process Supervision

In the basic assignment, each process lives on its own. Nobody else cares if a process terminates. In most real real-time operating systems, processes can be linked together in order to provide fault detection and tolerance. In the extra credit requirement, you should provide the following functionality:

• Processes can be appointed as supervisors of one or more other processes.
• When a supervised process terminates, the supervisor is notified.
• It should be possible to differentiate between controlled and uncontrolled termination, i.e. it should be possible for the supervisor to see if a subordinate process has crashed or if it terminated in good order.
• To provoke crashes, the semantics of the send operation is changed so that a process terminates if the receiving process has a full message queue.
• A demo application and application note should describe the mechanism and demonstrate that you have a working implementation of process supervision. The demo should include a supervisor that restarts its subordinates if they crash.

EC3: Dynamic Memory Management

In the basic specification, it is allowed to have a fixed limit on the number of processes in the system, as well as fixed-length message queues. It is also not at all necessary to provide dynamic memory allocation as a service to user processes. In this extra credit requirement, you should remove these limits. In particular:

• There should be a kernel module responsible for dynamically allocating memory for various purposes.
• There should no longer be a compile-time fixed upper bound on the number of processes in the system, process control blocks should be allocated dynamically.
• Message queues should be dynamic in size, allocating space only as needed.
• Out-of-memory situations have to be gracefully handled.
• A demonstration application should be written that demonstrates creation of processes and/or messages until memory runs out.
• A demonstration application should be written that demonstrates the use of dynamic memory allocation in a process.