Week 6 Flashcards
Crt.o
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.
File copied after crt.o
Foo.o copies code segment after crt.o and then bar.o goes after foo.
Follows process added processes in memory
Needed libraries for the code. Linker goes into the library and adds the stack and code files.
Fixing unresolved chains
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.
Logical address space
Address generated by CPU
Physical Address Space
Location in physical memory
Logical vs physical on binding
Compile and load time have the same binding. Execution time these addresses differ.
MMU
Memory management unit. In between Ram and Cpu, maps virtual addresses to physical addresses.
Relocation register
Register added to every virtual address space
MMU process
CPU generates logical address. Checks address against limit register to ensure address is within range. Add relocation register. End with physical address in memory.
Advantage of MMU
serves as memory protection for physical memory.
Contiguous memory
One block of memory allocated to a full program.
IBM Memory setup
Segments large enough to run biggest possible program
How are holes managed
OS keeps track of holes. OS will find hole big enough to fit process. When a process ends, its added to the free list.
First fit
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)
Best Fit
Find the smallest hole that can fit. Advantage: - Minimum amount of waste. Disadvantage: Search entire list and end up with tiny slivers
Worst fit
Look for largest block. Advantage: End up with big blocks. Disadvantage: Worst algorithm to use (it dumb).
Internal Fragmentation
Allocate memory in larger in general sized blocks. Extra memory in the block that’s useless.
External Fragmentation
Small holes spread through memory which none are big enough to satisfy a request.
Fragmentation trade - Allocate in smaller units
Less internal fragmentation but more overhead in managing allocation
Fragmentation trade - Allocate in larger units
Easier to manage, more internal fragmentation
50 percent rule
Of N allocated blocks, 0.5 N space is lost to fragmentation. Only 1/3 of memory is usable
Dynamic Loading
Only load routines when needed as memory is in short supply. Doesn’t require OS support. Applied in IBM, mainframe, JAVA Vm
Static Linking
Take full program and load it. Like in example with loading foo and bar.
Dynamic linking
Link all files, libraries, and data on the fly.
Program Link Table
Different programs are different places at different times. PLT table contains routines that are used or called by the routine and a pointer.
Process of dynamic linking
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.
Paging and frame
Divide virtual and physical memory into 4k sections so its no longer contiguous.
Page table
Each process has its own logical address space, thus each page has to map to a frame in physical memory.
How paging table works
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.
Page size
2^d bits
pages
2^logical bits/2^d
frames
2^physical/2^d
Page table size
pages * size of a word (4)
Total physical memory
frames * 1000
Frame table
Keeps track of which frames are free and which are allocated.
Downsides of page tables
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.
MMU Cache/Translation look-aside buffer
Minimizes memory traffic. Contains a small cache with most recent frame/page translations.
TLB miss/protocol
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.
Permanent entries in TLB
Kernel address
Sharing pages
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.
Hierarchical tables
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.
Hierarchical tables
Look at example in week 6
Issue with Hierarchical tables
Cost of each miss is one more memory access
Hashed page table
Instead of an array, the page table is a hash. Means you must deal with collisions.
Inverted Page Tables
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.
Hardware table walk
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.
Software table walk
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.
Virtual memory
Process of having more memory in physical than in virtual because not all needs to be in at once.
