Java程序辅导

First Semester Examination 2014
Introduction to Computer Systems
(COMP2300/COMP6300 Paper B)
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 6 bit word?   What is 
the range of numbers that is stored in a 6 bit word when two's complement 
representation is used?  Convert the octal number 072 to hexadecimal.  What 
decimal number would the octal number 072 represent if it was interpreted as 
a 6 bit two's complement number.
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 1.5 in the new format (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 a process you could use to create a digital 
logic circuit from a collection of logic gates that will implement a particular 
boolean function which is described by a truth table. 
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 had a CPU with: 8 bit addresses, byte addressable 
memory, a 3-way set associative data cache with a total of 96 bytes, each 
cache line containing 8 bytes, a LRU replacement approach is used within 
each of the sets;  also there is no pre-fetching.   How many cache lines are 
there in the cache?   How is the 8 bit address partitioned into tag, set, and 
word sections (give the number of bits in each section)?   Assuming the cache 
is initially completely empty and the below sequence of addresses is read by 
the CPU.  Place brackets around the reads that generate a cache miss for the 
sequence: 0x03, 0x25, 0x0F, 0xE3, 0x23, 0x0A, 0x28, 0x86, 0x03.
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 
Page 2 of 8 - Introduction to Computer Systems - (COMP2300/COMP6300) 2014
wait time if a FCFS scheduler is used?  How does this compare with the SJF 
scheduling approach?
ix. [4 marks] What is a TLB?  What information is stored in each entry of a TLB? 
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 prints “Hello World!” to the terminal.   
Place your answer in a file called 'hello.s' in the Q2 directory. (Hint you do not need to 
use a loop.)
(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 inclusive 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 takes a single file name as a parameter and 
outputs to standard output the size of the file in bytes.  You may assume the file 
exists and it is just a regular file.   Place your answer in the file called 'mysize.c' in the 
Q3 directory.  (hint - “man 2 stat”) 
(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]
"malloc" is a way a C program can obtain chunks of memory.  Once the memory is 
used by the program it can call "free" to indicate that this chunk is no longer needed.  
However, later the program may call "malloc" again and that same part of memory 
can be reused.    Generally the memory made available by "malloc" will be on the 
heap.  The C library will also need to have some meta data about what sections of 
the heap has been allocated so it will only allocate unused memory.
In this question in the C programming language you are required to implement your 
own malloc library.   This involve writing 3 functions: "mymalloc", "myfree", and 
"myinitmalloc".  "mymalloc" only allocates 4 byte chunks in each call (hence there is 
no size parameter like the normal malloc library call).   Similarly the "myfree" function 
will only free a 4 byte chunk.   These chunks must be aligned on normal integer  
boundaries.  
Your malloc library may only use a fixed sized array of 100 integers for both: storing 
the memory that is provided by your "mymalloc" function AND for storing the meta-
data about what has been allocated/freed.   This array is called "myHeap".   So 
although there are 100 integers that could fit in the "myHeap", the malloc will not be 
able to make available all of these as some of the heap must be used for keeping 
track of what is allocated/freed. 
As a secondary aim of your malloc library you should attempt to provide as many 
chunks as possible to the requesting program.  So minimise the meta-data overhead.
 
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 efficiency (in terms of  minimising meta-data overhead).  The 
marks for (c) are related to some analysis of your solution.    Note you need to get a 
correct solution working before you can gain any marks for efficiency. 
Page 7 of 8 - Introduction to Computer Systems - (COMP2300/COMP6300) 2014
(a) [10 marks] In the "mymalloc.c" file implement the functions:
• "myinitmalloc" – this frees any malloced memory and initializes the heap.
• "mymalloc" – allocates 4 bytes of memory from within the "myHeap" array and 
returns a pointer to those 4 bytes.  If there is no room in the heap then a NULL 
is returned.  Note the allocated memory must be integer aligned.
• "myfree" – frees previously allocated memory on the "myHeap",  note a pointer 
to the 4 bytes allocated is provided. 
The "mymalloc.c" file contains the "myHeap" array, the unimplemented function calls, 
and main function that does a basic test of using these functions.   So modify this file 
completing these unimplemented methods. 
You should be able to compile your C code:
% gcc -Wall -o mymalloc mymalloc.c
Then run it:
% ./mymalloc
12 
7 
16 
Put your answer in a file called “mymalloc.c” in the Q4 directory.   
(b) [5 marks] Improve the efficiency of your solution (in terms of minimizing the meta-
data size overhead).   Requires correct solution.   
(c)[5 marks] Analyses the amount of space your meta-data takes in your solution.     
Also construct an analytical model of the time it takes for the execution of the 
"mymalloc" and "myfree" functions.  Now these may change as memory is allocated 
and freed.    So in this model of the time performance consider worst case and some 
type of average case performance as a function of the amount of memory allocated.   
If you wished to improve the time it takes to execute "mymalloc" what changes would 
you make to your solution,  how would this affect the number of chunks that can be 
malloced and the performance of "mymalloc" and "myfree".   
Put your answer in a comment at the top of the “mymalloc.c” file in the Q4 directory.  
Page 8 of 8 - Introduction to Computer Systems - (COMP2300/COMP6300) 2014