1. Chapter1: Introduction
1.1. What is an operating system
1.1.1. 1.2 System software that manages computer hardware, software resources, and provides common services for computer programs
1.1.2. 1.3 as an Extended Machine
1.1.3. 1.4 Resource Manager
1.2. History of Operating Systems
1.2.1. 2.1 First generation 1945 - 1955
1.2.2. 2.2 Second generation 1955 - 1965
1.2.3. 2.3 Third generation 1965 – 1980
1.2.4. 2.4 Fourth generation 1980 – present
1.3. Computer Hardware Review
1.3.1. 3.1 CPU
1.3.1.1. 3.1.1 PC Program Counter
1.3.1.2. 3.1.2 SP Stack Pointer
1.3.1.3. 3.1.3 PSW Program Status Word
1.3.1.4. General Registers
1.3.1.5. Instruction Cycle
1.3.1.6. Pipeline
1.3.1.7. Superscalar
1.3.1.8. System Call
1.3.2. 3.2 I/O Devices
1.3.3. 3.3 Buses
1.3.4. 3.4Memory
1.3.4.1. Registers
1.3.4.2. Caching
1.3.4.3. Main Memory
1.3.4.4. Relocation and Protection
1.4. The Operating System Zoo
1.4.1. 4.1 Mainframe
1.4.1.1. 4.1.1 batch,
1.4.1.2. 4.1.2 multi programmed
1.4.1.3. 4.1.3 time-sharing, multitasking
1.4.1.4. 4.1.4 Application: High-End Web Server, Servers for Business-To- Business transactions
1.4.2. 4.2 Server
1.4.3. 4.3 Real-time, smart card
1.4.4. 4.4 Multiprocessor
1.4.4.1. 4.4.1 Multiple CPU
1.4.4.2. 4.4.2 Share computer bus, clock
1.4.4.3. Advantage: High system throughput • High availability • Multiprocessor system and Multicomputer system
1.4.5. 4.5 Personal computer
1.4.5.1. 4.5.1 Many I/O devices
1.4.5.2. 4.5.2 Interface to single user
1.4.5.3. 4.5.3 Modern Personal computer operating systems support multiprogramming
1.4.5.4. 4.5.4 Examples: MS Windows, Mac OS, Solaris, Linux
1.4.6. 4.6 Handheld computer
1.4.6.1. 4.6.1 Personal digital assistant (PDA): Palmtop, Pocket-PC, Cellular phones
1.4.6.2. 4.6.2 Restriction of memory size, speed of CPU, screen size, powers
1.4.6.3. Operating System: Palm OS, Windows CE (Consumer Electronic)
1.4.7. 4.7 Embedded
1.4.7.1. 4.7.1 Run on the computers that control device
1.4.7.2. 4.7.2 Typical examples are microwave ovens, TV set, MP3 players.
1.4.7.3. 4.7.3 All the software is in ROM, no untrusted software
1.4.8. 4.8 Sensor Node
1.4.8.1. 4.8.1 Network of tiny sensor nodes
1.4.8.2. 4.8.2 Restriction of memory size, speed of CPU, Powers
1.4.9. 4.9 Real-time, smart card
1.4.9.1. 4.9.1 Time is a key parameter
1.5. Operating System Concepts
1.5.1. 5.1 OS Components
1.5.1.1. 5.1.1 Process Management
1.5.1.2. 5.1.2 Main Memory Management (Address Spaces)
1.5.1.3. 5.1.3 File management
1.5.1.4. 5.1.4. I/O Management
1.5.1.5. 5.1.5 Protection and Security
1.5.1.6. 5.1.6 Operating System Services (The Shell)
1.5.2. 5.2 Operating System Services
1.6. System Calls
1.6.1. 6.1 Making System Calls
1.6.2. 6.2 Major POSIX System Calls (Lab)
1.6.3. 6.3 Examples of System Calls (Lab)
1.7. Operating System Structure
1.7.1. 7.1 Monolithic systems
1.7.2. 7.2 Layered Systems
1.7.3. 7.3 Microkernel
1.7.4. 7.4 Client-server model
1.7.5. 7.5 Virtual Machines
1.7.6. 7.6 Exokernel
2. Chapter 2 : Processes and Threads
2.1. Processes
2.1.1. 1.1 The Process Model
2.1.1.1. 1.1.1 Multiprogramming of four programs
2.1.1.2. 1.1.2 Conceptual model of 4 independent, sequential processes
2.1.1.3. 1.1.3 Only one program active at any instant
2.1.2. 1.2 Process Concept
2.1.2.1. 1.2.1 An operating system executes a variety of programs
2.1.2.2. 1.2.2 Process – a program in execution; process execution must progress in sequential fashion
2.1.2.3. 1.2.3 A process resources includes :
2.1.3. 1.3 Process in Memory
2.1.4. 1.4 Process Creation
2.1.5. 1.5 Process Termination
2.1.6. 1.6 Process Hierarchies
2.1.6.1. 1.6.1 Parent creates a child process, child processes can create its own process
2.1.6.2. 1.6.2 Windows has no concept of process hierarchy
2.1.7. 1.7 Process States
2.1.7.1. 1.7.1 process : running ,blocked , ready
2.1.7.2. 1.7.2 Transitions between states shown
2.1.7.3. 1.7.3 Lowest layer of process-structured OS
2.1.8. 1.8 Process Control Block (PCB)
2.1.9. 1.9 context switch
2.1.10. 1.10 Implementation of Processes
2.1.10.1. 1.10.1 Fields of a process table entry
2.1.11. 1.11 Modeling Multiprogramming
2.2. Threads
2.2.1. 2.1 The Thread Model
2.2.1.1. 2.1.1 Three processes each with one thread
2.2.2. 2.2 Process with single thread
2.2.2.1. A process: Address space , Single thread of execution,Other resource (open..)
2.2.3. 2.3 Process with multiple threads
2.2.3.1. 2.3.1 Address space ,Multiple threads of execution, each thread has private set
2.2.4. 2.4 Single and Multithreaded Processes
2.2.5. 2.5 Items shared and Items private
2.2.5.1. 2.5.1 Items shared by all threads in a process
2.2.5.2. 2.5.2 Items private to each thread
2.2.6. 2.6 Benefits
2.2.6.1. 2.6.1 Responsiveness
2.2.6.2. 2.6.2 Resource Sharing
2.2.6.3. 2.6.3 Economy
2.2.7. 2.7 Thread Usage
2.2.7.1. 2.7.1 A word processor with three threads
2.2.7.2. 2.7.2 A multithreaded Web server
2.2.8. 2.8 Implementing Threads in User Space
2.2.8.1. 2.8.1 A user-level threads package
2.2.9. 2.9 Implementing Threads in the Kernel
2.2.9.1. 2.9.1 A threads package managed by the kernel
2.2.10. 2.10 Hybrid Implementations
2.2.10.1. 2.10.1 Multiplexing user-level threads onto kernel level thread
2.3. Inter process communication
2.3.1. 3.1 Cooperating Processes
2.3.1.1. 3.1.1 Independent
2.3.1.2. 3.1.2 Cooperating
2.3.2. 3.2 Problem of shared data
2.3.2.1. 3.2.1 Concurrent access to shared data may result in data inconsistency
2.3.2.2. 3.2.2 Maintaining data consistency requires mechanisms to ensure the orderly execution of cooperating processes
2.3.2.3. 3.2.3 Need of mechanism for processes to communicate and to synchronize their actions
2.3.3. 3.3 Race Conditions
2.3.4. 3.4 Critical Regions
2.3.5. 3.5 Solution: Mutual exclusion with Busy waiting
2.3.5.1. 3.5.1 Software proposal
2.3.5.2. 3.5.2 Hardware proposal
2.3.6. 3.6 Synchronous solution with Sleep & Wakeup
2.3.6.1. 3.6.1 Don't need system’s support
2.3.6.2. 3.6.2 Hard to extend
2.4. Scheduling
2.4.1. 4.1 Introduction to Scheduling
2.4.1.1. 4.1.1 CPU burst distribution
2.4.1.2. 4.1.2 CPU–I/O Burst Cycle – Process execution consists of a cycle of CPU execution and I/O wait
2.4.2. 4.2 Scheduling in Batch Systems
2.4.2.1. 4.2.1 First-Come, First-Served (FCFS) Scheduling
2.4.2.2. 4.2.2. FCFS Scheduling (Cont.)
2.4.2.3. 4.2.3 Shortest-Job-First (SJF) Scheduling
2.4.3. 4.3 Scheduling in Interactive Systems
2.4.4. 4.4 Priority Scheduling
2.4.5. 4.5 Scheduling in Real-Time Systems
2.4.5.1. 4.5.1 Hard real-time systems – required to complete a critical task within a guaranteed amount of time
2.4.5.2. 4.5.2 Soft real-time computing – requires that critical processes receive priority over less fortunate ones
2.4.6. 4.6 Policy versus Mechanism
2.4.6.1. 4.6.1 Separate what is allowed to be done with how it is done
2.4.6.2. 4.6.2 Scheduling algorithm parameterized
2.4.6.3. 4.6.3 Parameters filled in by user processes
2.4.7. 4.7 Thread Scheduling
2.4.7.1. 4.7.1 Local Scheduling – How the threads library decides which thread to put onto an available
2.4.7.2. 4.7.2 Global Scheduling – How the kernel decides which kernel thread to run next
3. Chapter 6: Deadlocks
3.1. Resource
3.1.1. 1.1 Examples of computer resources
3.1.1.1. 1.1.1 printers
3.1.1.2. 1.1.2 tape drives
3.1.1.3. 1.1.3 tables
3.1.2. 1.2 Processes need access to resources in reasonable order
3.1.3. 1.3 Must wait if request is denied
3.2. Introduction to deadlocks
3.2.1. 2.1 Four Conditions for Deadlock
3.2.2. 2.2 Deadlock Modeling
3.2.3. 2.3 Strategies for dealing with Deadlocks
3.3. . The ostrich algorithm
3.3.1. 3.1 Pretend there is no problem
3.3.2. 3.2 UNIX and Windows takes this approach
3.4. Deadlock detection and recovery
3.4.1. 4.1 One Resource of Each Type
3.4.2. 4.2 Detection with Multiple Resource of Each Type
3.4.3. 4.3 Recovery from Deadlock
3.5. Deadlock avoidance
3.5.1. 5.1 Resource Trajectories
3.5.1.1. 5.1.1 Two process resource trajectories
3.5.2. 5.2 Basic Facts
3.5.3. 5.3 Safe, Unsafe , Deadlock State
3.5.4. 5.4 The Banker's Algorithm for a Single Resource
3.5.5. 5.5 Banker's Algorithm for Multiple Resources
3.6. Deadlock prevention
3.6.1. 6.1 Attacking the Mutual Exclusion Condition
3.6.2. 6.2 Attacking the Hold and Wait Condition
3.6.3. 6.3 Attacking the No Preemption Condition
3.6.4. 6.4 Attacking the Circular Wait Condition
3.7. Other issues
3.7.1. 7.1 Two-Phase Locking
3.7.2. 7.2 Non resource Deadlocks
3.7.3. 7.3 Starvation
4. Chapter 3 : Memory Management
4.1. No Memory Abstraction
4.1.1. 1.1 Monoprogramming without Swapping or Paging
4.1.1.1. 1.1.1 Three simple ways of organizing memory
4.1.2. 1.2 Multiple Programs Without Memory Abstraction
4.2. Memory Abstraction
4.2.1. 2.1 Base and Limit Registers
4.2.1.1. 2.1.1 can be used to give each process a separate address space.
4.2.2. 2.2 Dynamic relocation using a relocation register
4.2.3. 2.3 Relocation and Protection
4.2.3.1. 2.3.1 Cannot be sure where program will be loaded in memory
4.2.3.2. 2.3.2 Use base and limit values
4.2.4. 2.4 HW address protection with base and limit registers
4.2.5. 2.5 Swapping
4.2.5.1. 2.5.1 Schematic View of Swapping
4.2.5.2. 2.5.2 Multiple-partition allocation
4.2.5.3. 2.5.3 Multiple-partition allocation
4.2.5.4. 2.5.4 Multiple-partition allocation
4.2.5.5. 2.5.5 Dynamic Storage-Allocation Problem
4.3. Virtual Memory
4.3.1. 3.1 separation of user logical memory from physical memory
4.3.2. 3.2 Paging
4.3.2.1. 3.2.1 Virtual address space can be noncontiguous; process is allocated physical memory whenever the latter is available
4.3.3. 3.3 Address Translation Scheme
4.3.3.1. 3.3.1 Page number (p), Page offset (d)
4.3.4. 3.4 Paging Hardware
4.3.5. 3.5 Two-level page tables
4.3.5.1. 3.5.1 , 32 bit address with 2 page table fields
4.3.5.2. 3.5.2. Two-level page tables
4.3.6. 3.6 Typical page table entry
4.3.7. 3.7 Implementation of Page Table
4.3.7.1. 3.7.1 Page-table base register (PTBR)
4.3.7.2. 3.7.2 Page-table length register (PRLR)
4.4. Page Replacement Algorithms
4.4.1. 4.1 Optimal Page Replacement Algorithm
4.4.1.1. 4.1.1 Replace page needed at the farthest point in future
4.4.2. 4.2 Not Recently Used Page Replacement Algorithm
4.4.2.1. 4.2.1 Each page has Reference bit, Modified bit
4.4.2.2. 4.2.2. Pages are classified
4.4.2.3. 4.2.3 NRU removes page at random
4.4.3. 4.3 FIFO Page Replacement Algorithm
4.4.3.1. 4.3.1 Maintain a linked list of all pages
4.4.3.2. 4.3.2 Page at beginning of list replaced
4.4.3.3. 4.3.3 Disadvantage: page in memory the longest may be often used
4.4.4. 4.4 Second Chance Page Replacement Algorithm
4.4.4.1. 4.4.1 The Clock Page Replacement Algorithm
4.4.5. 4.5 Least Recently Used (LRU)
4.4.5.1. 4.5.1 Assume pages used recently will used again soon
4.4.5.2. 4.5.2 Must keep a linked list of pages
4.4.5.3. 4.5.3 Alternatively keep counter in each page table entry
4.4.6. 4.6 LRU
4.4.7. 4.7 Simulating LRU in Software
4.4.8. 4.8 Working Set Page Replacement
4.4.9. 4.9 The WSClock Page Replacement Algorithm
4.5. Design Issues For Paging System
4.5.1. 5.1 Local versus Global Allocation Policies
4.5.2. 5.2 Separate Instruction and Data Spaces
4.5.3. 5.4 Shared Pages
4.5.3.1. 5.4.1 Two processes sharing the same program sharing its page table
4.5.4. 5.5 Shared Libraries
4.5.4.1. 5.5.1 A shared library being used by two processes
4.6. Implementation issues
4.6.1. 6.1 Operating System Involvement with Paging
4.6.1.1. 6.1.1 Four times when OS involved with paging: creation -execution- Page fault time-termination time
4.6.2. 6.2 Page Fault Handling
4.6.2.1. 6.2.1 Hardware traps to kernel
4.6.2.2. 6.2.2. General registers saved
4.6.2.3. 6.2.3. OS determines which virtual page needed
4.6.3. 6.3 Locking Pages in Memory
4.6.3.1. 6.3.1 • Virtual memory and I/O occasionally interact
4.6.3.2. 6.3.2 Procissues call for read from device into buffer
4.6.3.3. 6.3.3 • Need to specify some pages locked
4.6.4. 6.4 Backing Store
4.6.5. 6.5 Separation of Policy and Mechanism
4.7. Virtual Memory Segmentation
5. Chapter4 :File Systems
5.1. Files
5.1.1. 1.1 File Concept
5.1.1.1. 1.1.1 Long-term Information Storage
5.1.2. 1.2 File Naming
5.1.3. 1.3 File Structure
5.1.3.1. 1.3.1 Three kinds of files:
5.1.3.1.1. byte sequence
5.1.3.1.2. record sequence
5.1.3.1.3. tree
5.1.4. 1.4 File Types
5.1.4.1. 1.4.1 Contiguous logical address space
5.1.4.2. 1.4.2 Types: Data, program , Regular, special (character, block)
5.1.5. 1.5 File Access
5.1.5.1. 1.5.1 Sequential access
5.1.5.2. 1.5.2 Random access
5.1.6. 1.6 File Attributes
5.1.7. 1.7 File Operations
5.2. Directories
5.2.1. 2.1 Single-Level Directory Systems
5.2.2. 2.2 Hierarchical Directory Systems
5.2.2.1. 2.2.1 A hierarchical directory system
5.2.3. 2.3 Path Names
5.2.4. 2.4 Directory Operations
5.3. File System Implementation
5.3.1. 3.1 Allocation Methods
5.3.1.1. 3.1.1 : Contiguous allocation
5.3.1.2. 3.1.2 Linked allocation
5.3.1.3. 3.1.3 Indexed allocation
5.3.2. 3.2 Implementing Directories
5.3.3. 3.3 Shared Files
5.3.4. 3.4 Log-Structured File Systems
5.3.5. 3.5 Journaling File Systems
5.3.6. 3.6 Virtual File Systems
5.4. File system Management and Optimization
5.4.1. 4.1 Disk Space Management
5.4.2. 4.2 File System Backups
5.4.3. 4.3 File System Consistency
5.4.4. 4.4 Caching
5.4.5. 4.5 Reducing Disk Arm Motion
5.5. Example File Systems
5.5.1. 6.1 CD-ROM File Systems
5.5.1.1. 6.1.1 Recording structure of a CD or CD-ROM
5.5.1.2. 6.1.2 The ISO 9660 directory entry
5.5.2. 6.2 Rock Ridge Extensions
5.5.2.1. 6.2.1 PX - POSIX attributes
5.5.2.2. 6.2.2 PN - Major and minor device numbers
5.5.3. 6.3 Joliet Extensions
5.5.3.1. 6.3.1 Joliet extension fields:
5.5.3.1.1. Long file names
5.5.3.1.2. Unicode character set
5.5.4. 6.4 The MS-DOS File System
5.5.4.1. 6.4.1 The MS-DOS directory entry
5.5.4.2. 6.4.2 Maximum partition for different block sizes • The empty boxes represent forbidden combinations
5.5.5. 6.5 The UNIX V7 File System
6. Chapter 5 Input/Output
6.1. Principles of I/O Hardware
6.1.1. 5.1 Types of I/O devices
6.1.1.1. 5.1.1 Block and Character Devices
6.1.2. 5.2 Common concepts
6.1.2.1. 5.2.1 I/O Device Controller
6.1.2.2. 5.2.3 I/O Port
6.1.2.3. 5.2.3 I/O Bus
6.1.3. 5.3 A Typical PC Bus Structure
6.1.4. 5.4 I/O address
6.1.5. 5.5 Memory-Mapped I/O
6.1.6. 5.6 Data transfer Method between CPU and I/O device
6.1.6.1. 5.6.1 Three Data I/O transfer Methods:
6.1.6.1.1. 5.6.1.1 Programmed I/O Interrupt-Driven I/O Direct Memory Access
6.1.7. 5.7 Programmed I/O, Polling
6.1.7.1. 5.7.1 Determines state of device
6.1.8. 5.8 Interrupt-Driven I/O
6.1.9. 5.9 Precise and Imprecise Interrupts
6.1.10. 5.10 Direct Memory Access (DMA)
6.2. Principles of I/O Software
6.2.1. 2.1 Goals of I/O Software
6.2.1.1. 2.1.1 Device independence
6.2.1.2. 2.1.2 Uniform naming
6.2.1.3. 2.1.3 Error handling
6.2.2. 2.2 Programmed I/O
6.2.3. 2.3 Interrupt-Driven I/O
6.2.4. 2.4 I/O Using DMA
6.3. I/O Software Layers
6.3.1. 3.1 Interrupt Handlers
6.3.1.1. 3.1.1 Interrupt handlers are best hidden
6.3.1.2. 3.1.2 Interrupt procedure does its task
6.3.2. 3.2 Device Drivers
6.3.2.1. 3.2.1 Logical position of device drivers is shown here
6.3.2.2. 3.2.2 Communications between drivers and device controllers goes over the bus
6.3.3. 3.3 Device-Independent I/O Software
6.4. Disks
6.4.1. 4.1 Disk Hardware
6.4.2. 4.2 Magnetic Disks
6.4.3. 4.3 RAID
6.4.4. 4.4 CD-ROMs
6.4.5. 4.5 CD-Recordables
6.4.6. 4.6 DVD
6.4.7. 4.7 Disk Formatting
6.4.8. 4.8 Disk Arm Scheduling Algorithms
6.4.9. 4.9 Error Handling
6.4.10. 4.10 Stable Storage (
6.5. Clocks
6.5.1. 5.1 Clock Hardware
6.5.2. 5.2 Clock Software
6.5.3. 5.3 Soft Timers
6.6. User Interfaces: Keyboard, Mouse, Monitor
6.6.1. 6.1 Keyboard Software
6.6.2. 6.2 The X Window System
6.6.3. 6.3 Graphical User Interfaces
6.6.4. 6.4 Bitmaps
6.6.5. 6.7 Fonts
6.7. Thin Clients
6.7.1. 7. 1 The THINC protocol display commands.
6.8. Power Management
6.8.1. 8.1 Hardware Issues
6.8.2. 8.2 The Display
6.8.3. 8.3 The CPU