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:
Set up a page table to translate logical to physical address.
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 simultaneously. If the page number is immediately available and used to access memory(without going into main memory).if the page number is not in the TLB, a memory reference to the page table must be made. Then TLB updated for next reference.
Some pages and its frame numbers will be saved in TLB, if the page we want is not in TLB, then go back to the page table to find it.
Unlike TLB, use page table only have to go to main memory twice, which means double time to spend, it will cost a lot and expensive. TLB only go to main memory for once, so it is much more useful.
2. What is the purpose of paging the page table?
Ans:
The number of pages may get larger and larger, so we have to use paging to divide some fixed size frames, then divide again to get pages in frame. So it will be easier to search because there paging can keep track of all free frames.
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.
Ans:
2K =2^11. So the number of pages is (2^32)/(2^11)=2^21 pages.
Then each entry is 4 bytes, so we require 4x2^21 = 2^23 bytes = 8 MB.
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:
a. External fragmentation:
Contiguous allocation with fixed size partitions does not suffer from external fragmentation, but contiguous allocation with variable sized partitions does. Pure paging does not suffer from external fragmentation because partitions and pages are fixed in size. Segmentation does suffer from external fragmentation.
b. Internal fragmentation
Segmentation and variable-sized partitions do not suffer from internal fragmentation, a partition is exactly as large as it needs to be. However, contiguous allocation with fixed-size partitions and paging both may suffer from internal fragmentation when partitions and pages are not completely filled.
c. Ability to share code across processes
Contiguous allocation does not provide support for code sharing. In segmentation, as long as the segments of a process do not mix text and data, we can easily share code between processes. We simply adjust the segment tables of each process to point to the same segment of code in memory. For security reasons, however, it would probably be desirable to have some method of preventing processes from modifying code, since doing so would allow one process to change the code executed by another. In pure paging, code can be shared across processes simply by sharing page frames. To do this, adjust the page tables of the two processes so that their different logical pages map to the same physical page frame. However, we do need to make certain that no page frame contains any data, which should not be shared. We could accomplish this by, for example, padding the last page of the text segment of the process with no-op machine language instructions.