A student writes a program in a high-level programming language. A compiler translates the
program into machine code.
(a) The compilation process has a number of stages. The output of the lexical analysis stage forms the input to the next stage.
(i) Identify this stage. [1]
(ii) State two tasks that occur at this stage. [2]
(b) The program uses pseudocode in place of a high-level language.
There are a number of reasons for performing optimisation. One reason is to produce
code that minimises the amount of memory used.
State another reason for the optimisation of code. [1]
(c) The following statement assigns an expression to the variable A.
Suggest what a compiler could do to optimise the following expression. [1]
A ← B + 2 * 6
7 points
7
Question 2
2.
(a) Complete the Boolean expression that corresponds to the following truth table.
(b) (i) Complete the Karnaugh map (K-map) for the truth table given in part (a). [1]
The K-map can be used to simplify the function in part (a).
(ii) Draw loop(s) around appropriate groups of 1s to produce an optimal sum-of-products.[2]
(iii) Using your answer to part (b)(ii), write the simplified sum-of-products Boolean
expression. X = ........................................................................................................................ [2]
14 points
14
Question 3
3.
A computer operating system (OS) uses paging for memory management.
In paging:
– main memory is divided into equal-size blocks, called page frames
– each process that is executed is divided into blocks of same size, called pages
– each process has a page table that is used to manage the pages of this process
The following table is the incomplete page table for a process, Y.
a) State two facts about Page 5. [2]
b) Process Y executes the last instruction in Page 5. This instruction is not a branch
instruction.
i) Explain the problem that now arises in the continued execution of process Y. [2]
ii) Explain how interrupts help to solve the problem that you explained in part b) i). [3]
c) When the next instruction is not present in main memory, the OS must load its page into a
page frame. If all page frames are currently in use, the OS overwrites the contents of a
page frame with the required page.
The page that is to be replaced is determined by a page replacement algorithm. One
possible algorithm is to replace the page which has been in memory the shortest amount
of time.
i) Give the additional data that would need to be stored in the page table. [1]
ii) Complete the table entry below to show what happens when Page 6 is swapped into
main memory. Include the data you have identified in part c) i) in the final column.
Assume that Page 1 is the one to be replaced.
In the final column, give an example of the data you have identified in part c) i). [3]
Process Y contains instructions that result in the execution of a loop, a very large number of times. All instructions within the loop are in Page 1.
The loop contains a call to a procedure whose instructions are all in Page 3.
All page frames are currently in use.
Page 1 is the page that has been in memory for the shortest time.
iii) Explain what happens to Page 1 and Page 3, each time the loop is executed. [3]
8 points
8
Question 4
4.
Match the computer terms being described below with its correct term.
Draggable item
arrow_right_alt
Corresponding Item
Physical memory and logical memory are split up into fixed-size memory blocks.
arrow_right_alt
quantum
Time when a process gets control of the CPU.
arrow_right_alt
pre-emptive
System which gives the illusion that there is unlimited memory available.
arrow_right_alt
virtual memory
When a process switches from running state to steady state or from waiting state to steady state.
arrow_right_alt
low level scheduler
When a process terminates or switches from running state to waiting state.
arrow_right_alt
paging
Algorithm which decides which process (in the ready state) should get CPU time next (running state).
arrow_right_alt
non-preemptive
Logical memory is split up into variable-size memory blocks.
arrow_right_alt
burst
A fixed time slice allotted to a process.
arrow_right_alt
segmentation
6 points
6
Question 5
5.
In this question, you are shown pseudocode in place of a real high-level language.
A compiler uses a keyword table and a symbol table.
Part of the keyword table is shown below.
– Tokens for keywords are shown in hexadecimal.
– All the keyword tokens are in the range 00 to 5F.
Entries in the symbol table are allocated tokens. These values start from 60 (hexadecimal).
Study the following piece of code:
a) Complete this symbol table to show its contents after the lexical analysis stage. [3]
b) Each cell below represents one byte of the output from the lexical analysis stage.
Using the keyword table and your answer to part a), complete the output from the lexical
analysis. [3]
9 points
9
Question 6
6.
Several syntax diagrams are shown.
(a) State whether each of the following passwords is valid or invalid and give a reason for
your choice.