Transcript CS 6560 Operating System Design

CS 6560 Operating System
Design
Lecture 2
Overview
• OS Structure
• Case Study: Linux
Operating System Structure
• Some Alternatives
– Monolithic Kernel – one big kernel program, not necessarily a mess as
Tanenbaum characterizes it
• Example: Linux
– Microkernel – run most of code in user mode, only a few functions reside
in kernel, other modules do most of the work
• Example: Mach
– http://www-2.cs.cmu.edu/afs/cs/project/mach/public/www/mach.html
• Example: HURD
– http://www.gnu.ai.mit.edu/software/hurd/hurd.html
– Layered System
• Example: the THE system by E. W. Dijkstra and his students
• Example: MULTICS
– Virtual Machines
• Examples: IBM VM/360, Java virtual machine (JVM), VMWare
– Exokernels – get away from the idea of abstracting hardware, concentrate
on multiplexing the computer’s resources, use libraries
• Example MIT : http://www.pdos.lcs.mit.edu/exo.html
– Distributed Systems
Kernel-based Systems (Monolithic)
System calls
General Purpose Functions
Device tables
Device Drivers
Device
Process Management
Application
Programs
Device
File Management
Interprocess Communication Management
Memory Management
Device
Device
Kernel
Microkernal-based Systems
Layered Systems (THE)
Distributed Systems
Case Study: Linux
• Ritchie and Thompson
• Bowman, et al.
• Mehta, et al.
Case Study Unix &Linux
•
•
•
•
•
10.1 History
Overview and Tour of Unix/Linux
Help
Program Development
Proc file system
Unix & Linux History
• MULTICS = MULTiplexed Information and
Computing Service
• Ken Thompson of AT&T Bell Labs began work on
stripped down version of MULTICS on a PDP-7
(used another computer to compile it)
• Brian Kernighan named it UNICS = UNIplexed
Information and Computing Service
• Named UNIX when it could compile itself.
• Dennis Ritchie joined.
More UNIX History
• Moved to PDP-11/20, then PDP-11/45 (256
KB), then PDP-11/70 (768 KB), the
Interdata 8/32
• Language
– First in assembly language (A)
– Then in B (a derivative of BCPL)
– Kernighan and Ritchie developed C and
Thompson and Ritchie rewrote UNIX in C.
More History
• 1974, Ritchie and Thompson wrote an paper
in Communications of ACM
– available online as 1978 revised version
– received ACM Turing award
• Spread to Universities, licensed by AT&T
AT&T Versions
• Thompson and Ritchie’s group (with complete source code)
– Version 6 – 8200 lines of C code and 900 lines of assembly
– Version 7 – 18,000 lines of C code and 2100 lines of assembly
– Versions 8, 9, 10
• AT&T commercial versions (after 1984 when AT&T was broken up)
– System III
– System V
• Release R2, R3, R4
• License sold to Novell in 1993 which sold it it to Santa Cruz Operation
in 1995
U C Berkeley Versions
• Funded by ARPA (= U S Department of
Defense Advanced Projects Agency )
• BSD = Berkeley Standard Distribution
• 1BSD, 2BSD, 3BSD, 4BSD
• 4BSD had virtual memory, long file names,
faster file system, vi, csh
Standardization of Unix
• Late 1980s: Two main version: BSD4.3 and AT&T SVR3,
plus many vendor versions, perhaps as many as 25
different versions
• AT&T: SVID (System V Interface Definition)
• IEEE: POSIX (Portable Operating System)
– 1003.1 defined interface to kernel as a set of library functions
• ANSI and ISO: Standardized C
• OSF = Open Software Foundation
• The Open Group – The Single UNIX Specification,
Version 3
– see: http://www.unix-systems.org/
MINIX
• Developed by Tanebaum as a teaching tool
• Microkernel design
• Size
– Microkernel: 1600 lines of C and 800 lines of assembly, plus
device drivers (2900 lines of C)
– File system: 5100 lines of C
– Memory: 2200 lines of C
• Version 2.0 in 1997 grew to 62,000 lines of C
LINUX
• Linus Torvalds – Finnish CS Student
• Borrowed ideas from MINIX: structure of source code,
layout of filesystem
• Monolithic kernel rather than Microkernel
• Sizes
– Version 0.01 (1991) 9,300 lines of C and 950 lines of assembly
– Version 1.0 (1994) 165,000 lines of C
– Version 2.0 (1996) 470,000 lines of C and 8000 lines of assembly
More on LINUX
• Free software
– Uses GNU Public License (GPL)
• Just the kernel – other parts of the system mainly
from the GNU project: www.gnu.org
• Some Web Sites:
– The Linux Kernel Archives
• www.kernel.org
– The Linux Documentation Project
• http://tldp.org/
– Linux Online
• http://www.linux.org/
Linux Versions
• Three numbers separated by periods
– First, the major version number (currently 2)
– Next, the minor version number (currently 6)
– Third, the release number
• Even minor numbers are stable releases and odd minor
numbers are developmental (beta) releases.
• Example: 2.6.22 is the current stable release of the current
stable kernel.
Unix Design Goals
Unix Design Goals and Principles
–
–
–
–
–
–
–
–
–
–
timesharing
simplicity
multiple processes
construction set approach: pipes and filters
designed by programmer for programmers
flexibility
unity
written in HLL (C)
on-line documentation
local maintenance
Some More Books
• Stones and Mathew, Beginning Linux Programming, Wrox.
• Stevens, Advanced Programming in the UNIX Environment.
• Keith Haviland, Dina Gray, Ben Salama, UNIX System Programming,
Addison Wesley, 1987.
• Maurice J. Bach, The Design of the UNIX Operating System, PrenticeHall, 1986.
• Brian W. Kernighan and and Dennis M. Ritchie, The C Programming
Language, Prentice-Hall, 2nd Edition, 1988.
• S. Leffler, M. McKusick, M. Karels, J. Quarterman, The Design and
Implementation of the 4.3BSD UNIX Operating System, AddisonWesley, 1989.
• Evi Nemeth, Garth Snyder, and Scott Seebas, UNIX System
Administration Handbook, Prentice-Hall, latest edition.
Software Architecture of Linux
• References:
– Bowman, Holt, Brewster, Linux as a Case Study, ICSE
1999.
– Nikunj R. Mehta, Nenad Medvidovic, Sandeep Phadke,
Towards a Taxonimy of Software Connectors, ICSE
2000.
• Levels of analysis
– Conceptual – high level based on documentation and
discussions
– Concrete – lower level, based on computation of
software connections
• Application to Linux
– Open source – entire source code can be examined
electronically
Bowman: Methodology
• Conceptual
– Consult Linux documentation
– Consult descriptions of related operating systems
• Concrete
– Use conceptual architecture as starting point
– Group source files into subsystems
– Use software tools to extract procedure calls, variable
references
– Determine relationships between source files
– Use relationships between source files and clustering of
files to determine relationships between subsystems
Source Code Organization
linux-2.4
include
kernel
mm
init
fs
lib
ipc
crypto
Documentation
net
drivers
abi
configs
arch
scripts
Results of Bowman Study
• Subsystems
–
–
–
–
–
–
–
Process Scheduler
Memory management
File System
Interprocess Communications
Network Interface
Library
Initialization
• Connections
• More connections at concrete model – nearly a complete graph
Comments by Mehta, et al.
• Procedure calls and data references don’t
give a clear picture of a system’s
architecture
• Higher level constructs called connectors
are more valuable
From Bowman’s Linux Conceptual Arch
File System
Memory
Manager
Network
Interface
Process
Scheduler
Initialization
Interprocess
Communication
Library
Bowman’s Kernel Subsystems
•
Process Scheduler
– Provides dynamic priority-based multitasking for user and kernel processes
– Provides primitives for creating and terminating processes
•
Memory Manager (mm)
–
–
–
–
•
Provides separate virtual memory addressing space for each user process
Uses swapping to support memory overbooked sharing
Provides physically and logically contiguous memory for kernel
Provides object caching for kernel
File System (fs)
– Provides uniform access to hardware and virtual devices from multiple types of file
systems
– Provides a dynamic tree-structured directory system for files
•
Network Interface (net)
– Provides access to network devices
•
Interprocess Communication (IPC)
– Provides communication facilities among processes on the same system
•
Initialization
– Initializes the Linux kernel on start up.
•
Library
– Provides routines that are used throughout the kernel.
Bowman’s FS Conceptual Arch
•
Device Drivers
– Performs all communications with supported hardware devices
•
Logical File Systems
– Implements a variety logical file systems that can be placed on physical devices
•
Executable File Formats
– Supports a variety of executable formats
•
File Quota
– Allows system administrators to limit the amount of file storage that individual
users may use
•
Buffer Cache
– Optimizes access to block devices by using virtual memory buffers
•
System Call Interface
– Provides uniform user program interface to file system
•
Virtual File System (VFS)
– Provides uniform kernel interface to file system
Bowman’s Concrete Arch for FS
Network
Interface
Memory
Manager
System
Call
Interface
Executable
File
Formats
Virtual
File
System
Logical
File
Systems
Device
Drivers
Buffer
Cache
Init
File
Quota
Process
Scheduler
IPC