CoSc 330 / Computer Systems

Computer Systems

Spring Semester, 2011

CoSc 330: Syllabus
Instructor: Stan Warford
Office: RAC 112
Office hours: Monday (11:00-11:50), Tuesday (9:00-9:50), Thursday (1:00-1:50), Friday (11:00-11:50), and by appointment.
Email: Message to Warford

A1, A2, A3, A4, A5, A6, A7, Test 1
A8, A9, A10, A11, A12, A13, A14, Test 2
A15, A16, A17, A18, A19, A20, A21, A22, A23, A24, Final

Announcements

Downloads

Download Pep/8.
Download errata page for Computer Systems, Fourth Edition, first printing.
Download lecture slides, Chapter 1 for Computer Systems, Fourth Edition.
Download lecture slides, Chapter 2 for Computer Systems, Fourth Edition.
Download lecture slides, Chapter 3 for Computer Systems, Fourth Edition.
Download lecture slides, Chapter 4 for Computer Systems, Fourth Edition.
Download lecture slides, Chapter 5 for Computer Systems, Fourth Edition.
Download lecture slides, Chapter 6 for Computer Systems, Fourth Edition.
Download lecture slides, Chapter 7 for Computer Systems, Fourth Edition.
Download lecture slides, Chapter 7 Java version for Computer Systems, Fourth Edition.
Download reference pages for Pep/8 and MIPS.
Download solutions for A24.
Download Java article "The Java Tree Withers," IEEE Computer, January, 2012.

Setup for C++

The first assignment at the beginning of the course is in C++. For this assignment, the procedures are the same as for programming in C++ in Data Structures last semester.

Setup for Java with NetBeans

Java is an interpreted language that requires the Java Virtual Machine to run. NetBeans is an open source Integrated Development Environment (IDE) that includes a text editor and debugging facility. Your local computer will need both the Java Virtual Machine and NetBeans to develop your programs.

For Mac users, the Java Virtual Machine is included with OS X. If you have Windows or Linux, go to java.sun.com, follow the link to Java SE, and download and install the Java SE Development Kit (JDK6). You will not need JDK 6 with Java EE, because we will not run our Java programs on the Web. Follow the Download link and read the installation instructions on how to install the JDK.

To install NetBeans on your local computer, go to www.netbeans.com and navigate to the Downloads section. Download and install NetBeans IDE 6.9.1 on your local machine.

Getting started with Java

Unlike C++, the standard file organization for Java is to have each class contained in its own source file with extension .java. The name of the class is the same as the name of the file. For example, class MyClass would be contained in the file MyClass.java. To compile a Java program on the command line, you could write the source file in the text editor of your choice, save it, and then compile it with the java compiler like this:

javac MyClass.java

If your program contains no errors, the object code would be stored in the file named MyClass.class. Java is an interpreted language, which means that .class files are not native machine code, but are in the form of Java byte code instead. To execute Java byte code, you cannot execute the .class file directly. Instead, you must execute the Java Virtual Machine, which takes the .class file as input like this:

java MyClass

Note that you do not type the .class extension, which is assumed by the Java Virtual Machine.

To compile and execute a Java program requires that you modify your path variables. The way to do that depends on whether you use Windows or OS X. Instead of pursuing this approach further, we will use NetBeans, which takes care of these issues automatically.

Getting started with NetBeans

The following scenerio is a description of how to create a Java "Hello, world!" program with NetBeans. Our naming convention will be to use a name beginning with an uppercase letter for the project, and the same name with Main appended for the class in the project with the main method.

Open NetBeans and select File > New Project... . In the New Project pane, select Categories: Java, and then Projects: Java Application. Click Next. The name of the project will be the name of a new folder that NetBeans creates. For this example, name the project Hello. Then click the Browse button and brouse to the location where you want your project to be stored.

IMPORTANT: We are using a file naming convention that is different from the NetBeans default. Verify that Create Main Class and Set as Main Project checkboxes are checked. But BEFORE you click Finish, change the name of the main class from hello.Main to HelloMain. Note that there is no longer a period in the name of the main class, and that the class name begins with an uppercase H. Now click Finish. NetBeans creates a directory structure that contains, among other things, the following file:

Hello/src/hello/HelloMain.java

The file HelloMain.java should be displayed in the NetBeans text editor with a stub comment for you to replace with Java code. To enter System.out.println("Hello, world!"); first type System.out. and note the code completion feature.

Save the source file. To compile and execute the application select Run > Run Main Project, or click the green run triangle on the tool bar. The Console pane appears and displays the output.

NetBeans saves the corresponding class file as follows:

Hello/build/classes/HelloMain.class

You can see the file structure by clicking the Files tab (as opposed to the Projects tab) in NetBeans. This file organization, where the source files are stored in one subdirectory and the class files in another subdirectory is convenient for large projects with many classes.

Handing in Java assignments

The standard way to distribute Java projects is with a JAR (Java Archive) file, which is what you must use to hand in your Java projects. Selecting the NetBeans command Run > Clean and Build Main Project on the main menu, or, equivalently, clicking the hammer-and-broom icon on the tool bar, makes a clean build of the project and also creates a JAR file for distribution. The default configuration for NetBeans is to only include the .class files in the JAR file. For your project to be graded, however, you must also include the .java source files.

To create a JAR file with source files for the above Hello project, first make sure the Project tab is selected. Right click the Hello project node and select Properties from the contextual menu. In the Project Properties window, select Categories: Build > Packaging. In the entry Exclude from JAR file: should be the String

**/*.java,**/*.form

The first item in the string tells NetBeans to exclude the .java file from the JAR file. Edit the string by removing the first item including the comma as follows

**/*.form

Click OK. Now, execute Clean and Build Project. NetBeans creates a new folder named dist for distribution, and puts the JAR file in it. The JAR file has the following path

Hello/dist/Hello.jar

The file Hello.jar is the one you would hand in electronically. Here are the instructions for submitting homework electronically.

Historic computers

Here are some historic pictures of early computers.

http://ftp.arl.mil/ftp/historic-computers/

Assignments

Text

Computer Systems, Fourth edition, J. Stanley Warford, Jones and Bartlett, 2010.

Text rebate

As the author of our text, if you purchase it new I will personally refund on your request 15% of the retail price you paid.

Exercises are handwritten to be handed in on paper in class. Problems are programs to be handed in electronically from your account on Sun. See the syllabus for further details.

A1

Due Thursday, January 12

Study Chapter 1.1, 1.2, 1.3, 2, 3.1, 3.2

Exercises 1.2, 1.10, 2.2(c), 2.3(c), 2.8

Problem 2.15.

Write your program in C++. Prompt the user exactly as shown on page 84. Name your program Prob0215.cpp. Note the uppercase P.

Notice

Monday, January 16, Martin Luther King Day
Class does not meet.

A2

Due Thursday, January 19

Study Chapter 3.3, 3.4, 3.6

Exercises 3.7, 3.14, 3.16, 3.18, 3.20, 3.21, 3.23

For 3.20 and 3.23: The exercises continue at the top of the next page.

Problem 3.57.

Write your program in Java with NetBeans by completing this code, which has the user interface already in place. Convert the eight characters in line to eight integers in the binNum array. Verify that each bit entered by the user is 0 or 1 and output an error message if it is not. If the user enters 11111101 the output to the console should be

Here is a link to Oracle's Java documentation. Scroll to the String class to see the methods you can use for the line variable. See the charAt method for extracting an individual character from line. I recommend you use the formatting capabilities of the System.out.printf() method. Name your NetBeans project Prob0357 and the class that has the main program as Prob0357Main. Note the uppercase P. Export the source file in a JAR file named Prob0357.jar as described above in the section Handing in Java assignments. Hand in the .jar file with the homework command on Sun.

A3

Due Monday, January 23

Study Chapter 4.1, 4.2

Exercises 3.25, 3.28, 3.30, 3.35, 3.37, 3.39, 4.4

For 3.25: Don't forget to convert the shifted values back to decimal. With ASL, show the effect on the NZVC bits. With ASR show the effect on the NZC bits. (ASR does not affect the V bit.)

Problem 3.61.

Write your program in Java with NetBeans by completing this code, which has the user interface already in place. Convert the eight characters in line to eight integers in the binNum array. Verify that each bit entered by the user is 0 or 1 and output an error message if it is not. If the user enters 11111101, the output to the console should be

11111101 (bin) = -3 (dec)

Name your NetBeans project Prob0361 and the class that has the main program as Prob0361Main. Note the uppercase P. Export the source file in a JAR file named Prob0361.jar. Hand in the .jar file with the homework command on Sun.

A4

Due Thursday, January 26

Study Chapter 4.3, 4.4

Exercise 4.1, 4.2, 4.6

Problem 4.12.

Download the Pep/8 system from the links given in the announcements section above and use it to write your machine language program. Name your program Prob0412.pepo.
Note the uppercase P. In general, pep8 assembly language source files end in .pep, machine language object files end in .pepo, and assembler listing files end in .pepl.

A5

Due Monday, January 30

Study Chapter 5.1

Exercise 4.9

Problem 4.15

Name your program Prob0415.pepo.

A6

Due Thursday, February 2

Study Chapter 5.2

Exercise 5.2, 5.4, 5.6

Problem 5.20

Name your program Prob0520.pep, not Prob0520.pepo.

A7

Due Monday, February 6

Exercise 5.11, 5.12

Problem 5.21, 5.22

Name your programs Prob0521.pep, and Prob0522.pep, not .pepo.

Test 1

Thursday, February 9

Chapters 1 through 5.2

A8

Due Monday, February 13

Study Chapter 5.3, 5.4

Exercise 5.14, 5.19

Problem 5.27, 5.29

IMPORTANT: From now on, trace tags for all variables and parameters are required for full credit.

A9

Due Thursday, February 16

Study Chapter 7.1

Exercise 7.1, 7.2, 7.4(b), 7.6(b, d, f), 7.7(b)

A10

Due Monday, February 20

Study Chapter 7.2

Exercise 7.11, 7.12, 7.13

Hint: In 7.13, you should only use four states in all parts of the problem.

A11

Due Thursday, February 23

Study Chapter 7.3

Problem 7.16

To save some typing, here is the program of Figure 7.25. Name your NetBeans project Prob0716.java and the class that has the main program as Prob0716Main. Export the source file in a JAR file named Prob0716.jar. Hand in the .jar file with the homework command on Sun.

Spring break

February 27 - March 2

A12

Due Monday, March 5

Problem 7.19

To save some typing, here is the program of Figure 7.26. If the user enters 0d, the output to the console should be

Number = 13 (dec)

To guarantee that the hexadecimal value does not occupy more than two bytes, check that the decimal value is not more than 65535. Note that 00000A is a valid hexadecimal constant even though it is longer than four characters.

Name your NetBeans project Prob0719.java and the class that has the main program as Prob0719Main. Create a separate source file for each Java class. Any of the functions listed on page 382 that you need, you will have to implement yourself. Export the source files in a JAR file named Prob0719.jar. Hand in the .jar file with the homework command on Sun.

A13

Due Thursday, March 8

Study the Java version of the program in Figure 7.31 (Main, InBuffer, Token, Tokenizer, Util)

Begin Problem 7.20(a)

Notice

Monday, March 12 is the last day to withdraw with a grade of W.

A14

Due Monday, March 12

Problem 7.20(a)

You must use Java, so change the code for the enumerated types in the problem statement accordingly. You must store hexValue as an integer as in the previous programming assignment.

Integers are stored in two bytes. When considered unsigned, the range is 0..65535. When considered signed the range is -32768..32767. Your program must accept integers in the range -32768..65535. Each time you scan a decimal digit and update the total value, check it against this range. If inputting a decimal digit makes the total value go out of this range return the invalid token.

Hexadecimal constants are also stored in two bytes and are never signed. The maximum value that a hexadecimal constant can have is 65535. Each time you scan a hex digit and update the total value, check it against this upper limit. If inputting a hex digit makes the total greater than this upper limit return the invalid token.

Addressing modes must be stored as identifiers. The parser will convert the identifiers to enumerated types by table look-up.

Here are lists of valid tokens and invalid tokens that your lexical analyzer should handle properly. Your lexical analyzer should recognize all the valid tokens and reject all the invalid tokens. This list is not exhaustive. There are many more strings of characters that should be accepted and, of course, many more that should be rejected. (See A19 for the specification of the final project.) Test your lexical analyzer thoroughly.

Valid tokens

<empty line>
<space>
alpha
alpha<space>
<space>alpha
.alpha
.alpha<space>
b7 0x23ab, i
b7 0x23ab ,SxF
b7 0x23ab,x<space>
0x2 0x2a 0x02a 0x002a
0x0 0xFFFF
-32768 65535

Tokenizer output

Empty token
Empty token
Identifier = alpha
Empty token
Identifier = alpha
Empty token
Identifier = alpha
Empty token
Dot command = alpha
Empty token
Dot command = alpha
Empty token
Identifier = b7
Hexadecimal constant = 9131
Addressing Mode = i
Empty token
Identifier = b7
Hexadecimal constant = 9131
Addressing Mode = SxF
Empty token
Identifier = b7
Hexadecimal constant = 9131
Addressing Mode = x
Empty token
Hexadecimal constant = 2
Hexadecimal constant = 42
Hexadecimal constant = 42
Hexadecimal constant = 42
Empty token
Hexadecimal constant = 0
Hexadecimal constant = 65535
Empty token
Integer    = -32768
Integer    = 65535
Empty token
Empty token

Invalid tokens

alpha$beta
0xQ
0x12345
-32769 65536

Tokenizer output

Identifier = alpha
Syntax error
Syntax error
Syntax error
Syntax error
Empty token

For now, hexadecimal constants may be output as a single decimal value. For example, the line

b7 .What 0xb7, abc 7

should produce the output

Identifier = b7
Dot command = What
Hexidecimal constant = 183
Addressing mode = abc
Integer = 7
Empty token

Name your NetBeans project Prob0720a and the class that has the main program as Prob0720aMain in a file named Prob0720aMain.java. Create a separate source file for each Java class. Export the source files in a JAR file named Prob0720a.jar. Hand in the .jar file with the homework command on Sun.

Test 2

Thursday, March 15

Chapters 5.3, 5.4, 7.1, 7.2, 7.3

A15

Due Monday, March 19

Study Chapter 7.4

Study the Java Map hash table example (main program). Study the Java version of the program in Figure 7.35 (main program, token classes, tokenizer, maps, code classes, argument classes, translator) and the Java UML diagram (diagrams). Here is the Java source code for Figure 7.35 in a .jar file.

Exercise 7.20(b)

A16

Due Thursday, March 22

Study Chapter 6.1, 6.2

Problems 6.12, 6.13

A17

Due Monday, March 26

Study Chapter 6.3

Problem 6.16

A18

Due Thursday, March 29

Study Chapter 6.3

Problem 6.17

A19

Due Monday, April 2

Problem 7.20(c)
Include a paper copy of the finite state machine design for the parser of your program.

IMPORTANT change in specification.
1. The text gives a list of the instruction set for your assembler. Your project must be able to translate a few additional ones. Here is the list of instructions your program should translate: Unary instructions -- STOP, ASLA, ASRA. Nonunary instructions -- BR, BRLT, BREQ, BRLE, CPA, DECI, DECO, ADDA, SUBA STA, LDA. Dot commands -- .BLOCK, .END. Constants -- decimal, hexadecimal.
2. The text says that you may assume that any instruction may use any addressing mode. However, for this project you must verify that the addressing modes used by the instruction are valid.
3. The text says that an addressing mode will be present for the branch instructions. However, for this project any branch instruction can omit the addressing mode, in which case your assembler must assume immediate addressing.

As with your token classes, the class for a nonunary mnemonic must have an integer attribute to store the hexadecimal constant. Also, the addressing mode attribute must be enumerated as described in Problem 20(a). Set up separate Java Maps for looking up unary mnemonic identifiers, looking up nonunary mnemonic identifiers, looking up dot commands, and looking up addressing modes. For your code classes, do not use a boolean attribute to distinguish unary from nonunary instructions. Instead, have separate classes for unary and nonunary instructions.

Although the problem description in the text does not specify a program listing, this phase is to complete the generateListing() methods of your code classes to emit the listing as shown in the Java version of our translation example. The output should conform to the standard pretty-printing format of the Pep/8 assembler when you select Format From Listing in the Edit menu as shown below. For hexadecimal constants, the %X format placeholder will output an integer value in hexadecimal format. Research the Java documentation for the field with and leading zero options. For strings, the %s format placeholder has options to either left-justify or right-justify in a field padded with spaces.

Valid input

br  0x17,  i
.BLOck    0x3
.block 1
deci  0x03,d
LDA 0x0003,   d
adda    0x9, i

deco 0xaB, s
stop
.end

Output

Program Listing
BR      0x0017      
.BLOCK  0x0003      
.BLOCK  1           
DECI    0x0003,d    
LDA     0x0003,d    
ADDA    0x0009,i 
   
DECO    0x00AB,s    
STOP                
.END

Invalid input

brr  0x7,  i
.BLOck   0xG
deci  0x03, e

The following error messages are only illustrative. Yours may differ, but should be informative about the error detected.

Output

ERROR on line 1: Illegal mnemonic
ERROR on line 2: Illegal hex constant
ERROR on line 3: Illegal addressing mode

Your program will be tested more extensively that the short examples above. Be sure to test it thoroughly.

Name your NetBeans project Prob0720c and the class that has the main program as Prob0720cMain in a file named Prob0720cMain.java. Create a separate source file for each Java class. Export the source files only in a jar file named Prob0720c.jar. Hand in the .jar file with the homework command on Sun.

A20

Due Thursday, April 5

Study Chapter 6.3

Problem 6.18, 6.22

For 6.22, also resubmit your program Prob0215.cpp from A1 using the homework command. Your assembly language program pr0622.pep must be an exact translation of your C++ program with symbols in assembly language corresponding to variable names in C++. Input the number of disks, the source peg, and the destination peg in that order.

A21

Due Monday, April 9

Study Chapter 6.4
Skip the section, Translating Arrays Passed as Parameters.

Problem 6.24, 6.25

A22

Due Thursday, April 12

Problem 7.20(d)

Complete the generateCode() methods of your code classes to emit the hexadecimal code for the assembly language program in a format suitable for use by the Pep/8 assembler. To test your object code copy the hex code from the Java console, paste it into the object code pane of the Pep/8 application, and execute your program. Remember that all hex digit pairs in the object code must be separated by exactly one space, no lines in the object code may contain a trailing space at the end of the line, and the entire sequence must terminate with lowercase zz.

To get a decimal value into hex, you can use the fact that n/256 is an 8-bit right shift. Use it to output the first byte of integer n. Also, n%256 is an 8-bit remainder. Use it to output the second byte of integer n.

The following shows what your output should look like for a sample input. Your object code could be all on one line, or it could be formatted as in the Pep/8 system you use in this course. The only requirement for formatting is that it will load and run if you copy and paste it into the objcet code pane of the Pep/8 system.

Valid input

br  0x17,  i
.BLOck    0x3
.block 1
deci  0x03,d
LDA 0x0003,   d
adda    0x9, i

deco 0xaB, s
stop
.end

Output

Object code
04 00 17
00 00 00
00
31 00 03
C1 00 03
70 00 09
3B 00 AB
00
zz

Program Listing
BR      0x0017      
.BLOCK  0x0003      
.BLOCK  1           
DECI    0x0003,d    
LDA     0x0003,d    
ADDA    0x0009,i 
   
DECO    0x00AB,s    
STOP                
.END

Name your NetBeans project Prob0720d and the class that has the main program as Prob0720dMain in a file named Prob0720dMain.java. Create a separate source file for each Java class. Export the source files in a JAR file named Prob0720d.jar. Hand in the .jar file with the homework command on Sun.

Notice

Friday, April 13 is the last day to withdraw with a grade of WP/WF.