1997/1998 S&N1 Exam Answers - Richard's Version
Q1.a -58 -> 2's Complement =
1 3 7 14 29 58 [Boggle Method]
0 0 1 1 1 0 1 0 [+58 in Binary]
1 1 0 0 0 1 0 1 [Invert]
1 [+1]
-----------------------------------
1 1 0 0 0 1 1 0 [2's Complement]
-----------------------------------
1100 0110 = C6 [Answer: C6h]
====================================================================
Q1.b 64h + 5Ch =
0110 0100 [64h]
0101 1100 [5Ch]
------------------------
1100 0000 [C0h] [Answer: C0h]
------------------------ [Flags: C=0, V=1, N=1, Z=0]
====================================================================
Q1.c 8Dh -> a: Unsigned, b: 2's Complement
a) 1000 1101 [8Dh]
1 0 0 0 1 1 0 1 [8Dh]
2 4 8 17 35 70 141 [Reverse Boggle]
[Answer: 141d]
b) 1 0 0 0 1 1 0 1 [8Dh]
1 [-1]
1 0 0 0 1 1 0 0
0 1 1 1 0 0 1 1 [Invert]
-----------------------------------
1 3 7 14 28 57 115 [Reverse Boggle]
[Answer: 115d]
=====================================================================
Q1.d -78.53125 -> IEEE 754
Sign Bit, Neg = 1
Integer = 78
Boggle Method = 1 2 4 9 19 39 78
= 0 1 0 0 1 1 1 0
= 0100 1110
Fraction = 0.53125 (5 bits = n/32)
= 32 x 0.53125 = 17
= 0.10001
Re-Assemble = Integer + Fraction
= 1001110.10001
= 1.00111010001 [Normalised]
Exponent = 10^6
= 6 + 127 = 133
= 1 2 4 8 16 33 66 133 [Boggle Method]
= 1 0 0 0 0 1 0 1
= 1000 0101
Sign + Exp + Mantissa
= 1 1000 0101 00111010001
Block in 4's and fill to 32 bits
= 1100 0010 1001 1101 0001 0000 0000 0000
= C 2 9 D 1 0 0 0
= C29D 1000 [Hex]
====================================================================
Q1.e Op Codes
Loc 26 27 97 98 Acc PC
Start 198 497 345 450 750 26
----------------------------------------
198 497 345 450 450 27
198 497 345 450 105 28
====================================================================
Q1.f RTL for Fetch + Execute of JMP nn
Fetch = PC -> MAR
MDR -> IR
PC + 1 -> PC
Execute = IR[Addr] -> PC
=====================================================================
Q1.g Deadlock
Involves two or more processes, where first process is waiting
for a resource that the second process needs, while the second
process is waiting for a resource that the first process needs.
[Diagram of Traffic Intersection]
=====================================================================
Q1.h Process States
=====================================================================
Q1.i What is IPL
It executes at startup and loads the first part of the Operating System
into RAM and transfers execution to it. Without this BootStrap program
the PC would not be able to start.
=====================================================================
Q1.j Multiprogramming
Because while one program is waiting for a resource to become free,
another program can be executing, thus improving the efficiency of
the whole program group. Also called multitasking.
=====================================================================
Q1.k Contiguous Disk File Storage
o Difficulty locating space for new files when disk becomes fragmented.
o Perfoming Disk De-Fragmentation to compact files and amalgamate space.
=====================================================================
Q1.l Optimising Compiler
o Looks for opportunities to restructure the code to speed up processing by:
a) Reducing quantity of code.
b) Eliminate repeated opperations.
c) Use resources more effectively.
o May decide to keep some commonly accessed variables in registers.
o Move calculations out of a loop if no variables are modified in the loop.
=====================================================================
Q1.m LAN Protocol
o CPU's are much faster allowing higher network data density.
o Today's LAN networks are as large as yesterday's WAN networks.
o The ratio between CPU clock cycles and LAN latency today is
similar to yesterdays ratio between CPU clock cycles and WAN latency.
=====================================================================
Q2.a Trace for 8 and 5
PC Mnem 95 96 97 98 99 Acc
--- ------ --- --- --- --- --- ---
00 LDA 96 001 000 000 000 000 000
01 STA 97 001 000 000 000 000 000
02 IN [8] 001 000 000 000 000 008
03 STA 98 001 000 000 008 000 008
04 IN [5] 001 000 000 008 000 005
05 STA 99 001 000 000 008 005 005
06 LDA 98 001 000 000 008 005 008
07 SUB 99 001 000 000 008 005 003
08 SKP 001 000 000 008 005 003
10 STA 98 001 000 000 003 005 003
11 LDA 97 001 000 000 003 005 000
12 ADD 95 001 000 000 003 005 001
13 STA 97 001 000 001 003 005 001
06 LDA 98 001 000 001 003 005 003
07 SUB 99 001 000 001 003 005 -02
08 SKP 001 000 001 003 005 -02
09 JMP 15 001 000 001 003 005 -02
15 LDA 97 001 000 001 003 005 001
16 OUT [1] 001 000 001 003 005 001
17 HLT 001 000 001 003 005 001
Program outputs a 1 (one)
=====================================================================
Q2.b Compnent of CPU
[See diagram in Q2.c and cheat!]
ALU = Arithmetic & Logic Unit, provides support of binary arithmetic
and boolean decision functions using input from Accumulator and one
other address. Output is directed to Accumulator.
Acc = Accumulator. One of the inputs to the ALU and also the output
of the ALU. Used to store intermediate results and one input for the
next calculation.
IR = Instruction Register. Accepts and decodes the CPU Instructions.
PC = Program Counter. Holds the address of the next instruction to
be fetched.
MAR = Memory Address Register. Holds the address of the next memory
location to be read from or written to.
MDR = Memory Data Register. Holds the data pointed at by the MAR.
IOAR = I/O Address Register. Holds the address of the memory location
defined as an I/O port into which data will be read or written by
an I/O device (Disk, Printer, Modem, etc.).
IODR = I/O Data Register. Holds the data pointed at by the IOAR.
=====================================================================
Q2.c Explain the CPU Diagram - See above!
=====================================================================
Q2.d Memory bus has 24 bit address & 32 bit data lines
i) memory locations = 16Mbytes ( 2^20 = meg, 2^4 = 16 )
ii) bytes per cycle = 4 ( 32 bits / 8 bits = 4 bytes )
=====================================================================
Q3.a Disk: 8 platters, 768 Cyl, 256 Sec, 512 bytes/sec.
i) Describe: platter, cylinder, track, sector.
platter: A double sided disk (two usable surfaces)
cylinder: Logically, collection of tracks on several surfaces
all sharing the same radius.
Track: Circular path for data storage on platter surface.
Tracks are stored concentrically.
Sector: Pie shaped segment of a track. Smallest addressable
area of disk surface. Numbered from zero starting
near disk spindle.
ii) 8 x 2 x 768 x 256 x 512
-----------------------
1024 x 1024
16 x 768
= --------
2 x 4
= 2 x 768 = 1536 Mbytes
=====================================================================
Q3.b Disk rotates at 4800 rpm, 8 sector cluster, seek time 11ms.
Ambiguous question! Does not state this is the same disk as Q3.a.
Does not state sectors per track.
If it is the same as Q3.a, then:
8 x 60 x 1000
= -----------------
256 x 4800
100
= --------
32 x 8
100
= -------- ms = 2.5 ms
256
=====================================================================
Q3.c Describe DMA Disk Read
Once initiated, DMA involves the I/O module writing or reading
directly to / from memory without CPU intervention. The CPU is
bypassed until the I/O module notifies the CPU that transfer is
complete, with an interrupt. The processor can do other tasks
while the DMA is active.
=====================================================================
Q3.d Video Card Resolution
The resolution of a video card is defined by the number of horizontal
and vertical pixels (picture elements) that the screen will display.
=====================================================================
Q3.e Interlaced/Non-Interlaced
Interlaced display is a method of screen refresh which increases the
screens vertical resolution by overlaying two fields of a lower
resolution with a slight vertical missalignment, interlacing the
two sets of scan lines.
I would recommend Non-Interlaced as the screen would display less
flicker and create a more stable image.
=====================================================================
Q4.a Disadvantage of CLI, name the parts:
i) Novice user will find it hard to remember the command syntax
ii) echo = command
"string" = argument
`cmd` = back-quoted sub-command - output will be inserted into string
=====================================================================
Q4.b Context Switching
Context switching is the term which describes multitasking at the
execution level. When a new program requires processing the
current program is suspended and all the associated registers are
saved. The process control block (PCB) contains information about
all the processes currently running and in suspension. When a
program terminates or it's time-slice ends, context is switched
again and the most appropriate suspended program is swapped back
in. The PCB remembers register locations and values, including the
program counter, the process ID, and any memory locations in use,
status flags, and the current execution status of each program.
=====================================================================
Q4.c Starvation
A Shortest Distance First (SDF) algorithm is processing a queue of
disk requests when a long-distance request enters the queue. If
more (shorter) requests keep appending to the queue, the long
request will never get serviced.
A solution would be to set a time limit or drop a gate on the queue
at regular intervals. Causing the queue to be emptied up to the gate
before serviceing the shorter requests that follow the gate.
Or add a priority to the queue whereby the priority rises exponentially
with the delay experienced by a queue member in the queue.
=====================================================================
Q4.d Non-Contiguous File
Dir = "Filename" -> 14
i) FAT =
------------------------------------------------- ----------------
|10|11|12|13|14|15|16|17|18|19|20|21|22|23|24|25|---|41|42|43|44|45|
------------------------------------------------- ----------------
|~~|nn|nn|nn|25|nn|nn|nn|nn|nn|nn|nn|42|nn|nn|22|---|nn|10|nn|nn|nn|
------------------------------------------------- ----------------
Where ~~ = End-of-File
ii) Allocate a new block (say 12) and update the pointer at block 10 thus:
----------------
|10|11|12|13|14|--->
----------------
|12|nn|~~|nn|25|--->
----------------
=====================================================================
Q5.a Scanning & Parsing
Scanning = Identifies recognisable "units" of the language and tokenises.
Parsing = Checks for validity or correctness of statements.
=====================================================================
Q5.b Railroad Diagrams
=====================================================================
Q5.c Parse Program
<while><variable><id limit><greater-than>
<unsigned-constant><id 0><do><begin>
<variable><id total><:=><variable>
<id total><+><variable><id limit>
<variable><id limit><:=><variable>
<id limit><-><unsigned-constant><id 1><end>
=====================================================================
Q5.d Generate LMC Assy Code for above
Label Loc Instr Arg
----- --- ----- ---
start 01 LDA total
02 ADD limit
03 STO total
04 LDA limit
05 SUB incr
06 STO limit
07 SKZ limit
08 JMP start
09 END
limit 10 DAT 003
total 11 DAT 000
incr 12 DAT 001
=====================================================================
Q6.a What is a protocol
A protocol is a set of agreed rules between two or more systems
that allow successful communications to be established over a
common infrastructure.
Using a standard protocol removed the need to re-invent the wheel
and is likely to prove more reliable, as new bugs in the protocol
are discovered less frequently, as time goes on and more experience
is gained.
=====================================================================
Q6.b Protocol Problems
o If a packet gets lost, the protocol will wait for an ACK for ever
o The protocol does not differentiate between lost packets or ACK's
o Packets are not numbered so duplicate packets are confused
FIX:
o Number packets so duplicates can be detected (also allows out or sequence
packets to be re-ordered correcly)
o Use a "timeout and resend" to stop indefinite waits
o Implement "up-to" ACK's to acknowledge several packets at once
=====================================================================
Q6.c No. Each layer should be responsible for only one task. Duplicating
the task in another layer will lead to confusion about who's
responsibility it is to recover the lost data. The lower layer
with either get the data or not. If not, it should request a
resend of the data. When the data stream is complete, the whole
chunk should be sent "upstairs" to the next layer in a complete
form. The layer above will only ever see complete data either on
time or late, but it will never see missing data if the layer
below is behaving correctly.
If the above is wrong, then the ISO 7 layer model is in need of
some serious re-work.
=====================================================================
End of Exam....
On the last page there is an incomplete question and two further questions
about UNIX stream editors. The are numbered 17.4, 17.5, 17.6 (I think).
What is the relevance of these questions, are we supposed to attempt them?