Guest User


a guest
Nov 19th, 2019
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. Most virtual memory systems use a technique called paging, which we will
  2. now describe. On any computer, programs reference a set of memory addresses.
  3. When a program executes an instruction like
  4. MOV REG,1000
  5. it does so to copy the contents of memory address 1000 to REG (or vice versa, depending on the computer). Addresses can be generated using indexing, base registers, segment registers, and other ways.
  6. CPU
  7. package
  8. CPU
  9. The CPU sends virtual
  10. addresses to the MMU
  11. The MMU sends physical
  12. addresses to the memory
  13. Memory
  14. management
  15. unit
  16. Memory Disk
  17. controller
  18. Bus
  19. Figure 3-8. The position and function of the MMU. Here the MMU is shown as
  20. being a part of the CPU chip because it commonly is nowadays. However, logically it could be a separate chip and was years ago.
  21. These program-generated addresses are called virtual addresses and form the
  22. virtual address space. On computers without virtual memory, the virtual address
  24. is put directly onto the memory bus and causes the physical memory word with the
  25. same address to be read or written. When virtual memory is used, the virtual addresses do not go directly to the memory bus. Instead, they go to an MMU (Memory Management Unit) that maps the virtual addresses onto the physical memory
  26. addresses, as illustrated in Fig. 3-8.
  27. A very simple example of how this mapping works is shown in Fig. 3-9. In
  28. this example, we have a computer that generates 16-bit addresses, from 0 up to
  29. 64K − 1. These are the virtual addresses. This computer, howev er, has only 32 KB
  30. of physical memory. So although 64-KB programs can be written, they cannot be
  31. loaded into memory in their entirety and run. A complete copy of a program’s core
  32. image, up to 64 KB, must be present on the disk, however, so that pieces can be
  33. brought in as needed.
  34. The virtual address space consists of fixed-size units called pages. The corresponding units in the physical memory are called page frames. The pages and page
  35. frames are generally the same size. In this example they are 4 KB, but page sizes
  36. from 512 bytes to a gigabyte have been used in real systems. With 64 KB of virtual
  37. address space and 32 KB of physical memory, we get 16 virtual pages and 8 page
  38. frames. Transfers between RAM and disk are always in whole pages. Many processors support multiple page sizes that can be mixed and matched as the operating
  39. system sees fit. For instance, the x86-64 architecture supports 4-KB, 2-MB, and
  40. 1-GB pages, so we could use 4-KB pages for user applications and a single 1-GB
  41. page for the kernel. We will see later why it is sometimes better to use a single
  42. large page, rather than a large number of small ones.
  43. The notation in Fig. 3-9 is as follows. The range marked 0K–4K means that
  44. the virtual or physical addresses in that page are 0 to 4095. The range 4K–8K
  45. refers to addresses 4096 to 8191, and so on. Each page contains exactly 4096 addresses starting at a multiple of 4096 and ending one shy of a multiple of 4096.
  46. When the program tries to access address 0, for example, using the instruction
  47. MOV REG,0
  48. virtual address 0 is sent to the MMU. The MMU sees that this virtual address falls
  49. in page 0 (0 to 4095), which according to its mapping is page frame 2 (8192 to
  50. 12287). It thus transforms the address to 8192 and outputs address 8192 onto the
  51. bus. The memory knows nothing at all about the MMU and just sees a request for
  52. reading or writing address 8192, which it honors. Thus, the MMU has effectively
  53. mapped all virtual addresses between 0 and 4095 onto physical addresses 8192 to
  54. 12287.
  55. Similarly, the instruction
  56. MOV REG,8192
  57. is effectively transformed into
  58. MOV REG,24576
  59. SEC. 3.3 VIRTUAL MEMORY 197
  60. Virtual
  61. address
  62. space
  63. Physical
  64. memory
  65. address
  66. 60K–64K
  67. 56K–60K
  68. 52K–56K
  69. 48K–52K
  70. 44K–48K
  71. 40K–44K
  72. 36K–40K
  73. 32K–36K
  74. 28K–32K
  75. 24K–28K
  76. 20K–24K
  77. 16K–20K
  78. 12K–16K
  79. 8K–12K
  80. 4K–8K
  81. 0K–4K
  82. 28K–32K
  83. 24K–28K
  84. 20K–24K
  85. 16K–20K
  86. 12K–16K
  87. 8K–12K
  88. 4K–8K
  89. 0K–4K
  90. Virtual page
  91. Page frame
  92. X
  93. X
  94. X
  95. X
  96. 7
  97. X
  98. 5
  99. X
  100. X
  101. X
  102. 3
  103. 4
  104. 0
  105. 6
  106. 1
  107. 2
  108. Figure 3-9. The relation between virtual addresses and physical memory addresses is given by the page table. Every page begins on a multiple of 4096 and
  109. ends 4095 addresses higher, so 4K–8K really means 4096–8191 and 8K to 12K
  110. means 8192–12287.
  111. because virtual address 8192 (in virtual page 2) is mapped onto 24576 (in physical
  112. page frame 6). As a third example, virtual address 20500 is 20 bytes from the start
  113. of virtual page 5 (virtual addresses 20480 to 24575) and maps onto physical address 12288 + 20 = 12308.
  114. By itself, this ability to map the 16 virtual pages onto any of the eight page
  115. frames by setting the MMU’s map appropriately does not solve the problem that
  116. the virtual address space is larger than the physical memory. Since we have only
  117. eight physical page frames, only eight of the virtual pages in Fig. 3-9 are mapped
  118. onto physical memory. The others, shown as a cross in the figure, are not mapped.
  119. In the actual hardware, a Present/absent bit keeps track of which pages are physically present in memory.
  120. What happens if the program references an unmapped address, for example, by
  121. using the instruction
  122. MOV REG,32780
  123. which is byte 12 within virtual page 8 (starting at 32768)? The MMU notices that
  124. the page is unmapped (indicated by a cross in the figure) and causes the CPU to
  126. trap to the operating system. This trap is called a page fault. The operating system
  127. picks a little-used page frame and writes its contents back to the disk (if it is not already there). It then fetches (also from the disk) the page that was just referenced
  128. into the page frame just freed, changes the map, and restarts the trapped instruction.
  129. For example, if the operating system decided to evict page frame 1, it would
  130. load virtual page 8 at physical address 4096 and make two changes to the MMU
  131. map. First, it would mark virtual page 1’s entry as unmapped, to trap any future accesses to virtual addresses between 4096 and 8191. Then it would replace the
  132. cross in virtual page 8’s entry with a 1, so that when the trapped instruction is reexecuted, it will map virtual address 32780 to physical address 4108 (4096 + 12).
  133. Now let us look inside the MMU to see how it works and why we hav e chosen
  134. to use a page size that is a power of 2. In Fig. 3-10 we see an example of a virtual
  135. address, 8196 (0010000000000100 in binary), being mapped using the MMU map
  136. of Fig. 3-9. The incoming 16-bit virtual address is split into a 4-bit page number
  137. and a 12-bit offset. With 4 bits for the page number, we can have 16 pages, and
  138. with 12 bits for the offset, we can address all 4096 bytes within a page.
  139. The page number is used as an index into the page table, yielding the number
  140. of the page frame corresponding to that virtual page. If the Present/absent bit is 0,
  141. a trap to the operating system is caused. If the bit is 1, the page frame number
  142. found in the page table is copied to the high-order 3 bits of the output register,
  143. along with the 12-bit offset, which is copied unmodified from the incoming virtual
  144. address. Together they form a 15-bit physical address. The output register is then
  145. put onto the memory bus as the physical memory address.
  146. 3.3.2 Page Tables
  147. In a simple implementation, the mapping of virtual addresses onto physical addresses can be summarized as follows: the virtual address is split into a virtual
  148. page number (high-order bits) and an offset (low-order bits). For example, with a
  149. 16-bit address and a 4-KB page size, the upper 4 bits could specify one of the 16
  150. virtual pages and the lower 12 bits would then specify the byte offset (0 to 4095)
  151. within the selected page. However a split with 3 or 5 or some other number of bits
  152. for the page is also possible. Different splits imply different page sizes.
  153. The virtual page number is used as an index into the page table to find the
  154. entry for that virtual page. From the page table entry, the page frame number (if
  155. any) is found. The page frame number is attached to the high-order end of the offset, replacing the virtual page number, to form a physical address that can be sent
  156. to the memory.
  157. Thus, the purpose of the page table is to map virtual pages onto page frames.
  158. Mathematically speaking, the page table is a function, with the virtual page number as argument and the physical frame number as result. Using the result of this
  159. SEC. 3.3 VIRTUAL MEMORY 199
  160. 15
  161. 14
  162. 13
  163. 12
  164. 11
  165. 10
  166. 9
  167. 8
  168. 7
  169. 6
  170. 5
  171. 4
  172. 3
  173. 2
  174. 1
  175. 0
  176. 000
  177. 000
  178. 000
  179. 000
  180. 111
  181. 000
  182. 101
  183. 000
  184. 000
  185. 000
  186. 011
  187. 100
  188. 000
  189. 110
  190. 001
  191. 010
  192. 0
  193. 0
  194. 0
  195. 0
  196. 1
  197. 0
  198. 1
  199. 0
  200. 0
  201. 0
  202. 1
  203. 1
  204. 1
  205. 1
  206. 1
  207. 1 Present/
  208. absent bit
  209. Page
  210. table
  211. 12-bit offset
  212. copied directly
  213. from input
  214. to output
  215. Virtual page = 2 is used
  216. as an index into the
  217. page table Incoming
  218. virtual
  219. address
  220. (8196)
  221. Outgoing
  222. physical
  223. address
  224. (24580)
  225. 110
  226. 1 1 0 0 0 0 0 0 0 0 0 0 1 0 0
  227. 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0
  228. Figure 3-10. The internal operation of the MMU with 16 4-KB pages.
  229. function, the virtual page field in a virtual address can be replaced by a page frame
  230. field, thus forming a physical memory address.
  231. In this chapter, we worry only about virtual memory and not full virtualization.
  232. In other words: no virtual machines yet. We will see in Chap. 7 that each virtual
  233. machine requires its own virtual memory and as a result the page table organization becomes much more complicated—involving shadow or nested page tables
  234. and more. Even without such arcane configurations, paging and virtual memory
  235. are fairly sophisticated, as we shall see.
  236. Structure of a Page Table Entry
  237. Let us now turn from the structure of the page tables in the large, to the details
  238. of a single page table entry. The exact layout of an entry in the page table is highly
  239. machine dependent, but the kind of information present is roughly the same from
  240. machine to machine. In Fig. 3-11 we present a sample page table entry. The size
  242. varies from computer to computer, but 32 bits is a common size. The most important field is the Pa g e frame number. After all, the goal of the page mapping is to
  243. output this value. Next to it we have the Present/absent bit. If this bit is 1, the
  244. entry is valid and can be used. If it is 0, the virtual page to which the entry belongs
  245. is not currently in memory. Accessing a page table entry with this bit set to 0
  246. causes a page fault.
  247. Caching
  248. disabled Modified Present/absent
  249. Page frame number
  250. Referenced Protection
  252. Figure 3-11. A typical page table entry.
  253. The Protection bits tell what kinds of access are permitted. In the simplest
  254. form, this field contains 1 bit, with 0 for read/write and 1 for read only. A more
  255. sophisticated arrangement is having 3 bits, one bit each for enabling reading, writing, and executing the page.
  256. The Modified and Referenced bits keep track of page usage. When a page is
  257. written to, the hardware automatically sets the Modified bit. This bit is of value
  258. when the operating system decides to reclaim a page frame. If the page in it has
  259. been modified (i.e., is ‘‘dirty’’), it must be written back to the disk. If it has not
  260. been modified (i.e., is ‘‘clean’’), it can just be abandoned, since the disk copy is
  261. still valid. The bit is sometimes called the dirty bit, since it reflects the page’s
  262. state.
  263. The Referenced bit is set whenever a page is referenced, either for reading or
  264. for writing. Its value is used to help the operating system choose a page to evict
  265. when a page fault occurs. Pages that are not being used are far better candidates
  266. than pages that are, and this bit plays an important role in several of the page replacement algorithms that we will study later in this chapter.
  267. Finally, the last bit allows caching to be disabled for the page. This feature is
  268. important for pages that map onto device registers rather than memory. If the operating system is sitting in a tight loop waiting for some I/O device to respond to a
  269. command it was just given, it is essential that the hardware keep fetching the word
  270. from the device, and not use an old cached copy. With this bit, caching can be
  271. turned off. Machines that have a separate I/O space and do not use memory-mapped I/O do not need this bit.
  272. Note that the disk address used to hold the page when it is not in memory is
  273. not part of the page table. The reason is simple. The page table holds only that
  274. information the hardware needs to translate a virtual address to a physical addres
  275. SEC. 3.3 VIRTUAL MEMORY 201
  276. Information the operating system needs to handle page faults is kept in software
  277. tables inside the operating system. The hardware does not need it.
  278. Before getting into more implementation issues, it is worth pointing out again
  279. that what virtual memory fundamentally does is create a new abstraction—the address space—which is an abstraction of physical memory, just as a process is an
  280. abstraction of the physical processor (CPU). Virtual memory can be implemented
  281. by breaking the virtual address space up into pages, and mapping each one onto
  282. some page frame of physical memory or having it (temporarily) unmapped. Thus
  283. this section is bassically about an abstraction created by the operating system and
  284. how that abstraction is managed.
RAW Paste Data