W6 - Memory Management (Part I)

Question 1

Why is memory management necessary?

Answer 1

The computer memory is shared by many processes.
The compiler has to produce code without knowing how many other processes there are, and where they are in memory.

Question 2

Main requirements for memory management

Answer 2

1) Relocation
2) Protection & Sharing
3) Each process working in its own address space.

Question 3

What is meant by relocation in memory management?

Answer 3

The ability to move the program from one place in memory to another.

Question 4

How many bytes does the stack pointer move when pushing or popping data?

Answer 4

4 bytes on a 32-bit system (e.g., x86)

8 bytes on a 64-bit system (e.g., x86-64)
Because the stack stores word-sized values:

Word = 4 bytes (32-bit)

Word = 8 bytes (64-bit)

Question 5

What is a virtual/logical address space in a process?

Answer 5

It’s the range of virtual memory addresses a process can use, which are translated to actual physical memory by the OS.
Each process gets a large, private virtual address space (e.g. too little on 16-bit, 4 GB on 32-bit, many TB on 64-bit).

Question 6

Base and limit registers

Answer 6

Base: Smallest legal physical memory address for a process.
Limit: The size of the range.

These two form a section of physical memory a process is allowed to occupy, and if this process attempts to access something outside the range an addressing error occurs (it causes a trap, so we switch into kernel mode).

Question 7

Logical/Virtual Address

Answer 7

Reference to a memory location, independent of the current use of memory. Instructions issued by CPU reference logical addresses (e.g. arguments for LOAD)

Question 8

Physical/Absolute Address

Answer 8

The actual location in memory. It’s physical memory.

Question 9

Address translation

Answer 9

Translating logical address into physical address using the page table.

Question 10

Who can check the page table

Answer 10

The CPU and the OS

Question 11

How does fixed partitioning work

Answer 11

Memory is divided into contiguous blocks at boot time, which don’t change. Requires a base register, which gets loaded by OS at context switch.

Question 12

Problems with fixed partitioning.

Answer 12

Since partitions are fixed, programs can potentially run out of space. You also deal with internal fragmentation, where memory is reserved for a process which we are not fully using.

Question 13

How does dynamic partitioning work

Answer 13

Partitions are created as programs are loaded. Requires a base register and limit register.

Question 14

What kind of fragmentation do we encounter with dynamic partitioning?

Answer 14

External fragmentation. Unused memory is broken up into small regions that are unuasble. We don’t get internal fragmentation though!

Question 15

What’s a better solution over partitioning?

Answer 15

Pages.

Question 16

How does paging work?

Answer 16

Physical address space is split into equal sized frames.
Logical address space is divided into equal size pages.
Page size = Frame size.
Program gets loaded into available pages. Pages get mapped to frames, this is recorded on the page table.

Question 17

Describe the uniqueness of page numbers.

Answer 17

Unique for each process, since each process gets its own page table.

Question 18

What kind of fragmentation do we get with paging?

Answer 18

Some internal fragmentation. This gets worse if you pick larger frame sizes / page sizes.

Question 19

How does swapping a page out of main memory work?

Answer 19

The page no longer corresponds to the frame in memory. It corresponds to a specific location in the disk instead, being stored in one or more blocks.

Question 20

In the context of paging, what do physical addresses and logical addresses represent?

Answer 20

Physical -> Frame
Logical -> Page

Question 21

Advantages of paging

Answer 21

We eliminate external fragmentation. If a process needs another page, just give it any frame in memory. This is only possible because its Random Access Memory, optimized to be accessed anywhere. (In a disk you’d have to rotate, seek, …).

It’s easy to implement.

Easy to model protection and sharing.

Easy to allocate physical memory.

Naturally opens up the possibility for Virtual Memory (swapping pages to disk).

Question 22

Why is page size a trade off?

Answer 22

Too big and internal fragmentation becomes more problematic.
Too small and we end up with too many pages. We need to store data in memory for them (page table), and CPU spends time translating too.
As memory gets cheaper, we can increase it

Question 23

Page table

Answer 23

Maps logical addresses (pages) to physical addresses (frames). It is indexed by page number.

Question 24

How would memory sharing work?

Answer 24

Multiple processes each have pages that translate to the exact same frames, letting them access the same data.

Question 25

How does paging protect processes?

Answer 25

Each process only has access to its allocated frames.

Question 26

Logical addresses break down into what two components?

Answer 26

Page number (Most significant bits / left side) Offset, which is address within page (Least significant bits / right side)

Question 27

We know the page number component of a logical address is made of X bits. What can we calculate from this?

Answer 27

The number of pages. 2^X

Question 28

We know the offset component of a logical address is made of Z bits. What can we calculate from this?

Answer 28

The size of each page. 2^Z.

Question 29

How do you actually extract the page number from the logical address.

Answer 29

You've got page number (X bits) on the left, and offset (Y bits) on the right. Shift the logical address to the left Y times (divide by 2^Y). Your page number is on the right hand side and can be read. You can do the same in reverse to form a logical address.

Question 30

How can you build a logical address out of a page number (X bits) and a offset (Y bits)

Answer 30

Take your page number, and right shift it Y times (it creates enough space for your offset of Y bits). You do this by dividing by 2^Y. The remaining space is padded with Y zeros. Just add your offset now.

Question 31

What data structure do we use for page tables?

Answer 31

Arrays.

Question 32

What does a page table entry look like?

Answer 32

A bit sequence, where we have a bunch of page flags and the frame number. Flags indicate things like if page is in memory or disk, if it has changed, if it is read only, ....

Question 33

How does address translation work?

Answer 33

Use the page number component of the logical address, and use a page table (special registers used to do this, page table stored in register) to find the frame number. Page number X Page table entry size = The exact page table entry you want, containing your frame number. Take your frame number, and multiply it by the size of the frame (each frame is 4096 bytes) to jump to the frame you want. Add your offset so you can select the exact byte out of 4096 that you want.

Question 34

Problems with paging

Answer 34

PAGE TABLE IS LARGE. >> 4KB pages and 32 bit addresses means 4MB per page table. That's an additional 4MB per process. It gets even worse for 64 bit addresses. MEMORY ACCESS IS SLOW. >> One lookup in page table, and one lookup to access data in memory.