第1页 / 共643页
第2页 / 共643页
第3页 / 共643页
第4页 / 共643页
第5页 / 共643页
第6页 / 共643页
第7页 / 共643页
第8页 / 共643页
操作系统三个简单的部分Operating Systems: Three Easy Pieces.pdf
To Everyone
To Educators
To Students
Acknowledgments
Final Words
References
A Dialogue on the Book
Introduction to Operating Systems
Virtualizing the CPU
Virtualizing Memory
Concurrency
Persistence
Design Goals
Some History
Summary
References
Virtualization
A Dialogue on Virtualization
The Abstraction: The Process
The Abstraction: A Process
Process API
Process Creation: A Little More Detail
Process States
Data Structures
Summary
References
Interlude: Process API
The fork() System Call
Adding wait() System Call
Finally, the exec() System Call
Why? Motivating the API
Other Parts of the API
Summary
References
Mechanism: Limited Direct Execution
Basic Technique: Limited Direct Execution
Problem #1: Restricted Operations
Problem #2: Switching Between Processes
Worried About Concurrency?
Summary
References
Homework (Measurement)
Scheduling: Introduction
Workload Assumptions
Scheduling Metrics
First In, First Out (FIFO)
Shortest Job First (SJF)
Shortest Time-to-Completion First (STCF)
Round Robin
Incorporating I/O
No More Oracle
Summary
References
Homework
Scheduling: The Multi-Level Feedback Queue
MLFQ: Basic Rules
Attempt #1: How to Change Priority
Attempt #2: The Priority Boost
Attempt #3: Better Accounting
Tuning MLFQ And Other Issues
MLFQ: Summary
References
Homework
Scheduling: Proportional Share
Basic Concept: Tickets Represent Your Share
Ticket Mechanisms
Implementation
An Example
How To Assign Tickets?
Why Not Deterministic?
Summary
References
Homework
Multiprocessor Scheduling (Advanced)
Background: Multiprocessor Architecture
Don't Forget Synchronization
One Final Issue: Cache Affinity
Single-Queue Scheduling
Multi-Queue Scheduling
Linux Multiprocessor Schedulers
Summary
References
Summary Dialogue on CPU Virtualization
A Dialogue on Memory Virtualization
The Abstraction: Address Spaces
Early Systems
Multiprogramming and Time Sharing
The Address Space
Goals
Summary
References
Interlude: Memory API
Types of Memory
The malloc() Call
The free() Call
Common Errors
Underlying OS Support
Other Calls
Summary
References
Mechanism: Address Translation
Assumptions
An Example
Dynamic (Hardware-based) Relocation
OS Issues
Summary
References
Homework
Segmentation
Segmentation: Generalized Base/Bounds
Which Segment Are We Referring To?
What About The Stack?
Support for Sharing
Fine-grained vs. Coarse-grained Segmentation
OS Support
Summary
References
Homework
Free-Space Management
Assumptions
Low-level Mechanisms
Basic Strategies
Other Approaches
Summary
References
Paging: Introduction
Where Are Page Tables Stored?
What's Actually In The Page Table?
Paging: Also Too Slow
A Memory Trace
Summary
References
Homework
Paging: Faster Translations (TLBs)
TLB Basic Algorithm
Example: Accessing An Array
Who Handles The TLB Miss?
TLB Contents: What's In There?
TLB Issue: Context Switches
Issue: Replacement Policy
A Real TLB Entry
Summary
References
Homework (Measurement)
Paging: Smaller Tables
Simple Solution: Bigger Pages
Hybrid Approach: Paging and Segments
Multi-level Page Tables
Inverted Page Tables
Swapping the Page Tables to Disk
Summary
References
Homework
Beyond Physical Memory: Mechanisms
Swap Space
The Present Bit
The Page Fault
What If Memory Is Full?
Page Fault Control Flow
When Replacements Really Occur
Summary
References
Beyond Physical Memory: Policies
Cache Management
The Optimal Replacement Policy
A Simple Policy: FIFO
Another Simple Policy: Random
Using History: LRU
Workload Examples
Implementing Historical Algorithms
Approximating LRU
Considering Dirty Pages
Other VM Policies
Thrashing
Summary
References
Homework
The VAX/VMS Virtual Memory System
Background
Memory Management Hardware
A Real Address Space
Page Replacement
Other Neat VM Tricks
Summary
References
Summary Dialogue on Memory Virtualization
Concurrency
A Dialogue on Concurrency
Concurrency: An Introduction
An Example: Thread Creation
Why It Gets Worse: Shared Data
The Heart of the Problem: Uncontrolled Scheduling
The Wish For Atomicity
One More Problem: Waiting For Another
Summary: Why in OS Class?
References
Homework
Interlude: Thread API
Thread Creation
Thread Completion
Locks
Condition Variables
Compiling and Running
Summary
References
Locks
Locks: The Basic Idea
Pthread Locks
Building A Lock
Evaluating Locks
Controlling Interrupts
Test And Set (Atomic Exchange)
Building A Working Spin Lock
Evaluating Spin Locks
Compare-And-Swap
Load-Linked and Store-Conditional
Fetch-And-Add
Summary: So Much Spinning
A Simple Approach: Just Yield, Baby
Using Queues: Sleeping Instead Of Spinning
Different OS, Different Support
Two-Phase Locks
Summary
References
Lock-based Concurrent Data Structures
Concurrent Counters
Concurrent Linked Lists
Concurrent Queues
Concurrent Hash Table
Summary
References
Condition Variables
Definition and Routines
The Producer/Consumer (Bound Buffer) Problem
Covering Conditions
Summary
References
Semaphores
Semaphores: A Definition
Binary Semaphores (Locks)
Semaphores As Condition Variables
The Producer/Consumer (Bounded-Buffer) Problem
Reader-Writer Locks
The Dining Philosophers
How To Implement Semaphores
Summary
References
Common Concurrency Problems
What Types Of Bugs Exist?
Non-Deadlock Bugs
Deadlock Bugs
Summary
References
Event-based Concurrency (Advanced)
The Basic Idea: An Event Loop
An Important API: select() (or poll())
Using select()
Why Simpler? No Locks Needed
A Problem: Blocking System Calls
A Solution: Asynchronous I/O
Another Problem: State Management
What Is Still Difficult With Events
Summary
References
Summary Dialogue on Concurrency
Persistence
A Dialogue on Persistence
I/O Devices
System Architecture
A Canonical Device
The Canonical Protocol
Lowering CPU Overhead With Interrupts
More Efficient Data Movement With DMA
Methods Of Device Interaction
Fitting Into The OS: The Device Driver
Case Study: A Simple IDE Disk Driver
Historical Notes
Summary
References
Hard Disk Drives
The Interface
Basic Geometry
A Simple Disk Drive
I/O Time: Doing The Math
Disk Scheduling
Summary
References
Homework
Redundant Arrays of Inexpensive Disks (RAIDs)
Interface And RAID Internals
Fault Model
How To Evaluate A RAID
RAID Level 0: Striping
RAID Level 1: Mirroring
RAID Level 4: Saving Space With Parity
RAID Level 5: Rotating Parity
RAID Comparison: A Summary
Other Interesting RAID Issues
Summary
References
Homework
Interlude: File and Directories
Files and Directories
The File System Interface
Creating Files
Reading and Writing Files
Reading And Writing, But Not Sequentially
Writing Immediately with fsync()
Renaming Files
Getting Information About Files
Removing Files
Making Directories
Reading Directories
Deleting Directories
Hard Links
Symbolic Links
Making and Mounting a File System
Summary
References
Homework
File System Implementation
The Way To Think
Overall Organization
File Organization: The Inode
Directory Organization
Free Space Management
Access Paths: Reading and Writing
Caching and Buffering
Summary
References
Homework
Locality and The Fast File System
The Problem: Poor Performance
FFS: Disk Awareness Is The Solution
Organizing Structure: The Cylinder Group
Policies: How To Allocate Files and Directories
Measuring File Locality
The Large-File Exception
A Few Other Things About FFS
Summary
References
Crash Consistency: FSCK and Journaling
A Detailed Example
Solution #1: The File System Checker
Solution #2: Journaling (or Write-Ahead Logging)
Solution #3: Other Approaches
Summary
References
Log-structured File Systems
Writing To Disk Sequentially
Writing Sequentially And Effectively
How Much To Buffer?
Problem: Finding Inodes
Solution Through Indirection: The Inode Map
The Checkpoint Region
Reading A File From Disk: A Recap
What About Directories?
A New Problem: Garbage Collection
Determining Block Liveness
A Policy Question: Which Blocks To Clean, And When?
Crash Recovery And The Log
Summary
References
Data Integrity and Protection
Disk Failure Modes
Handling Latent Sector Errors
Detecting Corruption: The Checksum
Using Checksums
A New Problem: Misdirected Writes
One Last Problem: Lost Writes
Scrubbing
Overheads Of Checksumming
Summary
References
Summary Dialogue on Persistence
A Dialogue on Distribution
Distributed Systems
Communication Basics
Unreliable Communication Layers
Reliable Communication Layers
Communication Abstractions
Remote Procedure Call (RPC)
Summary
References
Sun's Network File System (NFS)
A Basic Distributed File System
On To NFS
Focus: Simple and Fast Server Crash Recovery
Key To Fast Crash Recovery: Statelessness
The NFSv2 Protocol
From Protocol to Distributed File System
Handling Server Failure with Idempotent Operations
Improving Performance: Client-side Caching
The Cache Consistency Problem
Assessing NFS Cache Consistency
Implications on Server-Side Write Buffering
Summary
References
The Andrew File System (AFS)
AFS Version 1
Problems with Version 1
Improving the Protocol
AFS Version 2
Cache Consistency
Crash Recovery
Scale And Performance Of AFSv2
AFS: Other Improvements
Summary
References
Summary Dialogue on Distribution
General Index
Asides
Tips
Cruces
OPERATING SYSTEMS
THREE EASY PIECES
REMZI H. ARPACI-DUSSEAU
ANDREA C. ARPACI-DUSSEAU
UNIVERSITY OF WISCONSIN–MADISON
. .
c 2014 by Arpaci-Dusseau Books, Inc.
All rights reserved
i
To Vedat S. Arpaci, a lifelong inspiration
c 2014, ARPACI-DUSSEAU
THREE
EASY
PIECES
Preface
To Everyone
Welcome to this book! We hope you’ll enjoy reading it as much as we enjoyed
writing it. The book is called Operating Systems: Three Easy Pieces, and the title
is obviously an homage to one of the greatest sets of lecture notes ever created, by
one Richard Feynman on the topic of Physics [F96]. While this book will undoubt-
edly fall short of the high standard set by that famous physicist, perhaps it will be
good enough for you in your quest to understand what operating systems (and
more generally, systems) are all about.
The three easy pieces refer to the three major thematic elements the book is
organized around: virtualization, concurrency, and persistence.
In discussing
these concepts, we’ll end up discussing most of the important things an operating
system does; hopefully, you’ll also have some fun along the way. Learning new
things is fun, right? At least, it should be.
Each major concept is divided into a set of chapters, most of which present a
particular problem and then show how to solve it. The chapters are short, and try
(as best as possible) to reference the source material where the ideas really came
from. One of our goals in writing this book is to make the paths of history as clear
as possible, as we think that helps a student understand what is, what was, and
what will be more clearly. In this case, seeing how the sausage was made is nearly
as important as understanding what the sausage is good for1.
There are a couple devices we use throughout the book which are probably
worth introducing here. The first is the crux of the problem. Anytime we are
trying to solve a problem, we first try to state what the most important issue is;
such a crux of the problem is explicitly called out in the text, and hopefully solved
via the techniques, algorithms, and ideas presented in the rest of the text.
There are also numerous asides and tips throughout the text, adding a little
color to the mainline presentation. Asides tend to discuss something relevant (but
perhaps not essential) to the main text; tips tend to be general lessons that can be
applied to systems you build. An index at the end of the book lists all of these tips
and asides (as well as cruces, the odd plural of crux) for your convenience.
We use one of the oldest didactic methods, the dialogue, throughout the book,
as a way of presenting some of the material in a different light. These are used to
introduce the major thematic concepts (in a peachy way, as we will see), as well as
to review material every now and then. They are also a chance to write in a more
1Hint: eating! Or if you’re a vegetarian, running away from.
iii
iv
humorous style. Whether you find them useful, or humorous, well, that’s another
matter entirely.
At the beginning of each major section, we’ll first present an abstraction that an
operating system provides, and then work in subsequent chapters on the mecha-
nisms, policies, and other support needed to provide the abstraction. Abstractions
are fundamental to all aspects of Computer Science, so it is perhaps no surprise
that they are also essential in operating systems.
Throughout the chapters, we try to use real code (not pseudocode) where pos-
sible, so for virtually all examples, you should be able to type them up yourself
and run them. Running real code on real systems is the best way to learn about
operating systems, so we encourage you to do so when you can.
In various parts of the text, we have sprinkled in a few homeworks to ensure
that you are understanding what is going on. Many of these homeworks are little
simulations of pieces of the operating system; you should download the home-
works, and run them to quiz yourself. The homework simulators have the follow-
ing feature: by giving them a different random seed, you can generate a virtually
infinite set of problems; the simulators can also be told to solve the problems for
you. Thus, you can test and re-test yourself until you have achieved a good level
of understanding.
The most important addendum to this book is a set of projects in which you
learn about how real systems work by designing, implementing, and testing your
own code. All projects (as well as the code examples, mentioned above) are in
the C programming language [KR88]; C is a simple and powerful language that
underlies most operating systems, and thus worth adding to your tool-chest of
languages. Two types of projects are available (see the online appendix for ideas).
The first are systems programming projects; these projects are great for those who
are new to C and UNIX and want to learn how to do low-level C programming.
The second type are based on a real operating system kernel developed at MIT
called xv6 [CK+08]; these projects are great for students that already have some C
and want to get their hands dirty inside the OS. At Wisconsin, we’ve run the course
in three different ways: either all systems programming, all xv6 programming, or
a mix of both.
OPERATING
SYSTEMS
[VERSION 0.80]
WWW.OSTEP.ORG
相关推荐
2023年江西萍乡中考道德与法治真题及答案.doc
2012年重庆南川中考生物真题及答案.doc
2013年江西师范大学地理学综合及文艺理论基础考研真题.doc
2020年四川甘孜小升初语文真题及答案I卷.doc
2020年注册岩土工程师专业基础考试真题及答案.doc
2023-2024学年福建省厦门市九年级上学期数学月考试题及答案.doc
2021-2022学年辽宁省沈阳市大东区九年级上学期语文期末试题及答案.doc
2022-2023学年北京东城区初三第一学期物理期末试卷及答案.doc
2018上半年江西教师资格初中地理学科知识与教学能力真题及答案.doc
2012年河北国家公务员申论考试真题及答案-省级.doc
2020-2021学年江苏省扬州市江都区邵樊片九年级上学期数学第一次质量检测试题及答案.doc
2022下半年黑龙江教师资格证中学综合素质真题及答案.doc
