A Crash Course in Operating Systems

• Basic concepts of execution.
• Caching and swapping
• Mapping and context switching.
• Processes and scheduling
• Buffered input and output.
• Filesystems and inodes.

Peeling the Onion Several Ways

• Complex systems have multiple decompositions.
• Each shows a different aspect of the system.
• All are valid ways of understanding a system.
• They overlap and interrelate.
• Key to system administration is to choose the simplest model that describes the situation.

First layer: machines and operating system

• Machines
• Operating system
• Memory
• Disk
• Files
• Processes
• Runlevels
• Users
• Groups
• Shells
• Environments
• Applications

Machine:

• "bare metal": just hardware.
• "built machine": combination of hardware and software.
• "running machine": a collection of hardware and software that has a specific effect.
• "bootstrapping": taking a machine, in small steps, from non-working to working.

Semantic Bootstrapping

• Building a semantic model, from simple components.
• Start small, refine model as needed.
• Stop when enough detail is present to understand the problem.
• Often, this requires removing detail from the model.

Machine Components

• Memory
• CPU
• Peripherals
  • Disk
  • network
  • printing
• Oversimplified view:
  
  • CPU: Central Processing Unit: responsible for "computation"
  • Memory: where processes reside.
  • Devices: external things like network and disk.
  • Memory bus: method by which CPU reads and writes memory
    • Fast
    • Word grain: write or read one word at a time.
  • Device bus: method by which CPU reads and writes disk.
    • Slower
    • (Typically) Block grain: writes or reads a "block" of memory at a time (whose size varies, e.g., 512 bytes, 1 kb, 4 kb).

What can we forget?

• Basic skill: using a minimal model.
• What is the simplest model we can use?
• Must be complex enough to describe what happens when we make changes.
• Must be simple enough to understand.

Memory

• any way of storing information.
• best modelled as "blocks of bytes"
• A byte is 8 bits of memory.
• A word is either 16, 32, or 64 bits of memory. This is determined by the data bus width, an attribute of the CPU.
• A page is usually 4096=2^12 bytes of memory (it can vary).

Disk

• Disk: a device that contains blocks of bits.
• Partition: a distinguished section of a disk.
• Swap partition: on a disk, a partition that can substitute for memory.
• Filesystem: on a partition, a structure that contains files.
• Directories: containers that contain files
• Files: streams of bits.
• Protections: who can get to what files or directories.
• Oversimplified view:
  

Tiered Memory

• Idea: construct a system of memory with varying speeds, from very fast and expensive to very slow and inexpensive.
• Cache: close to processor.
  • Very fast (e.g., 2ghz)
  • Very expensive
  • Small (256kb)
• Physical : actual memory in machine.
  • Fast (e.g., 300 mhz)
  • Expensive
  • Relatively larger (512MB)
• Virtual: borrowed from disk.
  • Slow
  • Cheap
  • Very large (e.g., multiple GB)
• Oversimplified view:
  

Paging

• At any time, the CPU is reading or modifying words of memory in the cache.
• This memory maps to (is equivalent with) physical memory.
• At any time, the cache contains images of a few pages of physical memory.
• One page=4096 bytes (can vary).
• Paging determines which pages of physical memory are in cache at any time.

Physical/Cache Paging Algorithm

• At any one time, CPU is reading or modifying one or more words of cache.
• These correspond through mapping to particular words of physical memory.
• When a word is needed for reading or writing, "page in" the page (4096 bytes) containing it. This creates a copy in cache.
• When another page is needed, and there's no free page, "page out" the page that is "least recently used". This is a matter of copying it back to physical memory.
• Lots of other details on paging are unimportant. See Comp111 (operating systems) for more details.

Swapping

• At any time, the CPU contains only part of the memory it has available, the rest is virtual memory on disk
• If the operating system runs out of physical memory, it "swaps out" the page least recently used to disk. This makes a copy on disk and reuses the page.
• If the CPU needs a page, and it's on disk (virtual), the operating system "swaps in" the memory from disk.

Memory states

• A particular byte/page of memory can be in three states:
  1. cached
  2. physical
  3. virtual

Paging/Swapping Caveats

• Paging saves time (use a faster bus for CPU access than available in the machine)
  • Part of hardware.
  • Transparent to operating system.
• Swapping is slow, but saves memory.
  • Part of software and operating system.
  • Must be consciously managed by OS.
• "Swap heaven": a process is so large that it spends all of its time in swapping memory on and off of disk.
• "Superlinear speedup": when the data for a process gets small enough that it fits entirely into cache (<256kb), the process suddenly speeds up enormously.

Problem of the day

• Suppose you have a computer containing 4 8-byte pages of physical memory, 2 8-byte pages of cache, and 10 8-byte pages of swap. Suppose you run a program that occupies 12 pages of memory.

1. Give a plausible picture of the initial load image for the program, labelling its pages 0-11, presuming that the program will be allocated into memory from page 0 to page 11 and that pages that don't fit will be virtualized.
2. Suppose the program starts running in the first byte of page 0 and its first instruction accesses data in page 10. Draw a picture of all of memory after this access, labelling each page with the number of the page of the program whose data it contains.
3. Suppose the next instruction, still in page 0, accesses data in page 7. What will memory look like after this?

Spying on swapping: vmstat

• Tool for looking at swapping: vmstat

   lin09{couch}54: vmstat
      procs                      memory      swap          io     system      cpu
    r  b  w   swpd   free   buff  cache   si   so    bi    bo   in    cs us sy id
    1  0  0      0   2780  44568  46172    0    0     1     2   19     2  0  0  9
  

• procs: process count
  • r: running
  • b: blocked (not runnable; sleeping)
  • w: waiting (runnable when there is time)
• memory: status of physical memory
  • swpd: kb swapped out.
  • free: kb of unused memory.
  • buff: kb used as OS buffers.
  • cache: kb of cache in use.
• swap: swapping (virtual memory) statistics
  • si: # of blocks swapped in.
  • so: # of blocks swapped out.
• io: input/output statistics
  • bi: blocks in (read).
  • bo: blocks out (write).

Operating system

• So far, the computer is just one big bag of memory.
• Want to split this memory up into functional units that perform specific tasks.
• First component: the operating system.
• This is nothing more than a big program executing in memory, that can execute other programs.

UNIX Architecture

• The UNIX/Linux operating system is broken down into a few functional parts:
  
• The Kernel: the actual operating system program that runs all the time on the computer.
  • Talks with devices
  • Implements reusable subroutines that other programs can use.
  • Handles "scheduling" and "mapping" of other programs that run under control of the kernel.
• Libraries: functions that extend the function of the Kernel and can be called by other programs.
• Applications: programs that can run under control of the Kernel.
• Shell: the user interface: allows a user to run an application.

Processes

• So far, we have a kernel program that is running. We want to run our own programs as well.
• A functional unit of memory intended to be executed as an independent program is called a process.
• Crucial concept: memory mapping.

Mapping

• Memory mapping: make each process's view of memory
  • the same each time the particular process is executed.
  • different from that for any other process (excepting shared memory applications).
  • isolated from the operating system
• Oversimplified view:
  
• Again, process memory is mapped in pages.
• Each process gets a random sample of real pages.
• Pages are mapped from OS memory addresses to addresses in process space.
• Accomplished by specialized hardware.

Kinds of memory maps

• System: used by the operating system program (vmlinux) itself.
• User: used by a process managed by the operating system

Get used to it: overlapping layers

• We are used to describing systems via hierarchies
• A computer system is not just a hierarchy; it consists of overlapping layers that complement one another.
• A particular memory byte has
  • A cache state (cached, physical, virtual)
  • A map state (system or user)
  • Assignment to a particular process.
  • OS-relative address.
  • Process-relative address.
• These are all attributes of different layers of meaning about the same object.
• This kind of overlapping layering is typical in system and network administration.
• From the point of view of the operating system, all memory is in its control and consists of system memory and mapped processes.

Contexts

• An execution context is that information that a particular process requires in order to execute.
  • Which instruction the CPU is executing.
  • Contents of all CPU "registers"
  • What memory map is in effect.
  • Etc.
• Context-switching: the process of switching from executing one process to executing another.
• Scheduling: the process of determining when to switch contexts.
• Threads: multiple processes that mostly share one execution context. Also called "lightweight processes". E.g., a set of processes with the same memory map and differing execution stacks and instruction pointers.

How the OS copes with processes:

• Process table: a list of the processes currently running; this is where the execution context for each process is stored (in system memory).
• Each process in the table is assigned:
  • An execution context.
  • A scheduling priority. This is a number between -20 and 20 indicating how important it is for the process to complete its task. Low numbers indicate high priorities. The highest priority is -20, the lowest is +20.
  • A unique process identifier: a number uniquely identifying the process.
  • A unique parent identifier: what is the number of the process that spawned you?

The process scheduler:

• One process (or the OS) can run at a time
• Time-slice execution: run one process for awhile and then switch to another.
• Scheduling priority determines how often a process is run.
• Scheduling grain determines for how long a process runs at a time.

Spying on processes: ps

• ps: tell me about my processes:

   lin09{couch}74: ps
     PID TTY          TIME CMD
   12946 pts/1    00:00:00 tcsh
   13141 pts/1    00:00:00 ps
  

• ps -e: tell me about all processes:

   lin09{couch}75: ps -e
     PID TTY          TIME CMD
       1 ?        00:00:07 init
       2 ?        00:00:00 keventd
       3 ?        00:00:00 kapmd
       4 ?        00:00:02 ksoftirqd_CPU0
       9 ?        00:00:00 bdflush
       5 ?        00:00:02 kswapd
       6 ?        00:00:00 kscand/DMA
       7 ?        00:00:00 kscand/Normal
       8 ?        00:00:00 kscand/HighMem
      10 ?        00:00:00 kupdated
      11 ?        00:00:00 mdrecoveryd
   ...
   16238 ?        00:00:01 httpd
   16239 ?        00:00:01 httpd
   16240 ?        00:00:01 httpd
   12943 ?        00:00:00 sshd
   12945 ?        00:00:00 sshd
   12946 pts/1    00:00:00 tcsh
   13142 pts/1    00:00:00 ps
  

• ps -ef: tell me most everything about processes

   lin09{couch}76: ps -ef
   UID        PID  PPID  C STIME TTY          TIME CMD
   root         1     0  0 Jan06 ?        00:00:07 init
   root         2     1  0 Jan06 ?        00:00:00 [keventd]
   root         3     1  0 Jan06 ?        00:00:00 [kapmd]
   root         4     1  0 Jan06 ?        00:00:02 [ksoftirqd_CPU0]
   root         9     1  0 Jan06 ?        00:00:00 [bdflush]
   root         5     1  0 Jan06 ?        00:00:02 [kswapd]
   root         6     1  0 Jan06 ?        00:00:00 [kscand/DMA]
   root         7     1  0 Jan06 ?        00:00:00 [kscand/Normal]
   root         8     1  0 Jan06 ?        00:00:00 [kscand/HighMem]
   root        10     1  0 Jan06 ?        00:00:00 [kupdated]
   root        11     1  0 Jan06 ?        00:00:00 [mdrecoveryd]
   ...
   apache   16238   747  0 Jan25 ?        00:00:01 /usr/sbin/httpd
   apache   16239   747  0 Jan25 ?        00:00:01 /usr/sbin/httpd
   apache   16240   747  0 Jan25 ?        00:00:01 /usr/sbin/httpd
   root     12943   672  0 16:30 ?        00:00:00 /usr/sbin/sshd
   couch    12945 12943  0 16:30 ?        00:00:00 /usr/sbin/sshd
   couch    12946 12945  0 16:30 pts/1    00:00:00 -tcsh
   couch    13153 12946  0 16:44 pts/1    00:00:00 ps -ef
  

Fundamental goals of the OS

• Manage memory and resources.
• Initialize and schedule processes.
• Interact with devices.
• Basic problem: neither physical memory nor cache is persistent after a power failure.
• Need some form of persistent storage whose contents survive a power failure.

Filesystems

• A different use of disk than "swap".
• Actually, a structure imposed on a partition.
• Contains a directory structure that can contain files.
• Directories are special kinds of files that point to other files.

Filesystem structure.

• Two parts of any filesystem
  • Inodes("identity nodes"): descriptors for files and directories.
  • Blocks: content of files.
• Inodes contain
  • a unique inode number that uniquely identifies the inode within a given filesystem.
  • ownership and protection information for the file.
  • a pointer to the first block of the content.
  • a pointer to the next used or free inode.
• Blocks contain:
  • data content.
  • a pointer to the next block in the file.
  • a pointer to the next block in the used or free list.

Oversimplified model of how a filesystem works:

• Inodes are stored in an inode table, essentially an array.
• There are two linked lists of inodes, a free list and a used list.
• Blocks are also tracked via two linked lists, a free list and a used list.
• To create a file,
  • choose a block from the free block list, unlink from free block list and put into used block list.
  • choose an inode from the free inode list, unlink from free inode list, link it into the used inode list.
  • Point the inode at the block.
• This gives a one-block-long file.
• To delete a file,
  • Go to its inode, get the head of the block list.
  • unlink all elements of the block list from the used list, put them back into the free list.
  • unlink the inode from the used inode list, link into free inode list.
• What's oversimplified?
  • Free and used hashes, not lists.
  • Goal: use defragmented blocks to represent files.
  • Journalling: some filesystems modify a change journal instead of modifying the file contents directly.
  • Lots of other fancy features.

Very important notes on files

• "I'm givin' you a number, and taking 'way yo' name!"
• There is no naming information in an inode!
• File writes to a filesystem are cached just like memory and in much the same way.
  • Read a block.
  • Modify memory image of the block.
  • Write the block back to the disk.
• Problem with this caching is that it is done lazily
  • When the system is idle (no processes in run state).
  • When filesystem table caches are full.

Directories

• A directory is a kind of file.
• It's a map from names to numbers.
• Each number is an address of the next inode in a path.
• A directory contains no information on the owner, protection, or attributes of a file.
• A directory contains only one level of information.

Example: /usr/bin/gcc

• Each inode contains the address of the next directory block.
• Each directory contains the number of the inode of the next directory.

Directory requirements

• Every directory contains
  • '.': a pointer to the current directory that contains the inode number of the directory itself.
  • '..': a pointer to the parent directory containing this one.
• Caveats:
  • There is a top level directory in any filesystem, known as the root.
  • The root is its own parent.
  • given a pathname, e.g., /usr/bin/gcc, it's easy to get to the inode of the file. This is a list traversal.
  • given an inode, e.g., 42, it's hard to get back the pathname. This requires traversing to parents.

Problem of the day

• Consider the following list of inodes

   Inode  |  First block
       1  |           40 (dir) 
       3  |           45 (dir) 
       4  |           20 (file)  
       8  |           34 (dir) 
  

  and the following list of blocks, containing directories:

   Block  |  Pathname  | Inode
   -------+------------+---------
      34  |  foo       | 1 
          |  bar       | 4 
   -------+------------+---------
      40  |  cat       | 3
          |  dog       | 8 
   -------+------------+---------
      45  |  cat       | 4
          |  dog       | 8 
  

  Suppose the root inode is 8 and that this describes a root filesystem, starting at '/' with inode 8. Then:

1. what is the inode number of /foo/cat?
2. Give all possible absolute pathnames of inode 8.

The Super Block

• In a filesystem, the "Super block" tells where to locate the start of the inode and block tables, as well as where the root inode is.
• If this information is lost, the filesystem is nonsense.
• This information is so important that it is replicated throughout a filesystem, in several places.

Filesystems and the OS

• Mount table: describes where available filesystems are.
• Contents include
  • Filesystem location (device and partition)
  • Mount point: where to put root directory in normal filesystem.

Files and the OS

• Several OS data structures describe files.
• System file descriptor table: contains data on all open files.
• Process file descriptor table: contains data on files opened by particular processes.
• Process file descriptors are aliases: if two processes open the same file, they are using the same descriptor. If they write into it, their writes are concatenated!

File caching

• Similar concept to memory caching
• Each open file exists both on disk and in memory, in a set of file buffers.
• To read a word, read its block into a buffer in memory.
• To write a word, read its block into a buffer and change it in memory.
• Eventually, when there is time or one is out of memory, write changed cached buffer blocks back to disk.

Kinds of files and directories

• System : used in running OS.
• Application : used by processes.
• User : created by users for user needs.

Another taxonomy of files

• Programs : things that can execute on the machine.
• Scripts: things that can be interpreted as lists of commands.
• Configuration : files that tell programs how to work.
• Data : files that contain program data.