The logical address space in a computer system consists of 128 segments. Each segment can have up to 32 pages of 4K words each. Physical memory consists of 4K blocks of 4K words each. Formulate the logical and physical address formats.

This is a segmented-paged system. The logical address is divided into a segment number, a page number and a word number. The physical address is divided into a block number and a word number.

Logical address format

There are 128 segments, so the segment field needs $\log_2 128 = 7$ bits. Each segment has up to 32 pages, so the page field needs $\log_2 32 = 5$ bits. Each page has 4K words, so the word field needs $\log_2 4096 = 12$ bits. The logical address is

$$7 + 5 + 12 = 24 \text{ bits}$$

Physical address format

Physical memory has 4K blocks, so the block field needs $\log_2 4096 = 12$ bits. Each block has 4K words, so the word field needs 12 bits. The physical address is

$$12 + 12 = 24 \text{ bits}$$

Check of sizes

The logical space is $128 \times 32 \times 4096 = 2^{24}$ words. The physical memory is $4096 \times 4096 = 2^{24}$ words. Both are 16M words.

The two sizes can also be seen as counts. The logical space has $128 \times 32 = 4096$ pages in total, and the physical memory has 4096 blocks. So each logical page can in the best case have its own block, but a program uses far fewer pages than this at one time.

How the mapping works

The page size and the block size are both 4K words, so the 12 word bits are copied unchanged from the logical address to the physical address. Only the segment and page numbers must be translated into a block number.

The segment number selects an entry in the segment table. That entry gives the address of the page table of that segment. Each segment has its own page table with 32 entries. The page number selects an entry in this page table, and the entry holds a 12-bit block number. This block number is joined with the 12-bit word to give the physical address.

 Logical: [ Segment 7 ][ Page 5 ][ Word 12 ]
              |            |          |
        Segment table   Page table    |
              |------->  (32 entries) |
                          |           |
 Physical:           [ Block 12 ][ Word 12 ]

The mapping needs two table reads, one in the segment table and one in the page table, so it is slower than plain paging. A TLB is used to keep the recent translations and avoid these reads. Protection bits in the segment table also allow each segment to be marked read only or executable.

For example, if the entry of page 3 in the page table of segment 5 holds block 100, then the logical address (segment 5, page 3, word 20) maps to physical block 100 with word 20.