Chapter 10: Case Study 1: Unix and Linux
---


- timesharing was introduced in MIT's CTSS, which was the predecessor
  of MULTICS (Multiplexed Information and Computing Service);

- as Bell Labs jumped out of the MULTICS project, Ken Thompson decided
  to write his own stripped down version of MULTICS, given rise to UNIX;

- to avoid rewriting the whole system for each new architecture,
  Thompson decided to write the kernel in B, a simplified version
  of BCPL created by Thompson himself.  Because of some limitations, 
  Ritchie created a successor for B, called C.  Together, they 
  rewrote Unix in C;

- XENIX was Microsoft's Unix;

- after being broken up in 1984, AT&T release its version of Unix,
  called System III.  A better version, System V, appeared one year later;

- in 1993, AT&T sold its system to Novell, which then in 1995 sold it
  to Santa Cruz Operation (SCO);

- UCB got a copy of Unix Version 6 and created 1BSD, followed by 2BSD,
  both for the PDP-11;

- 4BSD included virtual memory, paging, longer filenames and an
  enhanced file system.  Also, TCP/IP was introduced.  This advances 
  made Sun, DEC and other big companies to adopt BSD instead of AT&T's
  Unix.

- in late 80's, IEEE guided the Unix standardization process, to
  create the POSIX (Portable Operating System) standard.

- Minix: Tanenbaum's microkernel-based Unix.

- whe Linux was being developed, AT&T was suing UCB for trademark
  infringement, which delayed the shipment of FreeBSD.  This gave
  time for Linux to get stable and widely distributed;

- Unix interface:

	- programs make system calls by putting the arguments in
	  registers and in the stack and issuing trap instructions
	  to switch from user to kernel mode;

- PROCESSES IN UNIX:

- process creation in Unix provides memory image isolation between
  parents and children;

- signals, or software interrupts, can be sent from on process to
  another;

- a process can only send signals to members of its process group (its
  parent, further ancestors, siblings, and children);

- if a process exits and its parent has not yet waited for it, the
  process becomes a zombie process, terminating when the parent waits
  for it;

- POSIX defines thread-related system calls, which can be implemented
  in either the kernel or user space;

- mutexes are intended for short-term locking, such as protecting a
  shared variable.  For long-term locking, threads should use
  condition variables;

- the kernel maintains two process-related data structures: the
  process table and the user structure.  The process table is always
  resident in memory, while the user structure can be paged out;

- information in the process table:

	- scheduling information;
	- memory image (pointers);
	- signals;
	- miscellaneous.

- the user structure contains information that is not needed while the
  process is swapped out, e.g. file information.  It includes:

	- machine registers;
	- system call state;
	- file descriptor table;
	- accounting;
	- kernel stack: a fixed stack used by the kernel part of the 
	  process;

- copy-on-write is used to avoid copying the whole virtual memory
  during process creation;

- BSD uses ULTs, while System V, Solaris, and Linux use kernel threads;

- there are problems when handling threads in the kernel:

	- when a process forks, should the child have all the threads
	  in the parent?  What happens if one of these threads was
 	  blocked waiting for the keyboard?  Not duplicating the 
	  threads may cause deadlocks, if for example the missing
	  thread was holding a mutex.

	- other problem is related to signal handling.  Which thread
	  should a SIGINT thrown by the keyboard?

	- Tanenbaum: "all solutions to these and other problems
	  usually cause something to break somewhere".

- Linux solves these problems by implementing the clone system call.
  In this syscall, a 5-bit flag is passed as parameter, wich specify:

	- CLONE_VM: share or not address space;
	- CLONE_FS: share mask, root, and working dirs;
	- CLONE_FILES: share file descriptors;
	- CLONE_SIGHAND: share the signal handler table;
	- CLONE_PID: new thread gets old PID;
 
- when a process waits for I/O, for example, it is put in a
  higher-priority queue, to minimize the time spent in the kernel;

- as Linux implements kernel threads, it schedules threads intead of
  processes;

- linux has three classes of threads for scheduling purposes:

	- real-time FIFO (highest priority);
	- real-time round robin;
	- timesharing;

- in linux, the higher the priority number, the better (in Unix, e.g.,
  I/O related operations are done with negative priority);

- each thread has an individual priority in the range [1,40].
  Classifying a thread as real-time adds a constant to its priority 
  to create a dynamic value (used for scheduling) called goodness;

- I/O-bounded threads get larger quanta and thus higher goodness than
  compute-bound threads;

- MEMORY MANAGEMENT

- processes in Unix have three segments: text, data and stack.  The
  text and the initialized data are part of the executable, which also
  contains a header specifying how much space should be allocated for
  uninitialized data at run time (will be zeroed out when allocated).
  
- when a program starts up, its stack is not empty, containing
  environment variables and arguments passed by the shell;

- the core map contains information about the contents of the page frames;

- the page deamon is waken up every 250ms and sees if a given number
  (fixed) of page frames is free.

- a swapper is called when the paging traffic is too big, taking
  complete process from memory (they stop competing for pages);

- dirty blocks are copied from the buffer cache to disk every 30 seconds;

- drivers are split in two parts. The top half runs in the context of
  the caller, while the bottom half runs in kernel mode.

- character devices do not use the buffer cache;

- FILE SYSTEM

- POSIX defines a flexible locking mechanism, through which a process
  can lock any number of bytes from a given file;

- locks are shared or exclusive;

- UNIX disk layout:

	- boot block::super block::i-nodes::data blocks

- BSD filesystem introduced the concept of cylinder groups, each with
  its own superblock, i-nodes, and data blocks.  This was done to
  avoid long seeks;

- another change made by BSD was to have two block sizes instead of
  one.

- SECURITY

- apart from the 9 permission bits used in Unix, a SETUID bit was
  added.  When a program with this bit set is executed, the effective
  UID for that process becomes the UID of the file's owner, instead
  of the one form the user that invoked the program.  It is the
  effective UID that is checked when a open request is handled;