Differences or similarities between Segmented paging and Paged segmentation?

Question

I was studying combined paging/segmentation systems and in my book there were two approaches to this :

1.paged segmentation
2.segmented paging

I could not make out the difference between the two. I think in paged segmentation the segment is divided into pages and in segmented paging the pages are divided into segments, though I don't know if I am right or wrong. Meanwhile on the internet the combined paging/segmentation is described using one scheme only. I can't figure out why in my coursebook there are two schemes for this. Any help would be deeply appreciated.

Answer 1

So,after vigorously searching on net for the difference or similarity between these two terms,I have come up on a final answer.First of all I would write down the similarities:

• They both (segmented paging and paged segmentation) are a type of paging/segmentation combined systems (Paging and Segmentation can be combined by dividing each segment into pages).
• In both the system the segments are divided into pages.

Now to describe the differences I will have to define and describe each term separately:

• Segmented paging- Segments are divided into pages.Implementation requires STR(segment table register) and PMT(page map table).In this scheme, each virtual address consists of a segment number, page number within that segment and an offset within that page.The segment number indexes into segment table which yields the base address of the page table for that segment.The page number indexes into the page table,each of which entry is a page frame.Adding the PFN(page frame number) and the offset results in the physical address.Hence addressing can be described by the following function :

va = (s,p,w) where, va is the virtual address, |s| determines number of segments (size of ST), |p| determines number of pages per segment (size of PT), |w| determines page size.

address_map(s, p, w)
{
pa = *(*(STR+s)+p)+w;
return pa;
}

The diagram is here:

• Paged Segmentation- Sometimes segment table or page table may too large to keep in physical memory(they can even reach MBs).Therefore,the segment table is divided into pages too and thus a page table of ST pages is created. The segment number is broken into page no.(s1) and page offset(s2) of page table of ST pages.So,the virtual address can be described as :

va = (s1,s2,p,w)

address_map
(s1, s2, p, w)
{
pa = *(*(*(STR+s1)+s2)+p)+w;
return pa;
}

The diagram description is here:

Answer 2

Best characteristics of paging

The fact is, paging has the following goodies:

1. Fast Allocation (At least faster than segmentation)
2. No External Fragmentation(The last page in this method suffers from Internal Fragmentation)

Best characteristics of segmentation

But there is also a great behavior seen from segmentation:

1. Sharing
2. Protection

The given terms, can be combined and create the following terms:

• Segmented Paging: The virtual address space is divided into segments. The physical address space is divided into page frames.
• Paged Segmentation: The main Segmentation Technique which uses the process segment table sometimes goes out of bound! Meaning that the size gets too large and the main memory does not have enough space to keep the segment table. Therefore the segment table and the segment number is divided into pages.

Requirements for the Segmented Paging

There are multiple steps need to be taken to achieve the Segmented Paging:

1. Each segment table entry represents a page table base address.
2. STR(Segment Table Register) and PMT(Page Map Table) are filled with desired values.
3. Each virtual address consists of a Segment Number, Page Number and the Offset within that page.
4. The segment number indexes into the segment table which gives us the the base address of the page table for that segment.
5. The page number indexes into the page table.
6. Each page table entry is a page frame.
7. Final result which is a Physical Address is found by adding the page frame number and the offset.

Requirements for the Paged segmentation

The following steps take place in this scheme:

1. Each segment entry is divided into multiple segments.
2. For each segment table entry, which represents a gathering of the pages, a page table is created.

Answer 3

Segmentation leads to slower page translations and swapping

For those reasons, segmentation was largely dropped on x86-64.

The main difference between them is that:

• paging splits memory into fixed sized chunks
• segmentation allows different widths for each chunk

While it might appear smarter to have configurable segment widths, as you increase memory size for a process, fragmentation is inevitable, e.g.:

|   | process 1 |       | process 2 |                        |
     -----------         -----------
0                                                            max

will eventually become as process 1 grows:

|   | process 1        || process 2 |                        |
     ------------------  -------------
0                                                            max

until a split is inevitable:

|   | process 1 part 1 || process 2 |   | process 1 part 2 | |
     ------------------  -----------     ------------------
0                                                            max

At this point:

• the only way to translate pages is to do binary searches over all pages of process 1, which takes an unacceptable log(n)
• a swap out of process 1 part 1 could be huge since that segment could be huge

With fixed sized pages however:

• every 32-bit translation does only 2 memory reads: directory and page table walk
• every swap is an acceptable 4KiB

Fixed sized chunks of memory are simply more manageable, and have dominated current OS design.

See also: How does x86 paging work?