Appendix A

The Z502 Machine

This appendix describes the functional aspects of the Z502 computer architecture, that is, its interface to software.

1. Overall Architecture

The overall architecture of the Z502 computer is shown in Figure A.1. The machine can operate in either the user mode or the kernel mode. Each mode has its own memory, registers and instruction set.

The instruction set of the User CPU resembles that of your favorite language, with the addition of system calls. This is described in Section 4. Every User program must be translated into this language before it can be run. In addition, the Kernel CPU is capable of executing privileged instructions, that activate I/O and switch contexts. These privileged instructions are vital to the operating system and are described in Section 5.

The machine has built-in primitives for switching modes. In addition, any mode of execution may be asynchronously exceptioned. When a user-mode execution is exceptioned, the machine is switched automatically to the kernel mode. A user program can invoke the kernel by a software induced exception called a SOFTWARE-TRAP. Interrupts, traps, and faults are described in Section 6.

The machine currently supports the following external devices: disk and delay timer. Characteristics of these I/O devices are described in Section 7.

The memory address translation of the Z502 machine is described in Section 8.

The Z502 machine comes in different configurations in terms of memory size. These configurations are briefly noted in Section 9. The behavior of the machine upon power on is discussed in Section 10.

2. Memory

The Z502 User memory consists of some number of thirty-two (32) bit (i.e., four byte) words. The number of words in a configuration is constrained to be a power of two. All user programs reside in this memory and address words in it by zero origin addresses. The operating system resides in the Kernel memory which is disjoint from User memory. The Z502 Kernel memory, per kindness of the machine manufacturer, is not constrained in size.

While in kernel mode the operating system can access User memory through the array MEMORY which is defined as:

char MEMORY [ PHYS_MEM_PGS * PGSIZE ] ;

Unless otherwise specified, the term Z502 memory from now on will be used to refer to the User memory only.

3. Registers

Table A.1 shows all of the registers and vectors of the Z502 machine.

The Z502_REG_ARG1…, Z502_REG_1…, and Z502_REG_PROGRAM_COUNTER may be directly manipulated from the user program. The page table registers are "seen" by user memory but are not accessible to the user program per se. Z502_REG_PAGE_TBL_ADDR and Z502_REG_PAGE_TBL_LENGTH are described in Section 8 on address translation. All of these User CPU registers are also available from kernel mode.

All the other registers and vectors in table A.1 are used in the kernel mode. The use of Z502_REG_CURRENT_CONTEXT, Z502_REG_INTERRUPT_MASK, TO_VECTOR, and STAT_VECTOR is explained in Section 5.2 on context switching and in Section 6 on exception handling.

There are other internal registers used in Kernel mode that are essential for kernel mode execution. But since they are not accessible by the operating system we shall not define them here.

The kernel registers listed in the table can be referenced in your operating system directly by their names given above. The register Z502_REG_CURRENT_CONTEXT, is a read-only register from the point of view of the operating system. STAT_VECTOR and TO_VECTOR are read/write.

4. The User Mode Instruction Set

4.1 Register usage

As mentioned above, the following registers are available for use in user programs:

Z502_REG_ARG1 … Z502_REG_ARG6
Z502_REG_1 … Z502_REG_9
Z502_REG_PROGRAM_COUNTER

In practice, the ARGs are reserved for system call argument transportation, so you should avoid touching them in a user program. The REGs are very useful however. They have the sterling attribute that they are saved across context switches. This is the one way you can be assured that a user program is reentrant. More discussion of their use is given in Appendix B.

The program counter is also saved across context switches. As such it provides a history of where execution is at any time. This means that even though your user program must be reentered from the top, it can use the PC to determine where in the program to go next. Again this is dealt with in greater detail in Appendix B.

4.2 System Calls

You are directed to Appendix C which has extensive detail on the user level system calls.

5. Kernel Mode Instruction Set

In kernel mode the CPU, as mentioned before, can directly execute your favorite language. Aside from the entire language complement, there are also

I/O primitives
memory primitives
context switching primitives
and "other" miscellaneous primitives

that can be invoked as routines.

We will describe the four types of primitives, starting with the I/O primitives.

5.1 I/O Primitives

The Kernel I/O primitives are the ones that start an I/O operation. Note that they merely start the operation, and when the instruction is executed, the device has not necessarily been accessed yet.

These primitives are invoked as routines in kernel mode; if not in Kernel Mode, a privileged instruction fault will occur. The caller may not return from these calls since an exception may occur at any time. Prepare for this eventuality.

Usage of Z502_READ_DISK

INT16 disk_id, cylinder, sector;
char buffer[SOME_SIZE];

Z502_READ_DISK( disk_id, cylinder, sector, &buffer )

Read data from disk disk_id, from cylinder "cylinder" and sector "sector".

1. There are MAX_NUMBER_OF_DISKS different disks available, numbered 1 to MAX_NUMBER_OF_DISKS.
2. There are NUM_SECTORS sectors per cylinder, numbered 0 to NUM_SECTORS - 1.
3. Cylinders are numbered from 0 to NUM_CYLINDERS - 1.
4. Data is returned to the location pointed to by "buffer".
5. The length of a sector and thus of the buffer is PGSIZE bytes.

You MUST do ALL setup and exception preparation before you make this hardware call. It's possible that you will not return from this routine.

The Z502 halts if a disk request is started while that disk is already busy. Since this is HARDWARE and not software, the disk returns errors by causing an exception. The hardware exception will contain one of the following values:

Usage of Z502_WRITE_DISK

INT16 disk_id, cylinder, sector;
char buffer[SOME_SIZE];

Z502_WRITE_DISK( disk_id, cylinder, sector, &buffer );

Write data to disk disk_id, from cylinder "cylinder" and sector "sector".

1. There are MAX_NUMBER_OF_DISKS different disks available, numbered 1 to MAX_NUMBER_OF_DISKS.
2. There are NUM_SECTORS sectors per cylinder, numbered 0 to NUM_SECTORS - 1.
3. Cylinders are numbered from 0 to NUM_CYLINDERS - 1.
4. Data is returned to the location pointed to by "buffer".
5. The length of a sector and thus of the buffer is PGSIZE bytes.

You MUST do ALL setup and exception preparation before you make this hardware call. It's possible that you will not return from this routine.

The Z502 halts if a disk request is started while that disk is already busy.

Since this is HARDWARE and not software, the disk returns errors by causing an exception. The hardware exception will contain one of the following values:

Usage of Z502_DELAY_TIMER

INT32 time_to_delay;

Z502_DELAY_TIMER( time_to_delay );

Cause a timer exception to occur at "time_to_delay" time units in the future.

If time_to_delay < 0, an exception with error ERR_BAD_PARAM is caused.

5.2 Memory Access Instructions

These are the hardware corollaries of the user mode instructions. Upon taking a memory Software Trap, the Z502 hardware directs execution immediately to these routines - the Operating System doesn't get to handle the memory request since it's not a system call. Usage of MEM_READ

INT32 address;
INT32 data;

MEM_READ( address, &data );

The information stored at location "address" is returned in the variable pointed to by "data". If the address is not valid (for any of a number of reasons), a page fault occurs, resulting in a call to the fault handler Usage of MEM_WRITE

INT32 address;
INT32 data;

MEM_WRITE( address, &data );

The information pointed to by "data" is stored in location "address". If the address is not valid, a page fault occurs, resulting in a call to your fault handler. Usage of READ_MODIFY

INT32 address;
INT32 already_locked;

READ_MODIFY( address, &already_locked );

This is an atomic hardware instruction. Upon execution of this instruction, one of two actions is possible:

1. If the location specified by "address" contains a zero, then the location is set to non-zero and upon return, "already_locked" == 0.
2. If the location specified by "address" contains a non-zero, then the location is NOT modified and upon return, "already_locked" != 0.

Common usage of this mechanism is as a lock. When "already_locked" returns a zero, then the caller of READ_MODIFY can assume that it is the only user of a particular location.

5.3 Context Switching Primitives

5.3.1 What is a Context?

Whenever the Z502 machine is executing code, we say it does so in some context. A context is a state of the executing CPU, essentially the contents of its registers. If the machine is in user mode, then it has a user-mode context. Otherwise it has a kernel-mode context. In our machine, a context includes the contents of the registers described in section 3.

The current context, that is, the contents of those registers mentioned above, can be captured by Z502 hardware and stored away in a data structure, predefined and known to hardware, in the Kernel memory. A context data structure can be loaded into the relevant Z502 registers, thereby causing the CPU to execute that context. This means that any state of execution, that is, a context, may be stored away and later resumed in our machine.

The context data structure as known to the Z502 hardware is not visible to the OS (you don't need to use it.) But the OS does hang on to the address of the context structure and uses it as a handle for telling the hardware what process/context to load next. The context data base is owned by the hardware and shouldn't be messed with by the Operating System.. One convenient way for the operating system to do this is to define a Process Control Block (PCB) that has lots of process related information in it. In addition, it contains the pointer to the context structure. That pointer can be handed to the hardware as needed.

5.3.2 Primitives that Manipulate Contexts

In the Z502 machine, a context data structure can be created or destroyed by invoking the MAKE_CONTEXT and DESTROY_CONTEXT primitives. The operating system can also cause a context switch by invoking the SWITCH_CONTEXT primitive. When the operating system switches the CPU into a different context we say it .i resumes that context. These primitives are invoked as C routines in kernel mode as described below: Usage of Z502_MAKE_CONTEXT

CONTEXT *context_pointer;
void starting_address();
BOOL kernel_or_user;

Z502_MAKE_CONTEXT( &context_pointer, starting_address, kernel_or_user );

Causes the Z502 to create a context. You must specify the starting address and whether that address is in user (USER_MODE) or kernel (KERNEL_MODE). The context_pointer is returned; this pointer must be used in all future communication between the OS and the Z502.

Note that you pass in a pointer to the pointer to the context. Usage of Z502_DESTROY_CONTEXT

CONTEXT *context_pointer;

Z502_DESTROY_CONTEXT( &context_pointer );

Causes the Z502 to destroy a context. Future reference to this context address will cause an error; since the context, and the process associated with it, no longer exist.

Note that you pass in a pointer to the pointer to the context. Usage of Z502_SWITCH_CONTEXT

BOOL save_or_destroy;
CONTEXT *context_pointer;

Z502_SWITCH_CONTEXT( save_or_destroy, &context_pointer );

Causes the Z502 to switch to a context given by context_pointer. The current context is saved if save_or_destroy is SWITCH_CONTEXT_SAVE_MODE. The current context is destroyed if save_or_destroy is SWITCH_CONTEXT_KILL_MODE.

Note that you pass in a pointer to the pointer to the context.

Note again that Z502_MAKE_CONTEXT only creates a new context data structure that magically resides somewhere in the hardware microstore; the new context is not executed until it is explicitly transferred to by a Z502_SWITCH_CONTEXT primitive.

These are the steps taken by Z502 when Z502_SWITCH_CONTEXT is invoked:

1. Before the SWITCH_CONTEXT, Z502_REG_CURRENT_CONTEXT points to the running context U and the internal registers contain the values of such context.
2. If SWITCH_CONTEXT_SAVE_MODE is specified in the argument save_or_destroy, then the current context (context U) is not destroyed. Note that for this context to be of any future use, you should save a pointer to it in a user variable before invoking Z502_SWITCH_CONTEXT.
3. If SWITCH_CONTEXT_KILL_MODE is specified, the current register values are not saved, and the context data structure previously pointed to by Z502_REG_CURRENT_CONTEXT (context U) is destroyed.
4. The context pointed to by the argument context_ptr (context V) is loaded into the registers. The contents of the register Z502_REG_CURRENT_CONTEXT are replaced by that of context_ptr.
5. Before going to the user process, the SWITCH_CONTEXT code calls a routine os_switch_context_complete which is under the control of the Operating System.

When Z502_SWITCH_CONTEXT finishes, the machine is in the mode specified by the context it has just resumed. Therefore Z502_SWITCH_CONTEXT is the vehicle for the Kernel mode to switch to User mode.

Remember that Z502_SWITCH_CONTEXT is a privileged instruction not available in User mode. Therefore, it can only be used to switch a context in KERNEL_MODE into another kernel context or into a user context. Switches from a user context into a kernel context are performed by hardware exceptions and SOFTWARE TRAP's, as described in the next section.

5.4 Other Hardware Primitives

The clock routine is used to determine the current time of day. Halt and Idle are here for your use; when you simply want to wait for the next interrupt, or when you want to halt the machine.

Usage of Z502_CLOCK

INT32 time_since_midnight;

Z502_CLOCK( &time_since_midnight );

The value returned is the time since the most recent midnight. In practice, it's the number of time units since the simulation began. Usage of Z502_HALT

Z502_HALT();

Call this routine when the simulation is complete. There is no return from this routine.

Usage of Z502_IDLE

Z502_IDLE();

When there is no process ready to run, call this hardware instruction. The Z502 will become idle until the next exception occurs. Warning! Undefined results occur if you destroy the current context and then call Z502_IDLE; this is because when you make the call, you're running on an illegal context.

6. Interrupts, traps, faults and Operating System Invocation

A switch to OS502 can be forced upon the current execution by a hardware exception. When a user-mode context wishes to invoke the kernel, presumably for some operating system services, it must execute a system call, that causes a SOFTWARE TRAP to occur. A SOFTWARE TRAP is handled by the hardware just like an exception or fault.

Exceptions can occur for several reasons. Each reason has an entry associated with it in each of the three vectors used for exceptions, faults and traps: TO_VECTOR , and STAT_VECTOR. Each time the CPU encounters an exception, it performs the following steps:

1. Set the STAT_VECTOR as described below.
2. Execute the routine pointed to by the TO_VECTOR entry associated with the reason. The execution will be in kernel mode.

These actions are performed in hardware atomically when an exception occurs.

6.1 Reasons for Exceptions

The various reasons for exceptions to occur are:

DISK AND DELAY_TIMER INTERRUPTS

An I/O instruction has completed. The meaning of the value of the STAT_VECTOR entry depends on the device (see Section 7 on Devices). Note that each of the devices has its own entry in the vectors. There may be more than one process waiting for I/O interrupts.

SOFTWARE_TRAP

The user program has executed a system call or SOFTWARE TRAP instruction, presumably requesting some service from the operating system. The entry in the STAT_VECTOR is the SOFTWARE TRAP code from the instruction. See the next section on Vector Nitty-Gritty for details.

PAGE_FAULT ( INVALID_MEMORY FAULT )

The virtual to physical address translation for a user instruction has failed (see Section 8 on Address Translation.) The STAT_VECTOR entry contains information about the faulting address.

CPU ERROR FAULT

For some reason, bad data was given to the CPU. An easy way to get this error is to pass a bad pointer to a context block to the hardware. The STAT_VECTOR entry contains an error code.

PRIVILEGED INSTRUCTION FAULT

The machine was in USER_MODE ( running a user program ) when a privileged hardware instruction was executed.

6.2 Masking Interrupts

The Operating System may want to prevent interrupts from occurring during some critical sections of code. Some "wimpy" systems disable future interrupts while handling current interrupts. Real systems would not do this however, since the interrupt latency can become excessively long. They would instead perform some critical portions of interrupt handling, and then reenable interrupts, allowing an interrupt on an interrupt. Obviously this requires having reentrant code.

The Z502_REG_INTERRUPT_MASK is simpler than in most machines. It is hardware read only. If the hardware would like to cause an interrupt, it first looks at this mask to determine if the OS will allow an interrupt. If the MASK is TRUE, then no interrupt will occur. If FALSE, the interrupt will occur as expected. It is assumed by the hardware that the Operating System will read/write this register as needed.

6.3 Vector Nitty-Gritty

This section contains details on how the TO_VECTOR and STAT_VECTOR are set up for each type of exception. The TO_VECTOR contains the addresses of the handlers for the three types of exceptions; in os_init(), there are pointers to the routines that will support these exceptions. In the table below are listed the various exceptions, the type of exception represented, and the offset into the TO_VECTOR that the hardware will reference when this exception occurs:

Here's what happens in STAT_VECTOR. You've just arrived at one of your three exception handlers via the mechanism just described. Now, which of the Exceptions got you there? To find out, you must poll STAT_VECTOR[SV_ACTIVE][exception] to find the entry that is NOT 0. That entry then indicates the exception reason. For instance, suppose

you then know that a fault has occurred because of bad data supplied to the CPU. Having found the relevant exception, you can then look in

STAT_VECTOR[SV_VALUE][exception]

to get more information about the exception. Look at the supplied code in base.c to understand how this is implemented. The table below lists the exceptions, what they mean, and the meaning of the SV_VALUE field for that exception.

NOTE: There is not an explicit mnemonic defined for each of the DISK_INTERRUPTs. Disk number 1 will interrupt with exception number DISK_INTERRUPT; disk number 2 at DISK_INTERRUPT + 1, all the way to the highest disk, MAX_NUMBER_OF_DISKS, which has exception number DISK_INTERRUPT + MAX_NUMBER_OF_DISKS - 1. NOTE ALSO: The hardware ONLY sets values in STAT_VECTOR. It's up to the Operating System to clear these locations. If the OS doesn't clear these values, there may be indeterminate and strange values in STAT_VECTOR the next time an exception occurs.

As mentioned in the above table, error codes can be returned in field SV_VALUE on an exception. Here's an explanation of those errors:

7. Device Notes

7.1 Disk

The Z502 disk is a single rotating circular surface with a single read/write head that moves along the radius of rotation. The disk surface is divided into NUM_SECTORS angular sectors. The area of the disk that lies under the head at each head position is called a cylinder. Each sector contains PGSIZE BYTES; each cylinder contains NUM_SECTORS of these sectors. The disk rotates at a rate of one revolution every 16 milliseconds, and the head takes 0.1 milliseconds to traverse each cylinder when it changes position. The Z502 disk may be considered to have a NUM_CYLINDERS number of cylinders.

Only one I/O operation can be outstanding at any time on one disk; however, different disks can be in use simultaneously. The Z502 machine will abort or fault if a disk read or write operation is issued while there is another disk operation still pending on that device.

7.2 Delay Timer

The Z502 delay timer produces an interrupt <argument> milliseconds after it is started. This is useful for maintaining the SLEEP system call, and for managing CPU time limiting. If the requested time delay is less than 0, the timer interrupts immediately with an ERR_BAD_PARAM.

8. Address Translation

As shown in Table A.1, address translation hardware is only applicable to the User Memory and only in user mode.

8.1 Virtual Memory

Under this scheme, the registers Z502_REG_PAGE_TBL_ADDR and Z502_REG_PAGE_TBL_LENGTH apply. This scheme allows addresses generated by a user program, referred to as virtual addresses, to be translated through a page table.

Memory is addressed in increments of BYTES. But 4-bytes, a long integer, is the quantity of information that is read/written.

Virtual addresses are converted to real addresses in the following steps:

• The virtual address is divided into a virtual page number (VPN) and an offset within a page. Since the page length varies among different models of the Z502, the number of bits in the VPN and the offset varies. Thus, the format of a virtual address is:

• NOTE: The simulator can determine the page size at system boot time. This potential forces well written virtual memory code and allows you to examine the effect of varying page sizes on the paging system. The student's os_init() routine can derive any project specific shift, mask or other quantities at boot time from PGBITS and PGSIZE. The page size is guaranteed to be a power of two.
• The virtual page number ( VPN ) is used as an index into a table whose address is contained in the page table register (Z502_REG_PAGE_TBL_ADDR). If the VPN exceeds the contents of the page-table length register (Z502_REG_PAGE_TBL_LENGTH), a page fault trap occurs. Otherwise, the page table entry corresponding to the VPN is obtained from the 16-bit word at address (Z502_REG_PAGE_TBL_ADDR) + VPN. The format of a page table entry is:

The masks available to you, defined in C are given here. These masks are used by the hardware, so don't mess with them.

PTBL_VALID_BIT
PTBL_MODIFIED_BIT
PTBL_REFERENCED_BIT
PTBL_PHYS_PG_NO

Note that no Z502 machine can ever have more than 2 ^ 12, or 4K pages of physical memory, since the real page number field is only 12 bits long. But it isn't required to have that much.

1. If the valid bit is zero, Z502 generates a fault to the kernel (page fault) and does not execute the instruction. The VPN causing the fault is placed in the STAT_VECTOR entry.
2. If the valid bit is one, the physical page number is combined with the offset within the page to obtain an N-bit physical address. Then normal execution continues, using the physical address in place of the virtual address. After execution, Z502 sets the referenced bit in the page table entry, and if the memory location has been written into, sets the modified bit.

NOTE: All references to memory are returned in chunks of 4-bytes (long integers). The reference address need NOT be on 4-byte boundaries however.

8.2 Page Table Setup

The page table information should be set up at the time of the first fault. At that fault time, Z502_REG_PAGE_TBL_ADDR and Z502_REG_PAGE_TBL_LENGTH should be defined; because these items will be saved thereafter by the hardware in the CONTEXT, the Operating System need not worry about maintaining them.

Also at that fault time, and on all subsequent faults, the operating system will modify the contents of the page table as described in the previous section.

9. Configurations

The size of the memory of a particular Z502 machine, along with its page size, is contained in the following definitions:

Both PHYS_MEM_PGS and PGSIZE are guaranteed to be powers of 2.

10. Bootstrapping

When the machine is powered on, the entire operating system is automatically loaded into the kernel memory. After loading read-only registers with proper values, the machine creates an initial kernel context pointing to the operating system routine os_init(). The machine then switches the CPU into this initial context, causing the execution of the operating system to begin. Note that registers STAT_VECTOR and TO_VECTOR are to be initialized by the operating system, not by bootstrapping hardware.