Thomas Anderson - Operating Systems: Principles and Practice, Vol. 4: Persistent Storage

Operating Systems: Principles and Practice (Second Edition)Volume IV: Persistent Storageby Thomas Anderson and Michael Dahlin
Copyright Thomas Anderson and Michael Dahlin, 2011-2015.

ISBN 978-0-9856735-6-7
Publisher: Recursive Books, Ltd., http://recursivebooks.com/
Cover: Reflection Lake, Mt. Rainier
Cover design: Cameron Neat
Illustrations: Cameron Neat
Copy editors: Sandy Kaplan, Whitney Schmidt
Ebook design: Robin Briggs
Web design: Adam Anderson

SUGGESTIONS, COMMENTS, and ERRORS. We welcome suggestions, comments anderror reports, by email to suggestions@recursivebooks.com

Notice of rights. All rights reserved. No part of this book may be reproduced, storedin a retrieval system, or transmitted in any form by any means electronic,mechanical, photocopying, recording, or otherwise without the prior writtenpermission of the publisher. For information on getting permissions for reprints andexcerpts, contact permissions@recursivebooks.com

Notice of liability. The information in this book is distributed on an As Is" basis,without warranty. Neither the authors nor Recursive Books shall have any liability toany person or entity with respect to any loss or damage caused or alleged to becaused directly or indirectly by the information or instructions contained inthis book or by the computer software and hardware products described init.

Trademarks: Throughout this book trademarked names are used. Rather than put atrademark symbol in every occurrence of a trademarked name, we state we are usingthe names only in an editorial fashion and to the benefit of the trademark ownerwith no intention of infringement of the trademark. All trademarks or service marksare the property of their respective owners.

To Robin, Sandra, Katya, and Adam Tom Anderson

To Marla, Kelly, and Keith Mike Dahlin

I: Kernels and Processes

1. Introduction

2. TheKernel Abstraction

3. The Programming Interface

II: Concurrency

4.Concurrency and Threads

5. Synchronizing Access to Shared Objects

6.Multi-Object Synchronization

7. Scheduling

III: Memory Management

8.Address Translation

9. Caching and Virtual Memory

10. Advanced MemoryManagement

IV

11.1

11.2

11.3

11.3.1
11.3.2
11.3.3
11.3.4

11.4

12.1

12.1.1
12.1.2
12.1.3

12.2

12.3

13.1

13.2

13.3

13.3.1
13.3.2
13.3.3
13.3.4

13.4

13.5

14.1

14.1.1
14.1.2
14.1.3
14.1.4

14.2

14.2.1
14.2.2
14.2.3

14.3

Operating Systems: Principles and Practice is a textbook for a first course inundergraduate operating systems. In use at over 50 colleges and universitiesworldwide, this textbook provides:

• A path for students to understand high level concepts all the way down to working code.
• Extensive worked examples integrated throughout the text provide students concrete guidance for completing homework assignments.
• A focus on up-to-date industry technologies and practice

The eBook edition is split into four volumes that together contain exactly thesame material as the (2nd) print edition of Operating Systems: Principles andPractice, reformatted for various screen sizes. Each volume is self-contained and canbe used as a standalone text, e.g., at schools that teach operating systems topicsacross multiple courses.

• Volume 1: Kernels and Processes. This volume contains Chapters 1-3 of the print edition. We describe the essential steps needed to isolate programs to prevent buggy applications and computer viruses from crashing or taking control of your system.
• Volume 2: Concurrency. This volume contains Chapters 4-7 of the print edition. We provide a concrete methodology for writing correct concurrent programs that is in widespread use in industry, and we explain the mechanisms for context switching and synchronization from fundamental concepts down to assembly code.
• Volume 3: Memory Management. This volume contains Chapters 8-10 of the print edition. We explain both the theory and mechanisms behind 64-bit address space translation, demand paging, and virtual machines.
• Volume 4: Persistent Storage. This volume contains Chapters 11-14 of the print edition. We explain the technologies underlying modern extent-based, journaling, and versioning file systems.

A more detailed description of each chapter is given in the preface to the printedition.

Many of our students tell us that operating systems was the best course they took asan undergraduate and also the most important for their careers. We are notalone many of our colleagues report receiving similar feedback from theirstudents.

Part of the excitement is that the core ideas in a modern operating system protection, concurrency, virtualization, resource allocation, and reliable storage have become widely applied throughout computer science, not just operatingsystem kernels. Whether you get a job at Facebook, Google, Microsoft, or any otherleading-edge technology company, it is impossible to build resilient, secure, andflexible computer systems without the ability to apply operating systems concepts ina variety of settings. In a modern world, nearly everything a user does is distributed,nearly every computer is multi-core, security threats abound, and many applicationssuch as web browsers have become mini-operating systems in their ownright.

It should be no surprise that for many computer science students, anundergraduate operating systems class has become a de facto requirement: a ticket toan internship and eventually to a full-time position.

Unfortunately, many operating systems textbooks are still stuck in the past,failing to keep pace with rapid technological change. Several widely-used bookswere initially written in the mid-1980s, and they often act as if technology stoppedat that point. Even when new topics are added, they are treated as an afterthought,without pruning material that has become less important. The result are textbooksthat are very long, very expensive, and yet fail to provide students more than asuperficial understanding of the material.

Our view is that operating systems have changed dramatically over the pasttwenty years, and that justifies a fresh look at both how the material is taught andwhat is taught. The pace of innovation in operating systems has, if anything,increased over the past few years, with the introduction of the iOS and Androidoperating systems for smartphones, the shift to multicore computers, and the adventof cloud computing.

To prepare students for this new world, we believe students need three things tosucceed at understanding operating systems at a deep level:

• Concepts and code. We believe it is important to teach students both principles and practice, concepts and implementation, rather than either alone. This textbook takes concepts all the way down to the level of working code, e.g., how a context switch works in assembly code. In our experience, this is the only way students will really understand and master the material. All of the code in this book is available from the authors web site, ospp.washington.edu.