Software Systems
Spring 2005

For today, you should have:

1) Finished Homework 4.

2) Worked on your project. 

3) Read about memory management.


Outline:

1) project tips

2) memory management overview

3) reading questions from notes13 

4) midpoint survey 


For next time you should:

1) work on your project (no new homework yet!)

2) read about the Lea allocator


Getting started
---------------

WARNING: mixed metaphors ahead!

Most projects have two phases, "wandering in the desert"
and "on rails".

The difference is whether, when you sit down to work on the
project, you know what to do.

Wandering is no fun, and it is very hard to get motivated for it.

The difference between success and failure is when you get sick
of wandering.

Tips for successful wandering:

1) Keep several balls in the air, so you have useful work to
   do while you wait.

   And so you have the best chance of finding a fruitful path.

2) Some reading is good, but avoid the fallacy that passing your
   eyes over paper is productive work.

   Do _something_ concrete early.

   Example: income inequality project

3) Write as you go.  Start writing your final report now.

   a) part of the introduction

   b) bibliography and related work.

   You will find it surprisingly useful to
   explain your project to yourself, and each other.

4) Use brainstorming techniques.

   I know they are corny, but they work.

   

What does an Operating System do?
---------------------------------

1) abstraction

   timesharing is the illusion of unshared hardware

   VM creates the illusion of a uniform address space


2) coordination (of shared resources)

   VM also prevents processes from accessing each other's memory

   other devices also need coordination


3) allocation (of resources)

   scheduling is allocation of time

   page replacement is allocation of physical memory (between processes)

   memory management is allocation of memory within a process


In the context of memory, "allocation" might refer to

1) the OS allocating an additional frame to a process.

   Allocation in units of (non-contiguous) pages.

2) a program allocating space in VM for a particular purpose.

   Allocation in units of (contiguous) bytes.


Memory management
-----------------

Within a process, there are several kinds of allocation.

At compile time (static allocation):

1) the code generator lays out the program text in memory.

2) if the compiler can tell how big something is, and how many
   times it will be allocated, it can allocate it at compile
   time, in the static segment.


At run time (dynamic allocation):

1) local variables are allocated on the stack

   usually the entire stack frame is allocated at once.


2) constructors allocate space in the heap

   variable size, contiguous allocation

   unpredicatable 


Deallocation:

1) objects in the static section are never deallocated

2) stack frames are deallocated when functions complete

   normal functions complete in FILO order

   (a co-routine is a function whose call/complete pattern
   is not stack structured)

3) dynamically-allocated objects can be deallocated any time
   after the last access.


How does the OS know?

1) the programmer might explicitly "free" the object.

2) the compiler might analyze the program and add deallocation
   code (not common in practice)

3) the run-time system might detect that an object cannot
   be accessed (how?)

#1 is called explicit memory management

#3 is called garbage collection.


Explicit memory management:

1) potentially optimal.

2) error prone.

3) often in conflict with modularity.


Garbage collection:

1) conservative (does not deallocate as soon as possible).

   sometimes needs a little help.

2) takes time.

3) used to be in conflict with real time constraints.


Contiguous allocation
---------------------

Fixed size is relatively easy (reduces to the non-contig problem)

Variable size is challenging.

Standish presents the baseline strategy

1) two-way linked list of free blocks

2) fit policy

3) coalescing

Lea presents an alternative with better performance.


Garbage collection
------------------

Two general strategies:

1) mark and sweep

   periodically stop the program and traverse the reference graph

   deallocate anything you _didn't_ visit


2) reference counting

   keep track of the number of references to each object

   when the last reference goes away, deallocate


Reference counting

1) more overhead

2) cannot collect circular data structures (without help)


Mark and sweep

1) used to impose noticeable delays

   current versions are incremental