Initial definitions

CPU

The central processing unit (CPU) is the electronic circuitry within a computer that carries out the instructions of a computer program by performing the basic arithmetic, logical, control and input/output (I/O) operations specified by the instructions. ¹

Register

A processor register is a quickly accessible location available to a computer’s central processing unit (CPU). Registers usually consist of a small amount of fast storage. ² A CPU only has a small number of registers.

Memory

Memory refers to the computer hardware integrated circuits that store information for immediate use in a computer; it is synonymous with the term “primary storage”. ³ The memory is much slower than the CPU register but much larger in size.

Computer system

A typical computer system consists of a CPU, memory and external devices such as hard drives (disks), keyboard, screens, mouse and printers. The CPU and the device controllers can execute in parallel, competing for memory cycles. To ensure orderly access to the shared memory, a memory controller is provided whose function is to synchronize the access to the memory.

Input/Output (I/O)

In computing, input/output or I/O (or, informally, io or IO) is the communication between an information processing system, such as a computer, and the outside world, possibly a human or another information processing system. Inputs are the signals or data received by the system and outputs are the signals or data sent from it. The term can also be used as part of an action; to “perform I/O” is to perform an input or output operation. ⁴

For our purposes, any transfer of information between the CPU/Memory and any of the external devices is considered I/O.

Usually I/O operations does not make use of the CPU but are handled by the external devices.

Operating system

An operating system (OS) is system software that manages computer hardware and software resources and provides common services for computer programs. ⁵ The OS controls the hardware and coordinates its use among the various application programs for the various user.

Program, executable and process

In order to execute a program, the operating system must first create a process and make the process execute the program.

Program

A set of instructions which is in human readable format. A passive entity stored on secondary storage.

Executable

A compiled form of a program including machine instructions and static data that a computer can load and execute. A passive entity stored on secondary storage.

Process

An executable loaded into memory and executing or waiting. A process typically executes for only a short time before it either finishes or needs to perform I/O (waiting). A process is an active entity and needs resources such as CPU time, memory etc to execute.

CPU context (CPU state)

At any point in time, the values of all the registers in the CPU defines the CPU context. Sometimes CPU state is used instead of CPU context.

More generally, a task context is the minimal set of data used by a task (which may be a process or thread) that must be saved to allow a task to be interrupted, and later continued from the same point. ⁶

Kernel

The kernel is a computer program that is the core of a computer’s operating system, with complete control over everything in the system. ⁷

Dual mode operation

In order to protect the operating system from user processes two modes are provided by the hardware: user mode and kernel mode.

Dual mode operation place restrictions on the type and scope of operations that can be executed by the CPU. This design allows the operating system kernel to execute with more privileges than user application processes.

Synchronous and asynchronous events

Synchronous means happening, existing, or arising at precisely the same time. ⁸ Asynchronous simply means “not synchronous”.

If an event occurs at the same instruction every time the program is executed with the same data and memory allocation, the event is synchronous. An synchronous event is directly related to the instruction currently being executed by the CPU. On the other hand, an asynchronous event is not directly related to the instruction currently being executed by the CPU.

Exceptions and interrupts

Interrupts and exceptions are used to notify the CPU of events that needs immediate attention during program execution.

Exceptions and interrupts are events that alters the normal sequence of instructions executed by a processor. Such events correspond to electrical signals generated by hardware circuits both inside and outside the CPU chip.

Exceptions are internal and synchronous

• Exceptions are used to handle internal program errors.
• Overflow, division by zero and bad data address are examples of internal errors in a program.
• Another name for exception is trap. A trap (or exception) is a software generated interrupt.
• Exceptions are produced by the CPU control unit while executing instructions and are considered to be synchronous because the control unit issues them only after terminating the execution of an instruction.

Interrupts are external and asynchronous

• Interrupts are used to notify the CPU of external events.
• Interrupts are generated by hardware devices outside the CPU at arbitrary times with respect to the CPU clock signals and are therefore considered to be asynchronous.
• Key-presses on a keyboard might happen at any time. Even if a program is run multiple times with the same input data, the timing of the key presses will most likely vary.
• Read and write requests to disk is similar to key presses. The disk controller is external to the executing process and the timing of a disk operation might vary even if the same program is executed several times.

Exception and interrupt handler

When an exception or interrupt occurs, execution transition from user mode to kernel mode where the exception or interrupt is handled. When the exception or interrupt has been handled execution resumes in user space.

System call

A user program requests service from the operating system using system calls. System calls are implemented using a special system call exception. Another name for exception is trap.

Exception and interrupt handling

What should be done when an exception or interrupt occurs?

Overview

When an exception or interrupt occurs, execution transition from user mode to kernel mode where the exception or interrupt is handled. When the exception or interrupt has been handled execution resumes in user space.

Details

When an exception or interrupt occurs, execution transition from user mode to kernel mode where the exception or interrupt is handled. In detail, the following steps must be taken to handle an exception or interrupts.

While entering the kernel, the context (values of all CPU registers) of the currently executing process must first be saved to memory.

The kernel is now ready to handle the exception/interrupt.

1. Determine the cause of the exception/interrupt.
2. Handle the exception/interrupt.

When the exception/interrupt have been handled the kernel performs the following steps:

1. Select a process to restore and resume.
2. Restore the context of the selected process.
3. Resume execution of the selected process.

CPU context (CPU state)

At any point in time, the values of all the registers in the CPU defines the context of the CPU. Another name used for CPU context is CPU state.

Saving context

The exception/interrupt handler uses the same CPU as the currently executing process. When entering the exception/interrupt handler, the values in all CPU registers to be used by the exception/interrupt handler must be saved to memory. The saved register values can later restored before resuming execution of the process.

Determine the cause

The handler may have been invoked for a number of reasons. The handler thus needs to determine the cause of the exception or interrupt. Information about what caused the exception or interrupt can be stored in dedicated registers or at predefined addresses in memory.

Handle the exception/interrupt

Next, the exception or interrupt needs to be serviced. For instance, if it was a keyboard interrupt, then the key code of the keypress is obtained and stored some where or some other appropriate action is taken. If it was an arithmetic overflow exception, an error message may be printed or the program may be terminated.

Select a process to resume

The exception/interrupt have now been handled and the kernel. The kernel may choose to resume the same process that was executing prior to handling the exception/interrupt or resume execution of any other process currently in memory.

Restoring context

The context of the CPU can now be restored for the chosen process by reading and restoring all register values from memory.

Resume

The process selected to be resumed must be resumed at the same point it was stopped. The address of this instruction was saved by the machine when the interrupt occurred, so it is simply a matter of getting this address and make the CPU continue to execute at this address.

Waiting for keyboard input

Humans are very slow compared to the CPU. No matter how fast you are, the CPU will be able to execute a huge number of instructions between every key-press you make.

• How can we make the CPU wait for a human user to press a key on the keyboard?
• Is it possible to make the CPU do something useful while waiting for user input?

Polling

To detect a key-press, one option is to repeatedly check the state of the input device until the device has detected a key press. Usually such a device will use one bit in a special device register to signal whether no input has occurred (bit = 0) or if new input is available (bit = 1).

Polling refers to actively sampling the status of an external device at regular intervals. Polling requires the use of the CPU to check the status of an external device. Polling also refers to the situation where a device is repeatedly checked for readiness, and if it is not the computer returns to a different task between checking the status.

Polling is most often used in terms of input/output (I/O), and is also referred to as polled I/O or software driven I/O.

More generally, polling can be summarized as follows.

1. A program cannot proceed until an external device becomes ready.
2. The program checks the status of the external device.
1. If the device is not ready, the program either:
1. Do some work not depending on the status of the device for a short amount of time, then go back to step 2.
2. Gives the CPU to another program, and then when the operating system gives it the CPU back again, go back to step 2.
2. The device is now ready, go to step 3.
3. The program can now proceed and take appropriate action.

Busy waiting

If the program continuously polls the device without doing anything in between checks, it’s called a busy-waiting.

Repeatedly checking the status of the input device require the use of the CPU. Using a conditional loop the CPU can repeatedly load the value of the status register to check if new input is available. While waiting for input the CPU doesn’t do any other work, the CPU is busy-waiting.

Interrupts

Interrupts are used to signal events external to the program (timers, serial ports, keyboard input etc). Interrupts are generated by other hardware devices outside the CPU at arbitrary times with respect to the CPU clock signals and are therefore considered to be asynchronous.

A user program executes in user mode (text segment). When an interrupt happens, control is automatically transferred to the interrupt handler executing in kernel mode (ktext segment).

An alternative to both polling and busy-waiting is to make the input device generate an interrupt every time new input is available. Using interrupts makes it possible for the CPU to do something useful, for example execute another program, while waiting for user input.

Multiprogramming

In general, I/O operations does not make use of the CPU but are handled by external devices. Compared to the CPU, I/O operations are very slow and while waiting for I/O the CPU is idle doing nothing. To overcome this problem multiprogramming was invented.

Job

In systems using multiprogramming a program loaded to memory and ready to execute is called a job.

Execute another job while waiting for I/O

The simple idea is to always have one job execute on the CPU by changing job when an I/O request is made.

States

In a multiprogramming system, a job can be in one of three states.

Running

The job is currently executing on the CPU. At any time, at most one job can be in this state.

Ready

The job is ready to run but currently not selected to do so.

Waiting

The job is blocked from running on the CPU while waiting for an I/O request to be completed.

State transitions

In a multiprogramming system, a the following state transitions are possible.

The problem is, how will the system know when an I/O request is completed?

Interrupts

To implement multiprogramming interrupts are used to notify the system of important events such as the completion of an I/O request.

Step by step

In a multiprogramming system, several jobs are kept in memory at the same time. Initially, all jobs are int the ready state.

One of the ready jobs is selected to execute on the CPU and changes state from ready to running. In this example, job 1 is selected to execute.

Eventually, the running job makes a request for I/O and the state changes from running to waiting.

Instead of idle waiting for the I/O request to complete, one of the ready jobs is selected to execute on the CPU and have its state change from ready to running. In this example job 3 is selected to execute.

Eventually the the I/O request job 1 is waiting for will complete and the CPU will be notified by an interrupt. In this example, job 1 was waiting for a keypress on the keyboard.

The state of the waiting job (job 1) will change from waiting to ready.

System call design

As an example of how multiprogramming handles I/O requests we will study how to wait for the user to input data from the keyboard.

Normally the operating system is responsible for handling user input and output. When a user program requests service from the operating system this is implemented as system calls.

We will start by to study how to implement a system call that lets the user input a single character from the keyboard. Next we will study how to implement a system call that lets the user input a string from the keyboard.

Read character system call design

Let’s sketch the design for a system call similar to the C library function getc that allows a program to read a single single character typed by a human user on the keyboard. The below figure shows an example where job 1 calls the custom getc system call and job 2 executes while job 1 waits for the user to press a key on the keyboard.

In the above figure important events are marked with a number inside a yellow circle.

1. Job 2 is ready to run and job 1 is running.
2. Job 1 uses the getc system call to read a character from the keyboard.
3. The system call uses a system call exception to enter the kernel.
   • The kernel saves the context (all register values) of job 1.
   • The kernel now knows that job 1 waits for input and changes its state from running to waiting.
   • The kernel restores the context of job 2.
4. The kernel resumes execution of job 2. Job 1 and changes its state from ready to running.
5. The human user presses a key on the keyboard.
6. The key-press causes a keyboard interrupt which is handled by the kernel.
   • The kernel saves the context of job 2 and changes its state from running to ready.
   • The kernel knows that job 1 waits for the getc system call to complete.
   • The kernel restores the context of job 1 and changes its state from waiting to running.
   • The ASCII value of the pressed key is made available to job 1.
7. The kernel resumes execution of job 1.

Multiprogramming

The result of the getc system call can not be obtained immediately, the kernel must wait for the user to press a key on the keyboard. When handling the getc system call, the kernel blocks the caller and make another job run until the user presses a key on the keyboard.

Null-terminated strings

A null-terminated string is a character string stored as an array containing the characters and terminated with a null character \0. ¹

Read string system call design

We have already studied how interrupts can be used to wait for a single keypress from a human user. How can we design a system call for inputting a string?

• To input a string we simply needs to wait for each keyboard interrupt and save the characters in an array (buffer).
• When the user presses enter (or there is no more space in the buffer) the buffer is terminated with null.

Input buffer

Where should the input buffer be allocated? In user space or in kernel space?

Memory safety

• It is not desirable for a user program to be able to read arbitrary data stored in the kernel.
• A user program could (possibly by mistake) corrupt the kernel by writing data outside the input buffer. This is called buffer overflow.

To enforce memory safety user programs are not allowed to access (read or write) kernel data but the kernel is allowed to read and write data in user space.

Buffer pointer

The kernel must know the address (pointer) to the input buffer in user space. 

Buffer size

The kernel must know the size of the input buffer and decide what to do when the buffer is full.

Read string system call example

To better understand the details of how the read string system call can be implemented we will study a small example with two jobs. In this example, job 1 allocates a 3 element input buffer and uses a system call to request the operating system to wait (using interrupts) for the user to fill this buffer with two characters and terminate the buffer with null. Until the input buffer is full the operating system (kernel) let job 2 execute between keyboard interrupts. 

System call convention

A common pattern for system calls and other library functions is for the caller to allocate a struct or array in user space. The caller pass a pointer to the struct or array as an argument to the system call or library function call. The system call or library function writes result data to the struct or array in user space using the provided pointer.

An alternative to the above patterns would be to return data (structure or array elements) on the stack. So why are pointers (call by reference) used instead of returning on the stack?

• Why do many functions that return structures in C, actually return pointers to structures?

Mips coprocessor 0

A MIPS processor consists of an integer processing unit (the CPU) and a collection of coprocessors that perform ancillary tasks or operate on other types of data such as floating-point numbers.

Integer arithmetic and logical operations are executed directly by the CPU. Floating point operations are executed by Coprocessor 1. Coprocessor 0 is used do manage exceptions and interrupts.

Normal user level code doesn’t have access Coprocessor 0, but interrupt and exception aware code has to use it. Coprocessor 0 has several registers which controls exceptions and interrupts.

Status (register 12)

The coprocess 0 status register is a read-write register used to enable or disable various types of interrupts.

Interrupt enable

If the interrupt enable bit is 1, interrupts are allowed. If it is 0, they are disabled.

Exception level

The exception level bit is normally 0, but is set to 1 after an exception occurs. When this bit is 1, interrupts are disabled and the EPC is not updated if another exception occurs. This bit prevents an exception handler from being disturbed by an interrupt or exception, but it should be reset when the handler finishes.

User mode

The user mode bit is 0 if the processor is running in kernel mode and 1 if it is running in user mode.

Interrupt mask

The 8 bit interrupt mask 8 field contains one bit for each of the 6 hardware level interrupts and the 2 software level interrupts. A mask bit set to 1 allows interrupts at that level to interrupt the processor. A mask bit set to 0 disables interrupts at that level.

Startup value

On startup the status register has the following value.

To see which bits are set in the status register on startup we must translate the hexadecimal startup value to binary.

Mars initializes the status register in coprocessor 0 to 0x0000ff11 = [binary] = 0000 0000 0000 0000 1111 1111 0001 0001.

On startup:

• Interrupts are enabled.
• User mode is set to 1.
• All interrupt mask bits are set to 1.

Cause (register 13)

The Cause register, is a mostly read-only register whose value is set by the system when an interrupt or exception occurs. It specifies what kind of interrupt or exception just happened.

When an exception or interrupt occur, a code is stored in the cause register as a 5 bit value (bits 2-6). This field is commonly referred to as the exception code although it is used for both exceptions and interrupts.

EPC (register 14)

Exception Program Counter (EPC) register. When an interrupt or exception occurs, the address of the currently executing instruction is copied from the Program Counter (PC) to EPC. This is the address that your handler jumps back to when it finishes.

Timer (register 9 and 11)

In SPIM, a timer is simulated with two more coprocessor registers: Count (register 9), whose value is continuously incremented by the hardware, and Compare (register 11), whose value can be set. When Count and Compare are equal, an interrupt is raised, at Cause register bit 15.

To schedule a timer interrupt, a fixed amount called the time slice (quantum) is stored in the Compare register. The smaller the time slice, the greater the frequency of timer interrupts.

Accessing registers in Coprocessor 0

To access a register in Coprocessor the register value must be transferred from Coprocessor 0 to one of the regular CPU registers. To update one of the registers in Coprocessor 0 a value in one of the of the regular CPU register in the CPU must be transferred to to one of the Coprocessor 0 registers.

If you want to modify a value in a Coprocessor 0 register, you need to move the register’s value to a general- purpose register with mfc0, modify the value there, and move the changed value back with mtc0.

mfc0

The mfc0 (Move From Coprocessor 0) instruction moves a value from a Coprocessor 0 register to a general-purpose register.

Example:

mfc0 $t5, $13  # Copy $13 (cause) from coprocessor 0 to $t5.

mtc0

The mtc0 (Move To Coprocessor 0) instruction moves a value from a general-purpose register to a Coprocessor 0 register.

Example:

mtc0 $v0, $12  # Copy $v0 to $12 (status) in coprocessor 0.

References

Assemblers, Linkers, and the SPIM Simulator

Memory mapped I/O

In order to study exceptions and interrupts we will use the Mips 32 simulator Mars. All instructions will be written for and tested using Mars but you should be able to use the Spim simulator if you prefer.

Mips system architecture

A Mips processor consists of an integer processing unit (the CPU) and a collection of coprocessors that perform ancillary tasks or operate on other types of data such as floating-point numbers.

Both Mars and Spim simulates two coprocessors:

• Coprocessor 0 handles exceptions and interrupts.
• Coprocessor 1 is the floating-point unit.

Integer arithmetic and logical operations are executed directly by the CPU. Floating point operations are executed by Coprocessor 1. Coprocessor 0 are used do manage exceptions and interrupts.

Receiver and transmitter

Mars simulates one I/O device: a memory-mapped console on which a program can read and write characters. The terminal device consists of two independent units: a receiver and a transmitter.

• The receiver reads characters typed on the keyboard.
• The transmitter display characters on the console.

Echo

The receiver and transmitter are completely independent. This means, for example, that characters typed at the keyboard are not automatically echoed on the display. Instead, a program must explicit echo a character by reading it from the receiver and writing it to the transmitter.

Memory layout

To execute a Mips program memory must be allocated. The Mips computer can address 4 Gbyte of memory, from address 0x0000 0000 to 0xffff ffff. User memory is limited to locations below 0x7fff ffff. In the below figure the layout of the memory allocated to a Mips program is shown.

The purpose of the various memory segments:

• The user level code is stored in the text segment.
• Static data (data know at compile time) use by the user program is stored in the data segment.
• Dynamic data (data allocated during runtime) by the user program is stored in the heap.
• The stack is used by the user program to store temporary data during for example subroutine calls.
• Kernel level code (exception and interrupt handlers) are stored in the kernel text segment.
• Static data used by the kernel is stored in the kernel data segment.
• Memory mapped registers for IO devices are stored in the memory mapped IO segment.

Memory-mapped terminal device

A program controls the terminal with four memory-mapped device registers. Memory-mapped means that each register appears as a special memory location. In this sense, these are not real registers but simply words (32 bit) values stored in memory.

Receiver control

The Receiver Control register is at memory location 0xffff0000. Only two of its bits are actually used.

Bit 0 is called ready:

• If it is 1, it means that a character has arrived from the keyboard but has not yet been read from the Receiver Data register.
• The ready bit is read-only: writes to it are ignored.
• The ready bit changes from 0 to 1 when a character is typed at the key- board, and it changes from 1 to 0 when the character is read from the Receiver Data register.

Bit 1 is the keyboard interrupt enable bit:

• This bit may be both read and written by a program.
• The interrupt enable is initially 0.
• If it is set to 1 by a program, the terminal requests an interrupt at hardware level 1 whenever a character is typed and the ready bit becomes 1. However, for the interrupt to affect the processor, interrupts must also be enabled in the Status register.
• All other bits of the Receiver Control register are unused.

Receiver data

The second terminal device register is the Receiver Data register at memory address 0xffff0004.

• The low-order 8 bits of this register contain the last character typed at the keyboard. All other bits contain 0s.
• This register is read-only and changes only when a new character is typed at the keyboard.
• Reading the Receiver Data register resets the ready bit in the Receiver Control register to 0.
• The value in this register is undefined if the Receiver Control register is 0.

Transmitter control

The third terminal device register is the Transmitter Control register at memory address 0xffff0008. Only the low-order 2 bits of this register are used. They behave much like the corresponding bits of the Receiver Control register.

Bit 0 is called ready:

• This bit is read-only.
• If this bit is 1, the transmitter is ready to accept a new character for output.
• If it is 0, the transmitter is still busy writing the previous character.

Bit 1 is the interrupt enable bit:

• This bit is readable and writable.
• If this bit is set to 1, then the terminal requests an interrupt at hardware level 0 whenever the transmitter is ready for a new character and the ready bit becomes 1.

Transmitter data

The final device register is the Transmitter Data register at memory address 0xffff000c.

Only the least 8 significant bits (the least significant byte) are used:

• When a value is written into this location, its low-order 8 bits (i.e., an ASCII character) are sent to the console.
• When the Transmitter Data register is written, the ready bit in the Transmitter Control register is reset to 0. This bit stays 0 until enough time has elapsed to transmit the character to the terminal; then the ready bit becomes 1 again.
• The Transmitter Data register should only be written when the ready bit of the Transmitter Control register is 1. If the transmitter is not ready, writes to the Transmitter Data register are ignored (the write appears to succeed but the character is not output).

Timing

In a physical computer sending a character to the terminal doesn’t happen instantly, the operation takes some time to complete.

The simulators Mars and SPIM measures time by counting the number executed instructions , not in real clock time. After writing a character to the receiver data register, this means that the transmitter does not become ready again until the processor executes a fixed number of instructions. If you stop the simulation and look at the ready bit, it will not change. However, if you let the simulation continue, the bit eventually changes back to 1.

References

Assemblers, Linkers, and the SPIM Simulator

Clone repository

Before you continue, you must clone the fundamental-os-concepts repository.

Use the git command

From the terminal, navigate to a directory where you want the cloned directory to be created and execute the following command.

git clone https://github.com/os-assignments/fundamental-os-concepts.git

Now you should see something similar to this in the terminal.

Cloning into 'fundamental-os-concepts1'...
remote: Counting objects: 7, done.
remote: Compressing objects: 100% (6/6), done.
remote: Total 7 (delta 0), reused 7 (delta 0), pack-reused 0
Unpacking objects: 100% (7/7), done.

Use the tree command

To get an overview of the cloned repository, use the tree command.

tree fundamental-os-concepts

Now you should see a tree view of all files and directories in the fundamental-os-concepts directory.

fundamental-os-concepts
├── README.md
├── higher-grade
│   └── multiprogramming.s
└── mandatory
    └── exceptions-and-interrupts.s

2 directories, 3 files

brew install tree

Introduction to exceptions and interrupts in Mips

Mandatory assignment

Learning outcomes

In this assignment you will study the differences between exceptions and interrupts and how to implement a simple exception and interrupt handler. You will also study how both exceptions and interrupts causes a transfer of control from user mode to kernel mode and back to user mode after the exception or interrupt have been handled by the kernel.

Method

To study exception and interrupt handling you will load a small Mips assembly program into the Mips simulator Mars. The program will deliberately trigger the following exceptions:

1. Arithmetic overflow.
2. Address error.
3. Trap.

By single-stepping the program you will examine in detail what actions are taken in order to handle each exception. You will also study keyboard interrupts and how this can be used make the CPU do something different while waiting for user input. To get a fully working system you must add or change the provided code at a few places.

Preparations

Before you continue you must perform the following preparations.

Learn about Mips and Mars

If you haven’t done so already, go through the introduction to Mips and Mars.

Install Mars on your private computer

Mars will run on any system (including Windows) as long as you have [Java installed][java-install]. If you prefer, you may download and install Mars on your private computer.

Clone repository

If you haven’t done so already, you must clone the fundamental-os-concepts repository.

Start Mars

If you don’t have Mars installed on your private computer, you can log in to the department Linux system and start Mars from the Applications menu under Programming.

Mars should now start and you should see something similar to this.

Open file

Open the file mandatory/exceptions-and-interrupts.s in Mars.

Study the source code

Study the assembly source code of the loaded program in the built in editor pane.

User level code

After an introductory comment you find the .text assembler directive followed by the label main which is the entry point of the user mode program. In main:

1. First an arithmetic overflow exception is triggered by adding 1 to the largest positive 32 bit two’s complement value 0x7fffffff.
2. Next an address error exception is triggered by trying to load a value from an invalid memory address (address 0).
3. Finally, a trap exception is triggered using the teqi (Trap EQual Immediate) instruction.

At the end of main the program enters an infinite loop incrementing a counter (register $s0).

Kernel level code

The assembler directive .ktext 0x80000180 instructs the assembler to place the generated machine instructions in the kernel text segment starting at memory address 0x80000180. Here the label __kernel_entry_point marks the entry point of the exception handler (kernel). Note that this label is not needed but simply included to make it obvious to a human reader where the exception handler starts.

When an exception or interrupt occurs, the address of the program counter of the currently executing program is automatically saved to the EPC register in coprocessor 0 and control is transferred from user mode to kernel mode.

When entering the kernel, the kernel must determine whether this due to an an exception or an interrupt.

1. First the kernel loads the value of the cause register from coprocessor 0.
2. Next the exception code is extracted from the cause register. The exception code will be zero for an interrupt and non-zero for an exception.
3. Using a conditional branch execution will continue at the label __interrupt for an interrupt and at label __exception for an exception.

For an exception, the exception code must be further examined to distinguish between different exceptions. For interrupts the pending interrupt bits in the cause register is used to distinguish between different interrupts. At the end of the kernel text segment at label __resume, execution is resumed in user mode at the address saved in the EPC register in coprocessor 0.

Adjust the run speed

Adjust the simulated run speed to 25 inst/sec or lower.

First test run

Before you continue, clear both the Mars Messages and Run I/O.

• Assemble the file by clicking on the icon with the screwdriver and wrench.

You should see something similar to the following in the Mars Messages display pane.

Assemble: assembling /path/to/file/exceptions-and-interrupts.s

Assemble: operation completed successfully.

• Click on the play icon to run the program to completion.

In the Run I/O display window you should see the following output.

===>      Arithmetic overflow       <===

===>      Arithmetic overflow       <===

===>      Arithmetic overflow       <===

===>      Arithmetic overflow       <===

The same error message is printed several times.

• Click on the stop button to stop the simulation.

Before you continue, clear both the Mars Messages and Run I/O.

Pseudo instructions

In the Execute pane the source instructions are shown in the Source column and the actual instructions produced by the assembler are shown in the Basic column. Note that the first source instruction li $s0, 0x7fffffff is a pseudo instruction that is translated to one lui instruction and one ori instruction, both using the $at (Assembler Temporary) register, i.e., register $1.

Arithmetic overflow step by step

It is now time to study the execution in more detail by execute one instruction at the time using the single step button .

• Assemble the file.

The largest positive integer

The program starts by storing the largest 32 bit positive two’s complement integer in register $s0 using the li (Load Immediate) instruction. This instruction is a pseudo instruction and translates to one lui instruction and one ori instruction.

• Execute the li $s0, 0x7fffffff instruction.

Now, look at the register pane.

Note that register $at (register number 1) have been highlighted and that the value stored in $at changed from the initial value 0x00000000 to 0x7fff0000 , i.e., the upper half of the 32 bit value 0x7fffffff is now stored in $at.

• Execute the ori $16, $1, 0x000ffff instruction.

Now $s0 (register number 4) will be highlighted in the register pane. Register $s0 now holds the value value 0x7fffffff = [32 bit binary] = 0111 1111 1111 1111 1111 1111 1111 1111, i.e., the largest positive 32 bit two’s two’s complement integer.

The program counter

The program counter stores the address of the next instruction to execute. In the register pane, look at the value of the program counter pc. We see that pc = 0x00400008. Also note that in the execute pane the instruction at this address is now highlighted.

The cause register

In the Coproc 0 tab in the register pane, look at the cause register (register 13).

The value in the cause register is currently 0x00000000.

Adding one

We will now try to add the value one (1) to the integer stored in $s0.

• Execute the addi $s1, $s0, 1 instruction.

The program counter have now jumped from 0x00400008 to 0x80000180, i.e., execution has transition to the kernel entry point. Now the status register (register 12) is highlighted in the register pane.

Note that the cause register changed from 0x00000000 to 0x00000030 and that EPC have been set to 0x00400008, i.e., been set to the address of the addi instruction causing the overflow exception.

Step backwards and forwards

One great feature of the Mars simulator is the possibility to execute the program backwards.

• Undo the execution of addi $s1, $s0, 1 instruction by clicking on the undo button.

Study the values of the program counter, the cause register and the EPC register.

• Execute the addi $s1, $s0, 1 instruction.

Keep undo and redo the execution of the addi instruction and make sure you understand that this addition causes a transfer of control from user mode to kernel mode due to an overflow exception and that information about the exception is stored in the cause register. When the exception happens, the address of the faulty instruction is automatically saved in the EPC register.

Transition from user mode to kernel mode

As a consequence of the overflow exception, execution has now transition from user mode to kernel mode. Execution now continues in the .ktext segment at the label __kernel_entry_point at address 0x80000180.

Get the value in the cause register

To investigate what caused the transfer from user mode to kernel mode, the kernel must fetch the value of the cause register from coprocessor 0.

• Execute the mfc0 $k0, $13 instruction.

In the register pane register $k0 should now be highlighted with value 0x00000030 = [binary] = 0000 0000 0000 0000 0000 0000 0011 0000, i.e, a copy of the cause register.

Mask all but the exception code (bits 2 - 6) to zero

The bits of the cause registers have different meaning.

In general, we can’t be sure if other bits than the exception code bits (bits 2 - 6) are set in the cause register. To set all bits but the exception code bits (bits 2 -6) to zero, the bitmask 0x0000007C = [binary] = 0000 0000 0000 0000 0000 0000 0111 1100 is used together with bitwise and (andi).

• Execute the andi $k1, $k0, 0x00007c instruction.

In the register pane, register $k1 should now have value 0x00000030 = [binary] = 0000 0000 0000 0000 0000 0000 0011 0000.

Shift two steps to the right

To get the value of the exception code we need to shift the value in $k1 two steps to the right.

• Execute the srl $k1, $k1, 2 instruction.

Register $k1 now hold the exception code = 0x0000000c = [binary] = 0000 0000 0000 0000 0000 0000 0000 1100 = [decimal] = 12.

Interrupt or exception

The exception code is zero for an interrupt and none zero for all exceptions. The beqz instruction is now used to jump to the label __interrupt if the exception code in $k1 is zero, otherwise execution continues on the next instruction.

• Execute the beqz $k1, __interrupt instruction.

The exception code is non zero and the branch is not taken.

Branch depending on the exception code

Next the beq instruction is used to make a conditional jump to the label __overflow_exception if the exception code in $k1 is equal to 12.

• Execute the pseudo instruction beq $k1, 12, __overflow_exception by clicking twice on step the step forward button.

The branch is taken and execution continues at label __overflow_exception.

Print error message

Next a “magic” Mars builtin system call is used to print the error message "===> Arithmetic overflow <===\n\n" stored as a null terminated string in the .kdata segment at label OVERFLOW_EXCEPTION.

• Single step four times execute the magic print string system call.

In the Run I/O pane you should now see the following message.

===>      Arithmetic overflow       <===

Next an unconditional jump to label __resume_from_exception is done.

• Execute the j __resume_from_exception instruction.

Resume from exception

Execution now continues at the label __resume_from_exception. Next the value of the EPC register is fetched from the coprocessor 0 register $14 to the CPU register $k0.

• Execute the mfc0 $k0, $14 instruction.

Register $k0 now have the value 0x00400008. This is the address that was automatically stored in EPC when the overflow exception occurred, i.e., the address of the instruction causing the overflow exception.

Next, the value in the $k0 register is stored back to the EPC register in coprocessor 0.

• Execute the mtc0 $k0, $14 instruction.

Transfer control back to user mode

The exception have now been handled by the kernel. The last thing to be done is to transfer control back to user mode using the eret instruction which makes and unconditional jump to the address currently stored in EPC.

• Execute the eret instruction.

Full circle

Execution now continues in user mode at the same instruction that caused the overflow exception in the first place.

• Click on the play button to continue execution. Don’t use the single-step button, use the play button.

In the Run I/O display window you should see the following output.

===>      Arithmetic overflow       <===

===>      Arithmetic overflow       <===

===>      Arithmetic overflow       <===

===>      Arithmetic overflow       <===

The same message is printed repeatedly in the Run I/O display.

• Click on the stop button to stop the simulation.

Solution

When resuming execution after an exception, we want to resume at the instruction following the instruction at the address saved in EPC. Each instruction is four bytes, hence we need to add four to EPC before executing eret.

• Click on edit to show the source code.
• Press Ctrl-F and search for todo_1.
• Uncomment the following line to add four to the EPC value.

# addi $k0, $k0, 4 # TODO: Uncomment this instruction

• Assemble the file.

Before you continue, clear both the Mars Messages and Run I/O.

• Click on the play icon to run the program to completion.

In the Run I/O display window you should see the following output.

===>      Arithmetic overflow       <===

===>      Unhandled exception       <===

===>      Unhandled exception       <===

This time there is exactly one arithmetic overflow error message followed by two messages about unhandled exceptions.

Infinite loop

The program is now stuck in the infinite loop at label infinite_loop. In the register pane you should be able to see how the value of register $s0 is constantly increasing.

• Click on the stop button to stop the simulation.

Address error and trap exceptions

At label todo_2 you must add code to:

• Branch to label __bad_address_exception for exception code 4.
• Branch to label __trap__exception for exception code 13.

• Assemble the file.

Before you continue, clear both the Mars Messages and Run I/O.

• Click on the play icon to run the program to completion.

In the Run I/O display window you should see the following output.

===>      Arithmetic overflow       <===

===>   Bad data address exception   <===

===>         Trap exception         <===

Pause the simulation

This time you should not halt the simulation, instead you should pause the simulation.

• Click on the pause button to pause the simulation.

Keyboard interrupts

We will now make the keyboard generate an interrupt for each keypress. In order to do this we must first setup the Mars MMIO simulator.

Enable the Keyboard and display MMIO simulator

To make MARS simulate the memory mapped keyboard receiver (and display transmitter) you must enable this feature.

Open the Keyboard and Display MMIO Simulator window

From the Tools menu, select Keyboard and Display MMIO Simulator.

A new window should now open.

The lower white area of this window is the simulated keyboard.

Connect to MIPS

To make MARS aware of the simulated memory mapped receiver (keyboard), press the Connect to MIPS button in the lower left corner of the Keyboard and Display MMIO Simulator window.

Resume the simulation

Now you can resume the simulation.

• Click on the play icon to resume the simulation.

Infinite loop

The program is now stuck in the infinite loop at label infinite_loop. In the register pane you should be able to see how the value of register $s0 is constantly increasing.

Type on the simulated keyboard

Click inside the lower white area of the MMIO simulator window and type a few characters.

Nothing happens, the program is still stuck in the infinite loop.

Stop the simulation

Before you continue, make sure to stop the simulation.

• Click on the stop button to stop the simulation.

Enable keyboard interrupts

At label todo_3 you must add code to enable keyboard interrupts. The simulated keyboard is configured by setting bits in the memory mapped transmitter control register which appears at address 0xffff0000.

To make the keyboard generate interrupts on keypresses, the bit 1 of receiver control must be set to 1.

• Assemble the file.

• Click on the play icon to run the program to completion.

Type on the simulated keyboard

Click inside the lower white area of the MMIO simulator window and type a single character.

When you type a character on the simulated keyboard a keyboard interrupt is generated. The interrupt is handled by the kernel.

• Click on the stop button to stop the simulation.

Known bug in Mars

There is a conflict between the built-in system call 12 read_char and the Keyboard and Display MMIO Simulator.

Echo

The ASCII value of the pressed key is stored in the memory mapped receiver data register.

At label todo_4 you must uncomment a number of instructions to load the ASCII value from receiver control and print it to Run I/O using the Mars builtin system cal.

• Assemble the file.

Click on the label __todo_4 in the labels window.

The instruction at label __todo_4 is now highlighted in the Execute pane. Add a breakpoint at this address by checking the checkbox in the leftmost Bkpt column.

• Click on the play icon to run the program to completion.

Once again, execution is stuck in the infinite loop incrementing the $s0 register.

Type on the simulated keyboard

Click inside the lower white area of the MMIO simulator window and type a single character.

Execution paused at the breakpoint

When you type a character on the simulated keyboard a keyboard interrupt is generated. The interrupt is handled by the kernel and execution is paused at the breakpoint.

Single step

Continue by single stepping and try to understand how the keyboard interrupt is handled by the kernel and execution resumes in the user mode infinite loop after the keyboard interrupt has been handled.

Once the keyboard interrupt have been handled you should see the pressed character printed to Run I/O display.

Repeat

Now you can press play again, press a key on the simulated keyboard and single step after the breakpoint. Repeat a few times to make sure you understand how the keyboard interrupt is handled.

Conclusions

Interrupts and exceptions are used to notify the CPU of events that needs immediate attention during program execution. Exceptions and interrupts are events that alters the normal sequence of instructions executed by a processor.

Exceptions are internal and synchronous

• Exceptions are used to handle internal program errors.
• Overflow, division by zero and bad data address are examples of internal errors in a program.
• Another name for exception is trap. A trap (or exception) is a software generated interrupt.
• Exceptions are produced by the CPU control unit while executing instructions and are considered to be synchronous because the control unit issues them only after terminating the execution of an instruction.

Interrupts are external and asynchronous

• Interrupts are used to notify the CPU of external events.
• Interrupts are generated by other hardware devices outside the CPU at arbitrary times with respect to the CPU clock signals and are therefore considered to be asynchronous.
• Key-presses on a keyboard might happen at any time. Even if a program is run multiple times with the same input data, the timing of the key presses will most likely vary.

Preparations for the code grading

This assignments is constructed more or less as a step-by-step tutorial. The purpose of the code grading is not for you (the student) to show the teaching staff that you got something to work as required. The focus is for you to be able to explain and discuss what you’ve done and what you learnt. In preparation for the code grading:

• Make sure you understand as much as possible of all the details.
• Single step the code in Mars.
• Read all the provided comments.
• Try to understand what happens in each step.

Multiprogramming and custom system calls in Mips

Optional assignment for higher grade (3 points)

The Mars built-in system calls

Previously you have used a number of system calls built in to MARS, for example to print strings and integers. Before calling any of the Mars built-in system calls, the system call code is placed in $v0. Next, the syscall instruction is used to invoke the system call.

In a real Mips system, the syscall instruction triggers a system call exception (exception code 8) that causes control to be transferred from user space to kernel space where the system call is handled. The kernel investigates the value in $v0 to determine which specific system call the user requested.

In Mars the built-in system calls are handled by the simulator and not by the kernel (exception and interrupt handler) code that you can study and modify. Unfortunately this makes it impossible to provide custom implementations of system calls using the syscall instruction.

No more magic

After all, this is a course about operating systems and we cannot be satisfied with the magic provided by the system calls built in to Mars. It is now time to implement our own custom system calls from scratch.

Timer interrupts

Unfortunately, Mars does not support timer interrupts. This makes it impossible for the kernel to to use a timer to swap between running jobs at regular intervals.

Multiprogramming

For the higher grade assignment you should implement a simplified version of multiprogramming.

System overview

An overview of the system is shown in the below figure.

For simplicity there will be exactly two jobs in the system. The kernel will implement three custom system calls: getjid, getc and gets. The kernel will use multiprogramming to switch job only when a job requests I/O using the getc or gets system call.

Two non-terminating jobs

To make the system as simple as possible, the kernel only need to support two non-terminating jobs. Only one job can execute on the CPU at the time.

Job id (jid)

The two jobs are identified by job id (jid) numbers 0 and 1 respectively.

No stack and no subroutines

To keep the system simple the jobs cannot use the stack nor can they make subroutine calls.

No memory protection

Mars does not support any form of memory protection. As a consequence there will be no memory protection between user space and kernel, nor will there be any memory protection between jobs. Thetwo jobs:

• execute in the same memory space
• share the same data segment.

Only one job can request I/O

The whole purpose of multiprogramming is to maximize the usage of the CPU. A job executes on the CPU until requesting I/O. When requesting I/O the job is blocked waiting for the I/O request to complete. While waiting the other job executes on the CPU.

In this simplified system, only one of the two non-terminating jobs can request I/O. While a job is waiting for the I/O request to complete the other job executes on the CPU.

States

At any time, each of the two non-terminating jobs job can be in one of the following three states.

Running

The job is selected to execute on the CPU.

Ready

The job is not selected to execute on the CPU but ready to do so if selected.

Waiting

The job has made a request for I/O using either getc or gets and s blocked from executing until the the request have been completed.

On startup of the system (boot) one job is selected to execute (running) and the other is marked as ready to run.

State transitions

In this simplified version of a a multiprogramming system with only two jobs, the following state transitions are possible.

In the below diagram a sequence of five events shows how the two jobs change states.

Kernel

In this system the kernel is responsible for handling all exceptions and interrupts. The kernel will also be responsible for managing the execution of the two jobs.

Kernel stack

In order for the kernel to be able to use subroutines, the the kernel will allocate a stack.

Job context

When a job executes it uses the CPU registers. At any time, the values of all the registers is called the context of the running job.

In this simplified system each job is only allowed to use the following six registers: $pc (program counter), $v0, $a0, $a1, $s0 and $at (should only be used by pseudo instructions).

Each register is four byte, hence 6*4 = 24 bytes of storage is needed to store the context. The contents of the registers are saved in the following order in each job context.

Addressing the context

If the address to a context is in register $t0, the address to each of the fields in the context is shown in the column Assembly notation in the following table.

Examples

In the following examples, the address to a context is in register $t0.

sw $t1,  8($t0)  # Store $t1 to the $a0 field in the context. 

lw $t2, 16($t0)  # Load the $s0 field from the context into $t2. 

Context array

To store the contexts of the two jobs, a two element array is used. The array is indexed by job id (0 or 1). Each element of the array is a pointer to storage allocated for the context.

Addressing the context array

The two element context array is indexed by job id (0 or 1). Each element of the context array is a pointer to a job context, i.e., a four byte address to a job context.

If ca is the address of the context array and jid the job id, the following table shows how to calculate the address to the context pointer the job with id jid.

Example

Multiplying with 4 is equivalent to shift left two bits. In Mips assembly the sll (Shif Left Logical) instruction is used to bit shift to the left.

If the context array is stored at label __context_array and the job id (jid) the of the running job is stored at label __running the following example shows how to get the address to the context of the running job.

# Get job id (jid) of the running job. 
	
lw $t0, __running 
	
# Offset to context pointer (0 or 4)  = jid * 4.
	
sll $t1, $t0, 2   # jid * 4
	
#  Pointer to context.
	
lw $t3, __context_array($t1)

Now $3 contains the address of the running jobs context and can be used to access fields within the context as described in the section addressing the context.

Save context

When entering the kernel, the context of the running job must be saved. i.e., the contents of $pc, $v0, $a0, $a1, $s0 and $at must be saved to memory.

Restore context

When the kernel resume the execution of a job, the job context is first restored, i.e., the values of $pc, $v0, $a0, $a1, $s0 and $at that previously been saved to memory are read from memory and restored.

Custom system calls

The kernel will implement the following system calls.

The teqi instruction

The teqi (Trap EQual Immediate) instruction is used to conditionally trigger a trap exception (exception code 13) that automatically transfers control to the kernel.

teqi rs, imm

The  teqi instruction will cause a trap exception (exception code 13) if the value in register rs is equal to the immediate constant imm.

**Example usage: **To trigger a trap exception we can compare $zero (allways zero) with zero.

teqi $zero, 0

Instead of using the syscall instruction we use teqi $zero, 0 when we want to perform one of the custom system calls.

Calling the custom getjid system call

An example showing how to use the custom getjid system call to get the job id of the caller:

li   $v0, 0
teqi $zero, 0

# On success $a0 will now contain the job id (jid) of the caller. 

The below figure shows an example where job 1 calls the custom getjid system call.

In the above figure important events are marked with a number inside a yellow circle.

1. Job 1 is ready to run and job 0 is running.
2. Job 0 uses a the custom getc system call to read a character from the keyboard.
3. The system call uses a trap exception to enter the kernel.
   • The kernel saves the context (all register values) of job 0.
   • Besides $k0 an $k1 the kernel can now safely use any of the registers saved to the job 1 context.
   • The kernel knows that the running job has id 0.
   • The kernel restores the context of job 0.
   • The kernel put the value 0 (the job id) in register $a0.
4. The kernel resumes execution of job 0.

Calling the custom getc system call

An example showing how to use the custom getc system call to read a character from the keyboard.

li   $v0, 12
teqi $zero, 0

# On succes $v0 will now contain the ASCII code of the pressed key. 

The below figure shows an example where job 1 calls the custom getc system call and job 2 executes while job 1 waits for the user to press a key on the keyboard.

In the above figure important events are marked with a number inside a yellow circle.

1. Job 1 is ready to run and job 0 is running.
2. Job 0 uses the custom getc system call to read a character from the keyboard.
3. The system call uses a trap exception to enter the kernel.
   • The kernel saves the context (all register values) of job 0.
   • The kernel now knows that job 0 waits for input and changes its state from running to waiting.
   • The kernel restores the context of job 1.
4. The kernel resumes execution of job 1 and changes its state from ready to running.
5. The human user presses a key on the keyboard.
6. The key-press causes a keyboard interrupt which is handled by the kernel.
   • The kernel knows from earlier that job 0 waits for the getc system call to complete.
   • The kernel saves the context of job 1 and changes its state from running to ready.
   • The kernel restores the context of job 0 and changes its state from waiting to running.
   • The ASCII value of the pressed key is placed in $v0.
7. The kernel resumes execution of job 0 with the ASCII value of the pressed key in $v0.

Known bug in Mars

There is a conflict between the built-in system call 12 read_char and the Keyboard and Display MMIO Simulator.

Clone repository

If you haven’t done so already, you must clone the fundamental-os-concepts repository.

Provided code

You don’t have to start from scratch but can use the provided higher-grade/multiprogramming.s as a starting point.

Higher grade points (max 3)

For 1 point your system must have working implementations of the custom getjid and getc system calls. Follow the labels TODO_1, TODO_2, …, TODO_8 in the provided multiprogramming.s file to guide you step by step.

For 3 points, in addition to the 1 point requirements above, your system must have a working implementation of the custom gets system call. You must also provide a user level job with a few test cases showing that gets works for different buffer sizes.