Software Systems
Spring 2005

For today, you should have:

1) worked on your project


Outline:

1) review / overview

2) survey

3) projects


For next time you should:

1) work on your project


The final exam
--------------

If you were writing the final exam, what would you ask about?

1) focus on important ideas, not tiny details.

   a meaningful test of an idea means expressing it or applying it.

2) ask some basic questions to test fundamental knowledge.

3) ask some challenging questions to test ability to synthesize.

   exam should be educational, not just evaluative.

4) test some material that was in readings but not class.

5) review quizzes for trouble spots.

6) provide new reading and test comprehension.


Goals:

1) last chance to reinforce material

2) measurement (internal/external, individual/group)

3) reward effort and understanding


Topics
------

Latency and bandwith

Disk drives

Caching

Processes and threads

Virtual memory and address spaces

Timesharing and scheduling algorithms

Page replacement algorithms

Queueing theory

Memory management and garbage collection

File system implementation / interface

Database algorithms

I/O implementation and abstraction

Distributed hash tables and P2P



Concepts
--------

Latency lags bandwidth

	caching, replication, prediction

The memory hierarchy

    Caching and locality

    Replacement algorithms (quick and dirty, slow and smart)

The process/thread abstraction

    thread of execution + address space + abstracted I/O

Scheduling (CPU, disk, etc.)

Real time

Indirection

OS as an interrupt handler

OS as an abstraction provider

OS as coordinator

The hardware/software interface

Interface stacks




Skills
------

CS arithmetic

Performance analysis:

1) measurement: caches

2) workload characterization: distribution of file sizes, etc.

3) modeling: lognormal and Pareto distributions

4) analysis: queueing theory, UBNE property

5) simulation: discrete event simulation

6) implementation:

7) verification: 

A little bit of C programming

Reading technical material (several kinds)

Project-related skills



Catalog of readings
-------------------

Patterson, "Latency lags bandwidth"

SCSI Interface Product Manual

Stallings, "The memory hierarchy"

Tanenbaum, "Processes and threads"

The Tanenbaum-Torvalds Debate (first page)

Wikipedia, "Address space"

Tanenbaum, "Scheduling"

Waldspurger and Weihl, "Lottery scheduling"

Harchol-Balter and Downey, "Exploiting Process Lifetime Distribution..."

Tanenbaum, "Virtual Memory"

Taylor and Karlin, "Queueing systems"

Wikipedia, "Pareto distribution"

Wikipedia, "Virtual memory" and "Memory management"

Tanenbaum, "Design issues for paging systems"

Standish, "Dynamic memory allocation"

Lea, "A memory allocator"

Berger, Zorn and McKinley, "Reconsidering Custom Memory Allocation"

Silberschatz and Galvin, "File system implementation"

Rosenblum and Ousterhout, "The LFS Storage Manager"

Raskin, "File names and structures"

Wikipedia, "Archy" and "Zooming User Interface"

Garcia-Molina, Ullman and Widom, "Using secondary storage effectively"

Silberschatz and Galvin, "I/O systems"  (two parts)

Wikipedia, "Hashtable" and "Distributed Hash Table"

Balakrishnan et al., "Looking up data in P2P Systems"