Week 6

Question 1

Crt.o

Answer 1

At link time, linker knows crt.o goes at the beginning of memory. Defines point where OS will begin executing the program usually with a name call entry. crt.o will call main. It contains variables and code. Code from crto.o goes to the beginning of the text segment and contains the exit hook.

Question 2

File copied after crt.o

Answer 2

Foo.o copies code segment after crt.o and then bar.o goes after foo.

Question 3

Follows process added processes in memory

Answer 3

Needed libraries for the code. Linker goes into the library and adds the stack and code files.

Question 4

Fixing unresolved chains

Answer 4

Crt.o has undefined references to main and exit. Linker sets up code to point to where main and exit actually are (foo and stdi.o). Go through foo.o code to link fopen, etc to stdio.o. Go through bar.o to link unresolved. If every symbol is resolved, the linker is done. If not, the linker will throw an error.

Question 5

Logical address space

Answer 5

Address generated by CPU

Question 6

Physical Address Space

Answer 6

Location in physical memory

Question 7

Logical vs physical on binding

Answer 7

Compile and load time have the same binding. Execution time these addresses differ.

Question 8

MMU

Answer 8

Memory management unit. In between Ram and Cpu, maps virtual addresses to physical addresses.

Question 9

Relocation register

Answer 9

Register added to every virtual address space

Question 10

MMU process

Answer 10

CPU generates logical address. Checks address against limit register to ensure address is within range. Add relocation register. End with physical address in memory.

Question 11

Advantage of MMU

Answer 11

serves as memory protection for physical memory.

Question 12

Contiguous memory

Answer 12

One block of memory allocated to a full program.

Question 13

IBM Memory setup

Answer 13

Segments large enough to run biggest possible program

Question 14

How are holes managed

Answer 14

OS keeps track of holes. OS will find hole big enough to fit process. When a process ends, its added to the free list.

Question 15

First fit

Answer 15

Use first hole that fits size requirement for process. Advantage: Only have to look at list until size is found (where we left off from the last look through)

Question 16

Best Fit

Answer 16

Find the smallest hole that can fit. Advantage: - Minimum amount of waste. Disadvantage: Search entire list and end up with tiny slivers

Question 17

Worst fit

Answer 17

Look for largest block. Advantage: End up with big blocks. Disadvantage: Worst algorithm to use (it dumb).

Question 18

Internal Fragmentation

Answer 18

Allocate memory in larger in general sized blocks. Extra memory in the block that’s useless.

Question 19

External Fragmentation

Answer 19

Small holes spread through memory which none are big enough to satisfy a request.

Question 20

Fragmentation trade - Allocate in smaller units

Answer 20

Less internal fragmentation but more overhead in managing allocation

Question 21

Fragmentation trade - Allocate in larger units

Answer 21

Easier to manage, more internal fragmentation

Question 22

50 percent rule

Answer 22

Of N allocated blocks, 0.5 N space is lost to fragmentation. Only 1/3 of memory is usable

Question 23

Dynamic Loading

Answer 23

Only load routines when needed as memory is in short supply. Doesn’t require OS support. Applied in IBM, mainframe, JAVA Vm

Question 24

Static Linking

Answer 24

Take full program and load it. Like in example with loading foo and bar.

Question 25

Dynamic linking

Answer 25

Link all files, libraries, and data on the fly.

Question 26

Program Link Table

Answer 26

Different programs are different places at different times. PLT table contains routines that are used or called by the routine and a pointer.

Question 27

Process of dynamic linking

Answer 27

Call a function. On its first call, the fopen function on the PLT is associated with a jump that calls the linker to find the actual location of fopen. Linker searches for the appropriate symbol in the in the shared libraries. The jump table is then updated with the appropriate address. Use link register to return to fopen and execute.

Question 28

Paging and frame

Answer 28

Divide virtual and physical memory into 4k sections so its no longer contiguous.

Question 29

Page table

Answer 29

Each process has its own logical address space, thus each page has to map to a frame in physical memory.

Question 30

How paging table works

Answer 30

Address generated by CPU. Lower bits represent d - location within the page. number of bits will indicate page size 2^bits. High bits of address is the index into the page table. Will be the offset to index to the location of the frame in main memory. This address will be combined to d to indicate the physical address.

Question 31

Page size

Answer 31

2^d bits

Question 32

#pages

Answer 32

2^logical bits/2^d

Question 33

#frames

Answer 33

2^physical/2^d

Question 34

Page table size

Answer 34

#pages * size of a word (4)

Question 35

Total physical memory

Answer 35

#frames * 1000

Question 36

Frame table

Answer 36

Keeps track of which frames are free and which are allocated.

Question 37

Downsides of page tables

Answer 37

Large and must be switched during context switch. Means a lot of overhead. Generates lots of extra traffic. MMU address logic halves the speed of access.

Question 38

MMU Cache/Translation look-aside buffer

Answer 38

Minimizes memory traffic. Contains a small cache with most recent frame/page translations.

Question 39

TLB miss/protocol

Answer 39

If the page/table translation isn't found. Requires one extra memory cycles table and then memory. New frame and page added to TLB. The TLB has a performance sensitive hit ratio.

Question 40

Permanent entries in TLB

Answer 40

Kernel address

Question 41

Sharing pages

Answer 41

Code should only ever be loaded once. Most processes can share their data. Will point to the same frame but private information like the stack will point to different frames.

Question 42

Hierarchical tables

Answer 42

Multiple tables. Page number offset is split into two or more segments. First section will be the offset for the first table and so on. Will end by getting the frame number and combining into a regular address.

Question 43

Hierarchical tables

Answer 43

Look at example in week 6

Question 44

Issue with Hierarchical tables

Answer 44

Cost of each miss is one more memory access

Question 45

Hashed page table

Answer 45

Instead of an array, the page table is a hash. Means you must deal with collisions.

Question 46

Inverted Page Tables

Answer 46

Indicates which frame is part of the frame. Search table for appropriate pid and page # in address. The offset will be the frame number. Hash table can shorten these problems.

Question 47

Hardware table walk

Answer 47

The MMU takes the virtual address and extracts the relevant parts (e.g., the page directory index, page table index, and the offset within the page).For each level of the page table, the MMU reads the table entry at that level. For example, at the first level (PGD), it reads the entry and gets the address of the next level table (page table). The MMU continues to access the page tables at each level (e.g., the second-level page table and so on) until it reaches the final page frame address (physical address). Finally, the MMU calculates the physical address by combining the frame number from the last level of the page table with the offset in the virtual address. The cost of this is the table +1.

Question 48

Software table walk

Answer 48

TLB generates a trap on a miss. OS reads the page tables in RAM and loads new entry into the TLB. CPU can continue after. Happens in NIOS II, MIPS. Cost is the interrupt routine.

Question 49

Virtual memory

Answer 49

Process of having more memory in physical than in virtual because not all needs to be in at once.