CPU Simulator

Joseph Bergin
Pace University

A Java CS1 course module introducing:

Basic CPU operation cycle
Concept of a Process
Concurrency (time slicing in the cpu)
Race Conditions with Shared Memory
Simple file i/o
Vector, Enumeration, Factory Method Pattern
Container Class Library
Queue processing
Inheritance and Polymorphism
Inner Classes
Singleton Pattern
Immutable Object Pattern
Cloning objects

Reinforces Assembler Language and completes it (jump instructions)

Introduction

This module extends the SimpleCPU, which focused on Assembler, to include a more complete Assembler and a CPU simulator that permits processes to be created and executed. It uses a randomized form of time slicing (It rolls a die to determine how many instructions of a process to execute in a process before interrupting it) to achieve a simulated concurrency model.

Student Handouts

Here is a library of sources for this project. (The handouts can be excerpted from these. The current versions show solutions to some of the possible exercises.) The main three files are CPUProcess, Program, and Simulator. These should be first given in hard copy only so that students will really read them. The rest are part of a basic Container library rather more sophisticated than the Java 1.1 util classes. These can be given in machine readable form. They could also be replaced by Java 2 Container class code. They are needed to get a Queue, and for randomization. Alternatively, if the students had previously built a queue, then most of these auxiliary classes could be dropped, and the students could use their own queue here (Tool Box pedagogical pattern).

Some time prior to the class in which it is to be discussed, the sources are distributed to students for study. The study should preferably be done in small teams. The instructor can also distribute a list of questions that should be answered about the code. Some of these questions could point to student resource material such as information in the course text on inner classes, for example.

The questions should require that they understand and can trace the writer code. Note that the arguments to the label instruction are not instruction numbers, but may be any "symbols". Also note that declare and label are pseudo operations and don't result in any code being entered into the process.

Lecture Outline

Question and Answer period. Note that the Instruction objects are Immutable. There are no mutators in these classes.
Queue processing. The queue class here is actually a double ended queue though it is used as a simple queue.
CPU fetch-increment-do cycle
Process concept (program + pc + stack + memory + io state) memory and io state may be shared with other processes. You can discuss how the queue achieves fairness in allocating execution time.
Brief explanation of jump logic in assembler. Note that the conditional jumps use the stacktop as a condition. They leave the stack top value in place.
In class exercise
(perhaps) Queue implementation using a linked list
Inheritance and Polymorphism (See the Instruction class hierarchy)Focus on how each Instruction object knows which execute operation to use when told to do so by the simulator in the step method.
Assignments and Wrap-up

In Class Exercise (team)

In small teams, the students can design a reader process to accompany the given writer. They could also develop the Class diagram for this program. (I may write this up as a pedagogical pattern "Reverse Engineering"). If some instructions were removed before the handouts were given, they could be asked to implement one of them. This can be a Student Design Sprint, in which the first round has teams of 2 students and the second round combines 2 teams so you have 4 students debugging each other's solutions. If the Queue from this library isn't used, students could design a queue using Student Design Sprint in 2 or 3 rounds.

Note that the program works as expected with one (simple) reader, but misbehaves with more than one. This is because the buffer (one element queue) is shared but not protected from simultaneous access.

Take Home Exercise (team or individual)

This exercise explores race conditions in a CPU with shared memory as well as the Singleton design pattern.

Some of the instruction classes can be removed from the hand out code and the students asked to implement them. They could be asked to develop a process to carry out some task.

Some of the classes here can be singletons (the simulator, for example). A handout explaining this pattern and its implementation can be given. The students can then choose which should be singletons and reimplement the instruction hierarchy accordingly. Note, however, that this pattern can't be used with Java inner classes since inner classes can't have static members.

The Queue class could be implemented by the students and used within.

Students can evaluate (and perhaps implement) an alternate design in which the process class is inner to the simulator class.

An extensive project might be to put a GUI on this model.

A very hard problem would to build the jump and label structure from a description. This implies that the instructor removed these from the code before handing it out, of course. It requires solving the forward reference problem. It was done here by keeping a vector of forward references which is examined each time a new label is defined to see if any previous references are to this label. If so, the corresponding jump instruction is updated.

Follow Up

The "memory" here is NOT an array of cells. Instead it is a hash table in which the variable names (integers actually) are the keys. This is a very abstract view, but one appropriate for teaching languages with symbolic addresses.

Note on the use of inner classes. The instructions are inner to the cpu process objects. This means that when they are created they have an implicit link to the process in which they are created. When such an object is cloned, the newly created clone will still have links back to the original containing object. This means (among other things) that a cloned instruction (from this program) that is placed into a NEW process object can't really get access to its own process variables like the serial number and state. Solutions to this include making the instruction class static (so that there is no link at all), or omitting the clone method altogether, requiring that a new process with the same program be created from scratch. We have implemented an alternate solution here, using a method makeCopyIn, that copies instructions in the context of the new process for insertion into its program.

Pedagogical Patterns

Larger than Life. Toy Box. Uses parts of a Tool Box. Fill in the Blanks. Student Design Sprint. Test Tube exploring concurrency and race conditions. See http://csis.pace.edu/~bergin/PedPat1.2.html, and http://csis.pace.edu/~bergin/fivepedpat.html for details.