Memory Management - 3

Question 1

What is segmentation?

Answer 1

Dividing the address sapce of each process into several sections

Question 2

What segments the compiler needs?

Answer 2

source text - the text to be translated.

symbol table

constants segments

stack

parse tree

compiler executable code

Most of these segments grow during execution.

Question 3

What is the segment table for?

Answer 3

Holds information for each segment:

where it starts - base, and its size - limit.

The CPU generate a virtual address for each reference - {s_num|off}.

off > S[s_num].limit -> trap; addressing error

else, physical address = S[s_num].limit + off

Question 4

Is the segmented address space virtual?

Answer 4

Of course.** If translating results with no actual page on **RAM,** we do **swapping.

Question 5

Need the programmer be aware to which technique is being used(Paging vs Segmentation)?

Answer 5

Paging - No. because every type of memory is treated in the same way.

Segmentation - Yes.

Question 6

How many linear address spaces are there?

(Paging vs Segmentation)

Answer 6

Linear address - virtual addresses which are calculated using segment translation.

Paging - just one. all in one segment

Segmentation - many

That is, with paging specific data can be placed anywhere within the virtual space. In segmentation it has a desired range.

Question 7

Can the total address space exceed the size of physical memory(Paging vs Segmentation)?

Answer 7

Paging - Yes, Segmentation - Yes. that’s the whole point with virtual addresses. Though in Segmentation, if one segment don’t have space in RAM we’re in problem..

Question 8

Can procedures and data be distinguished and saparetely protected(Paging vs Segmentation)?

Answer 8

Paging - No. Because each chunk of memory is mixing procedures and data. so we can’t treat each in a distinguished manner.

Segmentation - Yes. because with segments we make a distinction(in terms of memory chunks) between code and data.

Question 9

Can tables whose size fluctuates be accomodated easiliy(Paging vs Segmentation)?

Answer 9

Paging - No. Page table size if fixed.

Segmentation - Yes, each segment can dynamically grow.

Question 10

Is sharing of procedures between users facillitated(Paging vs Segmentation)?

facillitated = it makes it easier.

Answer 10

Paging - No. procedures have no distinguished area.

Segmentation - Yes.

procedures have distinguished area.

Question 11

Why was this technique invented?(Paging vs Segmentation)

Answer 11

Paging - to get a large linear address space without having to buy more physical memory

Segmentation - to allow programs and data to be broken up into logically independent address spaces and to aid sharing and protection.

Question 12

What are the advantages/disadvantages of Segmentation?

Answer 12

Advantages

Growing and shrinking independently. (not of a fixed size).

Sharing between processes simple - because the division into data/procedures and such

Linking is easier - same reason as above.

Protection easier - the distinction between types of data makes it easier.

Disadvantages

Pure segmentation - might cause external fragmentation

Segments may be very large - what if they don’t fit into physical memory?

Question 13

• How is the Segment Table reached?*
• How is protection defined?*

Answer 13

It is reached via two registers:

STBR - points to the table’s location in memory

STLR - indicates number of segments used by a program.

• if segment_number < STLR it is legal.*
• Each segment table entry contains:*

validation bit = 0 -> illegal segment

read/write/execute** **priviliges.

Note: protection bits associated with segments: code sharing occurs at segment level.

Question 14

Which problem Segmentation with Paging solves?

Answer 14

1. Too large Segments.
2. External fragmentation.

Question 15

How Segmentation + Paging is implemented in MULTICS?

Answer 15

• Each program has a segments table which itself is, a segment.*
• Each segment has a page table.*
• Each segment has segment descriptor. The descriptor-base-register points to its page table*
• Memory reference procedure:*

segment table is itself paged because it may be large.

1. CPU generates virtual address: {seg_num | d}

2. seg_num refers to STBR - discriptor base register.

3. STBR refers to the segment table entry: {segment length | page table base}

4.** d > segment length? **trap.

5.** d = {**page table offset|** **page offset}

6.** page table base + page table offset = **f

7.** f is not in memory? **page fault.

8.** f + page offset - **desired location

segment number -> segment descriptor -> check if page table is in memory(if not - segmentation fault) -> page table entry examined - page base(if not in memory - segmentation fault) -> offset is added to page base -> perform read/store etc.

Question 16

• What are the Unix memory management sys calls?*
• brk(addr), mmap(addr, len, prot,flags, fd, offset), unmap(addr, len)?*

Answer 16

POSIX does not specify how malloc is implemented.

brk(addr)

change data segment size. addr specifies the first address following new size.

mmap(addr, len, prot,flags, fd, offset)

map(open, if needed) file fd starting from offset in length len to virtual address addr(0 if OS is to set address)

unmap(addr, len)

unmap a file, or a portion of it(using len).

Question 17

What is Unix Page Daemon serve for?

Answer 17

Unix Page Daemon -

• Responsible to free page frames.
• Awakened periodically to inspect the state of memory - if less than 1/4’th of page frames are free, then it frees page frames.
• This strategy works better than evicting pages when needed; writing the modified to disk in hurry.
• It helps view all available memory as page-pool.
• It uses a global clock algorithm - two-handed clock.

Question 18

What is the Two-Handed Clock algorithm?

Answer 18

Two-Handed Clock algorithm:

• First hand - clears the reference bit.
• Seconds hand - frees pages.
• Each hand works against the other
  
  • If the reference bit is set - the distance between the hands increases(angle)
  • If two hands come together the page is being freed.
• If there is thrashing
  
  • the swapper process removes processes to disk
    
    • removes processes idle for 20 sec or more
    • if none - swap out the oldest.
• who get swapped back is a function of:
  
  • Time out of memory
  • size

Question 19

How Linux manages memory for processes?

Answer 19

Each process has:

• 3GB virutal memory
  
  • Composed of areas with same:
    
    • Protection
    • Paging properties
      
      • pageable or not
      • direction of growth
• 1GB of memory for kernel and pages tables
• A linked list of areas, sorted by virtual address:
  
  • text, data, memory-mapped-files,…

Question 20

How does Linux manage memory?

Answer 20

• Kernel is never swapped
• The buddy algortihm is used. In addtion:
  
  • Linked lists of same-size free blocks are maintained.
  • To reduce internal fragmentation:
    
    • A second memory allocation scheme manages smaller units inside buddy-blocks.
• Demand paging(no pre-paging)
• Dynamic backing store management

Question 21

What is Linux page replacement algorithm?

Answer 21

Linux page replacement algorithm:

• Varing of clock algorithm
• Order of inspection of the page-freeing daemon is:
  
  • By size of process - large to small
  • In virtual address order
• Freed pages are categorized:
  
  • clean; dirty; unbackedup
• Another daemon writes up dirty page periodically.