Operating Systems of Mobile Devices (OSMZ)

Week V. (8.3.-12.3.2021)

Memory management is usually divided into three levels - hardware, operating system and application level. We do not solve the technical level in this subject and we will focus only on the other two. At the operating system level, memory must be allocated to user programs and, if not required by the program, is reused for other programs. The operating system may pretend that the computer has much more memory than it really has, or that each program has all the memory available for its own use - a virtual memory system that handles these situations. At the application program level, memory management involves allocating sections of limited available memory for program objects and data structures, and usually also reusing memory that is no longer occupied.

Before we move on to the virtual memory, let's first describe a simple paging. The term pages corresponds to small sections of memory of the same size into which each program is divided. RAM is also divided into small sections of the same size called frames. The typical frame size is 4 kB. The frame and page size must be the same. The operating system loads the complete program into free frames of the operating memory at startup, at the same time it must remember which frames it has allocated to individual processes (e.g., by using page tables) and also record free frames in memory. Virtual memory then usually consists of a combination of paging and swapping to disk (only the currently used frames are held in physical memory, with the rest of the process on the disk).

Virtual addresses are translated into physical addresses by a Memory Management Unit (MMU). It also takes care of memory protection, checking cache coherence and managing the memory bus. If a virtual page does not map to physical memory, the MMU detects a page fault and asks the operating system to load the page into physical memory. The system then decides which frame of physical memory is no longer needed, can free it, and then loads the contents of the desired virtual page from disk into it. A key benefit of MMUs is memory protection: the operating system kernel can use MMUs to protect against program errors when it detects (or disables) access to memory that does not belong to the process. The advantage of using MMUs is also the elimination of the problem with fragmented memory. This is because a contiguous block of virtual addresses can be mapped to multiple blocks of physical memory, which may not be stored entirely.

If the page table contained records for the entire virtual space, it would be extremely large. With a 32-bit virtual address space alone, it would have one million records at a 4 kB page size. In addition, each process needs its own page table (each process has its own address space). The solution is to efficiently organize page tables into multiple levels and at the same time record only those items in the page table that are actually used. A special hardware cache in the processor - Translation Lookaside Buffer (TLB) is also used for fast translation. The TLB seeks to maintain records of those mappings that have been used recently and which are (therefore) expected to be used in the immediate future.

You can find the implementation of memory management and multilevel tables in Linux at /mm/memory.c To complete, you can read a more detailed explanation of paging in Linux.

PRESENTATION

LITERATURE

Andrew S. Tanenbaum - Modern operating systems. 4th edition:

  • Chapter 3 Memory Management (pp. 185 - 221)
  • 3.5.3 Page Size (pp. 225 - 227)
  • 3.6.2 Page Fault Handling (pp. 234 - 235)
  • 3.7 Segmentation (pp. 240 - 247)

ADDITIONAL READINGS

Translation lookaside buffer (TLB) demo
Memory organization in C (video). TLB features and matching speed measurement are behind recent Meltdown and Specter attacks.

QUESTIONS

After reading the above texts, you should be able to answer following questions from the topics for the exam, specifically:

  • Briefly characterize the function of MMU - address translation, explain the terms physical and virtual address.
  • Briefly describe the memory management scheme for monoprogramming without spooling and paging.
  • Briefly describe the memory control scheme for multiprocessor fixedpartition programming.
  • Explain the concept of realocation.
  • Describe memory management with bitmaps and linked-lists.
  • Briefly explain the concept of paging (virtual memory principle)