Computer Systems Flashcards
convert 100110 to decimal
convert 25 to binary
38 base10
11001 base 2
convert 11010111 to hexadecimal and explain
convert B4 to deciaml
look in groups of 4 so 1101 = 13 = D and 0111 = 7 so D7base16
B = 1011 4 = 0100 so 10110100 base 2
multiply these two binary numbers, v=11010 and w =1011
in v, bits d1,d3 and d4 are equal to 1. SO add that number of 0’s to the other number and then add them together.(usually pick the number with less 1s)
vxw = 10110 + 1011000 + 10110000
1s complement and problem with it
flip the bits for 1s complement.
problem with this is thier is 2 represetnations of 0
this is solved using 2’s complement where you flip bits and add 1
Von neuman architecture
Input –> memory –> output
Control Unit ALU
Normalised representation for r = 12.25
for base 2,base 10 and base 16
for b =2
12.25 = 1100.01 to normalise it more decimal point 4 spaces left so the answer is 0.110001 x 2^4
for b = 10
12.25 = 12.25. normalise it move decimal place 2 to left so
0.1225 x 10^2
for b =16
12 = C
0.25–> 0.25 x 16 = 4 so C.4 move decimal one to left so
0.C4 x 16^1
what is decimal number 0,-1 and -16 for an exponent e of 5 bits with bias 16
0base10 = 10000 this is as 16 is bias so it = 0
-1 = 01111
-16 = 00000
Endianness
Big - endian
little-endian
ways to represent data where a single value needs more than one byte to be stored
Most significant byte first
Least significant byte first
Hamming distance
minimum number of symbols that need to be changed when transforming sequence 1 into 2.
Even partiy
odd parity
if sum of seven meaningful bits is odd than the parity bit equals 1 so that sum of the bits become even.
If sum of the seven meaningful bits is even than parity bit = 1 so that sum of all bits is odd
hamming distance of v = 11011000 and w = 01011100
2
General rule for minimum hamming distance
d(c)-1 bits can be detected
(d(c)-1)/2 bits can be corrected.
How would you check for error when transferring message a 1010 to b 1011
Use extra parity bit with even parity so
A-10100 and B-10110
We see in b there’s an odd number of 1s so we know something’s wrong
How to decode a message
Look at book
Lossless compression
Frequently occurring symbols are mapped onto shortest possible encodings and rare symbols mapped onto longer encodings
Repeated occurrence of symbols are replaced by a pointer to their first occurrence
Run length encoding
Replace each sequence of a single symbol in the file by just a single occurrence of a symbol and number representing repitions
Use rle on 1111111 000000
1[7] 0[6]
Useful for long sequence of repeated symbols
However it needs minimum number of repitions before sequence encoded
Xor gate
0110
What do all gates look like
XOR —> box with =1 in it
And —>box with & in it
Or —> box with >=1 in it (other greater = sign )
Not—> box with 1 in it and open circle to go out
NAND —> box with & in it and open circle to go out
Half adder, full adder
Half adder carries out sum of two inputs and full adder three inputs
output i0 = 10110
i1 = 11100
i2 = 00011
i3 = 10001
selector uses two bits to represent i0 to i3
if selector = 10 whats output
ez 00011
Flip flops
Devices for storage of 1 bit data
How does SR flip flops work S = set R = reset
S= 1 and R = 0 Then output = 1
S= 0 and R = 1 Then output = 0
S = 0 and R = 0 Then output does not change
if s = 1 and R = 1 is illegal state
How to draw it
S—>|1 |o ——-|&|o ——- Q
Input of Q’ becomes second input in above nand gate
input of Q becomes second input in below nand gate
R—>|1 |o ——-|&|o ——- Q’
Register
Number of flip flops bundled together that can be accessed in parallel.
can contain input output for an adder
can store memory address of current instructions.
shift register
value after shift right and left
shifts content left or right. Each step one bit is lost and 0 bit is inserted.
n/2 if right
n x2 if left shift
race condition
how to deal with race condition
gate delays to react on a changed input
use a clock as it sets pc to sleep and wake them up again.
AIDJ operations
xi = c : assignment c is any natural number
xi = x +1
xi = x-1
if xi != 0 then goto Mn ( marker n) example 02
make add function with AIDJ
00 x1 = c
01 x2 = d
02 x2 = x2+1
x1 = x1 -1
if x1 != 0 then goto 02
CPU-S operations
xn = xn + xm
xn = xn - xm
xn = xn x xm
if xn != 0 then goto line
What do each do in CPU-S
DP1
DP2
IP
IR
+1
DR1
IDC
SEL
contains memory address for value for Data register 1
contains memory address for value for Data register 2
Register containing address of current instruction
Contains current instruction
increases content of IP by 1
Contains first operand for additrion
Opcode for CPU-S
JUMP - if DR1 != 0 then IP = {addr}
LOAD1 - DP1 = {addr}
LOAD2 - DP2 = {addr}
STORE - Write Acc to data memory using address DP1
what is the abstarct programme xn = xn + xm in assebmly language
LOAD1( with addr n)
LOAD2 (with addr m)
ADD
STORE
STOP
Limits of CPU-S
cannot use the value in ACC as input so have to store results in memory first
Supports smaller selection of instructions
LOAD1/2 and JUMP contatin address of DM and IM. so the length of the addr limits max size of DM and IM
What is clock used for in CPU-S
used to seperate the execution of the instructions from each other
Also used to split single instructions into several parts called fetch-executre
How does fetch decode execute work
F- Content of IM addressed by IP is fetched into IR
D- System decides which register needs new value or which signals needed for IP
E - Data registers read thier values from memory and devices of ALU execute their operations. Address of next instruction assigned to IP
Graph for input unit and output
input device <—> input module —–> data register
output device <—— output module <—— data register
CPU-S(I/O) new instructions
Input-S - write content of dR into memory cell
Output-S- write content of memory cell addressed by DP1 into DR of output unit
take 2 numbers from input . sum and output in CPU-S(I/O)
LOAD1(with<addr>= 0)
Input-S
LOAD1(with<addr>=1)
Input-S
LOAD1(with<addr> = 0)
LOAD2(with<addr>=1)
ADD
STORE
OUTPUT-S
STOP</addr></addr></addr></addr>
problems with CPU-S( I/O)
If size of input is unknown, CPU-S(I/O) cannot easily decide whether input has been completly transferred.
Every I/O of ALU must pass through memory. Inneficent and slows down data processing
How to amend problems of I/O
replace data registers with buffer memory so I/O devices can read data independently from current state of CPU
what is buffer memory
small memory that works in accordance with FIFO principle. Stores data when they become availalbe. Release them when they are needed.
benefits of buffer memory
more organised data registers and address registers of I/O unit to Cpu. allowing cpu to directly access content of these registers
Execution of input instruction
book
uses and limits for Programmed I/O
uses: keyboard input and output to non-graphical display
limits: input can only be read if its expected by programme. It is not possible to interrupt programme by external event.
why would we want computer to accept unrequested input.
incase of failure of vital system components
Attempt of executing illegal instructions
Intterupt servicing steps
- CPU executes programme A
- if Interrupt recivied, CPU complemets current instruction and then all content of registers in CPU stored in stack area
- Interrupt handler will be executed.
4 When completed, original content of registers restored and programme A resumes where it stopped.
Benefits of intterupts
Vital for efficeient handling of non-programmed input
Polling not required
Uses of Intterupts
Completion signals
external event notifications
Allocation of CPU time
Rules for multiple interrupts
Every intterupt given priority
1. Interrupt handler suspends normal programme
2. IH of interrupt 1 suspends IH of interrupt 2 if p(1) > p(2)
3 After completion, next interrupt with highest priority is serviced. if there are several interrupts the n order of occurance decides it.
How is DMA executed
Used when transferring large blocks of data
Using programmed I/o, CPU initiates DMA and sends parameters to I/O modules.
2. The I/O modules can write/read data into/from memory
3. The i/O module sends an interrupt to CPu as completion signal
SRAM VS DRAM
Sram based on flip-flops so content of memory cells stays unchanged unless changed by new input value
DRAM store content in capictors. This content fades away with time and needs to be refreshed every few ms
In Sram, read/write operations are very fast while in Dram they are slower
In SRAM, number of bits that can be stored on a single memory chip is limited.
In DRAM, memory capacity per chip is higher
SRAM is expensive as it needs 6 or more transisiotrs for storage of 1 bit.
DRAM can store one bit with one capacitor and one tranistor so is rather inexpensive.
Volatile
non volatile
if power is removed, then volatile devices lose their content. SUch as cache memory, RAM.
if power is removed. then devices keep their content. flash memory. used for permanenet storage/
semi conductor memory
mass storage
memory gap
Memory built from logic gates/capictors(RAM)
devices with mechanically moved parts(hdd)
semi conductory memory access time is at least 10 times faster than mass storage devices
cache memory adv and dis
can be accessed at speeds close to the CPU because of its location.
Allowing for programs to be executed more efficiently
Another advantage is lower power consuption as accessing cache memory consumes less power compared to main or secondary storage
However, due to gate delays and costs, we cannot operate a large cache memory at clock rate of CPU, therefore size is limited.
High cost due to cache being typically made from SRAM which is expensive.
Gow to find next instruction in cache memory
- If instruction are loaded into CPU’s registers, the address is first looked up in cache>
- if not in cache, its looked up in main memory. If found, instructio0n loaded into cache and CPU.
- If not found in main memory, instructions are loaded for mass storage into cahe and CPU
one vital aspect to find instructions in cache memory
physical and logical memory addresses.
logical address space divided into same size pages
split into page address and offset
Physical memory is divided into same size frames
consisting of frame address and offset
When CPU asks for logical address, it’s mapped onto physical address which is the position of the actual requested data
second vital aspect to find instructions in cache memory
Loading data from slower to faster memory
When CPU request data not contained in cache, then the content of that particular address along with the full page contating that adress is written to next level of memory hiearchy.
third vital aspect to find instructions in cache memory
Spatial locality
Programmes are organised in a way that often the next address requested by the CPU is very close to the previous one
what does memory management unit do
maps logical addresses onto physical addresses.
controls process of writing pages into cache
if cache or main memory is full, it determines which page is written back to the next slower level of memory hiearchy using FIFO or least frequently used page.
controls data integrity and de and encrypts data
First classification of buses
and advantage
Unidirectional bus - connects two devices with fixed roles.( one device is sender, other device is reciever of data) address bus
ad- no agreement necessary between devices about their role
Bi directional bus - connects two devices that both can be sender and reciever( data bus and control bus)
ad- more flexible regarding number of devices connected
Second classification of buses
and examples
parallel bus - all data travelling at the same time by using n wires in parallel where n corresponds to length of word being transferred.
eg. data bus between CPU and memory, ATA bus
Serial bus- transfers a word one bit after another. Word is decombosed by sending device and recomposed by revieveing device
USB, S-ATA bus
Advantage and disadvantage of Parallel and serial buses
Parallel bus have potetnital of higher data rates as they transfer more than one bit at a time
Serial buses faster than parallel buses due to clock rate and distance of parallel data transmission is limited by skew.(bits wont arrive exactly at same time)
Parallel buses need more space than serial buses
Serial buses preferred for long distance data transfer at high clock rates
Third classification
point-to-point buses - can connect exactly two deivices
eg buses between ALU and CU, AGP bus
multipoint- large number of devices use this single bus as common means of exchanging data.
PCI, USB
Von neumann bottlenech
all data have to pass the main bus system of computer
Synchronous transmission
Sender and reciever have the same clock allowoing a constant stream of data to be transmitted
asynchronous transmission and problems it creates
sender and reciver have different clocks
p1- the same data are mistakenly read multiple times by reciver if reciver hsa faster clock than sender.
p2- some data are missed by reciever, if reciever have slower clock than sender.
prevention of asynchronous transmission
stream of data to be transferred, needs to be divided into series of smaller pieces with breaks between transmissions so slower device has time to catch up
protocols of handshaking
SIMPLE
SEMI
FULL
How to know which devices allowed to use a bus
Daisy chaining method- All devices attached to bus are sequentially connected by a wire for a signal BAV
Device can only use bus if it recieves BAV
BAV fed into first device in chain(highest priority)
If device recieves BAV and does notGee want to use bus, it forwards bav to next device in chain
Polling- Bus controller consecutively generates the device addresses of all devices attached to bus
This address is forwarded to all devices
If a device recognizes its address and wants to use the bus, it blocks the usage for other devices by sending a busy signal to them
Independent request- Each device connceted to bus can send request signal to bus controller to use bus
bus contorller ranks all request in accordance with a priority and sends grant signal to selected device.
Selected device blocks usage of bus fpr pther devices by sending busy signal to them
General purpose computer
A general purpose computer is a computer that, given
sufficient time and memory, can solve every problem that,
in principle, is solvable by a computer
What do we need to do if we want to implement a new
instruction EQUIV for CPU-S that tests whether two
numbers are identical?
IDC must be modified so that it can decode the new instruction.
We need to make sure that the ALU of CPU-S contains a device
that can test whether two numbers are identical,
Since the instructions of CPU-S have an opcode of 3 bits, we can
only encode 2^3 = 8 different instructions. CPU-S already supports 8
instructions, and therefore we have to increase the length of the
opcode to 4 bits.
List three types of IO and descrribe them
Programmed I/O is always initiated by an instruction and
leads to a single word of input from the Input Unit to the
CPU or from the CPU to the Output Unit.
- An interrupt is a non-programmed input of one word into
the CPU that leads to a temporary suspension of the
programme executed by the CPU and initiates the start of
a specific new programme, the so-called interrupt
handler. - DMA is normally initiated by programmed I/O and leads to
a direct transfer of blocks of data from the Input Unit to
the Memory Unit or from the Memory Unit to the Output
Unit.
What connection is there between the length of a memory
address and
1. the size of the memory cells in the addressable memory?
2. the number of the memory cells in the addressable
memory?
- None.
- For a memory address of length n in ℕ, the number of
directly addressable memory cells equals 2^n.c
