1.Give the methods that are used in page table and TLB for searching the accessing pages. Compare the differences on the searches between these two hardwares and give reasons why TLB will help the search of the pages.
Ans:
Page table: Address generated by CPU is divided into:
(1)Page number(p) – used as an index into a page table which contains base address of each page in physical memory.
(2)Page offset(d) – combined with base address to define the physical memory address that is sent to the memory unit.
TLB: When presented with an item, it is compared with all keys simultaneously. If the page number is found in the TLB, its frame number is immediately available and used to access memory. If the page number is not in the TLB, a memory reference to the page table must be made. TLB should be active.
The differences on the searches between page table and TLB are that page table uses a specify index in the page table then find the address directly while TLB uses the method that compares with all keys(page numbers) simultaneously.
When page numbers can’t find in TLB then go back to page table. Because the page table is in the main memory, in order to avoid wasting time, so we use TLB to help the search of pages.
2. What is the purpose of paging the page table?
Ans：The purpose of paging the page table is to speed up the time of seeking the memory ,by doing so ,all of the data can be separated into group so that the system can search the data in a more efficient way.
3. Consider a 32bit address space with 2K bytes page size, assuming that each entry consists of 4 bytes, how much memory are required for the page table for each process? Explain your reason.
A 32 bit address can address 2^32 bytes in a byte addressable machine. Since the size of a page 4K bytes (2^12), the number of addressable pages is 2^32 / >2^12 = 2^20
With 4 byte entries in the page table we can reference 2^32 pages. Since each page is 2^12 B long, the maximum addressable physical memory size is 2^32 * 2^12 = 2^44 B (assuming no protection bits are used).
4. Compare the main memory organization schemes of contiguous-memory allocation, pure segmentation, and pure paging with respect to the following issues:
a. external fragmentation
b. internal fragmentation
c. ability to share code across processes
Ans:
Contiguous memory allocation scheme suffers from external fragmentation as address spaces are allocated contiguously and holes develop as old processes dies and new processes are initiated. It also does not allow processes to share code, since a process’s virtual memory segment is not broken into non-contiguous fine grained segments.
Pure segmentation also suffers from external fragmentation as a segment of a process is laid out contiguously in physical memory and fragmentation would occur as segments of dead processes are replaced by segments of new processes.
Segmentation, however, enables processes to share code;for instance, two different processes could share a code segment but have distinct data segments.
Pure paging does not suffer from external fragmentation, but instead suffers from internal fragmentation. Processes are allocated in page granularity and if a page is not completely utilized, it results in internal fragmentation and a corresponding wastage of space.Paging also enables processes to share code at the granularity of pages.