Computer Systems Principle - CheatSheet
Tools
Hexadecimal to Decimal converter
IEEE-754 Floating Point Converter
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 =
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.
Maximum number of data bytes that can be stored in the cache:
Number of bits in an address (Need to notice Memory is what addressable):
Number of set bits in an address:
Number of offset bits in an address:
Number of tag bits in an address:
Hit Ratio
The unit is %.
Effective Access Time
or
The unit is cycles.
Note:
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 from the graph
- Request Matrix Q = Matrix C-A
- equal to from the graph
- Available vector V - The resource you have after serving all those process at once
- equal to
- Resource vector R - Denote the Resource you have
- equal to or Points on from the graph
Real-time scheduling
Ideal (Perfect) Scheduling
Where is execution time, is the period. 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.
Where is execution time, is the period. 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 =
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
where N = records, n = levels, d = entries per index table
To find Average No. of access for a table of d entries:
Therefore
Average No. of access = Number of levels(index and record)