it-ebooks - Operating Systems Lecture Notes (Stanford CS140)

Lecture Notes for CS 140
Spring 2014
John Ousterhout

• Evolution of operating systems, phase 1:
  • Hardware expensive, humans cheap
  • One user at a time, working directly at console
  • First "operating system": I/O subroutine libraries shared by users
  • Simple batch monitor: get user away from the computer. OS = program to load and run user jobs, take dumps.
  • Data channels, interrupts, overlap of I/O and computation.
  • Memory protection and relocation enable multitasking: several users share the system
  • OS must manage interactions, concurrency
  • By mid-1960's operating systems had become large, complicated.
  • OS field emerges as important discipline with principles
• Evolution of operating systems, phase 2:
  • Hardware cheap, humans expensive
  • Interactive timesharing
    • Fancy file systems
    • Issues of response time, thrashing
  • Personal computers: computers are cheap, so put one in each terminal.
  • Networking: allow sharing and communication between machines.
  • Embedded devices: put computers in cell phones, stereo players, TVs, light switches
  • Are all the fancy features developed for timesharing still needed?
• The future of OSes:
  • Very small (devices)
  • Very large (datacenters, cloud)
• Characteristics of current OSes:
  • Enormous: millions of lines of code, 100-1000 engineer-years
  • Complex: asynchronous, hardware idiosyncrasies, performance is crucial.
  • Poorly understood
• Most of an operating system's functions fall in the category of coordination: allowing several things to work together efficiently and fairly:
  • Concurrency: allow several different tasks to be underway at the same time, as if each had a private machine. To keep track of everything, processes and threads were invented.
  • I/O devices. Don't want CPU to sit idle while an I/O device is working.
  • Memory: how can a single memory be shared among several processes?
  • Files: allow many files, for many different users, to share space on the same physical disk.
  • Networks: allow groups of computers to work together.
  • Security: how to allow interactions while protecting each participant from abuse by the others?

Lecture Notes for CS 140
Spring 2014
John Ousterhout

• Readings for this topic from Operating Systems: Principles and Practice: Chapter 4.

• Thread: a sequential execution stream
  • Executes a series of instructions in order (only one thing happens at a time).
• Process: one or more threads, along with their execution state.
  • Execution state: everything that can affect, or be affected by, a thread:
    • Code, data, registers, call stack, open files, network connections, time of day, etc.
  • Part of the process state is private to a thread
  • Part is shared among all threads in the process
• Evolution of operating system process model:
  • Early operating systems supported a single process with a single thread at a time (single tasking). They ran batch jobs (one user at a time).
  • Some early personal computer operating systems used single-tasking (e.g. MS-DOS), but these systems are almost unheard of today.
  • By late 1970's most operating systems were multitasking systems: they supported multiple processes, but each process had only a single thread.
  • In the 1990's most systems converted to multithreading: multiple threads within each process.
• Is a process the same as a program?

• Almost all computers today can execute multiple threads simultaneously:
  • Each processor chip typically contains multiple cores
  • Each core contains a complete CPU capable of executing threads
  • Many modern processors support hyperthreading: each physical core behaves as if it is actually two cores, so it can run two threads simultaneously (e.g. execute one thread while the other is waiting on a cache miss).
  • For example, a server might contain 2 Intel Xeon E5-2670 processors, each with 8 cores that supports 2-way hyperthreading. Overall, this computer can run 32 threads simultaneously.
  • May have more threads than cores
  • At any given time, most threads do not need to execute (they are waiting for something).

• OS uses a process control block to keep track of each process:
  • Execution state for each thread (saved registers, etc.)
  • Scheduling information
  • Information about memory used by this process
  • Information about open files
  • Accounting and other miscellaneous information
• At any given time a thread is in one of 3 states:
  • Running
  • Blocked: waiting for an event (disk I/O, incoming network packet, etc.)
  • Ready: waiting for CPU time
• Dispatcher: innermost portion of the OS that runs on each core:
  • Run a thread for a while
  • Save its state
  • Load state of another thread
  • Run it ...
• Context switch: changing the thread currently running on a core by first saving the state of the old process, then loading the state of the new thread.
• Note: the dispatcher is not itself a thread!
• Core can only do one thing at a time. If a thread is executing, dispatcher isn't: OS has lost control. How does OS regain control of core?
• Traps (events occurring in current thread that cause a change of control into the operating system):
  • System call.
  • Error (illegal instruction, addressing violation, etc.).
  • Page fault.
• Interrupts (events occurring outside the current thread that cause a state switch into the operating system):
  • Character typed at keyboard.
  • Completion of disk operation.
  • Timer: to make sure OS eventually gets control.
• How does dispatcher decide which thread to run next?
  • Plan 0: search process table from front, run first ready thread.
  • Plan 1: link together the ready threads into a queue. Dispatcher grabs first thread from the queue. When threads become ready, insert at back of queue.
  • Plan 2: give each thread a priority, organize the queue according to priority. Or, perhaps have multiple queues, one for each priority class.

• How the operating system creates a process:
  • Load code and data into memory.
  • Create and initialize process control block.
  • Create first thread with call stack.
  • Provide initial values for "saved state" for the thread
  • Make thread known to dispatcher; dispatcher "resumes" to start of new program.
• System calls for process creation in UNIX:
  • fork makes copy of current process, with one thread.
  • exec replaces memory with code and data from a given executable file. Doesn't return ("returns" to starting point of new program).
  • waitpid waits for a given process to exit.
  • Example:
    int pid = fork();if (pid == 0) { /* Child process */ exec("foo");} else { /* Parent process */ waitpid(pid, &status, options);}
  • Advantage: can modify process state before calling exec (e.g. change environment, open files).
  • Disadvantage: wasted work (most of forked state gets thrown away).
• System calls for process creation in Windows: