Week 7 address binding segmentation page tables

Question 1

The address binding problem

Answer 1

REMEMBER THIS
logical address - in binary file we have machine segment which contains machine code which contains address ( logical addresses)

address binding problem is mapping logical address (in program) to actual addresses in memory AT RUNTIME given the state of memory ( whats free and whats not ) is only known at runtime

Question 2

Non solutions to address binding problem:

why does avoiding multi programming not work ie only having one program in memory at a time

Answer 2

Would be incredibly slow
say a process was waiting for an io task to complete cpu would remain idle ( NO OTHER PROGRAM TO SWITCH TO)

Furthermore if we wanted to context switch to another program (which would be in disk) this would be even slower as retrieving from disk is very slow

Question 3

Non solution statically assign ranges of addresses to a program

Answer 3

Multiple instances of program have same range so overlap and interrfere

Lots of internal fragmentation likely - we assign memory to program that isnt used

How much memory a program needs depends on a lot of different things so know way to know in advance how much to statically assign

EVERY PROGRAM THAT MIGHT RUN WOULD NEED SPACE RESERVED

Question 4

whats load time relocation

Answer 4

While loading a program into memory, the loader adjusts the logical addresses (in the text segment) so they correctly reference the physical memory region where the program is placed.

Question 5

does load time relocation suffer from internal fragmentation

Answer 5

Yes - physical memory shared between proccesses

and we can see theres memory assigned for stack and heap (which grow initially empty) - memory allocated to a process and not in use == INTERNAL FRAGMENTATION

Question 6

does load time relocation suffer from external fragmentation

Answer 6

Yes Physical memory shared between processes (which can be of different size)

It may be the case that we have enough cumulative space in memory to fit a process but becuase that memory isnt contiguous we cant assign it to a process - external

Question 7

Problems with loadtime relocation

Answer 7

Physical address space shared amongst processes

This means :
. no fault isolation
- if a process has a bug it would cause other processes to not work and even os to not work

. no security -
process can read / write to other process memory

. Slow
- adjusting logical addresses so they
correctly reference the physical memory
region where the program is placed is
slow

Question 8

What is MMU

Answer 8

mmu is a conceptual device that sits between processor and memory and when a processor requests a region in memory the requested address is compared against the base and limit to see if request will be accepted

Question 9

Faults of Simple MMU

Answer 9

Fault isolation - good between process if a process bugs out doesnt lead to other processes not working or os crashing

Security - Process can no longer read or write to other process’ memory ( as base- physical start of process limit - end physical addres of process)

Internal - occurs if base and limit are fixed
external still occurs

Question 10

what is segmentation

Answer 10

Segmentation is a memory management scheme where a program’s logical address space is divided into variable-sized segments — such as code, data, stack, or heap — and each segment is mapped independently to physical memory using a segment table that stores the base address, limit, and access permissions for each segment.

Question 11

what is a segment of memory

Answer 11

a <base.> pair</base.>

Question 12

When is segmentation supported

Answer 12

MMU can work with multiple <base, limit> pairs

Question 13

JUST READ - read thorougly tho very important

Answer 13

We can divide up our regions (data , text , stack) into segments which allows us to put permissions on segments:
* We cant write to a text segment (as this just contains the instructions of program which shouldn’t be modified during runtime)
* we cant execute a stack segment etc

WE HAVE JUST DIVIDED PROCESS BY THEIR LOGICAL PURPOSE(DATA,TEXT,STACK…)

Question 14

Just read - read thoroughly though very important

Answer 14

so this is everyhting i know about the x86

Logical address = (segment, offset),

segment offset 16 bits
physical address 24 bits

We can have 4 active segments : CS ( code segment, DS) ( data segment) , SS (stack segment) , ES

ie if you want to change to a different data segment have to change selector value in data segment register to point to a different data segment

Table descriptor is a table that defines segments ( base , limit , access for each segment entry)
Each segment has a 16 bit register which has a selector that indexes into an entry in table descriptor

If you want to change a segment -> change selector value -> slow as active segments details cached but to know access non active segments details involves multiple memory accesses

Question 15

Why is there no internal fragementation in segmentation

Answer 15

Because segments can be different sizes and so we can just have the size of a segment be exactly equal to how much memory it needs

Question 16

why segmentation leads to non linear address space

Answer 16

Segments can be:
✅ Different sizes
✅ Overlapping
✅ Placed anywhere in physical memory

Question 17

properties of

Answer 17

Fault isolation- We can now isolate faults to specific regions ( ie text , stack , code segment) which gives us even better fault isolation - no longer just isolates between processes

Security:
since we have gone even finer grained we don’t just segment the process but the regions within a process so of course process A cant refer to the memory of process B

rewriting no longer an issue -
We aren’t changing references of machine instructions no more
Instructions have corresponding segment types
Address binding is now just a matter of making segments

fragmentation :
internal for same reason we mentioned before:

Segments maybe different sizes:
-This will come in useful as it helps eliminate internal fragmentation – which arises when a processes is allocated more memory than it uses- this is eliminated as we can make the segment size match how much memory it uses since sizes can be different

External Fragmentaion:
still a problem memory must be contiguous so if we require a segment to have more memory than there is available adhering to the fact that its contiguous (cant have part of a segments memory here and another elsewhere) we still cant use the available space

Question 18

what is paging

Answer 18

virtual memory divided into equal sized pages and physical into equal sized frame. Paging is the mapping of pages to frames.

Note SIZE OF PAGE = SIZE OF FRAME

Question 19

what must mmu do in paging

Answer 19

programs only see virtual address
(p , o ) page number , offset

mmu must translate p to f

offset remains the same

Question 20

Long winded explanation of why no external fragmentation

Answer 20

so essentially let me see if i understand correctly and you verify: Pages: equal sized blocks of virtual memory Frames : Equal sized blocks of physical memory Size of frame = size of page Why it eliminates External fragmentation: External fragmentation occured when we had available total space (but it was scattered) but we needed a large enough contiguos block of memory to satisfy However we can now place pages to frames non contiguosly: ie a process with 3 pages can go to frames 5,9 ,2 (non contiguos) This eliminates external fragmentation as we no longer need contiguos blocks to place pages into frames

Question 21

short winded explanation of why no external fragmentatio

Answer 21

No external fragmentation in paging because even though virtual addresses are contiguous, physical frames can be scattered — as long as there are enough free frames, pages can map into them in any order.

Question 22

Is there internal fragmentation and why

Answer 22

REMEMBER WE SAID PHYSICAL MEMORY IS DIVIDED INTO EQUAL SIZED FRAMES ( in this example each frame is 4KB)

If a program needs one more byte (of physical memory) we cant allocate a percentage of a frame to satisfy it we have to allocate it one more frame

However we limited it to 4095 bytes wasted (4096 -1)

Question 23

what does page table base register hold and why

Answer 23

page table base register holds base (starting physical address) of current page table

MMU then uses the page table to convert virtual address to physical address

Question 24

Look at notes for week 7 page 24 and page 25 beautiful diagram about conversion of virtual to physical address

Question 25

how do we use page table to get physical address

Answer 25

* Here the mmu contains the PTBR and in the diagram we can se it pointing to the base of the current page table * Remember offset stays the same * We use the page number to index (treat it like an array) so we look for index 5 in the page table (6th row) * This will contain the frame number * Since offset stays the same and we now have frame number we have the physical address

Question 26

SO WHY DO WE GUARANTEE PROCESSES WONT OVERLAP (interfere in physical memory) - PAGING

Answer 26

so reason it wont ever overlap (ie in paging) each process has itws own virtual address space and page table mmu converts virtual address to physical address using the process' page table so it wont ever overlap

Question 27

Why do we guarantree process' dont overlap in segmentation

Answer 27

different processes have different segments so : segment offset 42 for 2 different processes wont be the same and hence 2 different physical address

Question 28

Problem with paging ( problem 1 /2)

Answer 28

slow - what was once one memory access is now two we use the page table to look for frame number so we can access it We then do the actual memory access

Question 29

problem with paging (2/2

Answer 29

uses a lot of memory imagine 32 bit address 12 bit offset 20 bit 2^20 address per page table EVERY PROCESS NEEDS 2^20 table entries

Question 30

solution to problem1

Answer 30

use tlb tlb is a cache of page table entries we have the virtual address

tlb hit: look at tlb if page number present (tlb hit) you can find frame number without looking it up in page table ( havent accessed memory yet) We then do the actual memory access with the frame number we got from tlb tlb miss: look in tlb -> page number not there -> we look in page table for frame number ( 1 memory access so far) -> we then complete the actual access ( 2 memory access) TLB STORES THE DATA ON A TLB MISS SO FUTURE SEARCHES ARE FASTER

Question 31

solution to problem 2

Answer 31

Use multi level page tables

Question 32

What are the problems that arise if you try to fix the large memory needed in a normal paging system by using page table base and limit registers

Answer 32

1) Virtual address space must be contiguous and so page table can only grow linearly (downwards) but heap and stack require 2 independednt regions that grow towards each other and dont overlap 2) Leads to external frag Page table stored in physical memory . To extend page table you need enough contiguos space. Situations may occur where enough space but not contiguous - external frag

Question 33

what is a multilevel paging table

Answer 33

A multi-level page table is a hierarchical paging structure that only allocates entries for virtual pages mapped to physical memory, significantly reducing memory overhead compared to flat page tables.

Question 34

HOW DOES A 2 level page table work

Answer 34

so essentially is how it works imma try explain a two level page table so lets say you have a flat page table lets say process A page table you divide it into chunks ( fixed size no of frames) At root level youd have a page directory where each entry corresponds to a chunk ( in the original flat table) and an x in the page directory means whole chunk is invalid ( whole section of virtual addresses dont map to physical) so we save memroy and for the entries that are valid each entry point to the second level ( nested page table)

Question 35

Problem with multilevel page table

Answer 35

more complex translation ie multiple lookups ie in 2 level page table we split pageno into half We use top bits to index into page directory which tells us the nested page table we go to (based on where it points) We use the lower second half bits (of page table number) to index into nested page table and from there we get frame number

Question 36

solytion to slowness of multilevel pagetable

Answer 36

Problem we seen above is that ie: 2 level requires 2 extra memory accesses , 4 level requires four etc SLOW WE use TLB - MMU CACHE OF PAGETANLE ENTRIES We only have to do lookup for a tlb miss FOR MULTILEVEL ESPECIALLY WE BETTER MAKE SURE TLB MISSES ARE NOT COMMON DUE TO HOW SLOW IT IS ( EXTRA MEMORY ACCESSES)