CoSc 330 / Computer Systems

Computer Systems

Spring Semester, 2010

CoSc 330: Syllabus
Instructor: Stan Warford
Office: RAC 108B
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.

Setup for C++

A few of the assignments at the beginning of the course are in C++. For those assignments, the procedures are the same as for programming in C++ in Data Structures last semester.

Setting up for Java with Eclipse

Java is an interpreted language that requires the Java Virtual Machine to run. Eclipse 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 Eclipse 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 JDK6. You will not need the package with NetBeans, which is Sun's IDE, because we will be using Eclipse instead. You will not need JDK 6 with Java EE either, 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 SDK.

To install Eclipse on your local computer, go to www.eclipse.org and navigate to the Downloads section. Download and install Eclipse SDK 3.4.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 Eclipse, which takes care of these issues automatically.

Getting started with Eclipse

When Eclipse starts up the first time you must specify the current Eclipse workspace, which is a directory in your file system where you want to store your projects. Because most projects consist of more than one class, and each class is stored in its own source file, all the source files for a project are usually grouped together in a project directory. A project directory is a subdirectory of the workspace directory.

For very large numbers of classes the project can be further subdivided into packages. A package corresponds to a subdirectory of the project directory. Eclipse has good support for packages, but none of our projects have so many classes that they require such subdivision. We will be content to use the "default package", which has the scope of the project directory.

The following scenerio is a description of how to create a Java "Hello, world!" program with Eclipse. 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 Eclipse and select File > New > Project. Select option Java Project. The name of the project will be the name of a new folder that Eclipse creates in the workspace. For this example, name the project Hello. Project directories contain two invisible files named .classpath and .project, which Eclipse puts in the project directory when you create a new project.

Open the workbench and select the Java perspective if it is not already selected. (Use the perspective button on the top right tab.) Select File > New > Class, or right click on Hello in the Package Explorer. Verify that the source folder is Hello, name the class HelloMain, and check "public static void main". The class is created in a text editor pane with a stub comment for you to replace with Java code. To enter System.out.println("Hello, world!"); first type System. and note the code completion feature. Select option and press the enter key (or return) to autocomplete.

Save the source file. To compile and execute the application selece Run > Run As > Java Application. The Console pane appears and displays the output.

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 14

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 18, Martin Luther King Day
Class does not meet.

A2

Due Thursday, January 21

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 Eclipse 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 Sun'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. Name your Eclipse project Prob0357 and the class that has the main program as Prob0357Main. Note the uppercase P. Export the source file only in a jar file named Prob0357.jar. You must select File -> Export -> Java -> JAR file -> Next. UNCHECK "Export generated class files and resources". CHECK "Export Java source files and resources". Hand in the .jar file with the homework command.

A3

Due Monday, January 25

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 Eclipse 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 Eclipse project Prob0361 and the class that has the main program as Prob0361Main. Note the uppercase P. Export the source file only in a jar file named Prob0361.jar. Hand in the .jar file with the homework command.

A4

Due Thursday, January 28

Study Chapter 4.3, 4.4

Exercise 4.1, 4.2, 4.6

Problem 4.12.

Name your program Prob0412.pepo.
Note the uppercase P. In general, pep8 assembly language source files should end in .pep, machine language object files should end in .pepo, and assembler listing files should end in .pepl.

Download the Pep/8 system from the links given in the announcements section above.

A5

Due Monday, February 1

Study Chapter 5.1

Exercise 4.9

Problem 4.15

Name your program Prob0415.pepo.

A6

Due Thursday, February 4

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 8

Exercise 5.11, 5.12

Problem 5.21, 5.22

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

Test 1

Thursday, February 11

Chapters 1 through 5.2

A8

Due Monday, February 15

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 18

Study Chapter 7.1

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

A10

Due Monday, February 22

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 25

Study Chapter 7.3

Problem 7.16

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

Spring Break

March 1 - March 5

A12

Due Monday, March 8

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 Eclipse 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 only in a jar file named Prob0719.jar. Hand in the .jar file with the homework command.

Notice

Thursday, March 11, class does not meet due to professor's conference.

A13

Due Thursday, March 11

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

Begin Problem 7.20(a)

Notice

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

A14

Due Monday, March 15

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. 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 Eclipse 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 only in a jar file named Prob0720a.jar. Hand in the .jar file with the homework command.

Test 2

Thursday, March 18

Chapters 5.3, 5.4, 7.1, 7.2, 7.3

A15

Due Monday, March 22

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, translator, tokens, tokenizer, abstract code class, error code classes, argument classes, valid code classes) 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 25

Study Chapter 6.1, 6.2

Problems 6.12, 6.13

A17

Due Monday, March 29

Study Chapter 6.3

Problem 6.16

A18

Due Thursday, April 1

Study Chapter 6.3

Problem 6.17

A19

Due Monday, April 5

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

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 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.

IMPORTANT change in specification. 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.

Although the problem description in the text says to not use generateCode, it will be easier in the long run if you do. For now, your generateCode method will simply output the values of its attributes as shown below. In the final phase of your project, you will change the implementation of generateCode to output hexadecimal machine language.

Valid input

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

deco 0xaB, s
stop
.end

Output

Valid
Mnemonic = eM_BR
Hexadecimal constant = 23
Addressing mode = eA_IMMEDIATE
Valid
Dot command = eD_BLOCK
Hex constant = 3
Valid
Dot command = eD_BLOCK
Decimal constant = 1
Valid
Mnemonic = eM_DECI
Hexadecimal constant = 3
Addressing mode = eA_DIRECT
Valid
Mnemonic = eM_LDA
etc.

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 Eclipse 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.

A20

Due Thursday, April 8

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 12

Problem 7.20(d)

Replace 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.

Name your Eclipse 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 only in a jar file named Prob0720d.jar. Hand in the .jar file with the homework command.

A22

Due Thursday, April 15

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

Problem 6.24, 6.25

Notice

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