Import Settings: 
Base Settings: Brownstone Default
Highest Answer Letter: D
Multiple Keywords in Same Paragraph: No

Chapter: Chapter 8

Multiple Choice

1.  Absolute code can be generated for ____.
A)  compile-time binding
B)  load-time binding
C)  execution-time binding
D)  interrupt binding

Ans:  A
Feedback: 8.1.2
Difficulty:  Easy

2.  _____ is the method of binding instructions and data to memory performed by most general-purpose operating systems.
A)  Interrupt binding
B)  Compile time binding
C)  Execution time binding
D)  Load-time binding

Ans:  C
Feedback: 8.1.2
Difficulty:  Medium

3.  An address generated by a CPU is referred to as a ____.
A)  physical address
B)  logical address
C)  post relocation register address
D) Memory-Management Unit (MMU) generated address

Ans:  B
Feedback: 8.1.3
Difficulty:  Easy

4.  Suppose a program is operating with execution-time binding and the physical address generated is 300. The relocation register is set to 100. What is the corresponding logical address?
A)  199
B)  201
C)  200
D)  300

Ans:  C
Feedback: 8.1.3
Difficulty: Easy

5. The mapping of a logical address to a physical address is done in hardware by the ________.
A) memory-management-unit (MMU)
B) memory address register
C) relocation register
D) dynamic loading register

Ans: A
Feedback: 8.1.3
Difficulty:  Medium

6.  In a dynamically linked library, ____.
A)  loading is postponed until execution time
B)  system language libraries are treated like any other object module
C)  more disk space is used than in a statically linked library
D)  a stub is included in the image for each library-routine reference

Ans:  D
Feedback: 8.1.5
Difficulty:  Medium

7.  The _____ binding scheme facilitates swapping.
A)  interrupt time
B)  load time
C)  assembly time
D)  execution time

Ans:  D
Feedback: 8.2
Difficulty:  Medium

8.  The roll out, roll in variant of swapping is used ____.
A)  when a backing store is not necessary
B)  for the round-robin scheduling algorithm
C)  for priority-based scheduling algorithms 
D)  when the load on the system has temporarily been reduced

Ans:  C
Feedback: 8.2
Difficulty:  Medium

9.  _____ is the dynamic storage-allocation algorithm which results in the smallest leftover hole in memory.
A)  First fit
B)  Best fit
C)  Worst fit
D)  None of the above

Ans:  B
Feedback: 8.3.2
Difficulty:  Easy

10.  _____ is the dynamic storage-allocation algorithm which results in the largest leftover hole in memory.
A)  First fit
B)  Best fit
C)  Worst fit
D)  None of the above

Ans:  C
Feedback: 8.3.2
Difficulty: Easy

11.  Which of the following is true of compaction?
A)  It can be done at assembly, load, or execution time.
B)  It is used to solve the problem of internal fragmentation.
C)  It cannot shuffle memory contents.
D)  It is possible only if relocation is dynamic and done at execution time.

Ans:  D
Feedback: 8.3.3
Difficulty:  Medium

12.  A(n) ____ page table has one page entry for each real page (or frame) of memory.
A)  inverted
B)  clustered
C)  forward-mapped
D)  virtual

Ans:  A
Feedback: 8.6.3
Difficulty: Easy

13. Consider a logical address with a page size of 8 KB. How many bits must be used to represent the page offset in the logical address?
A) 10
B) 8
C) 13
D) 12

Ans: C
Feedback: 8.5
Difficulty: Easy

14. Consider a logical address with 18 bits used to represent an entry in a conventional page table. How many entries are in the conventional page table?
A) 262144
B) 1024
C) 1048576
D) 18

Ans: A
Feedback: 8.5
Difficulty: Easy

15.  Assume a system has a TLB hit ratio of 90%. It requires 15 nanoseconds to access the TLB, and 85 nanoseconds to access main memory. What is the effective memory access time in nanoseconds for this system?
A) 108.5 
B) 100 
C) 22 
D) 176.5

Ans: A
Feedback: 8.5.2
Difficulty: Medium

16. Given the logical address 0xAEF9 (in hexadecimal) with a page size of 256 bytes, what is the page number?
A) 0xAE
B) 0xF9
C) 0xA
D) 0x00F9

Ans: A
Feedback: 8.5
Difficulty: Medium

17. Given the logical address 0xAEF9 (in hexadecimal) with a page size of 256 bytes, what is the page offset?
A) 0xAE
B) 0xF9
C) 0xA
D) 0xF900

Ans: B
Feedback: 8.5
Difficulty: Medium

18. Consider a 32-bit address for a two-level paging system with an 8 KB page size. The outer page table has 1024 entries. How many bits are used to represent the second-level page table?
A) 10
B) 8
C) 12
D) 9

Ans: D
Feedback: 8.6.1
Difficulty: Medium

19. With segmentation, a logical address consists of _____.
A) segment number and offset
B) segment name and offset
C) segment number and page number
D) segment table and segment number

Ans: A
Feedback: 8.4.1
Difficulty: Easy

20. Which of the following data structures is appropriate for placing into its own segment?
A) heap
B) kernel code and data
C) user code and data
D) all of the above

Ans: D
Feedback: 8.4
Difficulty: Easy

21. Assume the value of the base and limit registers are 1200 and 350 respectively. Which of the following addresses is legal?
A) 355
B) 1200
C) 1551
D) all of the above

Ans: B
Feedback: 8.1.1
Difficulty: Easy

22. A(n) ______ matches the process with each entry in the TLB.
A) address-space identifier
B) process id
C) stack
D) page number

Ans: A
Feedback: 8.5.2
Difficulty: Medium

23. Which of the following statements are true with respect to hashed page tables?
A) They only work for sparse address spaces.
B) The virtual address is used to hash into the hash table.
C) A common approach for handling address spaces larger than 32 bits.
D) Hash table collisions do not occur because of the importance of paging.

Ans: C
Feedback: 8.6.2
Difficulty: Medium

24. Which of the following statements regarding the ARM architecture are false?
A) There are essentially four different page ranging from 4-KB to 16-MB in size.
B) There are two different levels of TLB.
C) One or two level paging may be used.
D) The micro TLB must be flushed at each context switch.

Ans: D
Feedback: 8.8
Difficulty: Difficult

25. Which of the following is not a reason explaining why mobile devices generally do not support swapping?
A) Limited space constraints of flash memory.
B) Small size of mobile applications do not require use of swap space. 
C) Limited number of writes of flash memory.
D) Poor throughput between main memory and flash memory.

Ans: B
Feedback: 8.2.2
Difficulty: Difficult

Essay

26.  What is the advantage of using dynamic loading?

Ans:  With dynamic loading a program does not have to be stored, in its entirety, in main memory. This allows the system to obtain better memory-space utilization. This also allows unused routines to stay out of main memory so that memory can be used more effectively. For example, code used to handle an obscure error would not always use up main memory.
Feedback: 8.1.4
Difficulty: Medium

27.  What is the context switch time, associated with swapping, if a disk drive with a transfer rate of 2 MB/s is used to swap out part of a program that is 200 KB in size? Assume that no seeks are necessary and that the average latency is 15 ms. The time should reflect only the amount of time necessary to swap out the process.

Ans:  200KB / 2048 KB per second + 15 ms = 113 ms
Feedback: 8.2
Difficulty: Medium

28.  When does external fragmentation occur?

Ans:  As processes are loaded and removed from memory, the free memory space is broken into little pieces.  External fragmentation exists when there is enough total memory space to satisfy a request, but the available spaces are not contiguous; storage is fragmented into a large number of small holes.  Both the first-fit and best-fit strategies for memory allocation suffer from external fragmentation.
Feedback: 8.3.3
Difficulty:  Medium

29. Distinguish between internal and external fragmentation.

Ans: Fragmentation occurs when memory is allocated and returned to the system. As this occurs, free memory is broken up into small chunks, often too small to be useful. External fragmentation occurs when there is sufficient total free memory to satisfy a memory request, yet the memory is not contiguous, so it cannot be assigned. Some contiguous allocation schemes may assign a process more memory than it actually requested (i.e. they may assign memory in fixed-block sizes).  Internal fragmentation occurs when a process is assigned more memory than it has requested and the wasted memory fragment is internal to a process.
Feedback: 8.3.3
Difficulty: Medium

30.  Explain the basic method for implementing paging.

Ans:  Physical memory is broken up into fixed-sized blocks called frames while logical memory is broken up into equal-sized blocks called pages. Whenever the CPU generates a logical address, the page number and offset into that page is used, in conjunction with a page table, to map the request to a location in physical memory.
Feedback: 8.5
Difficulty: Medium

31.  Describe how a transaction look-aside buffer (TLB) assists in the translation of a logical address to a physical address.

Ans:  Typically, large page tables are stored in main memory, and a page-table base register points are saved to the page table.  Therefore, two memory accesses are needed to access a byte (one for the page-table entry, one for the byte), causing memory access to be slowed by a factor of 2.  The standard solution to this problem is to use a TLB, a special, small fast-lookup hardware cache.  The TLB is associative, high speed memory.  Each entry consists of a key and value.  An item is compared with all keys simultaneously, and if the item is found, the corresponding value is returned.   
Feedback: 8.5.2
Difficulty: Medium

32.  How are illegal page addresses recognized and trapped by the operating system?

Ans:  Illegal addresses are trapped by the use of a valid-invalid bit, which is generally attached to each entry in the page table. When this bit is set to "valid," the associated page is in the process's logical address space and is thus a legal (or valid) page. When the bit is set to "invalid," the page is not in the process's logical address space. The operating system sets this bit for each page to allow or disallow access to the page. 
Feedback: 8.5.3
Difficulty: Medium

33.  Describe the elements of a hashed page table.

Ans:  A hashed page table contains hash values which correspond to a virtual page number. Each entry in the hash table contains a linked list of elements that hash to the same location (to handle collisions). Each element consists of three fields:  (1) the virtual page number, (2) the value of the mapped page frame, and (3) a pointer to the next element in the linked list.
Feedback: 8.6.2
Difficulty: Difficult

34.  Briefly describe the segmentation memory management scheme. How does it differ from the paging memory management scheme in terms of the user's view of memory? 

Ans:  Segmentation views a logical address as a collection of segments. Each segment has a name and length. The addresses specify both the segment name and the offset within the segment. The user therefore specifies each address by two quantities: a segment name and an offset. In contrast, in a paging scheme, the user specifies a single address, which is partitioned by the hardware into a page number and an offset, all invisible to the programmer.  
Feedback: 8.4
Difficulty: Medium

35.  Describe the partitions in a logical-address space of a process in the IA-32 architecture.

Ans:  The logical-address space is divided into two partitions. The first partition consists of up to 8 K segments that are private to that process. The second partition consists of up to 8 K segments that are shared among all the processes. Information about the first partition is kept in the local descriptor table (LDT); information about the second partition is kept in the global descriptor table (GDT).
Feedback: 8.7.1
Difficulty: Difficult

36.  How is a limit register used for protecting main memory?

Ans:  When the CPU is executing a process, it generates a logical memory address that is added to a relocation register in order to arrive at the physical memory address actually used by main memory. A limit register holds the maximum logical address that the CPU should be able to access. If any logical address is greater than or equal to the value in the limit register, then the logical address is a dangerous address and an error results.
Feedback: 8.1.1
Difficulty: Medium

37. Using Figure 8.14, describe how a logical address is translated to a physical address.

Ans: A logical address is generated by the CPU. This logical address consists of a page number and offset. The TLB is first checked to see if the page number is present. If so, a TLB hit, the corresponding page frame is extracted from the TLB, thus producing the physical address. In the case of a TLB miss, the page table must be searched according to page number for the corresponding page frame.
Feedback: 8.4
Difficulty: Medium

38. Explain why mobile operating systems generally do not support paging.

Ans: Mobile operating systems typically do not support swapping because file systems are typically employed using flash memory instead of magnetic hard disks. Flash memory is typically limited in size as well as having poor throughput between flash and main memory. Additionally, flash memory can only tolerate a limited number of writes before it becomes less reliable.
Feedback:
Difficulty: Medium

39. Using Figure 8.26, describe how address translation is performed on ARM architectures.

Ans: ARM supports four different page sizes: 4-KB and 16-KB page use two-level paging, the larger  1-MB and 16-MB page sizes use single-level paging. The ARM architecture uses two levels of TLBs - at one level is the micro TLB which is in fact separate TLBs for data and instructions. At the inner level is a single main TLB. Address translation begins wit first searching the micro TLB, and in case of a TLB miss, the main TLB is then checked. If the reference is not in the main TLB, the page table must then be consulted.
Feedback: 8.8
Difficulty: Medium

True/False

40.   A relocation register is used to check for invalid memory addresses generated by a CPU.

Ans:  False
Feedback: 8.1.2
Difficulty: Medium

41.  Reentrant code cannot be shared.

Ans:  False
Feedback: 8.5.4 
Difficulty: Easy

42. There is a 1:1 correspondence between the number of entries in the TLB and the number of entries in the page table.

Ans:  False
Feedback: 8.5.2
Difficulty: Easy

43.  Hierarchical page tables are appropriate for 64-bit architectures.

Ans:  False 
Feedback: 8.6.1
Difficulty: Medium

43.  The ARM architecture uses both single-level and two-level paging. 

Ans:  True
Feedback: 8.8
Difficulty: Medium

44. Fragmentation does not occur in a paging system.

Ans: False
Feedback: 8.5
Difficult: Medium

45. Hashed page tables are particularly useful for processes with sparse address spaces.

Ans: True
Feedback: 8.6.2
Difficulty: Easy

46. Inverted page tables require each process to have its own page table.

Ans: False
Feedback: 8.6.3
Difficulty: Medium

47. Without a mechanism such as an address-space identifier, the TLB must be flushed during a context switch.

Ans: True
Feedback: 8.5.2
Difficulty: Medium

48. A 32-bit logical address with 8 KB page size will have 1,000,000 entries in a conventional page table.

Ans: False
Feedback: 8.5
Difficulty: Medium

49. Hashed page tables are commonly used when handling addresses larger than 32 bits.

Ans: True
Feedback: 8.6.2
Difficulty: Easy

50. The x86-64 bit architecture only uses 48 of the 64 possible bits for representing virtual address space.

Ans: True
Feedback: 8.7.2
Difficulty: Medium

51. Mobile operating systems typically support swapping.

Ans: False
Feedback: 8.2.2
Difficulty: Easy