CS 1550 Lecture Notes - Lecture 5: Virtual Address Space, Virtual Memory, Linked List

56 views9 pages
21 Mar 2017
School
Course
Memory Management
Focusing on RAM
RAM is finite and has constraints, hence the need to manage
Exclusive Access
Memory is necessary for both process and OS
o Give some RAM to OS and some to Process
o Give all to Process and OS uses ROM
o Hybrid: Give RAM to both, and use ROM for device drivers
Doesn't make much sense, so we share
Fixed Partitions
Simplest way to share RAM
Can only change size of partitions after a reboot
Partitions should be sized appropriately
o Can we predict memory needs of a process?
If we know everything at compile time
Take executable and give a small space for a stack to
predict the programs max memory needs
Problems
o Assigning processes to a particular partition
Single queue (wait until next available queue)
We might want to skip the next process
Assigning small process to a large partition
o Is this a waste?
The whole point is to use CPU time, so an
empty partition is a waste.
Waste of RAM vs. Waste of CPU time
o Could fill up a space that a later, larger process
could've used
Queues for each partition
Could result in empty partitions
o Protection Problem: It's possible for a program in one partition to read or
modify code or data from another program in the same memory
Result of sharing
o Relocation Problem: program could move to different partition after each
execution
Why is this a problem?
find more resources at oneclass.com
find more resources at oneclass.com
Unlock document

This preview shows pages 1-3 of the document.
Unlock all 9 pages and 3 million more documents.

Already have an account? Log in
2
Absolute addressing
o Address could turn out to be invalid if the program is
in a different partition then it was before
Solution
o Protection
Know bounds of partition
Check if an address is in the bounds
Where: hardware (CPU itself)
When: all instructions (we are changing PC)
Make it fast: put bounds in registers (privileged)
o Relocation
Don't use absolute addressing
Rebasing: take all absolute addresses and rewrite them to
addresses that belong to our partition
Make absolute address relative to the base
Processor adds the base to absolute addresses
Best solution
Swapping
Temporarily kick out programs' memory to use their space
Take memory out of RAM and put on disk
Makes relocation problem worse
Relocation Problem
o Happens in the middle of execution (we have to worry about more than
just code pointers)
o Can't just not use absolute addressing (because pointers use absolute
addressing)
o Can't rebase because you can't locate the pointers in the stack/heap
easily
o Solution: Make absolute address relative to the base
Room to Grow
Need to allocate RAM that you may not end up using
Prior management techniques do not support room to grow
Allocation Management
Problem: two regions of memory where we want to manage dynamic allocations
(stack easy to manage & heap not easy to manage)
o Stack is predictable, only need a dividing line
o Heap is not predictable, a single line doesn't work, there's free space by
used space (holes)
Tracked via a bitmap
find more resources at oneclass.com
find more resources at oneclass.com
Unlock document

This preview shows pages 1-3 of the document.
Unlock all 9 pages and 3 million more documents.

Already have an account? Log in
3
Problem: Extra memory
Solution:
o Use chunks (1 bit per chunk instead of 1 bit per byte)
Problem: internal fragmentation
o Use different base binary
o Sparse data structure: use linked list (store rare
value)
Problem: linked list size isn't fixed (worst case:
not sparse, no runs)
Solution: allocate extra space for the linked list
(tax)
Overlays
Handwritten dynamic loading of subsets of a program's code and data
Build a subset of code and data that is available to make some progress, then
replace contents once progress is made, to make some more progress
o The programmer is responsible for identifying the subsets of code and
data that need to be loaded at the same time
o When moving from one overlay to the next, programmer needs to store
important data to disk
o Since no one wants to have to do this Virtual Memory
Physical addresses: in RAM
Virtual addresses: in address space
Virtual Memory
Attempt to simulate more memory than exists on the system through automatic
"overlays"
We want Mapping that takes a Virtual Address and produces a Physical Address
o Hash function
h(VA) --> PA
Doesn't work collisions
Prescriptive tells you where something HAS to be
Instead we want descriptive function describes the
mapping
o Table
Indexed by Virtual Address, stores Physical Address
Descriptive
Speed
Where does the work of using the table take place: CPU
(Memory Management Unit- MMU)
If the table can fit into the MMU, then the access to the table
will be fast
find more resources at oneclass.com
find more resources at oneclass.com
Unlock document

This preview shows pages 1-3 of the document.
Unlock all 9 pages and 3 million more documents.

Already have an account? Log in

Get access

Grade+20% OFF
$8 USD/m$10 USD/m
Billed $96 USD annually
Grade+
Homework Help
Study Guides
Textbook Solutions
Class Notes
Textbook Notes
Booster Class
40 Verified Answers
Class+
$8 USD/m
Billed $96 USD annually
Class+
Homework Help
Study Guides
Textbook Solutions
Class Notes
Textbook Notes
Booster Class
30 Verified Answers