Java程序辅导

First Semester Examination 2014
Introduction to Computer Systems
(COMP2300/COMP6300 Paper A)
Writing Period: 3 hour duration 
Study Period: 15 minutes duration 
Permitted Materials: One A4 page with notes on both sides. 
                The rPeANUt specification will be made available. Note also the standard  
lab tools are available including: Java, eclipse, kate, dia, gcc, man, rPeANUt, the  
calculator on the computer,  ... 
NO calculator permitted (physical electronic device). 
Please Read The Following Instructions Carefully. 
This exam will be marked out of 100 and consists of 4 questions. Questions are of 
unequal value. The value of each question is shown in square brackets. Questions 
that are partitioned into parts show the number of marks given to each part within 
square brackets. 
Students should attempt all questions.   Answers must be saved into the question's 
directory (Q1, Q2, Q3, Q4) using the file(s) described in the question statement.  
Marks may be lost for giving information that is irrelevant. 
Network traffic may be monitored for inappropriate communications between 
students, or attempts to gain access to the Internet. 
The marking scheme will put a high value on clarity so, as a general guide, it is better 
to give fewer answers in a clear manner than to outline a greater number of less 
clear answers. 
Page 1 of 8 - Introduction to Computer Systems - (COMP2300/COMP6300) 2014
Question 1 [40 marks]    
Highest marks are gained by providing clear, concise, and short answers. Save your 
answers in the text file 'Q1answers.txt' in the directory Q1 (note this file is already 
created with places to add your answers, so just open up 'Q1answers.txt' and save 
your answers directly into it).  This file can be edited using 'gedit'.   Please make 
certain that this file is saved both as you progress through the exam and before the 
exam ends.
i. [4 marks] How many different values can be stored in a 8 bit word?   What is 
the range of numbers that is stored in a 8 bit word when an unsigned integer 
with an offset of -64 is used (this enables us to store negative and positive 
numbers) ?  Given this representation (8 bit unsigned integer with a -64 offset) 
what decimal value does the bit pattern 0x2A represent?  If we added 0x2A to 
0x80 in this representation (these are the bit patterns) what would be the bit 
pattern of the resulting word (give your answer in hex)? 
ii. [4 marks] The IEEE 754 32-bit single-precision floating-point standard has 3 
types of numbers: special, normal and subnormal.   If we created a new 
floating-point format that uses the same approach as IEEE 754 except that it 
is 8 bit rather the 32 bits having 1 sign bit, 3 bits for the exponent, and 4 bits 
for the significand.  Note we would have a bias of 3 rather than 127 for the 
exponent in normalized numbers.   In this new format what decimal number 
does 0xA8 represent (please calculate, do not leave as an expression)?  What 
is the bit pattern for the decimal number -1.0 (give your answer in hex)? In this 
new format what percentage of the possible bit patterns are used for 
normalized numbers (please calculate,  do not leave your answer as an 
expression)?   
iii. [4 marks] In digital logic explain how a finite state machine could be 
constructed from a collection of logic gates and registers. 
iv. [4 marks] What is a library call?  Why are they important for modern operating 
systems?  What is the relationship between library calls and systems calls?  
Do all library calls result in a system call?
v. [4 marks]  What is a process? What is the relationship between: a process, 
thread,  and a program?  
vi. [4 marks] How does executing instructions "out of order" within a CPU improve 
performance? 
vii. [4 marks] Suppose you have a 4-way set associative cache which has in total 
4096 bytes of cache memory and each cache line is 128 bytes.  How many 
sets are there in this cache?  If memory is byte addressable and addresses 
are 16 bits then how many bytes are used for the tag?   
viii.[4 marks] Suppose 4 processes are currently waiting on the ready queue of a 
single threaded CPU.   If the CPU becomes available to schedule these 
processes and the burst times of the 4 processes are 10ms, 100ms, 40ms, 
and 10ms (also arriving on the ready queue in that order),  what is the average 
wait time if a FCFS scheduler is used?  How does this compare with the SJF 
scheduling approach?
ix. [4 marks] In Linux UDP/TCP communication can be achieved with the 
following systems calls: sendto, bind, socket, listen, read, write, accept, and 
Page 2 of 8 - Introduction to Computer Systems - (COMP2300/COMP6300) 2014
recvfrom.  If you wanted a program to just receive a single UDP message 
which system calls of the above would you use?  Also in what order would 
they be used?   How could you determine the IP address of the host that sent 
the message to your receiving program?  
x. [4 marks] In Linux what is a file descriptor?  In Linux what are the two available 
approaches for reading the contents of a file that use different underlying 
system calls (assuming you have a file descriptor of an open file)?  List some 
situations when you would use one approach over the other approach.
Page 3 of 8 - Introduction to Computer Systems - (COMP2300/COMP6300) 2014
Question 2 [20 marks]
To run rPeANUt open up a terminal and run the following:
% cd
% java -jar rPeANUt2.3.jar
(a) [5 marks] Write a program in rPeANUt that draws two white pixels to the rPeANUt 
screen.  The first is in the top left position (coordinate (0,0)) and the second is in the 
bottom right of the screen (coordinate (191,159)).  Other parts of the screen must 
remain black.   Once this is done the program should halt.     Place your answer in a 
file called 'dots.s' in the Q2 directory. 
(b) [5 marks] Disassemble the program given in the image below.   Place your 
answer in a file called 'disassemble.s' in the Q2 directory.    Note your disassembled 
program should be able to be assembled by the rPeANUt assembler to the exact 
program in the image without any errors (note I have included the file 
"disassemble.objdump" which was produced by the -objdump option, so one way of 
checking your solution is to 'diff' this file with the objdump of your disassembled 
code).     Also exactly what will the program do when it is run (answer this question 
as a comment within the source of the disassembled program)?    
Page 4 of 8 - Introduction to Computer Systems - (COMP2300/COMP6300) 2014
(c) [10 marks] The C code below calculates a simple arithmetic function, called 'func', 
on a series of pairs of positive integers.   Convert this C code into rPeANUt 
assembler code.   Your solution must implement a procedure for 'func' using the 
recursive approach given below.  Also, use the conventional rPeANUt stack frame 
approach for this procedure.    Note within 'func.s'  you are given some code that will 
print out the decimal numbers to the terminal.   Place your answer in a file called 
'func.s' in the Q2 directory. 
#include  
int func(int m, int n) {
   if(m >= 2*n)
      return func(func(m,2*n),n);
   else if (m >= n)
      return m-n;
   else
      return m;
}
void main() {
    printf(“%d\n”, func(9,2)); // prints 1
    printf(“%d\n”, func(13,5)); // prints 3
    printf(“%d\n”, func(100,5));  // prints 0
} 
Page 5 of 8 - Introduction to Computer Systems - (COMP2300/COMP6300) 2014
Question 3 [20 marks]
(a) [5 marks] Write a C program that outputs to standard out the numbers from 1 to 
10 with comma separation using a 'for' loop.  This list of numbers should be on a 
single line (put a newline character at the end of the line).  Place your answer in the 
file called  'count.c' in the Q3 directory.  When run from the command line you should 
see:   
$ ./count
1,2,3,4,5,6,7,8,9,10
$ 
(b) [5 marks] Write a C program that uses "truncate"  to change the size of a file to a 
particular size.   This could make the file smaller by cutting off the end of the file,  
keep the file the same length,  or make the file longer.   This program takes as 
parameters: the file name to truncate, and the size in bytes to truncate the file to.  It 
then truncates the file to that size.  You may assume the file exists, is writeable,  and 
is just a regular file.   Place your answer in the file called 'mytruncate.c' in the Q3 
directory.  (hint - “man 2 truncate”)  The command below when run would chop the 
end off the "100bytefile" making it 50 bytes long.
$ ./mytruncate 100bytefile 50
(c) [10 marks] Write a program in C that is given a list of numbers via standard input 
(each number is space separated and all the input is on a single line)  and finds the 
most common number in the list and prints it on a single line to standard output.  If 
the list is empty then it just prints "empty".    All the numbers in the list will be in the 
range 0 to 9 inclusive and the list will be at most 1000 elements long.   Note if a set of 
2 or more numbers are equally most common then output the highest number in that 
set of equally most common numbers.    Below are some examples of running the 
program on the command line (echo and a pipe are a simple way of directing input to 
the program).  Place your answer in the file called  'mostcommon.c' in the Q3 
directory.
$ echo "2 3 7 3 5" | ./mostcommon 
3 
$ echo "" | ./mostcommon 
empty 
$ echo "4" | ./mostcommon 
4 
$ echo "4 2 9 9 9 9 9" | ./mostcommon 
9 
$ echo "1 7 3" | ./mostcommon 
7 
$ echo "4 4 3 1 7 3" | ./mostcommon 
4 
Page 6 of 8 - Introduction to Computer Systems - (COMP2300/COMP6300) 2014
Question 4 [20 marks]
Writing assembly code can be repetitive, tedious and error prone.  Hence you can 
write a program that generates assembly code,  and in essence this is what a 
compiler does.    Although you are not asked to write a compiler in this question you 
will need to write some C code that generates rPeANUt assembly code.   The aim of 
this generated assembly code is to draw a filled in circle on the rPeANUt screen and 
then halt.  This rPeANUt code takes no input but just draws a fixed circle.    However, 
the C code takes as a parameter the radius of the circle to be drawn (an integer 
amount between 1 and 70 inclusive),  and outputs to standard output the rPeANUt 
assembly code that when assembled and run will draw the circle of that given radius.  
As a secondary aim the rPeANUt assembly code produced should minimise the 
rPeANUt instruction execution count.  
There are 3 parts to this question.   However you only implement one C program for 
this question. The marks for part (a) focus on correctness, whereas the marks for part 
(b) are more about performance.  The marks for (c) related to some analysis of your 
solution.    Note you need to get a correct solution working before you can gain any 
performance marks. 
You should be able to compile your C code:
% gcc -Wall -o gencircle gencircle.c
Then run it:
% ./gencircle 50 > circle50.s
Then load the circle50.s file into rPeANUt and hit run (remember this rPeANUt 
program takes no input).   A circle of radius 50 should appear on the screen then the 
program should halt.  A screen shot of this circle is given below:
As it turns out there are lots of different ways you could do this.   So you could embed 
most of the work for drawing the circle into the rPeANUt code,  which would then 
make the C code basically just printing out this fixed rPeANUt code.   Or you could do 
most of the work for drawing the circle in the C code and generate rPeANUt code 
that is just a long sequence of the required writes to the screen memory.     As you 
wish to minimise the rPeANUt instruction execution count the latter is a better option. 
Page 7 of 8 - Introduction to Computer Systems - (COMP2300/COMP6300) 2014
(a) [10 marks] Write a C program that takes a number as a parameter and prints to 
standard output the rPeANUt assembly code that draws a circle.  Given the 
coordinate system for the rPeANUt screen as stated in the rPeANUt specification and 
a radius of 'r' then a pixel at (x,y) is part of the circle and must be drawn white if and 
only if:
(x-96)*(x-96) + (y-80)*(y-80) < r*r
otherwise the pixel must remain black. 
Put your answer in a file called “gencircle.c” in the Q4 directory.   
(b) [5 marks] Improve the performance of your generated code (in terms of rPeANUt 
instruction execution count).   Requires correct solution.   
(c) [5 marks] Construct an analytical model of the space (number of instructions used 
by your rPeANUt code that is generated) along with the time performance (number of 
rPeANUt instructions executed) as a function of the circle size.     How does this 
compare to a theoretically optimal circle drawing method?   If these requirements 
were changed and the rPeANUt code had as input the circle's radius then could you 
use a similar approach?  Or how would you change your approach?  How would this 
affect your program and its space and time performance?  Explain and discuss your 
answer.      Put your answer in a comment at the top of the “gencircle.c” file in the Q4 
directory.  
Page 8 of 8 - Introduction to Computer Systems - (COMP2300/COMP6300) 2014