- Dangling pointers: better not recycle storage while it is still
being used.
- Core leaks: Better not "lose" storage by forgetting to free it
even when it cannot ever be used again.
Reference Counts: keep track of the number of
outstanding pointers to each chunk of memory. When this goes to zero, free thememory. Example: Smalltalk, file descriptors in Unix. Works fine for
hierarchical structures. The reference counts must be managed automatically (bythe system) so no mistakes are made in incrementing and decrementing them.
Garbage Collection: storage is not freed explicitly
(using free operation), but rather implicitly: just delete pointers. When thesystem needs storage, it searches through all of the pointers (must be able to
find them all!) and collects things that are not used. If structures arecircular then this is the only way to reclaim space. Makes life easier on the
application programmer, but garbage collectors are incredibly difficult toprogram and debug, especially if compaction is also done. Examples: Lisp,
capability systems.
How does garbage collection work?
- Must be able to find all objects.
- Must be able to find all pointers to objects.
- Pass 1: mark. Go through all pointers that are known to be in use:
local variables, global variables. Mark each object pointed to, and recursivelymark all objects it points to.
- Pass 2: sweep. Go through all objects, free up those that are not
marked.
Garbage collection is often expensive: 20% or more of
all CPU time in systems that use it.
Sharing main memory
Issues:
- Want to let several processes coexist in main memory.
- No process should need to be aware of the fact that memory is
shared. Each must run regardless of the number and/or locations of processes.
- Processes must not be able to corrupt each other.
- Efficiency (both of CPU and memory) should not be degraded badly
by sharing. After all, the purpose of sharing is to increase overall efficiency.
Relocation: draw a simple picture of memory with some
processes in it.
- Because several processes share memory, we cannot predict in
advance where a process will be loaded in memory. This is similar to acompiler's inability to predict where a subroutine will be after linking.
- Relocation adjusts a program to run in a different area of memory.
Linker is an example of static relocation used to combine modules into programs.We now look at relocation techniques that allow several programs to share one
main memory.
Static software relocation, no protection:
- Lowest memory holds OS.
- Processes are allocated memory above the OS.
- When a process is loaded, relocate it so that it can run in its
allocated memory area (just like linker: linker combines several modules intoone program, OS loader combines several processes to fit into one memory; only
difference is that there are no cross-references between processes).
- Problem: any process can destroy any other process and/or the
operating system.
- Examples: early batch monitors where only one job ran at a time
and all it could do was wreck the OS, which would be rebooted by an operator.Many of today's personal computers also operate in a similar fashion.
