Operating Systems

Part 2 - Main Memory Lab

By

Gracy Chowdary Mallipeddi

1. Consider a paging system with the page table stored in memory. If a memory reference
takes 200 nanoseconds, how long does a page memory reference take?

When using a paging system in which the page table is loaded into main memory, every memory
access generally needs to make two memory accesses to the page table entry and the real data.
One memory reference requires 200 nanoseconds so the total time of a page memory reference is
200 + 200 = 400 nanoseconds. Hence, every access to memory actually increases twice the time
because of the extra look up in the page table.

Paging System Memory Reference Time

In a basic paging system where the page table is stored in memory, every logical memory
access requires two physical memory accesses:

1. First access → Read the page table entry from memory (to get the frame number)

2. Second access → Access the actual data/instruction at the translated physical address

Calculation

Tpaged=2×Tmemory=2×200 ns=400 nanoseconds

Why Two Accesses?

Step Action Time

Step 1 Look up page table in memory to find 200 ns

frame number
Step 2 Access actual data at the physical address 200 ns

Total 400 ns

Key Insight

This effectively doubles memory access time, which is a significant performance penalty. A
single logical memory reference now costs 400 ns instead of 200 ns — a 100% overhead.

Why This Is a Problem & The Fix

This overhead is why real systems use a Translation Lookaside Buffer (TLB) — a fast
hardware cache for page table entries:

● Without TLB: 2 memory accesses = 400 ns (as calculated above)

● With TLB (hit): TLB lookup (~2–5 ns) + 1 memory access = ~202–205
ns ≈ nearly as fast as a direct access
● With TLB (miss): TLB lookup + 2 memory accesses = still ~404 ns, but misses are rare
 Since TLB hit rates are typically 95–99%, the effective memory access time stays close to
the base 200 ns in practice.

1. If a particular program can access physical addresses from 300040 through 420940
(inclusive), what will be the value stored in its ‘LIMIT’ register?

The LIMIT register contains the size of the logical address space of a
program. Since the program accesses addresses from 300040 through
420940 (inclusive), the total size is calculated as 420940 − 300040 + 1 =
120901. Therefore, the number in the LIMIT register will be 120901, which
will be the summation of the number of valid addressable locations.

Limit Register Value

What is the Limit Register?

In memory protection, a CPU uses two registers to define a process's memory boundaries:

Register Purpose

Base Register Stores the starting physical address of the process

Limit Register Stores the size (length) of the process's memory region

The CPU checks every memory access against these registers to ensure a process doesn't access
memory outside its allocated region.

Given Information
Parameter Value

Starting Physical Address 300040

Ending Physical Address 420940

Calculation

The Limit Register stores the size of the memory region, not the ending address.

Limit= Ending Address − Starting Address + 1

Limit = 420940 − 300040 + 1

Limit = 120901
 The +1 is added because both endpoints are inclusive — the range includes both
address 300040 and address 420940.

How the CPU Uses These Registers

Base Register = 300040
Limit Register = 120901

For every memory access, the CPU verifies:

Base ≤ Accessed Address < Base + Limit

300040 ≤ Address < 300040 + 120901

300040 ≤ Address < 420941

If the condition is violated, the CPU triggers a segmentation fault / protection fault, preventing
unauthorized memory access.

Summary
Register Value

Base Register 300,040

Limit Register 120,901

Addressable Range 300,040 → 420,940 (inclusive)

2. Given a logical address space of 32 pages with 1024 bytes per page, mapped onto a
physical memory of 16 pages (a) how many bits are required for the logical address? (b)
How many bits are required for the physical address?

This system uses a logical address space of 32 pages (1024 bytes/page). Because 1024 bytes is
2102 10 210, the offset needs 10 bits, and 32 pages are 252 525, which needs 5 bits of page
number. Thus, the logical address will take a total of 15 bits. In the case of the physical memory,
the number of pages is 16, and that corresponds to 242 424, thus 4 bits are required to represent
the frame number, and 10 bits to represent the offset. Therefore, 14 bits are needed in the
physical address.

Given:

● Logical address space = 32 pages

● Page size = 1024 bytes
● Physical memory = 16 pages
(a) Logical Address Calculation

Find number of bits for page number

The number of pages = 32

Page bits = log2(32) = 5 bits

Find number of bits for offset

Page size = 1024 bytes

Offset bits = log2(1024) = 10 bits

Total logical address

Logical address = Page number bits + Offset bits

5 + 10 = 15 bits

The logical address requires 15 bits

(b) Physical Address Calculation

Find number of bits for frame number

Physical memory = 16 pages

Frame bits = log2(16) = 4 bits

Offset bits remain the same

Offset bits = 10 bits

Total physical address

Physical address = Frame number bits + Offset bits

4 + 10 = 14 bits
The physical address requires 14 bits

3. The Size of the logical memory address is 32 bits, and the size of the physical address is
30 bits. The page is 4 KB. The size of each page table entry is 32 bits. What is the
maximum number of bits to store protection and other information in each page table
entry?

The size of the page is 4 KB, or 212212212, meaning that the offset takes 12 bits. Since the
physical address has 30 bits, the frame number has 30 -12=18 bits. Each page table entry is 32
bits, and 18 bits are used for the frame number. So, the rest of the 32 minus 18 = 14 bits can be
reserved for protection, status, and other control data.

Given:

● Logical address size = 32 bits

● Physical address size = 30 bits
● Page size = 4 KB = 4096 bytes
● Page table entry (PTE) size = 32 bits

Find offset bits

Page size = 4096 bytes

4096 = 212
Offset bits = 12 bits

Find page number bits (logical address)

Logical address = 32 bits
Page number bits = 32 − 12 = 20 bits

Find frame number bits (physical address)

Physical address = 30 bits
Frame number bits = 30 − 12 = 18 bits
Page Table Entry (PTE) breakdown

Each page table entry = 32 bits

Out of these:

● 18 bits → used for frame number

Remaining bits: 32 − 18 = 14 bits

Maximum number of bits for protection and other information = 14 bits

4. Run the code posted on Blackboard, P2-MemoryCode-Python, and answer the following
questions. You can run it online (e.g., [Link]
[Link]) or on your installed Python IDE (e.g., Thonny or PyCharm)

a. What memory location strategy is this code using?

The program uses the First-Fit memory allocation strategy. This is evident in the manner in
which the code cycles the list of memory blocks and picks the first block that is big enough to
fulfill the memory request. It does not seek the best (or smallest) appropriate block, but merely
takes memory out of the first block it can find that is of the appropriate size. This is typical of the
First-Fit method.

b. What is wrong with this program?

The biggest problem with this program is that it fails to split memory blocks after allocation,
effectively resulting in inefficient memory usage. When a part of the memory is allocated out of
a bigger block, the leftover space is not subdivided into a new free block. Consequently,
although there is adequate spare memory, the program is not able to allocate the memory to
subsequent requests. This can be seen in the output, where after allocating 5 units of a total of 10
units, 5 units again are requested, but this time it is denied, though there is sufficient memory.
This dispensability renders the program impractical and ineffective as compared to actual
memory management systems.

c. Paste a screenshot showing your program/output below.

5. Run the code posted on Blackboard, P2-MemoryCode-Python-enhanced, and answer the

following questions. You can run it online (e.g.,
[Link] or on your installed
Python IDE (e.g., Thonny or PyCharm)

a. What memory location strategy is this code using?

Enhanced program is a First-Fit memory allocation strategy with block splitting. Like the simple
version, it scans memory blocks in sequence and allocates the first block that is large enough to
meet the request. But unlike the simple type, this program enhances memory use by dividing
bigger blocks into two portions when a smaller one is allocated. A portion of it is assigned to the
process and the rest is stored as a new free block. This can be witnessed in the output where
memory is allocated into various blocks upon allocation.

b. How is this different from the program in #5?

The major difference between this enhanced program and the program in Question 5 is that, in
this version, the memory block splitting is applied, and this greatly increases memory utilization.
In the simple program, after a block has been allocated, the rest of the memory is not used,
causing allocation failures when there is enough memory to allocate. The enhanced program, in
contrast, allocates blocks in large block sizes and lets the remaining free memory be re-allocated
to a smaller block in future allocations. This is seen clearly in the output, where, following the
allocation of 5 units out of a total of 12, the rest of the 7 units can still be allocated further.

c. Paste a screenshot showing your program/output below.

Reference
Mutlu, O., Meza, J., & Subramanian, L. (2015). The main memory system: Challenges and
opportunities.

Hicks, K. L., Foster, J. L., & Engle, R. W. (2016). Measuring working memory capacity on the
web with the online working memory lab (the OWL). Journal of Applied Research in Memory
and Cognition, 5(4), 478-489.

Faerber, F., Kemper, A., Larson, P. Å., Levandoski, J., Neumann, T., & Pavlo, A. (2017). Main
memory database systems. Foundations and Trends in Databases, 8(1-2), 1-130.