Keep it up! Let's improve your performance and the performance of our LC-3 computer (WARNING: Do NOT try to feed your LC-3 a baked good).

(MUST DO) Operating Systems 1: Privilege

Objectives

• Describe the purpose and benefits of an operating system

• Describe the concept of “privilege” and how the LC-3 implements it, including the memory map, processor status register (PSR), and system calls

• Describe how user programs are supposed to interact with the LC-3 hardware and what violation occurs if they attempt to circumvent that process

Video Notes

• @09:18: I want to reiterate what the two values of PSR[15], i.e. the Privilege Mode, mean.

  • PSR[15] == 1 means the system is in user space or unprivileged mode

  • PSR[15] == 0 means the system is in system space or privileged mode

Additional Resources

• “Introduction to Computing Systems”, Section 9.1

Exercises

• End-of-chapter question 9.15, 16.a

• What are the names and address ranges of the privileged areas of memory? Explain the purpose of making these areas of memory privileged.

• Explain the significance of starting each of our LC-3 programs with .ORIG x3000.

• Describe the hardware features in the LC-3 that support the concept of “privilege”. Be sure to include a discussion of the following terms:

  • PSR and privilege mode

  • System space/Supervisor stack/SSP, HW page, and privileged memory

  • TRAP/system call and access control violation

• Label and describe the main parts of the LC-3 memory map. Which ones are privileged and why?

• Describe the purpose and benefits of an operating system in terms that a Plebe could understand.

• What’s [that]? What’s its purpose, i.e. how does it support the concept of “privilege”?

  • System space

  • Supervisor stack

  • SSP

  • HW page

  • Privilege mode (PSR[15])

  • TRAP instruction

  • Access control violation

• The LC-3 has two stack pointers. What are they and why does the LC-3 have two of them?

(MUST DO) Memory-Mapped Input v1

Objectives

• Describe memory-mapped input (i.e. describe the circuit that allows the LC-3 to read from an input device by reading from a memory location)

• Write LC-3 assembly programs to read from memory-mapped input devices, accounting for synchronization

Additional Resources

• “Introduction to Computing Systems”, Sections 9.2.1 and 9.2.2

Exercises

• End-of-chapter questions 9.1, 5, 6, 9, 12 (Should read “Section 9.2.2”), 14, 44, 45

• Design the logic needed so that reading KBDR clears KBSR[15] and so that KBDR is only changed if KBSR[15]==0.

• The basic set of ASCII characters only includes 128 values, with 127 being the highest numbered character. If the value in the KBDR is 128 to 255, this is not likely a valid ASCII character. Update the basic input service routine on page 321 of the textbook so that only valid ASCII characters are returned to the program.

• Assume KBSR[13] is a “Receive enable” bit: KBDR rejects any incoming values if the “receive enable” bit is cleared. Design the logic to implement this feature.

  • Update the basic input service routine on page 321 of the textbook to only check for input values if the “receive enable” bit is set.

• Extend Figure 9.4 to include a row of 8 switches, like on the digital trainers in the lab. Assign it a valid value in the HW page. Do you think this input device needs a status register? Why or why not? If you think so, what should each bit of the status register mean?

  • What other input devices might be useful to have on the LC-3? Can you think of how to design the circuit so that they can be controlled and read using memory-mapped input?

• Why does the Address Control Logic need to know if memory is being read from or written to (the “R.W” signal in Figure 9.4)? What problems would or could occur if that signal weren’t given to the Address Control Logic?

• Describe memory-mapped input in terms a bright high school student could understand.

• What’s the maximum size of the actual data memory in the LC-3, given that a portion of the memory map is set aside for HW devices?

• What’s the maximum number of HW devices the LC-3 can support, given the amount of the memory map set aside for them? You can assume that each HW device requires two words of memory, just like how the keyboard required a KBDR and KBSR. Don’t forget that two spaces in memory are already allocated for the PSR and MSR!

• What’s [this]? How does it support memory-mapped input?

  • Address control logic

  • KBDR

  • KBSR

  • INMUX

• How can we tell if there has been a new value written to KBDR since the last time it was read?

(MUST DO) Memory-Mapped Output v1

Objectives

• Describe memory-mapped output (i.e. describe the circuit that allows the LC-3 to write to an output device by writing to a memory location)

• Compare and contrast memory-mapped with programmed IO

• Write LC-3 assembly programs to write to memory-mapped output devices, accounting for synchronization

Additional Resources

• “Introduction to Computing Systems”, Sections 9.2.1 and 9.2.3-9.2.5

Exercises

• End-of-chapter questions 9.1, 8, 10, 13, 34

• Design the logic needed so that the display device reading DDR clears DSR[15] and so that writes to DDR are only permitted if DSR[15]==1.

• Assume DSR[13] is a “transmit enable” bit: values in the DDR are only sent to the display if the “transmit enable” bit is set. Design the logic to implement this feature.

  • Update the basic output service routine on page 323 of the textbook so that DDR is only written to if the “transmit enable” bit is set.

• Extend Figure 9.4 to include a row of 8 LEDs, like on the digital trainers in the lab. Assign it a valid value in the HW page. Do you think this output device needs a status register? Why or why not? If you think so, what should each bit of the status register mean?

  • What other output devices might be useful to have on the LC-3? Can you think of how to design the circuit so that they can be controlled and read using memory-mapped output?

• Re-evaluate your answer to the following question, knowing what you now know about memory-mapped output: Why does the Address Control Logic need to know if memory is being read from or written to (the “R.W” signal in Figure 9.6)? What problems would or could occur if that signal weren’t given to the Address Control Logic?

• Describe memory-mapped output in terms your non-EECS friends could understand.

• What’s [this]? How does it support memory-mapped input?

  • Address control logic

  • DDR

  • DSR

  • INMUX

• How can we tell if the last value written to the display has been transmitted to the display?

(MUST DO) Operating System Routines

Objectives

• Describe the sequence of events executed by the TRAP and RTI instructions

• Describe the Trap Vector Table and OS Service Routines

• Trace OS Service Routines that:

  • receive ASCII characters from the keyboard,

  • transmit ASCII characters to a display,

  • halt the processor, and

  • transmit nul-terminated strings to a display.

Video Notes

• @08:30: More information about the TRAP routines can be found in Table A.3. Take note that the mnemonic for each TRAP routine is also a valid assembly instruction in the LC-3 Simulator; for example, you can write "OUT" in your LC-3 assembly in place of "TRAP x21" and the assembler will call the correct service routine.

Additional Resources

• “Introduction to Computing Systems”, Section 9.3

Exercises

• End-of-chapter questions 9.16(b,c), 18, 19, 20, 23, 24, 26, 28, 30, 31, 46-49

  • NOTE: For 9.16(b), "RET" should instead be "RTI".

• Complete the table below.

• Write a program that uses the OS service routines discussed in this section.

  • When you get to the “TRAP _____” instruction, be sure to click the “Step in” button (right-angle arrow pointing to the right) instead of the “Step over” button so that you can watch the OS service routine execute.

  • Inspect the values of R6 and PSR. Do they make sense?

  • Inspect the memory values in the Trap Vector Table. Do they make sense?

• Write a new OS service routine to do something useful of your own choosing and then use it in a program.

• Add information about the TRAP routines GETC and PUTSP to the table in the "Must do" exercise. Refer to Table A.3 and inspect the LC-3 Simulator memory where you might expect to find these TRAP routines for information.

• What’s the total number of OS service routines the LC-3 can support?

• What’s the maximum allowable size for all OS service routines in the LC-3 memory map? What problem will inevitably result if all of that space is taken up with service routines?

• What must happen immediately before the LC-3 [jumps to the OS service routine, returns from the OS service routine] (assume that PSR[15]==[0,1])? Explain the importance of those steps.

• A user program calls a TRAP routine and immediately before the first instruction of the routine executes, the registers look like that below. Find the two problems with the registers below. What is one other thing about the registers below that must be true, given the current scenario?

• When you first select the "Simulator" tab in the LC-3 Simulator, you may have noticed that the program appears to start at x0200, which has the instructions below. This appears to be "startup code" (i.e. code that sets up the processor at first power-on before user code is allowed to run) and the fact that it's located at the first memory address in System Space leads me to believe that the writers of the LC-3 Simulator assumed that this would be the first series of instructions to be executed when the LC-3 was first "turned on". Take a look at the code to determine what it's doing and why it might important to do it at start-up.

(MUST DO) Interrupts 1: Causing the Interrupt to Occur

Objectives

• Compare and contrast polling with interrupt-driven IO

• Describe the additional circuitry required for the LC-3 to generate and respond to interrupts

• Describe the changes to the PSR and KBSR/DSR registers that support interrupts

• Identify when in the instruction cycle the LC-3 responds to interrupts

Video Notes

• PSR[14]/GIE is often not depicted when the PSR is shown in the textbook and it's not implemented in the LC-3 Simulator (to my knowledge). Nonetheless, every modern computer that I'm aware of with an interrupt system has the equivalent of a "global interrupt enable", so we'll continue to use it in our discussions of the LC-3.

Additional Resources

• “Introduction to Computing Systems”, Sections 9.4.1-9.4.4

Exercises

• Imagine that the LC-3 is about to process an interrupt and that KBSR, DSR, and PSR have the values listed below. Assume that the priority of an interrupt from the keyboard has the value 3 and that from the display has the value 1.

  • Complete the table below.

  • Which interrupt is about to be processed?

• What’s the purpose of the encoder in the diagram below?

• Pick random values for PSR[14] (global interrupt enable), PSR[10:8] (priority level of the currently running program), KBSR[15] (new data bit), KBSR[14] (keyboard interrupt enable), DSR[14] (ready bit), DSR[14] (display interrupt enable), and the priority levels for the keyboard and display interrupt service routines. Then answer some or all of the questions below.

  • Which device (if either) has the right to request an interrupt?

  • Which device (if either) is currently requesting an interrupt?

  • What’s the highest priority device in need of service (if any)?

  • What’s the priority level of the program that’s currently being executed? Is this higher or lower than the priority of the interrupt being requested from the IO devices (if any)?

  • Are interrupts enable globally?

  • Does the processor execute an interrupt service routine or not?

(MUST DO) Interrupts 2: Handling the Interrupt Request

Objectives

• Describe the sequence of events initiated by an interrupt service request

• Describe the Interrupt Vector Table

• Compare and contrast the handling of OS service routines and interrupt service routines

Video Notes

• There isn’t a need to set PSR[15] explicitly, since it happens automatically when the old PSR is restored.

Additional Resources

• “Introduction to Computing Systems”, Sections 9.4.5-9.4.7

Exercises

• End-of-chapter questions 9.32, 33 (a-c), 35, 42, 43, 51, 53, 54 (first 2 questions)

• The interrupt vector table seems to be able to support 256 different interrupt routines but the encoder only supports 8 priority levels. To make things easy, we assumed that there can be only 7 interrupt sources, one each for the 7 priority levels above 0 (where user code is assumed to be running). How might the interrupt circuitry be changed to accommodate as many as 256 different interrupt sources?

(SHOULD DO) Race Conditions

Objectives

• Define a “race condition”

• Identify code that exhibits the possibility for a race condition

• Write code that accounts for race conditions

Video Notes

• In the notes for this lesson I fail to show the ISR saving any of the callee-saved registers when it runs. This is wrong and would result in some terrible errors, since the ISR would completely trash whatever values were in R0 and R1 being used by another program! The corrected version of the ISR is below.
  ;Keyboard ISR (M[x0180] = x0500)
  .ORIG x0500
  ADD R6, R6, #-2
  STR R0, R6, #1
  STR R1, R6, #0
  LDI R0, KBDR
  ECHO LDI R1, DSR
  BRzp ECHO
  STI R0, DDR
  LDR R1, R6, #0
  LDR R0, R6, #1
  ADD R6, R6, #2
  RTI
  .END

Additional Resources

• “Introduction to Computing Systems”, Section 9.5

Exercises

• End-of-chapter questions 9.33 (d), 40, 41, 54 (third question)

(SHOULD DO) Sharing Data Wisely

Objectives

• Identify when the sharing of data could result in a data race

• Write interrupt service routines that can share data with user programs, accounting for data races

Video Notes

• In the notes for this lesson I fail to show either ISR saving any of the callee-saved registers when they run. This is wrong and would result in some terrible errors, since both ISRs would completely trash whatever value was in R0 used by another program! The corrected versions of both ISRs are below.

  • First ISR
    ;Keyboard ISR (M[x0180] = x0500)
    .ORIG x0500
    ADD R6, R6, #-1
    STR R0, R6, #0
    LDI R0, PTR_COUNT
    ADD R0, R0, #1
    STI R0, PTR_COUNT
    LDR R0, R6, #0
    ADD R6, R6, #1
    RTI
    PTR_COUNT .FILL COUNT
    .END

  • Second ISR
    ;Keyboard ISR (M[x0180] = x0500)
    .ORIG x0500
    ADD R6, R6, #-1
    STR R0, R6, #0
    ;If KBDR == 'xA' ("enter" key):
    LDI R0, PTR_ENTER_FLAG
    ADD R0, R0, #1
    STI R0, PTR_ENTER_FLAG
    LDR R0, R6, #0
    ADD R6, R6, #1
    RTI
    PTR_ENTER_FLAG .FILL ENTER_FLAG
    .END

Additional Resources

• “Introduction to Computing Systems”, Section 9.5

Exercises

• End-of-chapter questions 9.33 (d), 40, 41, 54 (third question)

• Implement the second example (the one that has a critical section which needs protecting) from the lecture video in the LC-3 Simulator (or code a similar one that you come up with!).

• Write a program that:

  • Tests for the keys 'w', 'a', 's', and 'd' to be pressed in the keyboard ISR, putting a 1, 2, 3, or 4 into a shared variable based on the key pressed. The user program reads the shared variable and repeatedly prints "UP", "LEFT", "DOWN", or "RIGHT" to the screen based on the value in the shared variable.

  • Adds characters to a shared string in the keyboard ISR until the "enter" key is detected, at which point it changes another shared variable to 1. The user program, while printing a message in an infinite loop, displays the user's message when the shared variable is 1 followed by "Oh, pardon me, I wasn't done speaking yet", sets the shared variable to 0 and then continues.

(ASPIRE TO DO) Returning from HALT

Objectives

• Describe the circuitry that can restart the LC-3 after a HALT instruction

Additional Resources

• Arduino Datasheet

Exercises

• End-of-chapter questions 9.17, 27

• Consider the “Character Count” program from Figure 7.2.

  • This program has a problem if the HALT instruction returns; what is it?

  • Modify that program to prevent the error you described above.

(MUST DO) Operating Systems 2: Priority

Objectives

• Describe the purpose and benefits of an operating system

• Describe the concept of “priority” and how the LC-3 implements it, including priority level, interrupt requests, and the interrupt vector table

Video Notes

• It was very intentional that "Prog2" is shown as having a priority level of 4, since the only interrupt we will implement in this class is the keyboard ISR, which has a priority of 4. "Prog2", then, is basically synonymous with the keyboard ISR.

• Although there are advantages to having an interrupt system that implements the concept of priority, it's also possible to assign different priority levels to different user programs entirely in software. Exactly how to do that, however, is the subject of another class!

Additional Resources

• “Introduction to Computing Systems”, Sections 9.1.1 and 9.4.6

Exercises

• End-of-chapter questions 9.37, 38

• Describe the hardware features in the LC-3 that support the concept of “priority”. Be sure to include a discussion of the following terms:

  • PSR, global interrupt enable, and priority level

  • The circuitry that supports interrupts, including the interrupt vector table

• Although an ISR may have priority in a given situation, there is still only one specific time in the instruction cycle when the LC-3 is designed to handle interrupt requests. What's the greatest number of clock cycles an interrupt request would need to wait before being serviced? Do the math first assuming that memory accesses take 1 clock cycle, then again assuming they take 5 clock cycles, and one more time assuming they take 100 clock cycles. What's the amount of time in seconds that an interrupt request would have to wait if the clock frequency of the LC-3 were 100 kHz? 1MHz? 1 GHz?

(MUST DO) Memory-Mapped Input-Output v2

Objectives

• Describe how the LC-3 interacts with IO devices, including memory-mapped registers, synchronization, and interrupts

• Write short interrupt service routines for the keyboard and display IO devices

Video Notes

• In the notes for this lesson I fail to show the ISR saving any of the callee-saved registers when it runs. This is wrong and would result in some terrible errors, since the ISR would completely trash whatever values were in R0 and R1 being used by another program! The corrected version of the ISR is below.
  ;Keyboard ISR (M[x0180] = x0500)
  .ORIG x0500
  ADD R6, R6, #-2
  STR R0, R6, #1
  STR R1, R6, #0
  LDI R0, KBDR
  ECHO LDI R1, DSR
  BRzp ECHO
  STI R0, DDR
  LDR R1, R6, #0
  LDR R0, R6, #1
  ADD R6, R6, #2
  RTI
  .END

Additional Resources

• “Introduction to Computing Systems”, Sections 9.2.2, 9.2.3, 9.4

Exercises

• End-of-chapter questions 9.1, 7, 11, 36-40, 50

• The lecture notes showed the start of a program that uses the keyboard ISR to echo typed characters to the display, but otherwise does nothing in the main program. Finish writing this program so that it will execute in the LC-3 Simulator and then test it to make sure it works. (Hint: You’ll need one new TRAP routine to make this work!)

• Modern microcontrollers have dozens of peripherals with hundreds of total registers that operate them. To support this architecture, INMUX would have to have an input for every single register, which seems prohibitively difficult. What might be a better way to allow these many hundreds of devices to all send data to the MDR?

(ASPIRE TO DO) The Calculator Program

Objectives

• Describe the flowchart for the calculator program

• Convert integers in the range [-999, 999] to ASCII values and back

• Describe postfix notation

• After reading Chapter 10: trace a large LC-3 program that demonstrates sequential decomposition, the use of HW IO, and stack-based arithmetic

Additional Resources

• “Introduction to Computing Systems”, Chapter 10

Exercises

• End-of-chapter exercises 10.1-9

• Enter the full Calculator Program into the LC-3 Simulator and enter a few postfix expressions, checking the results to ensure it works.