GOALS

To study

• the basic principles of memory management in non-virtual memory environment, and then
• the principles of virtual memory and it's implementation.

Key words: logical address, physical address, MMU and address translation, paging and page tables, segmentation and segment tables, translation lookaside buffer (TLB)

TEXT IN COURSE BOOK

• Stallings luku 7.1-7.4: Memory Management (+ Appendix 7A [not asked in exam])
  • 5.ed: pages 300-331
  • 4.ed: pages 301-332
• Stallings luku 8.1: Virtual Memory (pages 333-353)
  • 5.ed: pages 332-352
  • 4.ed: pages 333-353

SLIDES and OTHER MATERIALS

• Slides in Finnish to appear later. Available also from the course page
  • Luento 5: Muistinhallinnasta 2s/A4, 6s/A4
  • Luento 6: Yksinkertainen segmentointi ja sivutus 2s/A4, 6s/A4
  • Luento 7: Virtuaalimuisti ja sivutus 2s/A4, 6s/A4
  • Luento 8: Segmentointi ja sivutus virtuaalimuistissa 2s/A4, 6s/A4
• See also Stallings's pages

Other Materials: Tanenbaum A.S.: Modern Operating Systems. 2nd ed. 2001. Pages 189-214, 249-262.

EXERCISES A-C

The report must be returned on paper latest on Friday 15.10. into the mailbox beside the room D225 (before 12 o'clock). You can also leave the report to the teacher during the small group meeting on Wednesday 13.10.

Before the first meeting: Study the following questions carefully. Think about possible solutions. Write down all your ideas, results, problems, and unclear parts. 1. meeting: In a study group, study the exercises together. Think and discuss about what issues you already know, what items you need to find more information about, what information is needed, etc. You can consult the teacher of the small group session, but he will not solve the problems for you. He can gie you hints and show the right way for solveing the problem, if you are totally lost. Between the two meetings: You may need to discuss together between the meetings to write your report. These discussion you need to organise yourselves. You may wish to use personal meetings at Exactum or somewhere else, use e-mail, irc, webCT (if you want to use webCT, please contact Tiina Niklander). You are expected to write your report before the second meeting. 2. meeting: Study groups present their solutions and report contents to other groups during the meeting. After the 2. meeting: If you feel that you need to modify your report, you'll have two days after the meeting to finalise your report. For example, you may want to add/change/correct some items in your report based on the presentations during the meeting. Please notice, that you'll have ONLY two days for this.

A - EXERCISES Each Team: Give your solutions to the following 6 exercises.

2.1 - DYNAMIC MEMORY ALLOCATION

The memory consists of the following hole sizes in memory order: 10K, 4K, 32K, 18K, 7K, 9K, 12K and 15K.

Which hole is taken for successive segment requests of 12K, 10K and 9K, if the algorithm used is

a) First Fit b) Best Fit c) Next Fit (continues from the beginning of memory) d) Worst Fit

In which order should the available areas be kept in free memory area list (ordered by the memory address or by the size)? Think about the reservation and freeing, as well as how easily the subsequent areas are joined together.

What might have been the big idea, when someone suggested the Worst Fit algorithm?

2.2 - BUDDY SYSTEM

A minicomputer uses Buddy System for memory management. Initially it has one free block of 256KB at address 0. The smallest used block size is 4KB.

a) What problems of static and what problems of dynamic memeory allocation are avoided in Buddy System? How many separate lists are used for free lists? Why not use just one list?

b) After successive requests for 5KB, 25KB, 35KB and 20KB come in, how many blocks are left unallocated and what are their sizes and addresses? Draw the free lists. How much memory is used (wasted) by the internal fragmentation?

c) Continue by freeing the 5KB block. What are the addresses and the sizes of free blocks? Draw the free lists.

2.3 - THE ROLE OF THE MMU

Memory management unit (MMU) has a register PTR (Page Table Register) for the memory address of the page table. Also associative TLB (Translation Lookaside Buffer) with 16 entries is used. Page size is 1024 bytes and the page-table has one-level.

Describe what happens inside the MMU when the processor is given to a new process, that refers among others to virtual addresses 0, 1 ... 510, 2001, 2002 and 500 ... 510. You need not to describe algorithms used for page replacement or space allocation. Fix the details needed.

Please notice, that the every time a page fault happens, the executed process is swapped.

2.4 - PAGING vs SEGMENTATION

a) How does the implementation of virtual memory differ if it is using segmentation instead of paging? What are the benefits of segmentation compared to paging? And vice versa.

b) What kind of information is needed in the page table entry? in segment table entry?

c) What are the benefits of using TLB? Would it be possible to get the virtual memory to function without the TLB? What information is stored in the TLB when a) using paging and b) using segmentation?

d)Explain the address translation in MMU in segmented system.

2.5 - COMBINED SEGMENTATION AND PAGING

Why do some systems combine segmentation and paging?

Assume a task is divided into 4 equal-sized segments, and that the system builds an 8-entry page descriptor table for each segment. Thus, the system has a combination of segmentation and paging. Assume also that the page size is 2Kbytes.

a) What is the maximum size of each segment?

b) What is the maximum logical address space for the task?

c) Assume that an element in physical location 0x00021ABC is accessed by this task. What is the format of the logical address that the task generates for it?

d) What is the maximum physical address space for this system?

2.6 - INVERTED PAGE TABLE

A machine has 48-bit virtual addresses and 32-bit physical addresses. Page size is 8KB. How many entries are needed for a conventional page table? For an inverted page table? Why is it still more common to use conventional page tables instead of inverted page tables?

B - SELECT YOUR FAVOURITE REVIEW QUESTIONS Each team: List five review questions that you consider most relevant for this section, and explain why it is important to understand the answers. A good review question requires understandin a lot about the issue. A question that only asks about some very small details is not a very good review question. If there are areas that would need more detailed explanations, please give a hint.

C - EVALUATION Each team: Please evaluate your teams work as well as your own work using the following pdf form (in Finnish). The form will be handed to the team in the small group session. The evaluation has two goals: (1) to collect information about the exercises and study groups, and (2) to help study groups to make their work even better. We appriciate short answers that give the essentials in a compact form. Please try to be open minded. Answer to each question and give also your reasonings.

Part 1 Part 3

Failing prepares for success.