Homework 1: P-Machine
COP 3402: Systems Software
Spring 2025
See Webcourses for due dates.
Purpose
In this homework you will form a team and implement a virtual machine called the P-machine.
Teams must be either 1 person team or 2 people team.
Directions
(100 points) Implement and submit the P-machine as described in the rest of this document.
For the implementation, your code must be written in ANSI standard C and must compile with gcc and run correctly on Eustis. We recommend using the flag -Wall and fixing all warnings.
What to Read
Our recommended book is Systems Software: Essential Concepts (by Montagne) in which we recommend reading chapters 1-3.
In this assignment, you will implement a virtual machine (VM) known as the P-machine (PM/0).
P-Machine Architecture
The P-machine is a stack machine that conceptually has one memory area called the process address space (PAS). The process address space is divided into three contiguous segments: The first 10 locations, called “unused”, the “text”, which contains the instructions for the VM to execute and the “stack,” which is organized as a data-stack to be used by the PM/0 CPU.
Registers
The PM/0 has a few built-in registers used for its execution: The registers are named:
• base pointer (BP), which points to the base of the current activation record
• stack pointer (SP), which points to the current top of the stack. The stack grows downwards.,
• program counter (PC), which points to the next instruction to be executed.
• Instruction Register (IR), which store the instruction to be executed
The use of these registers will be explained in detail below. The stack grows downwards.
Instruction Format
The Instruction Set Architecture (ISA) of the PM/0 hasinstructions that each have three components, which are integers (i.e., they have the C type int) named as follows.
OPis the operation code.
Lindicates the lexicographical level (We will give more details on L below)
Mdepending of the operators it indicates:
- A number (when OP is LIT or INC).
- A program address (when OP is JMP, JPC, or CAL).
- A data address (when OP is LOD, STO)
- The identity of the arithmetic/relational operation associated to the OPR op-code.
(e.g. OPR 0 2 (ADD) or OPR 0 4 (MUL))
The list of instructions for the ISA can be found in Appendix A and B.
P-Machine Cycles
The PM/0 instruction cycle conceptually does the following for each instruction:
The PM/0 instruction cycle is carried out in two steps. The first step is the fetch cycle, where the instruction pointed to by the program counter (PC) is fetched from the “text” segment, placed in the instruction register (IR) and the PC is incremented to point to the next instruction in the code list. In the second stepthe instruction in the IR is executed using the “stack” segment. (This does not mean that the instruction is stored in the “stack segment.”)
Fetch Cycle:
1.- IR.OP ß pas[pc]
IR.L ß pas[pc + 1]
IR.M ß pas[pc + 2]
(note that each instruction need 3 entries in array “TEXT”.
2.- (PCß PC + 3).
Execute Cycle:
The op-code (OP) component in the IR register (IR.OP) indicates the operation to be executed. For example, if IRencodes the instruction “2 0 2”, then the machine adds the top two elements of the stack, popping them off the stack in the process, and stores the result in the top of the stack (so in the end sp is one less than it was at the start). Note that arithmetic overflows and underflows happen as in C int arithmetic.
PM/0 initial/Default Values
When the PM/0 starts execution.
BP == 499, SP == 500, and PC == 10;
This means that execution starts with the “text segment” element 10. Similarly, the initial “stack” segment values are all zero (BP=499 and SP = BP + 1).
The figure bellow illustrates the process address space:
Last instruction BP SP
0 10
PAS UNUSED TEXT OP L M STACK ???
499 500
PC
Size Limits
Initial values for PM/0 CPU registers are:
BP = 499
SP = BP + 1;
PC = 10;
Initial process address space values are all zero:
pas[0] =0, pas[1] =0, pas[3] =0…..[n-1] = 0.
Constant Values:
ARRAY_SIZE is 500
Note: Be aware that in PM/0 the stack is growing downwards
Assignment Instructions and Guidelines:
1. The VM must be written in C and must run on Eustis3. If it runs in your PC but not on Eustis, for us it does not run.
2. The input file name should be read as a command line argument at runtime, for example: $ ./a.out input.txt (A deduction of 5 points will be applied to submissions that do not implement this).
3. Program output should be printed to the screen, and should follow the formatting of the example in Appendix C. A deduction of 5 points will be applied to submissions that do not implement this.
4. Submit to Webcourses:
a) A readme text file indicating how to compile and run the VM
b) The source code of your PM/0 VM which should be named “vm.c”
c) A signed sheet indicating the contribution of each team member to the project.
d) Student names should be written in the header comment of each source code file, in the readme, and in the comments of the submission
e) Do not change the ISA. Do not add instructions or combine instructions. Do not change the format of the input. If you do so, your grade will be zero.
f) Include comments in your program. If you do not comments, your grade will be zero.
g) Do not implement each VM instruction with a function. If you do, a penalty of -100 will be applied to your grade. You should only have functions: main, base, auxiliary functions to print but you must not use functions to implement instructions or FETCH. (Appendix D).
h) The team member(s) must be the same for all projects. In case of problems within the team. The team will be split and each member must continue working as a one-member team for all other projects.
i) On late submissions:
o One day late 10% off.
o Two days late 20% off.
o Submissions will not be accepted after two days.
o Resubmissions are not accepted after two days.
o Your latest submission is the one that will be graded.
We will be using a bash script to test your programs. This means your program should follow the output guidelines listed (see Appendix C for an example). You don’t need to be concerned about whitespace beyond newline characters. We use diff -w.
Rubric:
If you submit a program from another semester or we detect plagiarism your grade is F for this course.
Using functions to implement instructions even if only one is implemented that way, means that your grade will be “zero”.
Pointers and handling of dynamic data structures is not allowed. If you do your grade is “zero”. Only file pointer is allowed.
-100 – Does not compile
10 – Compiles
25 – Produces lines of meaningful execution before segfaulting or looping infinitely
5 – Follows IO specifications (takes command line argument for input file name and prints output to console)
10 – README.txt containing author names
5 – Fetch cycle is implemented correctly
10 – Well commented source code
5 – Arithmetic instructions are implemented correctly
5 – Read and write instructions are implemented correctly
10 – Load and store instructions are implemented correctly
10 – Call and return instructions are implemented correctly
5 – Follows formatting guidelines correctly, source code is named vm.c
Appendix A
Instruction Set Architecture (ISA) – (eventually we will use “stack” to refer to the stack segment in PAS)
In the following tables, italicized names (such as p) are meta-variables that refer to integers. If an instruction’s field is notated as “-“, then its value does not matter (we use 0 as a placeholder for such values in examples).
ISA:
01 – LIT0, MPushes a constant value (literal) M onto the stack
02 – OPR0, MOperation to be performed on the data at the top of the stack. (orreturn from function)
03 – LODL, MLoad value to top of stack from the stack location at offset M from L lexicographical levels down
04 – STOL, MStore value at top of stack in the stack location at offset M
from L lexicographical levels down
05 – CALL, MCall procedure at code index M (generates new
Activation Record and PC ß M)
06 – INC0, MAllocate M memory words (increment SP by M). First threeare reserved to Static Link (SL), Dynamic Link (DL), and Return Address (RA)
07 – JMP0, MJump to instruction M (PC ßM)
08 – JPC 0, MJump to instruction M if top stack element is 0
09 – SYS 0, 1Write the top stack element to the screen
SYS 0, 2Read in input from the user and store it on top of the stack
SYS 0, 3End of program (Set “eop” flag to zero)
OP Code Number OP Mnemonic L M Comment (Explanation)
01 LIT 0 n Literal push: sp ß sp- 1; pas[sp] ßn
02 RTN 0 0 Returns from a subroutine is encoded 0 0 0 and restores the caller’s AR:
sp ← bp + 1; bp ← pas[sp - 2]; pc ← pas[sp -3];
03 LOD n a Load value to top of stack from the stack location at offset o from n lexicographical levels down
sp ß sp - 1;
pas[sp] ß pas[base(bp, n) - o];
04 STO n o Store value at top of stack in the stack location at offset o from n lexicographical levels down
pas[base(bp, n) - o] ß pas[sp];
sp = sp +1;
05 CAL n a Call the procedure at code address a, generating a new activation record and setting PC to a:
pas[sp - 1] ß base(bp, n); /* static link (SL)
pas[sp - 2] ß bp;/* dynamic link (DL)
pas[sp - 3] ß pc; /*return address (RA)
bp ß sp - 1;
pc ß a;
06 INC 0 n Allocate n locals on the stack
sp ß sp - n;
07 JMP 0 a Jump to address a:
PC ← a
08 JPC 0 a Jump conditionally: if the value in stack[sp] is 0, then jump to a and pop the stack:if (stack[SP] == 0) then { pc (← a; } sp ← sp+1
09 SYS 0 1 Output of the value in stack[SP] to standard output as a character and pop:putc(stack[sp]); sp ← sp+1
(You can use printf if you wish)
SYS 0 2 Read an integer, as character value, from standard input (stdin) and store it on the top of the stack.sp ← sp-1; stack[sp] ← getc();
(You can use fscanf if you wish)
SYS 0 3 Halt the program (Set “eop” flag to zero)
Appendix B (Arithmetic/Logical Instructions)
ISA Pseudo Code
02 – OPR 0, #(1 <= # <= 10)
1ADDpas[sp + 1] ß pas[sp + 1] + pas[sp]
sp ß sp + 1;
2SUBpas[sp + 1] ß pas[sp + 1] - pas[sp]
sp ß sp + 1;
3MULpas[sp + 1] ß pas[sp + 1] * pas[sp]
sp ß sp + 1;
4DIVpas[sp + 1] ß pas[sp + 1] / pas[sp]
sp ß sp + 1;
5EQLpas[sp + 1] ß pas[sp + 1] == pas[sp]
sp ß sp + 1;
6NEQpas[sp + 1] ß pas[sp + 1] != pas[sp]
sp ß sp + 1;
7LSSpas[sp + 1] ß pas[sp + 1] < pas[sp]
sp ß sp + 1;
8LEQpas[sp + 1] ß pas[sp + 1] <= pas[sp]
sp ß sp + 1;
9GTRpas[sp + 1] ß pas[sp + 1] > pas[sp]
sp ß sp + 1;
10GEQpas[sp + 1] ß pas[sp + 1] >= pas[sp]
sp ß sp + 1;
Appendix C
Example of Execution
This example shows how to print the stack after the execution of each instruction.
INPUT FILE (In this example the program was stored at memory address zero)
For every line, there must be 3 values representing OP, Land M.
7 0 45
7 0 6
6 0 4
1 0 4
1 0 3
2 0 3
4 1 4
1 0 14
3 1 4
2 0 7
8 0 39
1 0 7
7 0 42
1 0 5
2 0 0
6 0 5
9 0 2
5 0 6
9 0 1
9 0 3
When the input file (program) is read in to be stored in the text segment starting at location 10 in the process address space, each instruction will need three memory locations to be stored. Therefore, the PC must be incremented by 3 in the fetch cycle.
10 13 16 19 22 25 …
7 0 45 7 0 6 6 0 4 1 0 4 1 0 3 2 0 4 etc
The initial CPU register values for the example in this appendix are:
SP = 500;
BP = SP - 1;
PC = 10;
IR = 0 0 0; (a struct or a linear array can be used to implement IR)
Hint: Each instruction uses 3 array elements and each data value just uses 1 array element.
OUTPUT FILE (In this example the program was storedat memory address zero)
Print out the execution of the program in the virtual machine, showing the stack and pc, bp, and sp.
NOTE: It is necessary to separate each Activation Record with a bar “|”.
PCBPSPstack
Initial values:10499500
JMP04545499500
INC05484994950 0 0 0 0
Please Enter an Integer: 3
SYS02514994940 0 0 0 0 3
CAL0664934940 0 0 0 0 3
INC0494934900 0 0 0 0 3 | 499 499 54 0
LIT04124934890 0 0 0 0 3 | 499 499 54 0 4
LIT03154934880 0 0 0 0 3 | 499 499 54 0 4 3
MUL03184934890 0 0 0 0 3 | 499 499 54 0 12
STO14214934900 0 0 0 12 3 | 499 499 54 0
LIT014244934890 0 0 0 12 3 | 499 499 54 0 14
LOD14274934880 0 0 0 12 3 | 499 499 54 0 14 12
LSS07304934890 0 0 0 12 3 | 499 499 54 0 0
JPC039394934900 0 0 0 12 3 | 499 499 54 0
LIT05424934890 0 0 0 12 3 | 499 499 54 0 5
RTN00544994940 0 0 0 12 3
Output result is: 3
SYS01574994950 0 0 0 12
SYS03604994950 0 0 0 12
Appendix D
Helpful Tips
This function will be helpful to find a variable in a different Activation Record some L levels down:
/**********************************************/
/*Find base L levels down */
/* */
/**********************************************/
int base( int BP, int L)
{
int arb = BP;// arb = activation record base
while ( L > 0) //find base L levels down
{
arb = pas[arb];
L--;
}
return arb;
}
For example in the instruction:
STO L, M - You can do stack [base (IR.L) + IR.M]= pas[SP] to store the content of the top of the stack into an AR in the stack, located L levels down from the current AR.
Note1: we are working at the CPU level therefore the instruction format must have only 3 fields. Any program whose number of fields in the instruction format is graterthan 3 will get a zero.
Note2: If your program does not follow the specifications, your grade will get a zero.
Note3: if any of the instructions is implemented by calling a function, your grade will be zero.
Note4: If you use dynamic memory handling, your grade will be zero.
Note5: Pointers are not allowed, except to read a file.
請加QQ：99515681 郵箱：99515681@qq.com WX：codinghelp
