代写C CPU系统进程、线程调度、代写ALU，Memory管理

日期：2018-05-21 01:06

The CPU

You have already constructed an arithmetic logic unit (ALU), and you have written the the bitfield manipulations needed to decode a 32-bit instruction word into the fields that control execution. Now we need to build the rest of the central processing unit (CPU), including registers, an interface to memory, and the sequential logic for executing programs that may have loops and conditional branches.

ALU

The ALU is a part of the CPU. In other words, an ALU object will be a field (variable) in the CPU object.

Memory

A simulated memory has been provided for you. It is very simple: Basically memory is just a list of 32-bit words, which we can model as Python ints. There just a few complications:

We want see our computer run, so we need to our memory to act as a model component in the model-view-controller design scheme. Therefore memory.py defines two event types (subclasses of MemoryEvent, which in turn are subclasses of MVCEvent) for memory reads. A MemoryRead event announces obtaining a value from memory and MemoryWrite announces storing a value into memory. Class Memory notifies its listeners of those events.

We need to deal with attempts to read or write non-existant memory cells. For example, if our memory contains 1024 (that is, 0x400) memory cells, and a machine language program attempts to read the memory cell at address 0x5A4, what should happen? In fact this is usually handled in the operating system, rather than the hardware, but we'll gloss over that detail and raise a SegFault exception, named lovingly after the operating system exception that you can look forward to encountering often when you learn C or C++.

Finally, we need some way for our programs to perform input and output (I/O). Simulating I/O could potentially be more complex than simulating the CPU, but we want to keep it very simple. The DM2018S has only a very simple I/O device for printing a number and another for reading a number. What does this have to do with memory? As in many real computers, access to the Duck Machine I/O devices is triggered by accesses to certain designated memory addresses. Instead of using the plain Memory class, we'll use the MemoryMappedIO subclass which allows some memory addresses to be hooked external functions. The main program in duck_machine.py hooks memory address 510 to a function that reads an integer and memory address 511 to a function that writes an integer.

Registers

Like any self-respecting CPU, the Duck Machine has a small number of very fast memory cells right on the CPU chip. Model DM2018S has 16 registers, numbered r0..r15. Registers r1..r15 are all registers with normal behavior, although r15 has a special use within the CPU. r0 is a special zero register that always holds zero. Class Register and ZeroRegister are provided for you in file register.py.

CPU State

The CPU needs to keep a few pieces of information as it executes:

The memory address from which the next instruction will be fetched. This is kept in register r15, so we do not need any additional variables for it.

The condition code from the last instruction executed. This will be used to determine whether the next instruction should be executed or skipped. It is a value of type CondFlag defined in file instr_format.py, and has exactly the same potential values as the condition field of a machine instruction. Since we always want the first instruction in a program to execute, condition code should initially be CondFlag.ALWAYS, i.e., all of its bits should be 1.

Whether the CPU is halted or not. This boolean value is initialzed to False. It may be set to True by executing the HALT instruction.

Each of these elements of CPU state will be fields (variables) in a CPU object. That includes the 16 registers (which can be a list of Register objects) and a reference to memory. You will need to create and/or initialize them in the constructor (the __init__ method). Since memory is not actually part of the CPU, a reference to memory should be passed to the constructor, so the method header for the __init__ method should look like this:

 def __init__(self, memory):

Since CPU is a subclass of MVCListenable, we also need to execute the constructor of MVCListenable. We don't want to repeat that code in class CPU, because that would be a nightmare if we ever needed to change some details in MVCListenable. Instead, we want to say “execute the constructor of the superclass”, which we can do in Python like this:

 super().__init__()

Sequential Logic

The CPU component (class CPU) needs logic for executing a single instruction, and logic for running continuously.

CPU.step()

This method is the heart of the CPU's sequential logic. The fetch/decodee/execute cycle is not very complicated, but the steps must be carried out in the proper order:

Fetch: The first step is to read a machine instruction. Instructions are in memory. Register r15 is treated as the program counter, so we need to get the value from r15, and use that value to address memory (Memory.get(address)).

Decode: Once we have the instruction word, we need to decode its bit fields into the meaningful parts of an instruction. This is the decode logic you developed in the prior project. It should produce an Instruction object with several fields.

Execute: This step can be broken down further:

Determine whether this instruction should be executed or skipped. This is called predicated execution. If any of the flag bits in the condition code (from the prior instruction) are also in the condition code field of the instruction, we say the predicate is satisfied. If the predicate is satisfied, then this instruction should be executed. Otherwise we will skip some of the following steps.

If the predicate is satisfied, then

Get the values of the two source registers. The instruction contains the indexes of the registers; we need to get their contents from the Register objects in the CPU.

Add the (signed) value of the offset field to the value of the second source register.

Increment the program counter (contents of register r15). Why now? We are doing it after getting the source register contents so that we don't change r15 before using its value. We are doing it before computing and saving a result so that, if we modify the r15, the modified value will replace the incremented value.

Send the operation code and two operand values to the ALU object (that is, call the ALU.exec() method), and obtain a result and condition code. Save the condition code in the CPU state.

What we do with the operation result (returned from ALU.exec()) depends on the operation code. If the operation is LOAD or STORE, then the result is a memory address, and we either copy a value from memory into the target register (for a LOAD) or copy the value from the target register into the designated memory cell (for a STORE). If the operation code is HALT, we just change the CPU state to halted. For all other operations, the result is stored in the target register.

If the predicate is not satisfied, then

Increment the program counter register, but don't do anything else with this instruction.

We also need to update the display. Notice that the CPUStep event class takes the address of the instruction to be executed, the binary instruction word, and the decoded instruction. The best place to do this is therefore after decoding the instruction but before executing it. The event notification should look something like this (possibly with different variable names):

  self.notify_all(CPUStep(self, instr_addr, instr_word, instr))

CPU.run()

The run method is very simple — it's just a loop that calls the step method repeatedly. There are just a few details that provide some extra control:

A starting address. By default, we will always start program execution at address 0, but it might be useful to be able to start execution at a different address. (In some real CPUs, this address is taken from a known address in read-only memory.) This value should be stored in the program counter, r15, before starting execution.

A flag (boolean) for single-step mode. It should default to False, that is, the CPU normally runs without pausing until it executes the HALT instruction, but a single-step mode makes debugging both DM2018S programs and the DM2018S processor itself much easier. In single-step mode, the loop simply pauses for input each time through the loop, like this:

           if single_step:

               input("Step {}; press enter".format(step_count))

The header for the run method should look like this:

   def run(self, from_addr=0, single_step=False) -> None:

How to approach this project

Starter code for this project is at https://github.com/UO-CIS211/duck_machine.

Once again the amount of code to write is fairly small, but it requires some care to do it correctly. You can expect to spend a good deal of your time debugging. For debugging, the single-step option and the visual display of CPU state are very helpful, but only if you know what you expect to see. For that, it helps to start with extremely simple DM2018S programs.

Start with a program that has no branching, no predication, and no access to main memory. I have provided this one in assembly language as first.asm and in object code as first.obj:

#

# A first DM2018S program.  This program uses only sequential

# control flow (no predication or branching) and only affects

# registers.  When the program halts, we should see that register

# 1 contains value 1, register 2 contains value 2, and register

# 3 contains value 3.

#

  ADD  r1,r0,r0[1]    # r1 = 1

  ADD  r2,r0,r0[2]    # r2 = 2

  ADD  r3,r1,r2       # r3 = r1 + r2

  HALT r0,r0,r0

Run the program like this:

python3 duck_machine.py --display programs/first.obj

When it halts, you should see the results in the registers display:

Next, you could try a program that accesses memory cells, like second.asm:

#  Second DM2018S:  1 + 2 = 3, but

#  this time reading a value from memory

#  and storing into memory.

#

ADD   r1,r0,r0[1]    # r1 = 1

LOAD  r2,x           # r2 = Mem[x]

ADD   r3,r1,r2       # r3 = r1 + r2

STORE r3,y           # Mem[y] = r3

HALT   r0,r0,r0

x: DATA  2              # A memory cell to hold x, initialized to 2

y: DATA 99              # A memory cell to hold y

Note that this program contains references to variables x and y. Those names are meaningless to the DM2018S, which needs numeric addresses for the memory cells. In the following project we'll take care of that by building an assembler, which will first resolve those variable names into addresses like this:

ADD   r1,r0,r0[1]    # r1 = 1

LOAD r2,r0,r15[4]  # Access variable 'x'

ADD   r3,r1,r2       # r3 = r1 + r2

STORE r3,r0,r15[3]  # Access variable 'y'

HALT   r0,r0,r0

x: DATA  2              # A memory cell to hold x, initialized to 2

y: DATA 99              # A memory cell to hold y

... and then into object code ...

264503297

130563076

265046016

197934083

62914560

2

99

Execute this program as we did the first, and we should see the value 3 stored in memory as well as in register r3:

Emboldened by success, you might next try a program with conditional branches and input/output, like max.asm:

# Determine the maximum of two integers.

# This program triggers memory-mapped IO to

# read integers from the console and to

# write integers to the console.

  LOAD r1,r0,r0[510]     # Trigger read from console

  LOAD r2,r0,r0[510]     # Trigger read from console

  SUB  r0,r1,r2[0]

  JUMP/P r1bigger

  STORE r2,r0,r0[511]    # Trigger write to console

  HALT r0,r0,r0

r1bigger:

  STORE r1,r0,r0[511]    # Trigger write to console

  HALT r0,r0,r0

We can't run max.asm directly, because it is assembly language source code, rather than object code. But we can run max.obj, which was created from max.asm by “assembling” it.

If we run this code without the display, we expect this interaction:

python3 duck_machine.py  programs/max.obj

Quack! Gimme an int! 17

Quack! Gimme an int! 38

Quack!: 38

Halted

python3 duck_machine.py  programs/max.obj

Quack! Gimme an int! 93

Quack! Gimme an int! 24

Quack!: 93

Halted

Suppose that isn't what we see. Suppose we get a different result, or (most likely) the duck machine simulator crashes. How can you debug it? In addition to the display, there are two other useful tools to bring to bear. The first is single-stepping. Use the --step command line argument to pause after each instruction. This is especially useful together with the --display argument, so that you can inspect the state of your simulated CPU before and after each instruction:

python3 duck_machine.py  programs/max.obj --step --display

Quack! Gimme an int! 93

Step 1; press enter

Quack! Gimme an int! 88

Step 2; press enter

Step 3; press enter

Step 4; press enter

Quack!: 93

Step 5; press enter

Step 6; press enter

Halted

Press enter to end

Single-stepping will at least help you find where execution went wrong (but only if you have already decided what you expect to see after each step).

When you know what part of your simulator code is not doing what you think it should, you can obtain additional information with the logging facility. This is like adding print statements, but much more convenient. Within the cpu.py file, as within many of the Python starter code modules I write, you can where the logging facility is configured:

import logging

logging.basicConfig()

log = logging.getLogger(__name__)

log.setLevel(logging.INFO)

Here it is set to the INFO level to print only informational messages and warnings. For more verbose output, we can set it to the DEBUG level:

log.setLevel(logging.DEBUG)

This will activate calls to log.debug(), which we can place in the code like print statements, e.g.,

           if opcode == OpCode.LOAD:

               log.debug("Loading value from memory address {} to register {}".format(result, instr.reg_target))

               memval = self.memory.get(result)

You can then run your program again, with or without the display. The extra output will of course depend on what log.debug() calls you placed in your code. Make sure each one prints something that is unique (e.g., indicating where in the program it is), because otherwise it is very easy to get confused about which output comes from which debugging statement. My sample solution produces the following debugging output:

python3 duck_machine.py  programs/max.obj

DEBUG:cpu:Step at PC=0

DEBUG:cpu:Instruction: LOAD      r1,r0,r0[510]

DEBUG:cpu:Predicate passed

DEBUG:cpu:Loading value from memory address 510 to register 1

Quack! Gimme an int! 12

DEBUG:cpu:Step at PC=1

DEBUG:cpu:Instruction: LOAD      r2,r0,r0[510]

DEBUG:cpu:Predicate passed

DEBUG:cpu:Loading value from memory address 510 to register 2

Quack! Gimme an int! 39

DEBUG:cpu:Step at PC=2

DEBUG:cpu:Instruction: SUB      r0,r1,r2[0]

DEBUG:cpu:Predicate passed

DEBUG:cpu:Step at PC=3

DEBUG:cpu:Instruction: ADD/P    r15,r0,r15[3]

DEBUG:cpu:Predicated instruction will not execute

DEBUG:cpu:Step at PC=4

DEBUG:cpu:Instruction: STORE      r2,r0,r0[511]

DEBUG:cpu:Predicate passed

DEBUG:cpu:Storing register 2 into memory address 511

Quack!: 39

DEBUG:cpu:Step at PC=5

DEBUG:cpu:Instruction: HALT      r0,r0,r0[0]

DEBUG:cpu:Predicate passed

Halted

In each line produced by the logging module, the first part (DEBUG:) identifies it as the result of a call to log.debug, and the second part identifies the module name (cpu); the message given to log.debug (e.g., “Predicate passed”) follows.

After you have found and fixed your bug, you could remove the calls to log.debug, but if they might be useful in the future you can leave them in the code and just deactivate them by changing the logging level back to INFO:

log.setLevel(logging.INFO)