Questions.
Internal fragmentation leads to poor utilization of memory that is marked as used by the operating system. Explain how internal fragmentation occurs and how it can be dealt with.
External fragmentation leads to poor utilization of memory that is marked as free by the operating system. Explain how external fragmentation occurs and how it can be dealt with.
Explain how memory virtualization through paging works and what kind of hardware and operating system support it requires.
At the level of individual address bits and entry flags, describe the process of obtaining physical address from virtual address on a processor that only has the Translation Lookaside Buffer. Explain the role of the operating system in this process.
Do not concentrate on the addresses alone. The address translation process also reads and writes some flags in the entries of the Translation Lookaside Buffer.
A thorough answer should also explain the relationship between the widths of the address fields and the sizes of the address translation structures.
At the level of individual address bits and entry flags, describe the process of obtaining physical address from virtual address on a processor that supports multilevel page tables. Explain the role of an operating system in this process.
Do not concentrate on the addresses alone. The address translation process also reads and writes some flags in the entries of the multilevel page tables.
A thorough answer should also explain the relationship between the widths of the address fields and the sizes of the address translation structures.
Explain the relation between the page size and the size of the information describing the mapping of virtual addresses to physical memory and list the advantages and disadvantages associated with using smaller and larger page sizes.
List the advantages and disadvantages of using multilevel page table as a data structure for storing the mapping of virtual to physical memory.
List the advantages and disadvantages of inverse page table as a data structure for storing the mapping of virtual to physical memory.
Explain what a Translation Lookaside Buffer is used for.
Describe the hardware realization of a Translation Lookaside Buffer and explain the principle and advantages of limited associativity.
How does the switching of process context influence the contents of the Translation Lookaside Buffer ? Describe ways to minimize the influence.
Provide at least two criteria that can be used to evaluate the performance of a page replacement algorithm.
Explain the principle of the First In First Out page replacement algorithm and evaluate the feasibility of its implementation on contemporary hardware along with its advantages and disadvantages.
Explain the principle of the Not Recently Used page replacement algorithm and evaluate the feasibility of its implementation on contemporary hardware along with its advantages and disadvantages.
Explain the principle of the Least Recently Used page replacement algorithm and evaluate the feasibility of its implementation on contemporary hardware along with its advantages and disadvantages.
Explain the principle of the Least Frequently Used page replacement algorithm and evaluate the feasibility of its implementation on contemporary hardware along with its advantages and disadvantages.
Explain what is a working set of a process.
Explain what is a locality of reference and how it can be exploited to design or enhance a page replacement algorithm.
Explain what is thrashing and what causes it. Describe what can the operating system do to prevent thrashing and how can the system detect it.
Explain the concept of memory mapped files.
Explain the priciple of the copy-on-write mechanism and provide an example of its application in an operating system.
Exercises.
Consider a system using 32 bit virtual and 32 bit physical addresses. Choose and describe a way the processor in this system should translate virtual addresses to physical. Choose a page size and explain what kind of operation is the page size well suited for.
Design a data structure for mapping virtual addresses to physical and describe in detail all the records used in the structure. When designing the data structure, take into account the choice of the address translation mechanism and explain why is the resulting data structure well suited for the system.
Describe the involvement of the operating system in the process of translating a virtual address to physical (if any), and provide a sketch of the algorithms for handling a page fault and selecting a page for eviction.
Among other things, approaches to address translation differ in the range of exceptions that the operating system must handle. These might include access protection exception, address translation exception, page fault exception. Does your description of the operating system involvement cover all the exceptions applicable in the chosen approach to address translation ?
Besides the addresses, the data structure for address mapping typically contains many other fields that control access protection or help page replacement. Is your description of the data structure detailed enough to include these fields ?
Consider the previous example except the system is using 32 bit virtual and 36 bit physical addresses.
Consider the previous example except the system is using 54 bit virtual and 44 bit physical addresses.