Tools

IEEE Convertion

Convert single-precision floating point number into decimal number.

Find Sign Bit (S.), Exponent bits (E.)

e = Exponent bits - 127

Find Fraction bits

Find Mantissa

Final decimal = $(-1)^S \times (1 + m) \times 2^e$

Convert decimal numbers into single-precision floating point number.

Find Sign Bit (S.), Exponent bits (E.)

Exp = e + 127

Find Mantissa

With S (1 bit), Exp (8 bit) and M (23 bit), the floating point number is constructed.

To Hexadecimal sequence, break into 4 x 8 bits and translate them.

Paging

Translate logical address to physical address:

First convert into binary.
- first 10 bits is entry of page directory
- next 10 bits is entry of page table
- last 12 bits is the offset
Find Entry in the page directory then use the content to find S.A. of page table
Find Entry in the page table then use the content to find S.A. of target page
Physical address = S.A. of target page + offset

Addressing Mode

Length of General Registers:

32 bits: EAX, EBX, ECX,EDX
16 bits: AX, BX, CX, DX, BP, DI, SI
8 bits: AH, AL, BH, BL, CH, CL, DH, DL

1 byte = 00H, 2 byte = 0000H, 4 byte = 00000000H

Common Addressing Modes

Register Mode
- MOV AX,BX
Immediate Mode
- MOV AX,1000
Direct Addressing Mode
- MOV AX,[1B67H]
Register Indirect Addressing Mode
- MOV AX,[BX]
Register Relative Mode
- MOV AX,[BX-3H]
base-plus-index mode
- MOV AX,[BX+SI]
- MOV AX,SI[BX]
base relative-plus-index mode
- MOV AX,[BX+SI-2H]
- MOV AX,SI[BX-2H]

Note: Always read 2 bytes of Data for 16 bit registers.

Cache

Number of Blocks in the memory system are competing for the slots.

Block refers to the memory system
then you move it inside the slot
so the slot contains a block.

$\text{No. of Block in Memory System} = 2^\text{setbit+offsetbit}$

$\text{No. of Block in Cache System} = \text{No. of Slot} = \text{No. of Ways} \times 2^\text{setbit}$

$\text{Size of Slot} = \text{Size of Block} = 2^\text{offsetbit}$

Maximum number of data bytes that can be stored in the cache:

$\text{Cache Size} = \text{No. of Slot} \times \text{Size of Slot}$

Number of bits in an address (Need to notice Memory is what addressable):

$\text{Number of bits in an address} = log_2{(\text{Memory Size})}$

Number of set bits in an address:

$\text{Set bit} = log_2(\frac{\text{No. of Slots}}{\text{No. of Ways}})$

Number of offset bits in an address:

$\text{Offset bit} = log_2(\text{Size of Slot})$

Number of tag bits in an address:

$\text{Tag bit} = \text{Total bits} - \text{Offset bit} - \text{Set bit}$

Hit Ratio

$HR = \frac{\text{No of Hit}}{\text{No of Access}}$

The unit is %.

Effective Access Time

$EAT = \frac{\text{Access time}}{ICtr}$

$EAT = \frac{\text{(No. of hits)}\times T_h + \text{(No. of misses)}\times T_m}{\text{Total No. of Access}}$

The unit is cycles.

Note: $T_h < T_m$

Replacement Policy

LIFO – Last-in-first-out
FIFO – First-in-first-out
LRU – least recently used
LFU – least frequently used

Interrupt

Real Mode Interrupt

Need to Check IVT

A type n INT means its interrupt vector No. is n.

The starting address of its interrupt service procedure (ISR) is the nth vector in the interrupt vector table(IVT).

IVN determines the vector number of IVT (starts from 0)
Starting Address of ISR = Segment X 10 + Offset

Protected Mode Interrupt

Need to Check interrupt descriptor table (IDT)

IVN determines the entry of IDT
First Row and Last Row are Offset, Third Row is Segment Selector
Segment Selector (13 bits Selector , 1 bit TI, 2 bit RPL)
Selector determines the Entry of GDT/LDT, TI bit determines GDT (TI = 0) or LDT (GDT = 1)
Depends on System we use (Mostly 80286)
Find Base and Limit
Starting Address of ISR of device = Base + Offset
Ending Address of ISR of device = Base + Limit
Size of ISR = Ending Address - Starting Address + 1

+1 because there we count from byte 0.

Process

A process switch can only occur when there is a mode switch.

3 States of Process

Running
Block
Ready

Systemcall - Enter Block State after executed for @time

High/Low Priority Process might have different time units

Uniprocessor scheduling

Turnaround Time (TAT)

The time interval between the submission of a process and its completion (= execution time + waiting time)
Turnaround Time = finish - arrival

Normalized turnaround time (NTT)

NTT = TurnaroundTime/Service Time
Higher TurnaroundTime or NTT = Lower Performance

Response time

Response ratio = (Waiting Time + Service Time)/Service Time

Deadlock

Allocation matix A - Denote the Resource you already allocated to each process
Claim matrix C - Denote the Resource still need for each process
- equal to $[R] \rightarrow (P)$ from the graph
Request Matrix Q = Matrix C-A
- equal to $(P) \rightarrow [R]$ from the graph
Available vector V - The resource you have after serving all those process at once
- equal to $R - \sum A_{row}$
Resource vector R - Denote the Resource you have
- equal to $V + \sum A_{row}$ or Points on $R_s$ from the graph

Real-time scheduling

Ideal (Perfect) Scheduling

$\frac{C_{1}}{T_{1}}+\frac{C_{2}}{T_{2}}+\cdots+\frac{C_{n}}{T_{n}} \leq 1$

Where $C$ is execution time, $T$ is the period. $n$ is the number of processes.

Rate Monotonic Scheduling (RMS)

Though it is possible to achieve greater overall processor utilization and accommodate more periodic tasks with earliest deadline scheduling (EDS), RMS has been widely adopted in industrial applications.

$\frac{C_{1}}{T_{1}}+\frac{C_{2}}{T_{2}}+\cdots+\frac{C_{n}}{T_{n}} \leq n\left(2^{1 / n}-1\right)$

Where $C$ is execution time, $T$ is the period. $n$ is the number of processes.

Stability is easier to achieve with RMS.

B-Tree (Balanced Tree)

Minimum degree (d)

Used to determine number of keys in a node:
- maximum keys = $2d-1$

Insert a key

Search the tree for the key. If the key is not in the tree, then reach a leaf node.

If node has < 2d-1 keys then insert the key
If node is full, then promote the median key to next higher level, split the nodes.

Average No. of access

$d^{n+1} = N$

where N = records, n = levels, d = entries per index table

To find Average No. of access for a table of d entries:

$\sum_1^{d-1}fP(f) = \frac{d}{2}$

Therefore

Average No. of access = Number of levels(index and record) $\times \frac{d}{2}$

$= (n+1)\times \frac{d}{2}$