18EC1202

Computer Organisation and Architecture

CO1 & CO2

09-02-2019 KLEF_SK_CO1 and CO2 1

 Computer Organisation and Architecture
Computer Organisation Computer Architecture
✓ It refers to the operational units and ✓ It refers to those attributes of a
the interconnections between them, system that are visible to the
that achieve architectural specifications programmer and have a direct impact
on logical execution of a program
✓ High level concepts
✓ Low level concepts/Logical units
✓ Transparent from programmer
✓ Realization of the abstract model ✓ Concepts that the programmer deals
with directly
✓ It tells ‘How’ to implement
✓ Defines the system in abstract manner
✓ Physical components like circuits with
✓ ‘What’ does system do/Functionality
adders/subtractors
✓ Types of instructions & addressing
modes
09-02-2019 KLEF_SK_CO1 and CO2 2
 Basic Block Diagram of a Computer

09-02-2019 KLEF_SK_CO1 and CO2 3

 Basic Block Diagram of a Computer
Input Unit Central Processing Unit
Control Unit
✓ Consist of some basic components
that accept data and instructions in ✓ It has a set of registers and circuits
some form and connect them into to generate control signals
an internal form of signals usable by Arithmetic and Logic Unit
system.
✓ It is responsible for executing
Output Unit arithmetic and logical operations
✓ It serve as a medium for displaying Memory Unit
the results.
✓ A place to store data and
instructions temporarily

09-02-2019 KLEF_SK_CO1 and CO2 4

 Representation of information
Decimal 2's Complement 1's complement Signed Magnitude

Unsigned Numbers +7 0111 0111 0111

+6 0110 0110 0110

✓ size of Integer depends on +5 0101 0101 0101

Representation of real numbers

word size +4 0100 0100 0100

+3 0011 0011 0011

✓ working with natural numbers +2 0010 0010 0010

+1 0001 0001 0001

✓ the range for natural number +0 0000 0000 0000

is from 0 to 2n - 1 -0 ----- 1111 1000

-1 1111 1110 1001

Signed Numbers -2 1110 1101 1010

-3 1101 1100 1011

✓ Signed magnitude form -4 1100 1011 1100

✓ 1’s Complement form -5

-6
1011

1010
1010

1001
1101

1110

✓ 2’s Complement form -7 1001 1000 1111

-8 1000 ------ -------

09-02-2019 KLEF_SK_CO1 and CO2 5

Two schemes to represent real number
✓ Fixed-point representation
✓ Floating-point representation
Fixed-point representation
In a fixed point representation a number will be stored in two parts i.e.,
✓ the part before decimal point and the part after decimal point
✓ the position of decimal point is fixed and number of bits before and after
decimal point are also predefined
✓ For a 24 bit number, 16 bits before decimal point and 7 bits after decimal
point with one sign bit, in signed magnitude form, then the range is

( 1(sign) + 16(before decimal point) + 7(after decimal point) )

09-02-2019 KLEF_SK_CO1 and CO2 6
Floating-point representation
✓ Numbers are represented by a mantissa comprising the significant digits and an
exponent part of Radix R

✓ Numbers are often normalized, such that the decimal point is placed to the
right of the first non zero digit.
Example: 5236 is equivalent to .5236 * 104
IEEE standard (IEEE 754) floating point format
✓ IEEE has proposed two standard for representing floating-point number
✓ Single precision
✓ Double precision

09-02-2019 KLEF_SK_CO1 and CO2 7

✓ The IEEE-754 single precision floating point standard uses an 1 Sign bit, 8-bit
exponent (with a bias of 127) and a 23-bit significand.
✓ The IEEE-754 double precision standard uses an 1 Sign bit, 11-bit exponent
(with a bias of 1023) and a 52-bit significand.

Number if Bits Used

IEEE 754
Standard Significand or
Sign Exponent
Mantissa
Single Precision
1 8 23
(Total 32 Bits)
Double Precision
1 11 52
(Total 64 Bits)
09-02-2019 KLEF_SK_CO1 and CO2 8
Example:
Express -3.75 as a floating point number using IEEE single precision.
Steps-Quick Glance
✓ First, let’s normalize according to IEEE rules: 1. Conversion
2. Normalization
✓ 3.75 = -11.112 = -1.111 x 21 3. Bias
✓(XS127 for SP)
✓ The bias is 127, so we add 127 + 1 = 128 (this is our exponent) ✓(XS1023 for DP)

✓ The first 1 in the significand is implied, so we have:

(implied)
✓ Since we have an implied 1 in the significand, this equates to
-(1).1112 x 2 (128 – 127) = -1.1112 x 21 = -11.112 = -3.75.

09-02-2019 KLEF_SK_CO1 and CO2 9

 Arithmetic and Logic Unit representation
✓ The basic arithmetic microoperations are ✓ The additional arithmetic microoperations
are
✓Addition
✓Add with carry
✓Subtraction
✓Subtract with borrow
✓Increment
✓Transfer/Load etc..…
✓Decrement
Summary of Typical Arithmetic Micro-Operations
R3  R1 + R2 Contents of R1 plus R2 transferred to R3
R3  R1 - R2 Contents of R1 minus R2 transferred to R3
R2  R2’ Complement the contents of R2
R2  R2’+ 1 2's complement the contents of R2 (negate)
R3  R1 + R2’+ 1 subtraction
R1  R1 + 1 Increment
R1  R1 - 1 Decrement

09-02-2019 KLEF_SK_CO1 and CO2 10

 Cin
S1
S0 Logic Unit
A0 X0 C0
S1 D0
S0 FA
4 Bit ALU Design –

B0 0 4x1 Y0 C1
1 MUX
Arithmetic Unit

2
3
A1 X1 C1
S1 FA D1
S0
B1 0 4x1 Y1 C2
1 MUX
2
3
A2 X2 C2
S1 FA D2
S0
B2 0 4x1 Y2 C3
1 MUX
2
3
A3 X3 C3
S1 FA D3
S0
B3 0 4x1 Y3 C4
1 MUX
2
3 Cout
0

Block Diagram of an ALU

S1 S0 Cin Y Output Microoperation
0 0 0 B D=A+B Add
Operations

0 0 1 B D=A+B+1 Add with carry

0 1 0 B’ D = A + B’ Subtract with borrow
0 1 1 B’ D = A + B’+ 1 Subtract
1 0 0 0 D=A Transfer A
1 0 1 0 D=A+1 Increment A
1 1 0 1 D=A-1 Decrement A
1 1 1 1 D=A Transfer A

09-02-2019 KLEF_SK_CO1 and CO2 11

 Control Unit – General Block

09-02-2019 KLEF_SK_CO1 and CO2 12

 Control Unit of a Basic Computer

09-02-2019 KLEF_SK_CO1 and CO2 13

09-02-2019 KLEF_SK_CO1 and CO2 14
09-02-2019 KLEF_SK_CO1 and CO2 15
 Introduction to CPU
The operation or task that must perform by CPU are:

✓ Fetch Instruction

✓ Interpret Instruction

✓ Fetch Data

✓ Process data

✓ Write data

09-02-2019 KLEF_SK_CO1 and CO2 16

 Generic Computer CPU Internal
Organization Organization

09-02-2019 KLEF_SK_CO1 and CO2 17

 CPU System Bus

09-02-2019 KLEF_SK_CO1 and CO2 18

 Internal Structure of CPU

09-02-2019 KLEF_SK_CO1 and CO2 19

 Register Organization

The registers in the CPU can be categorized into two groups:

✓ User-visible registers
✓ Control and status registers
User-visible Registers:
✓ General Purpose Registers
✓ Data Registers
✓ Address Registers
✓ Condition Codes

09-02-2019 KLEF_SK_CO1 and CO2 20

Address registers:
✓ Segment pointer
✓ Index registers
✓ Stack pointer
Four registers are essential to instruction execution:
1. Program Counter (PC)
2. Instruction Register (IR)
3. Memory Address Register (MAR)
4. Memory Buffer Register (MBR)
09-02-2019 KLEF_SK_CO1 and CO2 21
Processor Status Word
1. Sign
2. Zero
3. Carry
4. Equal
5. Overflow
6. Interrupt enable/disable
7. Supervisor

09-02-2019 KLEF_SK_CO1 and CO2 22

Instruction interpretation and execution

09-02-2019 KLEF_SK_CO1 and CO2 23

An instruction cycle consists of three phase,
1. Fetch cycle
2. Decode
3. Execution cycle

Operation of a CPU:
1. Fetch the contents of a given memory location and load them into a CPU
register.
2. Store a word of data from a CPU register into a given memory location.
3. Transfer a word of data from one CPU register to another or to the ALU.
4. Perform an arithmetic or logic operation, and store the result in a CPU
register
09-02-2019 KLEF_SK_CO1 and CO2 24
Concept of Program Execution
1. Fetch the contents of the memory location pointed at by the PC. The
contents of this location are interpreted as an instruction to be
executed. Hence, they are stored in the instruction register (IR).
2. Symbolically this can be written as:
IR = [ [PC] ]
3. Increment the contents of the PC by 1.
PC = [PC] + 1
4. Carry out the actions specified by the instruction stored in the IR.

09-02-2019 KLEF_SK_CO1 and CO2 25

 Single bus organization of the data path inside the CPU

09-02-2019 KLEF_SK_CO1 and CO2 26

 Addressing Modes

The most common addressing techniques are:

✓ Immediate
✓ Direct
✓ Indirect
✓ Register
✓ Register Indirect
✓ Displacement
✓ Stack

09-02-2019 KLEF_SK_CO1 and CO2 27

 To explain the addressing modes, the following notation is used:

A - Contents of an address field in the instruction that refers to a

memory

R - Contents of an address field in the instruction that refers to a

register

EA - Actual (effective) address of the location containing the

referenced operand

(X) - Contents of location X

09-02-2019 KLEF_SK_CO1 and CO2 28

Immediate Addressing
✓ The simplest form of addressing is immediate addressing
✓ Operand is part of instruction
✓ Operand = address field Instruction Format
Example: ADD 5 Opcode Operand
✓ Add 5 to contents of accumulator
✓ 5 is operand
✓ No memory reference to fetch data
✓ Fast
✓ Limited range

09-02-2019 KLEF_SK_CO1 and CO2 29

Direct Addressing
Instruction Format
✓ Address field contains address of operand
Opcode Address A
✓ Effective address (EA) = address field (A) Memory
Example: ADD A
✓ Add contents of cell A to accumulator
✓ Look in memory at address A for operand Operand

✓ Single memory reference to access data

✓ No additional calculations to work out effective address
✓ Limited address space

09-02-2019 KLEF_SK_CO1 and CO2 30

Indirect Addressing
✓ Memory cell pointed to by address field contains the address of (pointer to) the
operand
✓ EA = (A) i.e., Look in A, find address (A) and look there for operand
Example: ADD (A)
✓ Add contents of cell pointed to by contents of A to accumulator
✓ Large address space Instruction Format

✓ 2n where n = word length Opcode Address A

Memory
✓ May be nested, multilevel, cascaded
Pointer to operand
Example: EA = (((A)))
Operand
✓ Multiple memory accesses to find operand
✓ Hence slower
09-02-2019 KLEF_SK_CO1 and CO2 31
Register Addressing
✓ Operand is held in register named in address filed
✓ EA = R, Limited number of registers
Instruction
✓ Very small address field needed
Opcode Register Address R
✓ Shorter instructions Registers

✓ Faster instruction fetch

✓ No memory access
Operand
✓ Very fast execution
✓ Very limited address space
✓ Multiple registers helps performance
✓ Requires good assembly programming or compiler writing
✓ Direct addressing
09-02-2019 KLEF_SK_CO1 and CO2 32
 Instruction
Register Indirect Addressing
Opcode Register Address R Memory
✓ Indirect addressing
✓ EA = (R)
Registers
✓ Operand is in memory cell pointed to by
contents of register R
Pointer to Operand Operand
✓ Large address space (2n)
✓ One fewer memory access than indirect
addressing

09-02-2019 KLEF_SK_CO1 and CO2 33

Displacement Addressing
✓ EA = A + (R)
✓ Address field hold two values
A = base value
R = register that holds displacement or vice versa

Instruction

Opcode Register R Address A

Memory
+
Registers

Pointer to Operand Operand

09-02-2019 KLEF_SK_CO1 and CO2 34

Displacement Addressing
✓ Relative Addressing
✓ Base-Register Addressing
✓ Indexing
Relative Addressing
✓ A version of displacement addressing
✓ R = Program counter, PC
✓ EA = A + (PC) i.e. get operand from A cells from current location pointed to by
PC
✓ locality of reference & cache usage

09-02-2019 KLEF_SK_CO1 and CO2 35

Base-Register Addressing
✓ A holds displacement
✓ R holds pointer to base address
✓ R may be explicit or implicit
✓ Indexed Addressing
A = base
R = displacement
EA = A + (R)
✓ Good for accessing arrays
EA = A + (R)
R++
09-02-2019 KLEF_SK_CO1 and CO2 36
Indexing
✓ Auto-indexing
✓ Auto-incrementing
EA = A + (R)
R = (R) + 1
✓ Auto-decrementing
EA = A + (R)
R = (R) – 1
✓ Postindexing (indexing is performed after the indirection(dereferencing))
EA = (A) + (R)
✓ Preindexing (indexing is performed before the indirection(dereferencing))
EA = ( A + (R) )
09-02-2019 KLEF_SK_CO1 and CO2 37
Stack Addressing
✓ Operand is (implicitly) on top of stack
Example:
ADD - this instruction will POP top two items from the stack, add them,
and will then PUSH the result to the top of the stack.

09-02-2019 KLEF_SK_CO1 and CO2 38

 Instruction Set
✓ Operation of a CPU depends on Instruction set
✓ Machine instructions or computer instructions
✓ Opcodes are represented by abbreviations, called mnemonics

4-bits 6-bits 6-bits

Opcode Operand1 Operand2

A simple instruction format

09-02-2019 KLEF_SK_CO1 and CO2 39

 Types of Operations
The instruction set of a CPU
can be categorized as Types of Operands 1. Data Transfer
follows:
1. Addresses 2. Arithmetic
1. Data Processing
2. Numbers 3. Logical
2. Data Storage
3. Characters 4. Conversion
3. Data Movement
4. Logical Data 5. Input Output [ I/O ]
4. Control
6. System Control

7. Transfer Control
09-02-2019 KLEF_SK_CO1 and CO2 40
1. Data Transfer Operations
Move (Transfer) - Transfer word or block from source to destination

Store - Transfer word from processor to memory

Load (fetch) - Transfer word from memory to processor

Exchange - Swap contents of source and destination

Clear (reset) - Transfer word of 0s to destination

Set - Transfer word of 1s to destination

Push - Transfer word from source to top of stack

Pop - Transfer word from top of stack to destination

09-02-2019 KLEF_SK_CO1 and CO2 41
2. Arithmetic Operations
Add - Compute sum of two operands

Subtract - Compute difference of two operands

Multiply - Compute product of two operands

Divide - Compute quotient of two operands

Absolute - Replace operand by its absolute value

Negate - Change sign of operand

Increment - Add 1 to operand

Decrement - Subtract 1 from operand

09-02-2019 KLEF_SK_CO1 and CO2 42
3. Logical Operations
AND - Performs the logical operation AND bitwise
OR - Performs the logical operation OR bitwise
NOT - Performs the logical operation NOT bitwise
Exclusive OR - Performs the specified logical operation Exclusive-OR bitwise
Test - Test specified condition; set flag(s) based on outcome
Compare - Make logical or arithmetic comparison Set flag(s) based on outcome
Set Control Variables - Class of instructions to set controls for protection purposes, interrupt
handling, timer control etc.
Shift - Left (right) shift operand, introducing constant at end
Rotate - Left (right) shift operation, with wraparound end
09-02-2019 KLEF_SK_CO1 and CO2 43
4. Input/output Operations
Input (Read) - Transfer data from specified I/O port or device to destination
(e.g., main memory or processor register)
Output (Write) - Transfer data from specified source to I/O port or device.
Start I/O - Transfer instructions to I/O processor to initiate I/O operation.
Test I/O - Transfer status information from I/O system to specified
destination
5. System Control Operations
✓ System control instructions are those which are used for system setting and it can
be used only in privileged state.
✓ Typically, these instructions are reserved for the use of operating systems.

09-02-2019 KLEF_SK_CO1 and CO2 44

6. Transfer of Control Operations
The most common transfer-of-control operations found in instruction set are:
1. Branch - Branch instruction, also called a jump instruction
2. Skip - The skip implies that one instruction to be skipped
Procedure call - A procedure is a self contained computer program that is
incorporated into a large program. At any point in the program
the procedure may be invoked, or called
Example: Branch
BRP X - Branch to location X if result is positive
BRN X - Branch to location X if result is negative
BRZ X - Branch to location X is result is zero
BRO X - Branch to location X if overflow occurs
09-02-2019 KLEF_SK_CO1 and CO2 45
Example: Skip
ISZ R1 - This instruction will increment the value of the register R1. If the result of
the increment is zero, then it will skip the next instruction
Example: Procedure
Consider a machine language instruction CALL X, which stands for call
procedure at location X. If the register approach is used, CALL X causes the following
actions:
RN PC + IL
PC X
where RN is a register that is always used for this purpose, PC is the program
counter and IL is the instruction length. The called procedure can now save the
contents of RN to be used for the later return.
09-02-2019 KLEF_SK_CO1 and CO2 46
 Instruction Format

Opcode
Zero Address Instruction

Opcode Address
One Address Instruction

Opcode Address1 Address2

Two Address Instruction

Opcode Address1 Address2 Address3

Three Address Instruction

09-02-2019 KLEF_SK_CO1 and CO2 47

Example1:
X = (A + B) * (C + D)
Using three address instructions Using one address instructions
ADD R1 , A , B R 1 <--M [ A ] + M [ B ] LOAD A A C <- M [ A ]
ADD R2 , C , D R 2 <--M [ C ] + M [ D ]
ADD B A C <- A C + M [ B ]
MUL X , R1 , R2 M [ X ] <--R 1 * R 2
STORE T M [ T ] <- A C
Using Two address instructions
LOAD C A C <- M [ C ]
MOV R1 , A R 1 <--M [ A ]
ADD R1 , B R 1 <--R 1 + M [ B ] ADD D A C <- A C + M [ D ]
MOV R2 , C R 2 <--M [ C ] MUL T A C <- A C • M [ T ]
ADD R2 , D R 2 <--R 2 + M [ D ] STORE X M [ X ] <- A C
MUL R1 , R2 R 1 <--R 1 * R 2
MOV X , R1 M [ X ] <--R 1
09-02-2019 KLEF_SK_CO1 and CO2 48
 Example1: Example2:
X = (A + B) * (C + D) A = (B+C)-(D+E)
Using Zero address instructions Using three address Instructions.
ADD T0, B, C
ADD T1, D, E
SUB A, T0, T1

09-02-2019 KLEF_SK_CO1 and CO2 49

 Stack Organization

Block diagram
09-02-2019 of 64- word stack KLEF_SK_CO1 and CO2 50
 Subroutine Calls
Requirements

Set PC to arbitrary address

Return PC to instruction after call sequence

Handle nested subroutine calls

Save and restore caller’s registers

Pass an arbitrary number of arguments

Pass and return structures

Allocate and de-allocate space for local variables

09-02-2019 KLEF_SK_CO1 and CO2 51
09-02-2019 KLEF_SK_CO1 and CO2 52
 Common Micro-Operations

There are 4 types of Micro-Ops:

1. Transfer: transfers data from one register to another
R0 <- R1
2. Arithmetic: performs arithmetic on data in registers
R0 <- R1 + R2
3. Logic/bit manipulation: performs bit (Boolean) operations on data
R0 <- R1 & R2 ; or R0 <- R1 | R2
4. Shift: shift data in registers by one or more bit positions
R0 <- R1 << 3; or R0 <- R2 >> 2

09-02-2019 KLEF_SK_CO1 and CO2 53

 Micro-Ops Transfer - Parallel

✓ Parallel transfer is typically used for

transfers between registers
Example: Transfer all contents of A
into B on one clock pulse
A <- B
✓ Control function:
we can do this by structuring the
RTL expression to indicate the
controlling condition
Example: P: A<- B

09-02-2019 KLEF_SK_CO1 and CO2 54

 Micro-Ops Transfer - Serial

✓ Serial transfer is used to specify that a

collection of bits are to be moved, but
that the transfer is to occur one bit at a
time
✓ Example:
S: A <- B, B <-B

09-02-2019 KLEF_SK_CO1 and CO2 55

 Micro-Ops Transfer - Bus
✓ A bus consists of a set of parallel data lines
✓ To transfer data using a bus:
✓ Connect the output of the source register to the bus;
✓ Connect the input of the target register to the bus;
✓ When the clock pulse arrives, the transfer occurs

09-02-2019 KLEF_SK_CO1 and CO2 56

 Micro-Ops Transfer - Memory
✓ Memory transfers are similar to register transfers, but…
✓ Memory to register transfers are called read operations, while register to
memory transfers are called write operations
✓ RTL expressions for a read operation, assuming the use of an address registers:
AR <- address
DR <- M[AR]
✓ RTL expressions for a write operation, assuming use of a data register:
AR <- address
DR <- value
M[AR] <- DR

09-02-2019 KLEF_SK_CO1 and CO2 57

 Machine Level, Assembly and High Level language

09-02-2019 KLEF_SK_CO1 and CO2 58

 Machine Level, Assembly and High Level language

09-02-2019 KLEF_SK_CO1 and CO2 59

 Machine Level, Assembly and High Level language

09-02-2019 KLEF_SK_CO1 and CO2 60

 Machine Level, Assembly and High Level language
Advantages of High Level Language

09-02-2019 KLEF_SK_CO1 and CO2 61

Advantages Assembly Language:

✓ The symbolic programming of Assembly Language is easier to understand and

saves a lot of time and effort of the programmer.

✓ It is easier to correct errors and modify program instructions

✓ Assembly Language has the same efficiency of execution as the machine level
language. Because this is one-to-one translator between assembly language
program and its corresponding machine language program.

09-02-2019 KLEF_SK_CO1 and CO2 62

 Memory Organization

09-02-2019 KLEF_SK_CO1 and CO2 63

09-02-2019 KLEF_SK_CO1 and CO2 64
Classification of Memory (Computer)
✓ Primary Memory or Internal Memory
✓ Secondary Memory or External Memory
Primary Memory:
RAM: Random Access Memories are volatile in nature. As soon as the computer
is switched off, the contents of memory are also lost.
Types: SRAM, DRAM
ROM: Read only memories are non volatile in nature. The storage is permanent,
but it is read only memory. We can not store new information in ROM.
Types: PROM, EPROM, EEPROM, UVPROM

09-02-2019 KLEF_SK_CO1 and CO2 65

Main Memory Organization Memory Characteristics
✓ 16X4 Means 16 Locations & 4 bits in ✓ Very closely connected to the CPU.
each Location ✓ Contents are quickly and easily
✓ Read – Retrieve data from memory to changed.
CPU registers ✓ Holds the programs and data that the
✓ Write – Store data to memory from CPU processor is actively working with.
registers ✓ Interacts with the processor millions
✓ To transfer data we require data bus of times per second.
✓ To specify or to identify a particular ✓ Nothing permanent is kept in main
memory location we require address memory
bus

09-02-2019 KLEF_SK_CO1 and CO2 66

Main Memory Organization
✓ Main Memory - Communicates directly with CPU
✓ Auxiliary Memory - Provides backup storage
✓ Cache Memory - High speed memory that holds block of data needed by CPU
✓ CM – 100ns; MM – 700ns; AM – 1000 times of MM
✓ Multiprogramming - More than one program processed by CPU concurrently
✓ Memory management system - Supervises the flow of information between
auxiliary memory and main memory
✓ Boot strap loader - Program to start computer software operation
✓ Memory address map - Table that specifies the memory address assigned to
establish addressing of memory

09-02-2019 KLEF_SK_CO1 and CO2 67

 RAM AND ROM Structure

09-02-2019 KLEF_SK_CO1 and CO2 68

09-02-2019 KLEF_SK_CO1 and CO2 69
09-02-2019 KLEF_SK_CO1 and CO2 70
 Memory Management - Five State Process Model
1. New: A program is admitted to execute, but not
yet ready to execute. The operating system will
initialize the process by moving it to the ready
state.
2. Ready: The process is ready to execute and is
waiting for access to the processor.
3. Running: The process is being executed by the
processor. At any given time, only one process is in
running state.
4. Waiting: The process is suspended from execution,
waiting for some system resource, such as I/O.
5. Exit: The process has terminated and will be
destroyed by the operating system.

09-02-2019 KLEF_SK_CO1 and CO2 71

 Memory Management

Uniprogramming system:
✓ Main memory is divided into two parts :
1. Part for the operating system
2. Part for the program currently
being executed.
Multiprogramming system:
✓ Main memory is divided into two parts :
1. Part for the operating system
2. The user part of memory is
subdivided to accommodate
multiple processes.

09-02-2019 KLEF_SK_CO1 and CO2 72

 Partitioning
Splitting of memory into sections to allocate processes including operating system.
There are two scheme for partitioning :
1. Fixed size partitions
2. Variable size partitions
Two simple ways to slightly remove the problem
of memory wastage:
✓ Contiguous: Join the adjacent holes into one
large hole, so that some process can be
accommodated into the hole.
✓ Compaction: From time to time go through
Note: The unused portion of memory in each
memory and move all hole into one free block
partition is termed as hole – Memory wastage
of memory.

09-02-2019 KLEF_SK_CO1 and CO2 73

The effect of dynamic partitioning

09-02-2019 KLEF_SK_CO1 and CO2 74

Paging
✓ Both unequal fixed size and variable size partitions are inefficient in the use of memory
✓ Another scheme for use of memory which is known as paging.
✓ Memory is partitioned into equal fixed size chunks that are relatively small - frames or page
frames
✓ Each process or program is also divided into small fixed chunks of same size – pages
✓ A page of a program could be assigned to available page frame
✓ The operating system maintains a page table for each process.
✓ Within the program, each logical address consists of page number and a relative address
within the page.
✓ A logical address is the location of a word relative to the beginning of the program
✓ A logical address consists of page number and relative address within the page

09-02-2019 KLEF_SK_CO1 and CO2 75

 Translation of Logical Address to Physical Address

09-02-2019 KLEF_SK_CO1 and CO2 76

 Cache Memory
✓ High speed (towards CPU speed)
✓ Small size (power & cost)
✓ Locality of reference – References to memory at any given interval of time tend to
be confined with in a few localized areas in memory.
✓ Hit ratio – Number of hits to the total CPU references to memory.
✓ Mapping – Transformation of data from main memory to cache memory is referred
as mapping process.
✓ Three types of mapping
✓ Associative mapping
✓ Direct mapping
✓ Set-associative mapping
09-02-2019 KLEF_SK_CO1 and CO2 77
Associative Mapping

Addressing relationships between main

and cache memories

09-02-2019 KLEF_SK_CO1 and CO2 78

 Direct mapping cache with block size of 8 words

Direct Mapping of cache organization

09-02-2019 KLEF_SK_CO1 and CO2 79

Set Associative Mapping

09-02-2019 KLEF_SK_CO1 and CO2 80

Cache Replacement Policies

1. Least Recently Used (LRU) replacement policy

2. First In First Out (FIFO) replacement policy

3. Random replacement policy

09-02-2019 KLEF_SK_CO1 and CO2 81

 Virtual Memory
✓ The concept of paging helps us to develop truly effective multiprogramming systems
✓ It is not required to load the whole process to the main memory, because the
execution may be confined to a small section of the program
✓ Instead of loading all the pages of a process, each page of process is brought in only
when it is needed, i.e. on demand. This scheme is known as demand paging
✓ The main memory is referred to as real memory or physical memory.
✓ A programmer or user perceives a much larger memory that is allocated on the disk.
This memory is referred to as virtual memory
✓ To improve the performance some special hardware is added to the system along with
OS - Memory Management Unit (MMU).
✓ Memory Management Unit (MMU) - translates virtual address to physical address

09-02-2019 KLEF_SK_CO1 and CO2 82

 Memory Management Unit (MMU)

09-02-2019 KLEF_SK_CO1 and CO2 83

 Relation between memory space and address in
a virtual memory system
09-02-2019 KLEF_SK_CO1 and CO2 84
 Memory table for Mapping a Virtual address

09-02-2019 KLEF_SK_CO1 and CO2 85

 Address space and memory space split into groups of 1K words

09-02-2019 KLEF_SK_CO1 and CO2 86

Memory Table in a paged system

09-02-2019 KLEF_SK_CO1 and CO2 87

An Associative Memory Page Table

09-02-2019 KLEF_SK_CO1 and CO2 88