http:^^www.cs.wisc.edu^~cs537-1^memory.html

This data set contains WWW-pages collected from computer science departments of various universities

combining a block of size 2<sup>n</sup> with its buddy creates a properly
aligned block of size 2<sup>n+1</sup>
For example, blocks of size 4 could start at addresses 0, 4, 8, 12, 16, 20, etc.
The blocks at 0 and 4 are buddies; combining them gives a block at 0 of
length 8.  Similarly 8 and 12 are buddies, 16 and 20 are buddies, etc.
The blocks at 4 and 8 are not buddies even though they are neighbors:
Combining them would give a block of size 8 starting at address 4, which
is not a multiple of 8.
The address of a block's buddy
can be easily calculated by flipping the nth bit from the right in the
binary representation of the block's address.
For example, the pairs of buddies (0,4), (8,12), (16,20) in binary are
(00000,00100), (01000,01100), (10000,10100).  In each case, the two addresses
in the pair differ only in the third bit from the right.
In short, you can find the address of the buddy of a block by taking the
exclusive <em>or</em> of the address of the block with its size.
To allocate a block of a given size, first round the size up to the next
power of two and look on the list of blocks of that size.
If that list is empty, split a block from the next higher list (if that
list is empty, first add two blocks to it by splitting a block from the
next higher list, and so on).
When deallocating a block, first check to see whether the block's buddy
is free.  If so, combine the block with its buddy and add the resulting
block to the next higher free list.  As with allocations, deallocations
can cascade to higher and higher lists.

<a name="core_compaction"> <h3> Compaction and Garbage Collection </h3> </a>

What do you do when you run out of memory?
Any of these methods can fail because all the memory is allocated,
or because there is too much fragmentation.
Malloc, which is being used to allocate the data segment
of a Unix process, just gives up and calls the (expensive) OS call to
expand the data segment.
A memory manager allocating real physical memory doesn't have that
luxury.  The allocation attempt simply fails.
There are two ways of delaying this catastrophe, compaction and garbage
collection.
<p>
Compaction attacks the problem of fragmentation by moving all the allocated
blocks to one end of memory, thus combining all the holes.
Aside from the obvious cost of all that copying, there is an important
limitation to compaction:
Any pointers to a block need to be updated when the block is moved.
Unless it is possible to find all such pointers, compaction is not possible.
Pointers can stored in the allocated blocks themselves as well as other
places in the client of the memory manager.
In some situations, pointers can point not only to the start of blocks
but also into their bodies.
For example, if a block contains executable code, a branch instruction
might be a pointer to another location in the same block.
Compaction is performed in three phases.
First, the new location of each block is calculated to determine the
distance the block will be moved.
Then each pointer is updated by adding to it the amount that the block it
is pointing (in)to will be moved.
Finally, the data is actually moved.
There are various clever tricks possible to combine these operations.
<p>
Garbage collection finds blocks of memory that are inaccessible and 
returns them to the free list.
As with compaction, garbage collection normally assumes we find all
pointers to blocks, both within the blocks themselves and ``from the outside.''
If that is not possible, we can still
do ``conservative'' garbage collection in which
every word in memory that contains a value that appears to be a pointer
is treated as a pointer.
The conservative approach may fail to collect blocks that are garbage,
but it will never mistakenly collect accessible blocks.
There are three main approaches to garbage collection:
reference counting, mark-and-sweep, and generational algorithms.
<p>
Reference counting keeps in each block a count of the number of pointers
to the block.
When the count drops to zero, the block may be freed.
This approach is only practical in situations where there is some
``higher level'' software to keep track of the counts (it's much too hard
to do by hand), and even then, it will not detect cyclic structures of
garbage:
Consider a cycle of blocks, each of which is only pointed to by its
predecessor in the cycle.
Each block has a reference count of 1, but the entire cycle is garbage.
<p>
Mark-and-sweep works in two passes:
First we mark all non-garbage blocks by doing a depth-first search
starting with each pointer ``from outside'':
<pre><font color="0f0fff">
    void mark(Address b) {
        mark block b;
        for (each pointer p in block b) {
            if (the block pointed to by p is not marked)
                mark(p);
        }
    }
</font></pre>
The second pass sweeps through all blocks and returns the unmarked ones
to the free list.
The sweep pass usually also does compaction, as decribed above.
<p>
There are two problems with mark-and-sweep.
First, the amount of work in the mark pass is proportional to the amount of
<em>non</em>-garbage.  Thus if memory is nearly full, it will do a lot
of work with very little payoff.
Second, the mark phase does a lot of jumping around in memory, which is
bad for virtual memory systems, as we will soon see.
<p>
The third approach to garbage collection is called <em>generational</em>
collection.
Memory is divided into <em>spaces</em>.
When a space is chosen for garbage collection, all subsequent references
to objects in that space cause the object to be copied to a new space.
After a while, the old space either becomes empty and can be returned to the
free list all at once, or at least it becomes so sparse that a mark-and-sweep
garbage collection on it will be cheap.
As an empirical fact, objects tend to be either short-lived or long-lived.
In other words, an object that has survived for a while is likely to
live a lot longer.
By carefully choosing where to move objects when they are referenced,
we can arrange to have some spaces filled only with long-lived objects,
which are very unlikely to become garbage.
We garbage-collect these spaces seldom if ever.

<a name="core_swapping"> <h3> Swapping </h3> </a>

When all else fails, <samp><font color="0f0fff">allocate</font></samp> simply fails.
In the case of an application program, it may be adequate to simply
print an error message and exit.
An OS must be able recover more gracefully.
<p>
We motivated memory management by the desire to have many processes in
memory at once.
In a batch system, if the OS cannot allocate memory to start a new job, it
can ``recover'' by simply delaying starting the job.
If there is a queue of jobs waiting to be created, the OS might
want to go down the list, looking for a smaller job that can be
created right away.
This approach maximizes utilization of memory, but can starve large jobs.
The situation is analogous to short-term CPU scheduling, in which SJF
gives optimal CPU utilization but can starve long bursts.
The same trick works here: aging.
As a job waits longer and longer, increase its priority, until its
priority is so high that the OS refuses to skip over it looking for
a more recently arrived but smaller job.
<p>
An alterantive way of avoiding starvation is to use
a memory-allocation scheme with fixed partitions (holes
are not split or combined).  Assuming no job is bigger than the biggest
partion, there will be no starvation, provided that each time a partition
is freed, we start the first job in line that is smaller than that
partition.
However, we have another choice analogous to the
difference between first-fit and best fit.
Of course we want to use the ``best'' hole for each job (the smallest
free partition that is at least as big as the job), but suppose the
next job in line is small and all the small partitions are
currently in use.
We might want to delay starting that job and look through the arrival
queue for a job that better uses the partitions currently available.
This policy re-introduces the possibility of starvation, which we
can combat by aging, as above.
<p>
If a disk is available, we can also <em>swap</em> blocked jobs out to disk.
When a job finishes, we first swap back jobs form disk before allowing
new jobs to start.
When a job is blocked (either because it wants to do I/O or because our
short-term scheduling algorithm says to switch to another job), we have a
choice of leaving it in memory or swapping it out.
One way of looking at this scheme is that it increases the multiprogramming
level (the number of jobs ``in memory'') at the cost of making it
(<em>much</em>) more expensive to switch jobs.
A variant of the MLFQ (multi-level feedback queues) CPU scheduling algorithm is
particularly attractive for this situation.
The queues are numbered from 0 up to some maximum.
When a job becomes ready, it enters queue zero.
The CPU scheduler always runs a job from the lowest-numbered non-empty
queue (i.e., the priority is the negative of the queue number).
It runs a job from queue <em>i</em> for a maximum of <em>i</em> quanta.
If the job does not block or complete within that time limit, it is
added to the next higher queue.
This algorithm behaves like RR with short quata in that short bursts
get high priority, but does not incur the overhead of frequent
swaps between jobs with long bursts.
The number of swaps is limited to the logarithm of the burst size.

<hr>

<address>
<i>
<!WA5><a HREF="mailto:[e-mail]">
[e-mail]
</a>
<br>
Thu Oct 31 15:38:54 CST 1996
</i>
</address>
<br>
Copyright &#169; 1996 by Marvin Solomon.  All rights reserved.

</body>

</html>