I. Overview of Systems Software What consitutes systems software? What are examples? What does a compiler do? How is a compiler different than an interpreter? What is an assembler? A. Compilation overview ------------------------------------------ INFO. FLOW FOR COMPILED LANGUAGES Source ---> [ Compiler ] ---> Object Code Code Other | Module(s) | \ | \ v Library v(Static) Code --> [Linker] | | v Executable (ELF) | | v [Loader] Dynamic | Library - | Code | | v v (Dynamic)<-Running [Linker]-->Program [Operating System (OS)] ------------------------------------------ What's an example of a programming language that source code might be written in? B. Interpreter overview ------------------------------------------ FLOW FOR INTERPRETED LANGUAGES Source--> [ Interpreter ]--> (Bytecode) Other | Module(s) | \ | \ | Library v v Code --> [Virtual Dynamic > Machine] Library / Code [Operating System (OS)] ------------------------------------------ What are some examples of interpreted programming languages? What are the advantages of using a VM (vs. direct execution)? C. OS support for running programs What is a computer's memory like (as a data structure)? 1. Object Files ------------------------------------------ OBJECT FILES def: an *object file* holds What data is needed? ------------------------------------------ What information must be stored in an object file? If you were designing a format for object files, which would you put first? ------------------------------------------ OBJECT FILE FORMAT ------------------------------------------ II. The Tiny Machine A. Computer Organization, von Neumann architecture What are the main parts of a computer CPU? ------------------------------------------ VON NEUMANN ARCHITECTURE (HARDWARE) /------> [ PC ] | | | v |------> [ MAR ] | | | v | [ MEMORY ] | [ (RAM) ] | [ ] | | | v IR [OP|ADDR] <-> [ MDR ] <--> [ ACCUM ] | | | ^ v v v | /---------\ \-----------------/ | / DECODER \ \ ALU / | \-----------/ > \-------------/ | | / > | | v /--/ / v | [Control] / \------------/ [Unit ] -----/ ------------------------------------------ What is a register? What does the PC do? What does an address mean? What does an address in the PC mean? What does the MAR do? What is stored in the MEMORY? Can the program be altered once it is in MEMORY? What does the MDR do? What does the ALU do? What does the decoder do? What is the ACCUM? B. Tiny Machine ISA ------------------------------------------ WARNING! This is not a description of HW1's ISA! Different instructions! It's The "Tiny Machine", NOT for HW1 ------------------------------------------ 1. Instruction Cycle ------------------------------------------ INSTRUCTION CYCLE 1. Fetch: IR <- MEMORY[PC] 2. Execute: ; Advance the PC ; decode and ; execute instruction in IR ------------------------------------------ 2. Execution of Instructions for the Tiny Machine How will we know if we have enough instructions? a. Load ------------------------------------------ EXECUTING LOD ; put IR's ADDR field into MAR ; fetch location into MDR ; move MDR's contents into ACCUM ------------------------------------------ b. Store ------------------------------------------ EXECUTING STO ; put IR's ADDR field into MAR ; move ACCUM into MDR ; put MDR into MEMORY at address in MAR ------------------------------------------ c. Subtraction ------------------------------------------ EXECUTING SUB ; put IR's ADDR field into MAR ; fetch location into MDR ; Compute ACCUM - MDR ------------------------------------------ d. Halt ------------------------------------------ EXECUTING HLT ; Stop execution, program ends normally ------------------------------------------ Does HLT need any address (operands)? e. Other instructions? Are we missing anything to run programs? i. Jump ------------------------------------------ EXECUTING JMP ; put IR's ADDR field into PC ------------------------------------------ ii. Conditional Jump and if-then-else ------------------------------------------ EXECUTING SKZ ; If ACCUM is 0 then skip next instr. ------------------------------------------ Does SKZ need any operands? What happens to the PC if the condition is false? How would SKZ be used to program an if-then-else? What if there is no else part? What if the condition is supposed to be zero? iii. Loops Will this be enough to do while loops? ------------------------------------------ TRANSLATING WHILE LOOPS while (COND == 0) { S } S2 is translated into: ------------------------------------------ Do we need to evaluate the condition (COND) each time? What about for loops? What about a break statement? What about continue statements? iv. Input/Output What kind of data should be input? ------------------------------------------ EXECUTING CIN ; read a single char from input ------------------------------------------ How can a program test for EOF or error? Could we use the address field for something? ------------------------------------------ EXECUTING COU ; write ACCUM to output as a character ------------------------------------------ Could we use the address field for something? v. Logical operations ------------------------------------------ EXECUTING OR ; put IR's ADDR field into MAR ; fetch location into MDR ; Compute ACCUM | MDR ------------------------------------------ f. Condition codes ------------------------------------------ REFLECTING CONDITIONS IN HARDWARE Use a register to indicate value in ACCUM Z is 1 when ACCUM is 0 G is 1 when ACCUM is positive L is 1 when ACCUM is negative x86 architecture has a program status word containing: Interrupt flags Supervisory mode flag condition codes ------------------------------------------ If we have these condition codes, how to efficiently test them? 3. Summary of Tiny Machine ISA ------------------------------------------ SUMMARY OF TINY MACHINE ISA OP CODE MNEMONIC ADDR? 1 LOD Y 2 STO Y 3 ADD Y 4 SUB Y 5 CIN ? 6 COU ? 7 HLT 8 JMP Y 9 SKZ 10 SKG 11 SKL 12 OR Y 13 AND Y 14 NOT FOR YOU TO DO Write a program in machine code to: - input two chars - print Y if they are the same - print N otherwise ------------------------------------------ What's hard about this? What do we need to assume (some values in locations for chars)? C. Assembly language So, why do we need assembly language? ------------------------------------------ ASSEMBLY LANGUAGE FEATURES - Mnemonics for opcodes - Names for locations - Initialization of data - Comments ------------------------------------------ 1. Our example in assembly language ------------------------------------------ EXAMPLE IN ASSEMBLY LANGUAGE .begin ; text (code) section ; read a char into c1 start: CIN STO c1 CIN ; read char into ACCUM SUB c1 SKZ JMP n ; jump to n if different LOD yc ; output "Y\n" COU LOD nl COU HLT n: LOD nc ; output "N\n" COU LOD nl COU HLT .end start ; data section .data c1 1 0 .data yc 1 89 .data nc 1 78 .data nl 1 10 ------------------------------------------ What does an assembler need to do? What kind of data structures would help with those tasks? What kind of guarantees should an assembler make? ------------------------------------------ ASSEMBLY LANGUAGE DIRECTIVES Help structure the program: ------------------------------------------ D. tracing (as in a debugger) Should we trace how that executes? ------------------------------------------ DEBUGGER TRACE Addr OP ADDR 0 LIT 89 1 STO 89 2 LIT 78 3 STO 78 4 LIT 10 5 STO 100 6 CIN 0 7 STO 103 8 CIN 0 9 SUB 103 10 SKZ 0 11 JMP 17 12 LOD 89 13 COU 0 14 LOD 100 15 COU 0 16 HLT 0 17 LOD 78 18 COU 0 19 LOD 100 20 COU 0 21 HLT 0 Tracing ... PC: 0 ACCUM: 0 memory: 0: 0x59 1: 0x2000059 2: 0x4e 3: 0x200004e 4: 0xa 5: 0x2000064 6: 0x5000000 7: 0x2000067 8: 0x5000000 9: 0x4000067 10: 0x9000000 11: 0x8000011 12: 0x1000059 13: 0x6000000 14: 0x1000064 15: 0x6000000 16: 0x7000000 17: 0x100004e 18: 0x6000000 19: 0x1000064 20: 0x6000000 21: 0x7000000 22: 0x0 ... 100: 0 ... ==> addr: 0 LIT 89 PC: 1 ACCUM: 89 memory: 0: 0x59 1: 0x2000059 2: 0x4e 3: 0x200004e 4: 0xa 5: 0x2000064 6: 0x5000000 7: 0x2000067 8: 0x5000000 9: 0x4000067 10: 0x9000000 11: 0x8000011 12: 0x1000059 13: 0x6000000 14: 0x1000064 15: 0x6000000 16: 0x7000000 17: 0x100004e 18: 0x6000000 19: 0x1000064 20: 0x6000000 21: 0x7000000 22: 0x0 ... 100: 0 ... ==> addr: 1 STO 89 PC: 2 ACCUM: 89 memory: 0: 0x59 1: 0x2000059 2: 0x4e 3: 0x200004e 4: 0xa 5: 0x2000064 6: 0x5000000 7: 0x2000067 8: 0x5000000 9: 0x4000067 10: 0x9000000 11: 0x8000011 12: 0x1000059 13: 0x6000000 14: 0x1000064 15: 0x6000000 16: 0x7000000 17: 0x100004e 18: 0x6000000 19: 0x1000064 20: 0x6000000 21: 0x7000000 22: 0x0 ... 89: 0x59 90: 0x0 ... 100: 0 ... ==> addr: 2 LIT 78 PC: 3 ACCUM: 78 memory: 0: 0x59 1: 0x2000059 2: 0x4e 3: 0x200004e 4: 0xa 5: 0x2000064 6: 0x5000000 7: 0x2000067 8: 0x5000000 9: 0x4000067 10: 0x9000000 11: 0x8000011 12: 0x1000059 13: 0x6000000 14: 0x1000064 15: 0x6000000 16: 0x7000000 17: 0x100004e 18: 0x6000000 19: 0x1000064 20: 0x6000000 21: 0x7000000 22: 0x0 ... 89: 0x59 90: 0x0 ... 100: 0 ... ==> addr: 3 STO 78 PC: 4 ACCUM: 78 memory: 0: 0x59 1: 0x2000059 2: 0x4e 3: 0x200004e 4: 0xa 5: 0x2000064 6: 0x5000000 7: 0x2000067 8: 0x5000000 9: 0x4000067 10: 0x9000000 11: 0x8000011 12: 0x1000059 13: 0x6000000 14: 0x1000064 15: 0x6000000 16: 0x7000000 17: 0x100004e 18: 0x6000000 19: 0x1000064 20: 0x6000000 21: 0x7000000 22: 0x0 ... 78: 0x4e 79: 0x0 ... 89: 0x59 90: 0x0 ... 100: 0 ... ==> addr: 4 LIT 10 PC: 5 ACCUM: 10 memory: 0: 0x59 1: 0x2000059 2: 0x4e 3: 0x200004e 4: 0xa 5: 0x2000064 6: 0x5000000 7: 0x2000067 8: 0x5000000 9: 0x4000067 10: 0x9000000 11: 0x8000011 12: 0x1000059 13: 0x6000000 14: 0x1000064 15: 0x6000000 16: 0x7000000 17: 0x100004e 18: 0x6000000 19: 0x1000064 20: 0x6000000 21: 0x7000000 22: 0x0 ... 78: 0x4e 79: 0x0 ... 89: 0x59 90: 0x0 ... 100: 0 ... ==> addr: 5 STO 100 PC: 6 ACCUM: 10 memory: 0: 0x59 1: 0x2000059 2: 0x4e 3: 0x200004e 4: 0xa 5: 0x2000064 6: 0x5000000 7: 0x2000067 8: 0x5000000 9: 0x4000067 10: 0x9000000 11: 0x8000011 12: 0x1000059 13: 0x6000000 14: 0x1000064 15: 0x6000000 16: 0x7000000 17: 0x100004e 18: 0x6000000 19: 0x1000064 20: 0x6000000 21: 0x7000000 22: 0x0 ... 78: 0x4e 79: 0x0 ... 89: 0x59 90: 0x0 ... 100: 10 101: 0 ... ==> addr: 6 CIN 0 PC: 7 ACCUM: 97 memory: 0: 0x59 1: 0x2000059 2: 0x4e 3: 0x200004e 4: 0xa 5: 0x2000064 6: 0x5000000 7: 0x2000067 8: 0x5000000 9: 0x4000067 10: 0x9000000 11: 0x8000011 12: 0x1000059 13: 0x6000000 14: 0x1000064 15: 0x6000000 16: 0x7000000 17: 0x100004e 18: 0x6000000 19: 0x1000064 20: 0x6000000 21: 0x7000000 22: 0x0 ... 78: 0x4e 79: 0x0 ... 89: 0x59 90: 0x0 ... 100: 10 101: 0 ... ==> addr: 7 STO 103 PC: 8 ACCUM: 97 memory: 0: 0x59 1: 0x2000059 2: 0x4e 3: 0x200004e 4: 0xa 5: 0x2000064 6: 0x5000000 7: 0x2000067 8: 0x5000000 9: 0x4000067 10: 0x9000000 11: 0x8000011 12: 0x1000059 13: 0x6000000 14: 0x1000064 15: 0x6000000 16: 0x7000000 17: 0x100004e 18: 0x6000000 19: 0x1000064 20: 0x6000000 21: 0x7000000 22: 0x0 ... 78: 0x4e 79: 0x0 ... 89: 0x59 90: 0x0 ... 100: 10 101: 0 ... 103: 97 104: 0 ... ==> addr: 8 CIN 0 PC: 9 ACCUM: 97 memory: 0: 0x59 1: 0x2000059 2: 0x4e 3: 0x200004e 4: 0xa 5: 0x2000064 6: 0x5000000 7: 0x2000067 8: 0x5000000 9: 0x4000067 10: 0x9000000 11: 0x8000011 12: 0x1000059 13: 0x6000000 14: 0x1000064 15: 0x6000000 16: 0x7000000 17: 0x100004e 18: 0x6000000 19: 0x1000064 20: 0x6000000 21: 0x7000000 22: 0x0 ... 78: 0x4e 79: 0x0 ... 89: 0x59 90: 0x0 ... 100: 10 101: 0 ... 103: 97 104: 0 ... ==> addr: 9 SUB 103 PC: 10 ACCUM: 0 memory: 0: 0x59 1: 0x2000059 2: 0x4e 3: 0x200004e 4: 0xa 5: 0x2000064 6: 0x5000000 7: 0x2000067 8: 0x5000000 9: 0x4000067 10: 0x9000000 11: 0x8000011 12: 0x1000059 13: 0x6000000 14: 0x1000064 15: 0x6000000 16: 0x7000000 17: 0x100004e 18: 0x6000000 19: 0x1000064 20: 0x6000000 21: 0x7000000 22: 0x0 ... 78: 0x4e 79: 0x0 ... 89: 0x59 90: 0x0 ... 100: 10 101: 0 ... 103: 97 104: 0 ... ==> addr: 10 SKZ 0 PC: 12 ACCUM: 0 memory: 0: 0x59 1: 0x2000059 2: 0x4e 3: 0x200004e 4: 0xa 5: 0x2000064 6: 0x5000000 7: 0x2000067 8: 0x5000000 9: 0x4000067 10: 0x9000000 11: 0x8000011 12: 0x1000059 13: 0x6000000 14: 0x1000064 15: 0x6000000 16: 0x7000000 17: 0x100004e 18: 0x6000000 19: 0x1000064 20: 0x6000000 21: 0x7000000 22: 0x0 ... 78: 0x4e 79: 0x0 ... 89: 0x59 90: 0x0 ... 100: 10 101: 0 ... 103: 97 104: 0 ... ==> addr: 12 LOD 89 PC: 13 ACCUM: 89 memory: 0: 0x59 1: 0x2000059 2: 0x4e 3: 0x200004e 4: 0xa 5: 0x2000064 6: 0x5000000 7: 0x2000067 8: 0x5000000 9: 0x4000067 10: 0x9000000 11: 0x8000011 12: 0x1000059 13: 0x6000000 14: 0x1000064 15: 0x6000000 16: 0x7000000 17: 0x100004e 18: 0x6000000 19: 0x1000064 20: 0x6000000 21: 0x7000000 22: 0x0 ... 78: 0x4e 79: 0x0 ... 89: 0x59 90: 0x0 ... 100: 10 101: 0 ... 103: 97 104: 0 ... ==> addr: 13 COU 0 YPC: 14 ACCUM: 89 memory: 0: 0x59 1: 0x2000059 2: 0x4e 3: 0x200004e 4: 0xa 5: 0x2000064 6: 0x5000000 7: 0x2000067 8: 0x5000000 9: 0x4000067 10: 0x9000000 11: 0x8000011 12: 0x1000059 13: 0x6000000 14: 0x1000064 15: 0x6000000 16: 0x7000000 17: 0x100004e 18: 0x6000000 19: 0x1000064 20: 0x6000000 21: 0x7000000 22: 0x0 ... 78: 0x4e 79: 0x0 ... 89: 0x59 90: 0x0 ... 100: 10 101: 0 ... 103: 97 104: 0 ... ==> addr: 14 LOD 100 PC: 15 ACCUM: 10 memory: 0: 0x59 1: 0x2000059 2: 0x4e 3: 0x200004e 4: 0xa 5: 0x2000064 6: 0x5000000 7: 0x2000067 8: 0x5000000 9: 0x4000067 10: 0x9000000 11: 0x8000011 12: 0x1000059 13: 0x6000000 14: 0x1000064 15: 0x6000000 16: 0x7000000 17: 0x100004e 18: 0x6000000 19: 0x1000064 20: 0x6000000 21: 0x7000000 22: 0x0 ... 78: 0x4e 79: 0x0 ... 89: 0x59 90: 0x0 ... 100: 10 101: 0 ... 103: 97 104: 0 ... ==> addr: 15 COU 0 PC: 16 ACCUM: 10 memory: 0: 0x59 1: 0x2000059 2: 0x4e 3: 0x200004e 4: 0xa 5: 0x2000064 6: 0x5000000 7: 0x2000067 8: 0x5000000 9: 0x4000067 10: 0x9000000 11: 0x8000011 12: 0x1000059 13: 0x6000000 14: 0x1000064 15: 0x6000000 16: 0x7000000 17: 0x100004e 18: 0x6000000 19: 0x1000064 20: 0x6000000 21: 0x7000000 22: 0x0 ... 78: 0x4e 79: 0x0 ... 89: 0x59 90: 0x0 ... 100: 10 101: 0 ... 103: 97 104: 0 ... ==> addr: 16 HLT 0 PC: 17 ACCUM: 10 memory: 0: 0x59 1: 0x2000059 2: 0x4e 3: 0x200004e 4: 0xa 5: 0x2000064 6: 0x5000000 7: 0x2000067 8: 0x5000000 9: 0x4000067 10: 0x9000000 11: 0x8000011 12: 0x1000059 13: 0x6000000 14: 0x1000064 15: 0x6000000 16: 0x7000000 17: 0x100004e 18: 0x6000000 19: 0x1000064 20: 0x6000000 21: 0x7000000 22: 0x0 ... 78: 0x4e 79: 0x0 ... 89: 0x59 90: 0x0 ... 100: 10 101: 0 ... 103: 97 104: 0 ... ------------------------------------------ E. Register Machine with Load/Store Architecture Is the Tiny Machine Turing complete? Is the tiny machine easy to program? Would the tiny machine be efficient? 1. memory hierarchy ------------------------------------------ BACKGROUND: SPEED OF COMPUTER MEMORY Speed Cost/bit ======= ========= Fastest Expensive Registers Cache Memory (SRAM) RAM (Main Memory, DRAM) Spinning Magnetic Disk (HDD) External Drives (Tape, Optical) Slowest Cheapest ------------------------------------------ Do programs need to move data from main memory to caches? Do programs need to move data from memory to registers? Would programs execute faster if we used faster memory more? 2. Register Machine a. Basics of the Architecture ------------------------------------------ REGISTER MACHINE ARCHITECTURE - Word-oriented (4 bytes) but byte-addressed - All instructions 32 bits long must be aligned on word boundary - 32 registers ------------------------------------------ b. Instructions (ISA) ------------------------------------------ REGISTER MACHINE ISA Arithmetic and logic instructions - work with 3 registers - format: [op:6|rs:5|rt:5|rd:5|shift:5|func:6] - example: ADD s t d means GPR[d] <- GPR[s] + GPR[d] Intermediate operand instructions - work with 2 registers - format: [ op:6 | rs:5 | rt:5 | immed: 16 ] - example: ADDI s t i means GPR[t] <- GPR[s] + sgnExt(i) where sgnExt(i) i sign extended Jump instructions - work with a 26 bit address - format: [ op:6 | addr: 26 ] - example: JMP a means PC <- formAddress(a) System call instructions - work with a code and function - format: [ op:6 | code:20 | func:6 ] - example SYS 10 means stop the program's execution where sgnExt(0xFFFF) = 0xFFFFFFFF sgnExt(0x0000) = 0x00000000 sgnExt(0x0001) = 0x00000001 formAddress concatenates high bits of PC with the 26 bit address + 2 bits of 0 (to align on a word) so if PC = 0xFACADE, then formAddress(0x00DECADE) = 0x007B2B78 ------------------------------------------ 3. Other kinds of ISAs What other options are there for designing an ISA? What features of normal programming are hard with these ISAs?