• In the beginning: Expensive Hardware, Cheap People Goal: maximize hardware utilization.
• Now: Cheap Hardware, Expensive People Goal: make it easy for people to use computer.

• Problem: Code to manipulate external I/O devices. Is very complex, and is a major source of programming difficulty.
• Solution: Build a subroutine library (device drivers) to manage the interaction with the I/O devices. The library is loaded into the top of memory and stays there. This is the first example of something that would grow into an operating system.

• Problem: computer idles while programmer sets things up. Poor utilization of huge investment.
• Solution: Hire a specialized person to do setup. Faster than programmer, but still a lot slower than the machine.
• Solution: Build a batch monitor. Store jobs on a disk (spooling), have computer read them in one at a time and execute them. Big change in computer usage: debugging now done offline from print outs and memory dumps. No more instant feedback.
• Problem: At any given time, job is actively using either the CPU or an I/O device, and the rest of the machine is idle and therefore unutilized.
• Solution: Allow the job to overlap computation and I/O. Buffering and interrupt handling added to subroutine library.
• Problem: one job can't keep both CPU and I/O devices busy. (Have compute-bound jobs that tend to use only the CPU and I/O-bound jobs that tend to use only the I/O devices.) Get poor utilization either of CPU or I/O devices.
• Solution: multiprogramming - several jobs share system. Dynamically switch from one job to another when the running job does I/O. Big issue: protection. Don't want one job to affect the results of another. Memory protection and relocation added to hardware, OS must manage new hardware functionality. OS starts to become a significant software system. OS also starts to take up significant resources on its own.

• Issue: It becomes important to make computers easier to use and to improve the productivity of the people. One big productivity sink: having to wait for batch output (but is this really true?). So, it is important to run interactively. But computers are still so expensive that you can't buy one for every person. Solution: interactive timesharing.
• Problem: Old batch schedulers were designed to run a job for as long as it was utilizing the CPU effectively (in practice, until it tried to do some I/O). But now, people need reasonable response time from the computer.
• Solution: Preemptive scheduling.
• Problem: People need to have their data and programs around while they use the computer.
• Solution: Add file systems for quick access to data. Computer becomes a repository for data, and people don't have to use card decks or tapes to store their data.
• Problem: The boss logs in and gets terrible response time because the machine is overloaded.
• Solution: Prioritized scheduling. The boss gets more of the machine than the peons. But, CPU scheduling is just an example of resource allocation problems. The timeshared machine was full of limited resources (CPU time, disk space, physical memory space, etc.) and it became the responsibility of the OS to mediate the allocation of the resources. So, developed things like disk and physical memory quotas, etc.

• Provides Abstractions Hardware has low-level physical resources with complicated, idiosyncratic interfaces. OS provides abstractions that present clean interfaces. Goal: make computer easier to use. Examples: Processes, Unbounded Memory, Files, Synchronization and Communication Mechanisms.
• Provides Standard Interface Goal: portability. Unix runs on many very different computer systems. To a first approximation can port programs across systems with little effort.
• Mediates Resource Usage Goal: allow multiple users to share resources fairly, efficiently, safely and securely. Examples:
  • Multiple processes share one processor. (preemptable resource)
  • Multiple programs share one physical memory (preemptable resource).
  • Multiple users and files share one disk. (non-preemptable resource)
  • Multiple programs share a given amount of disk and network bandwidth (preemptable resource).
• Consumes Resources Solaris takes up about 8Mbytes physical memory (or about $400).

• I/O devices run concurrently with CPU, interrupting CPU when done.
• On a multiprocessor multiple user processes execute in parallel.
• Multiple workstations execute concurrently and communicate by sending messages over a network. Protocol processing takes place asynchronously.

• An execution stream is a sequence of instructions.
• Process state determines the effect of the instructions. It usually includes (but is not restricted to):
  • Registers
  • Stack
  • Memory (global variables and dynamically allocated memory)
  • Open file tables
  • Signal management information
  Key concept: processes are separated: no process can directly affect the state of another process.

• The shell you type stuff into is a process.
• When you execute a program you have just compiled, the OS generates a process to run the program.
• Your WWW browser is a process.

• Uniprogramming: only one process at a time. Typical example: DOS. Problem: users often wish to perform more than one activity at a time (load a remote file while editing a program, for example), and uniprogramming does not allow this. So DOS and other uniprogrammed systems put in things like memory-resident programs that invoked asynchronously, but still have separation problems. One key problem with DOS is that there is no memory protection - one program may write the memory of another program, causing weird bugs.
• Multiprogramming: multiple processes at a time. Typical of Unix plus all currently envisioned new operating systems. Allows system to separate out activities cleanly.

• Registers - almost all machines save registers in PCB.
• Processor Status Word.
• What about memory? Most machines allow memory from multiple processes to coexist in the physical memory of the machine. Some may require Memory Management Unit (MMU) changes on a context switch. But, some early personal computers switched all of process's memory out to disk (!!!).

• User hits a key. The keystroke is echoed on the screen.
• A user program issues a system call to read a file. The operating system figures out which disk blocks to bring in, and generates a request to the disk controller to read the disk blocks into memory.
• The disk controller finishes reading in the disk block and generates and interrupt. The OS moves the read data into the user program and restarts the user program.
• A Mosaic or Netscape user asks for a URL to be retrieved. This eventually generates requests to the OS to send request packets out over the network to a remote WWW server. The OS sends the packets.
• The response packets come back from the WWW server, interrupting the processor. The OS figures out which process should get the packets, then routes the packets to that process.
• Time-slice timer goes off. The OS must save the state of the current process, choose another process to run, the give the CPU to that process.

• When process issues a system call to read a file, the process's thread will take over, figure out which disk accesses to generate, and issue the low level instructions required to start the transfer. It then suspends until the disk finishes reading in the data.
• When process starts up a remote TCP connection, its thread handles the low-level details of sending out network packets.

• If two processes issue read file system calls at close to the same time, must make sure that the OS serializes the disk requests appropriately.
• When one process allocates memory, its thread must find some free memory and give it to the process. Must ensure that multiple threads allocate disjoint pieces of memory.

• An interrupt occurs, transferring control away from one thread to an interrupt handler.
• A time-slice switch occurs, transferring control from one thread to another.
• Two threads running on different processors read and write the same memory.

• Two threads need to issue disk requests. First thread starts to program disk controller (assume it is memory-mapped, and must issue multiple writes to specify a disk operation). In the meantime, the second thread runs on a different processor and also issues the memory-mapped writes to program the disk controller. The disk controller gets horribly confused and reads the wrong disk block.
• Two threads need to write to the display. The first thread starts to build its request, but before it finishes a time-slice switch occurs and the second thread starts its request. The combination of the two threads issues a forbidden request sequence, and smoke starts pouring out of the display.
• For accounting reasons the operating system keeps track of how much time is spent in each user program. It also keeps a running sum of the total amount of time spent in all user programs. Two threads increment their local counters for their processes, then concurrently increment the global counter. Their increments interfere, and the recorded total time spent in all user processes is less than the sum of the local times.

		  class Thread {
		    public:
		      Thread(char* debugName);
		      ~Thread();
		      void Fork(void (*func)(int), int arg);
		      void Yield();
		      void Finish();
		  }
		  

		  int a = 0;
		  void sum(int p) {
		    a++;
		    printf("%d : a = %d\n", p, a);
		  }
		  void main() {
		    Thread *t = new Thread("child");
		    t->Fork(sum, 1);
		    sum(0);
		  }
		  

		          la      a, %r0
		          ld      [%r0],%r1
		          add     %r1,1,%r1
		          st      %r1,[%r0]

		          ld      [%r0], %o3 ! parameters are passed starting with %o0
		          mov     %o0, %o1
		          la      .L17, %o0
		          call    printf
		  

		  0 : 1                                      0 : 1
		  1 : 2                                      1 : 1

		  1 : 2                                      1 : 1
		  0 : 1                                      0 : 1

		  1 : 1                                      0 : 2
		  0 : 2                                      1 : 2

		  0 : 2                                      1 : 2
		  1 : 1                                      0 : 2
		  

		  class Semaphore {
		    public:
		      Semaphore(char* debugName, int initialValue);
		      ~Semaphore();
		      void P();
		      void V();
		  }
		  

• Semphore(name, count) : creates a semaphore and initializes the counter to count.
• P() : Atomically waits until the counter is greater than 0, then decrements the counter and returns.
• V() : Atomically increments the counter.

		  int a = 0;
		  Semaphore *s;
		  void sum(int p) {
		    int t;
		    s->P();
		    a++;
		    t = a;
		    s->V();
		    printf("%d : a = %d\n", p, t);
		  }
		  void main() {
		    Thread *t = new Thread("child");
		    s = new Semaphore("s", 1);
		    t->Fork(sum, 1);
		    sum(0);
		  }
		  

		  Semaphore *s;
		  void consumer(int dummy) {
		    while (1) {
		      s->P();
		      consume the next unit of data
		    }
		  }
		  void producer(int dummy) {
		    while (1) {
		      produce the next unit of data
		      s->V();
		    }
		  }
		  void main() {
		    s = new Semaphore("s", 0);
		    Thread *t = new Thread("consumer");
		    t->Fork(consumer, 1);
		    t = new Thread("producer");
		    t->Fork(producer, 1);
		  }
		  

		  Semaphore *full;
		  Semaphore *empty;
		  void consumer(int dummy) {
		    while (1) {
		      full->P();
		      consume the next unit of data
		      empty->V();
		    }
		  }
		  void producer(int dummy) {
		    while (1) {
		      empty->P();
		      produce the next unit of data
		      full->V();
		    }
		  }
		  void main() {
		    empty = new Semaphore("empty", N);
		    full = new Semaphore("full", 0);
		    Thread *t = new Thread("consumer");
		    t->Fork(consumer, 1);
		    t = new Thread("producer");
		    t->Fork(producer, 1);
		  }
		  

		  class Lock {
		    public:
		      Lock(char* debugName);              // initialize lock to be FREE
		      ~Lock();                            // deallocate lock
		      void Acquire(); // these are the only operations on a lock
		      void Release(); // they are both *atomic*
		  }
		  

• Lock(name) : creates a lock that starts out in the unlocked state.
• Acquire() : Atomically waits until the lock state is unlocked, then sets the lock state to locked.
• Release() : Atomically changes the lock state to unlocked from locked.

• Only one thread can acquire lock at a time. (safety)
• If multiple threads try to acquire an unlocked lock, one of the threads will get it. (liveness)
• All unlocks complete in finite time. (liveness)

• Efficiency: take up as little resources as possible.
• Fairness: threads acquire lock in the order they ask for it. Are also weaker forms of fairness.
• Simple to use.

		  class Condition {
		    public:
		      Condition(char* debugName);
		      ~Condition();
		      void Wait(Lock *conditionLock);
		      void Signal(Lock *conditionLock);
		      void Broadcast(Lock *conditionLock);
		  }
		  

• Condition(name) : creates a condition variable.
• Wait(Lock *l) : Atomically releases the lock and waits. When Wait returns the lock will have been reacquired.
• Signal(Lock *l) : Enables one of the waiting threads to run. When Signal returns the lock is still acquired.
• Broadcast(Lock *l) : Enables all of the waiting threads to run. When Broadcast returns the lock is still acquired.

		  Lock *l;
		  Condition *c;
		  int avail = 0;
		  void consumer(int dummy) {
		    while (1) {
		      l->Acquire();
		      if (avail == 0) {
		        c->Wait(l);
		      }
		      consume the next unit of data
		      avail--;
		      l->Release();
		    }
		  }
		  void producer(int dummy) {
		    while (1) {
		      l->Acquire();
		      produce the next unit of data
		      avail++;
		      c->Signal(l);
		      l->Release();
		    }
		  }
		  void main() {
		    l = new Lock("l");
		    c = new Condition("c");
		    Thread *t = new Thread("consumer");
		    t->Fork(consumer, 1);
		    Thread *t = new Thread("consumer");
		    t->Fork(consumer, 2);
		    t = new Thread("producer");
		    t->Fork(producer, 1);
		  }
		  

• Thread 2 calls consumer, and suspends.
• Thread 1 calls producer, and signals thread 2.
• Instead of thread 2 running next, thread 3 runs next, calls consumer, and consumes the element. (Note: with Hoare monitors, thread 2 would always run next, so this would not happen.)
• Thread 2 runs, and tries to consume an item that is not there. Depending on the data structure used to store produced items, may get some kind of illegal access error.

		  void consumer(int dummy) {
		    while (1) {
		      l->Acquire();
		      while (avail == 0) {
		        c->Wait(l);
		      }
		      consume the next unit of data
		      avail--;
		      l->Release();
		    }
		  }
		  

		  allocate(int dummy) {
		    while (1) {
		      wait for coins from user
		      n = get();
		      give number n to user
		    }
		  }
		  deallocate(int dummy) {
		    while (1) {
		      wait for number n from user
		      put(i);
		    }
		  }
		  main() {
		    for (i = 0; i < P; i++) {
		      t = new Thread("allocate");
		      t->Fork(allocate, 0);
		      t = new Thread("deallocate");
		      t->Fork(deallocate, 0);
		    }
		  }
		  

		  int a[N];
		  int get() {
		    for (i = 0; i < N; i++) {
		      if (a == 0) {
		        a = 1;
		        return(i+1);
		      }
		    }
		  }
		  void put(int i) {
		    a[i-1] = 0;
		  }