Operating Systems: Three Easy Pieces
OPERATING SYSTEMSTHREE EASY PIECESREMZI H. ARPACI-DUSSEAUANDREA C. ARPACI-DUSSEAUUNIVERSITY OF WISCONSIN–MADISON.c2014 by Arpaci-Dusseau Books, Inc.All rights reservediTo Vedat S. Arpaci, a lifelong inspirationTHREEc2014, ARPACI-DUSSEAUEASYPIECESPrefaceTo EveryoneWelcome to this book! We hope you’ll enjoy reading it as much as we enjoyedwriting it. The book is called Operating Systems: Three Easy Pieces, and the titleis obviously an homage to one of the greatest sets of lecture notes ever created, byone Richard Feynman on the topic of Physics [F96]. While this book will undoubtedly fall short of the high standard set by that famous physicist, perhaps it will begood enough for you in your quest to understand what operating systems (andmore generally, systems) are all about.The three easy pieces refer to the three major thematic elements the book isorganized around: virtualization, concurrency, and persistence. In discussingthese concepts, we’ll end up discussing most of the important things an operatingsystem does; hopefully, you’ll also have some fun along the way. Learning newthings 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 camefrom. One of our goals in writing this book is to make the paths of history as clearas possible, as we think that helps a student understand what is, what was, andwhat will be more clearly. In this case, seeing how the sausage was made is nearlyas important as understanding what the sausage is good for1.There are a couple devices we use throughout the book which are probablyworth introducing here. The first is the crux of the problem. Anytime we aretrying 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 solvedvia the techniques, algorithms, and ideas presented in the rest of the text.In many places, we’ll explain how a system works by showing its behaviorover time. These timelines are at the essence of understanding; if you know whathappens, for example, when a process page faults, you are on your way to trulyunderstanding how virtual memory operates. If you comprehend what takes placewhen a journaling file system writes a block to disk, you have taken the first stepstowards mastery of storage systems.There are also numerous asides and tips throughout the text, adding a littlecolor to the mainline presentation. Asides tend to discuss something relevant (butperhaps not essential) to the main text; tips tend to be general lessons that can be1 Hint: eating! Or if you’re a vegetarian, running away from.iiiivapplied to systems you build. An index at the end of the book lists all of these tipsand 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 tointroduce the major thematic concepts (in a peachy way, as we will see), as well asto review material every now and then. They are also a chance to write in a morehumorous style. Whether you find them useful, or humorous, well, that’s anothermatter 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 mechanisms, policies, and other support needed to provide the abstraction. Abstractionsare fundamental to all aspects of Computer Science, so it is perhaps no surprisethat they are also essential in operating systems.Throughout the chapters, we try to use real code (not pseudocode) where possible, so for virtually all examples, you should be able to type them up yourselfand run them. Running real code on real systems is the best way to learn aboutoperating 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 ensurethat you are understanding what is going on. Many of these homeworks are littlesimulations of pieces of the operating system; you should download the homeworks, and run them to quiz yourself. The homework simulators have the following feature: by giving them a different random seed, you can generate a virtuallyinfinite set of problems; the simulators can also be told to solve the problems foryou. Thus, you can test and re-test yourself until you have achieved a good levelof understanding.The most important addendum to this book is a set of projects in which youlearn about how real systems work by designing, implementing, and testing yourown code. All projects (as well as the code examples, mentioned above) are inthe C programming language [KR88]; C is a simple and powerful language thatunderlies most operating systems, and thus worth adding to your tool-chest oflanguages. Two types of projects are available (see the online appendix for ideas).The first are systems programming projects; these projects are great for those whoare 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 MITcalled xv6 [CK 08]; these projects are great for students that already have some Cand want to get their hands dirty inside the OS. At Wisconsin, we’ve run the coursein three different ways: either all systems programming, all xv6 programming, ora mix of both.OPERATINGSYSTEMS[VERSION 0.81]
WWW.OSTEP.ORGvTo EducatorsIf you are an instructor or professor who wishes to use this book, please feelfree to do so. As you may have noticed, they are free and available on-line fromthe following web page:http://www.ostep.orgYou can also purchase a printed copy from lulu.com. Look for it on the webpage above.The (current) proper citation for the book is as follows:Operating Systems: Three Easy PiecesRemzi H. Arpaci-Dusseau and Andrea C. Arpaci-DusseauArpaci-Dusseau Books, Inc.May, 2014 (Version 0.8)http://www.ostep.orgThe course divides fairly well across a 15-week semester, in which you cancover most of the topics within at a reasonable level of depth. Cramming thecourse into a 10-week quarter probably requires dropping some detail from eachof the pieces. There are also a few chapters on virtual machine monitors, which weusually squeeze in sometime during the semester, either right at end of the largesection on virtualization, or near the end as an aside.One slightly unusual aspect of the book is that concurrency, a topic at the frontof many OS books, is pushed off herein until the student has built an understanding of virtualization of the CPU and of memory. In our experience in teachingthis course for nearly 15 years, students have a hard time understanding how theconcurrency problem arises, or why they are trying to solve it, if they don’t yet understand what an address space is, what a process is, or why context switches canoccur at arbitrary points in time. Once they do understand these concepts, however, introducing the notion of threads and the problems that arise due to thembecomes rather easy, or at least, easier.As much as is possible, we use a chalkboard (or whiteboard) to deliver a lecture. On these more conceptual days, we come to class with a few major ideas
and examples in mind and use the board to present them. Handouts are usefulto give the students concrete problems to solve based on the material. On morepractical days, we simply plug a laptop into the projector and show real code; thisstyle works particularly well for concurrency lectures as well as for any discussion sections where you show students code that is relevant for their projects. Wedon’t generally use slides to present material, but have now made a set availablefor those who prefer that style of presentation.If you’d like a copy of any of these materials, please drop us an email. We havealready shared them with many others around the world.One last request: if you use the free online chapters, please just link to them,instead of making a local copy. This helps us track usage (over 1 million chaptersdownloaded in the past few years!) and also ensures students get the latest andgreatest version.THREEc2014, ARPACI-DUSSEAUEASYPIECESviTo StudentsIf you are a student reading this book, thank you! It is an honor for us toprovide some material to help you in your pursuit of knowledge about operatingsystems. We both think back fondly towards some textbooks of our undergraduatedays (e.g., Hennessy and Patterson [HP90], the classic book on computer architecture) and hope this book will become one of those positive memories for you.You may have noticed this book is free and available online2. There is one majorreason for this: textbooks are generally too expensive. This book, we hope, is thefirst of a new wave of free materials to help those in pursuit of their education,regardless of which part of the world they come from or how much they are willingto spend for a book. Failing that, it is one free book, which is better than none.We also hope, where possible, to point you to the original sources of muchof the material in the book: the great papers and persons who have shaped the
field of operating systems over the years. Ideas are not pulled out of the air; theycome from smart and hard-working people (including numerous Turing-awardwinners3), and thus we should strive to celebrate those ideas and people wherepossible. In doing so, we hopefully can better understand the revolutions thathave taken place, instead of writing texts as if those thoughts have always beenpresent [K62]. Further, perhaps such references will encourage you to dig deeperon your own; reading the famous papers of our field is certainly one of the bestways to learn.2A digression here: “free” in the way we use it here does not mean open source, and itdoes not mean the book is not copyrighted with the usual protections – it is! What it meansisthat you can download the chapters and use them to learn about operating systems. Whynotan open-source book, just like Linux is an open-source kernel? Well, we believe it isimportantfor a book to have a single voice throughout, and have worked hard to provide such avoice.When you’re reading it, the book should kind of feel like a dialogue with the personexplainingsomething to you. Hence, our approach.3The Turing Award is the highest award in Computer Science; it is like the Nobel Prize,except that you have never heard of it.OPERATINGSYSTEMS[VERSION 0.81]WWW.OSTEP.ORGviiAcknowledgmentsThis section will contain thanks to those who helped us put the book together.The important thing for now: your name could go here! But, you have to help. Sosend us some feedback and help debug this book. And you could be famous! Or,at least, have your name in some book.The people who have helped so far include: Abhirami Senthilkumaran*, Adam
Drescher* (WUSTL), Adam Eggum, Aditya Venkataraman, Adriana Iamnitchi andclass (USF), Ahmed Fikri*, Ajaykrishna Raghavan, Akiel Khan, Alex Wyler, AliRazeen (Duke), Andrew Valencik (Saint Mary’s), Anand Mundada, B. BrahmanandaReddy (Minnesota), Bala Subrahmanyam Kambala, Benita Bose, Biswajit Mazumder(Clemson), Bobby Jack, Bj örn Lindberg, Brennan Payne, Brian Gorman, Brian Kroth,Caleb Sumner (Southern Adventist U.), Cara Lauritzen, Charlotte Kissinger, ChienChung Shen (Delaware)*, Christoph Jaeger, Cody Hanson, Dan Soendergaard (U.Aarhus), David Hanle (Grinnell), David Hartman, Deepika Muthukumar, DheerajShetty (NC State), Dorian Arnold (New Mexico), Dustin Metzler, Dustin Passofaro,Eduardo Stelmaszczyk, Emad Sadeghi, Emily Jacobson, Emmett Witchel (Texas),Erik Turk, Ernst Biersack (France), Finn Kuusisto*, Guilherme Baptista, HamidReza Ghasemi, Hao Chen, Henry Abbey, Hrishikesh Amur, Huanchen Zhang*,Huseyin Sular, Hugo Diaz, Itai Hass (Toronto), Jake Gillberg, James Perry (U.Michigan-Dearborn)*, Jan Reineke (Universität des Saarlandes), Jay Lim, JerodWeinman (Grinnell), Jiao Dong (Rutgers), Joe Jean (NYU), Joel Kuntz (Saint Mary’s),Joel Sommers (Colgate), John Brady (Grinnell), Jonathan Perry (MIT), Jun He, KarlWallinger, Kartik Singhal, Kaushik Kannan, Kevin Liu*, Lei Tian (U. NebraskaLincoln), Leslie Schultz, Liang Yin, Lihao Wang, Martha Ferris, Masashi Kishikawa(Sony), Matt Reichoff, Matty Williams, Meng Huang, Mike Griepentrog, MingChen (Stonybrook), Mohammed Alali (Delaware), Murugan Kandaswamy, NatashaEilbert, Nathan Dipiazza, Nathan Sullivan, Neeraj Badlani (N.C. State), NelsonGomez, Nghia Huynh (Texas), Nick Weinandt, Patricio Jara, Perry Kivolowitz,Radford Smith, Riccardo Mutschlechner, Ripudaman Singh, Robert Ord ò nez andclass (Southern Adventist), Rohan Das (Toronto)*, Rohan Pasalkar (Minnesota),Ross Aiken, Ruslan Kiselev, Ryland Herrick, Samer Al-Kiswany, Sandeep Ummadi(Minnesota), Satish Chebrolu (NetApp), Satyanarayana Shanmugam*, Seth Pollen,Sharad Punuganti, Shreevatsa R., Sivaraman Sivaraman*, Srinivasan Thirunarayanan*,Suriyhaprakhas Balaram Sankari, Sy Jin Cheah, Thomas Griebel, Tongxin Zheng,Tony Adkins, Torin Rudeen (Princeton), Tuo Wang, Varun Vats, William Royle(Grinnell), Xiang Peng, Xu Di, Yudong Sun, Yue Zhuo (Texas A&M), Yufui Ren, ZefRosnBrick, Zuyu Zhang. Special thanks to those marked with an asterisk above,who have gone above and beyond in their suggestions for improvement.
Special thanks to Professor Joe Meehean (Lynchburg) for his detailed notes oneach chapter, to Professor Jerod Weinman (Grinnell) and his entire class for theirincredible booklets, to Professor Chien-Chung Shen (Delaware) for his invaluableand detailed reading and comments, and Adam Drescher (WUSTL) for his careful reading and suggestions. All have helped these authors immeasurably in therefinement of the materials herein.Also, many thanks to the hundreds of students who have taken 537 over theyears. In particular, the Fall ’08 class who encouraged the first written form ofthese notes (they were sick of not having any kind of textbook to read — pushystudents!), and then praised them enough for us to keep going (including one hiTHREEc2014, ARPACI-DUSSEAUEASYPIECESviiilarious “ZOMG! You should totally write a textbook!” comment in our courseevaluations that year).A great debt of thanks is also owed to the brave few who took the xv6 projectlab course, much of which is now incorporated into the main 537 course. FromSpring ’09: Justin Cherniak, Patrick Deline, Matt Czech, Tony Gregerson, MichaelGriepentrog, Tyler Harter, Ryan Kroiss, Eric Radzikowski, Wesley Reardan, RajivVaidyanathan, and Christopher Waclawik. From Fall ’09: Nick Bearson, AaronBrown, Alex Bird, David Capel, Keith Gould, Tom Grim, Jeffrey Hugo, BrandonJohnson, John Kjell, Boyan Li, James Loethen, Will McCardell, Ryan Szaroletta, Simon Tso, and Ben Yule. From Spring ’10: Patrick Blesi, Aidan Dennis-Oehling,Paras Doshi, Jake Friedman, Benjamin Frisch, Evan Hanson, Pikkili Hemanth,Michael Jeung, Alex Langenfeld, Scott Rick, Mike Treffert, Garret Staus, BrennanWall, Hans Werner, Soo-Young Yang, and Carlos Griffin (almost).Although they do not directly help with the book, our graduate students havetaught us much of what we know about systems. We talk with them regularlywhile they are at Wisconsin, but they do all the real work — and by telling us about
what they are doing, we learn new things every week. This list includes the following collection of current and former students with whom we have published papers; an asterisk marks those who received a Ph.D. under our guidance: AbhishekRajimwale, Ao Ma, Brian Forney, Chris Dragga, Deepak Ramamurthi, FlorentinaPopovici*, Haryadi S. Gunawi*, James Nugent, John Bent*, Lanyue Lu, LakshmiBairavasundaram*, Laxman Visampalli, Leo Arulraj, Meenali Rungta, Muthian Sivathanu*, Nathan Burnett*, Nitin Agrawal*, Sriram Subramanian*, Stephen ToddJones*, Suli Yang, Swaminathan Sundararaman*, Swetha Krishnan, Thanh Do*,Thanumalayan S. Pillai, Timothy Denehy*, Tyler Harter, Venkat Venkataramani,Vijay Chidambaram, Vijayan Prabhakaran*, Yiying Zhang*, Yupu Zhang*, ZevWeiss.A final debt of gratitude is also owed to Aaron Brown, who first took this coursemany years ago (Spring ’09), then took the xv6 lab course (Fall ’09), and finally wasa graduate teaching assistant for the course for two years or so (Fall ’10 throughSpring ’12). His tireless work has vastly improved the state of the projects (particularly those in xv6 land) and thus has helped better the learning experience forcountless undergraduates and graduates here at Wisconsin. As Aaron would say(in his usual succinct manner): “Thx.”OPERATINGSYSTEMS[VERSION 0.81]WWW.OSTEP.ORGixFinal WordsYeats famously said “Education is not the filling of a pail but the lighting of afire.” He was right but wrong at the same time4. You do have to “fill the pail” a bit,and these notes are certainly here to help with that part of your education; after all,when you go to interview at Google, and they ask you a trick question about howto use semaphores, it might be good to actually know what a semaphore is, right?But Yeats’s larger point is obviously on the mark: the real point of educationis to get you interested in something, to learn something more about the subjectmatter on your own and not just what you have to digest to get a good grade in
some class. As one of our fathers (Remzi’s dad, Vedat Arpaci) used to say, “Learnbeyond the classroom”.We created these notes to spark your interest in operating systems, to read moreabout the topic on your own, to talk to your professor about all the exciting research that is going on in the field, and even to get involved with that research. Itis a great field(!), full of exciting and wonderful ideas that have shaped computinghistory in profound and important ways. And while we understand this fire won’tlight for all of you, we hope it does for many, or even a few. Because once that fireis lit, well, that is when you truly become capable of doing something great. Andthus the real point of the educational process: to go forth, to study many new andfascinating topics, to learn, to mature, and most importantly, to find somethingthat lights a fire for you.Andrea and RemziMarried coupleProfessors of Computer Science at the University of WisconsinChief Lighters of Fires, hopefully54 If he actually said this; as with many famous quotes, the history of this gem is murky.5 If this sounds like we are admitting some past history as arsonists, you are probablymissing the point. Probably. If this sounds cheesy, well, that’s because it is, but you’ll justhaveto forgive us for that.THREEc2014, ARPACI-DUSSEAUEASYPIECESxReferences[CK 08] “The xv6 Operating System”Russ Cox, Frans Kaashoek, Robert Morris, Nickolai ZeldovichFrom: http://pdos.csail.mit.edu/6.828/2008/index.htmlxv6 was developed as a port of the original UNIX version 6 and represents a beautiful,clean, and simple
way to understand a modern operating system.[F96] “Six Easy Pieces: Essentials Of Physics Explained By Its Most Brilliant Teacher”Richard P. FeynmanBasic Books, 1996This book reprints the six easiest chapters of Feynman’s Lectures on Physics, from 1963.If you likePhysics, it is a fantastic read.[HP90] “Computer Architecture a Quantitative Approach” (1st ed.)David A. Patterson and John L. HennessyMorgan-Kaufman, 1990A book that encouraged each of us at our undergraduate institutions to pursue graduatestudies; we laterboth had the pleasure of working with Patterson, who greatly shaped the foundations ofour researchcareers.[KR88] “The C Programming Language”Brian Kernighan and Dennis RitchiePrentice-Hall, April 1988The C programming reference that everyone should have, by the people who invented thelanguage.[K62] “The Structure of Scientific Revolutions”Thomas S. KuhnUniversity of Chicago Press, 1962A great and famous read about the fundamentals of the scientific process. Mop-up work,anomaly, crisis,and revolution. We are mostly destined to do mop-up work, alas.OPERATINGSYSTEMS[VERSION 0.81]WWW.OSTEP.ORGContentsTo Everyone iiiTo Educators
vTo Students . viAcknowledgments viiFinal Words ixReferences .x1A Dialogue on the Book12Introduction to Operating Systems32.1Virtualizing the CPU .52.2Virtualizing Memory .72.3Concurrency 82.4Persistence . 112.5Design Goals 132.6Some History . . 142.7Summary . . 18References . 19IVirtualization
213A Dialogue on Virtualization234The Abstraction: The Process254.1The Abstraction: A Process . 264.2Process API 274.3Process Creation: A Little More Detail 284.4Process States . . 294.5Data Structures . 314.6Summary . . 33References . 34Homework . 35xixiiCONTENTS5Interlude: Process API375.1The fork() System Call . . 375.2The wait() System Call . . 39
5.3Finally, The exec() System Call 405.4Why? Motivating The API . 415.5Other Parts Of The API 445.6Summary . . 44References . 45Homework (Code) 466Mechanism: Limited Direct Execution496.1Basic Technique: Limited Direct Execution . 496.2Problem #1: Restricted Operations 506.3Problem #2: Switching Between Processes . 546.4Worried About Concurrency? . . 586.5Summary . . 59References . 61Homework (Measurement) . 627Scheduling: Introduction637.1Workload Assumptions 637.2Scheduling Metrics . . 64
7.3First In, First Out (FIFO) . . 647.4Shortest Job First (SJF) 667.5Shortest Time-to-Completion First (STCF) . 677.6A New Metric: Response Time . . 687.7Round Robin 697.8Incorporating I/O 717.9No More Oracle . 727.10 Summary . . 72References . 73Homework . 748Scheduling:The Multi-Level Feedback Queue758.1MLFQ: Basic Rules . . 768.2Attempt #1: How To Change Priority . 778.3Attempt #2: The Priority Boost . . 808.4Attempt #3: Better Accounting . . 818.5Tuning MLFQ And Other Issues . 828.6MLFQ: Summary 83
References . 85Homework . 869Scheduling: Proportional Share879.1Basic Concept: Tickets Represent Your Share 879.2Ticket Mechanisms . . 899.3Implementation . 90OPERATINGSYSTEMS[VERSION 0.81]WWW.OSTEP.ORGCONTENTSxiii9.4An Example 919.5How To Assign Tickets? 929.6Why Not Deterministic? . . 929.7Summary . . 93References . 95Homework . 9610 Multiprocessor Scheduling (Advanced)9710.1 Background: Multiprocessor Architecture . 9810.2 Don’t Forget Synchronization . . 10010.3 One Final Issue: Cache Affinity . 101
10.4 Single-Queue Scheduling . . 10110.5 Multi-Queue Scheduling . . 10310.6 Linux Multiprocessor Schedulers 10610.7 Summary . . 106References . 10711 Summary Dialogue on CPU Virtualization10912 A Dialogue on Memory Virtualization11113 The Abstraction: Address Spaces11313.1 Early Systems . . 11313.2 Multiprogramming and Time Sharing . 11413.3 The Address Space . . 11513.4 Goals . 11713.5 Summary . . 119References . 12014 Interlude: Memory API12314.1 Types of Memory 12314.2 The malloc() Call . . 12414.3 The free() Call 12614.4 Common Errors . 12614.5 Underlying OS Support 12914.6 Other Calls . 13014.7 Summary . . 130References . 131Homework (Code) 13215 Mechanism: Address Translation13515.1 Assumptions 13615.2 An Example 136
15.3 Dynamic (Hardware-based) Relocation 13915.4 Hardware Support: A Summary . 14215.5 Operating System Issues . . 14315.6 Summary . . 146THREEc2014, ARPACI-DUSSEAUEASYPIECESxivCONTENTSReferences . 147Homework . 14816 Segmentation14916.1 Segmentation: Generalized Base/Bounds . 14916.2 Which Segment Are We Referring To? . 15216.3 What About The Stack? 15316.4 Support for Sharing . . 15416.5 Fine-grained vs. Coarse-grained Segmentation . 15516.6 OS Support . 15516.7 Summary . . 157References . 158Homework . 16017 Free-Space Management16117.1 Assumptions 16217.2 Low-level Mechanisms 16317.3 Basic Strategies . 17117.4 Other Approaches 17317.5 Summary . . 175References . 176
Homework . 17718 Paging: Introduction17918.1 A Simple Example And Overview 17918.2 Where Are Page Tables Stored? . 18318.3 What’s Actually In The Page Table? . . 18418.4 Paging: Also Too Slow 18518.5 A Memory Trace . 18618.6 Summary . . 189References . 190Homework . 19119 Paging: Faster Translations (TLBs)19319.1 TLB Basic Algorithm . 19319.2 Example: Accessing An Array . . 19519.3 Who Handles The TLB Miss? 19719.4 TLB Contents: What’s In There? . 19919.5 TLB Issue: Context Switches 20019.6 Issue: Replacement Policy . 20219.7 A Real TLB Entry 20319.8 Summary . . 204References . 205Homework (Measurement) . 20720 Paging: Smaller Tables21120.1 Simple Solution: Bigger Pages . . 211OPERATINGSYSTEMS[VERSION 0.81]WWW.OSTEP.ORGCONTENTSxv
20.2 Hybrid Approach: Paging and Segments . . 21220.3 Multi-level Page Tables 21520.4 Inverted Page Tables . 22220.5 Swapping the Page Tables to Disk 22320.6 Summary . . 223References . 224Homework . 22521 Beyond Physical Memory: Mechanisms22721.1 Swap Space . 22821.2 The Present Bit . . 22921.3 The Page Fault . . 23021.4 What If Memory Is Full? . . 23121.5 Page Fault Control Flow . . 23221.6 When Replacements Really Occur 23321.7 Summary . . 234References . 23522 Beyond Physical Memory: Policies23722.1 Cache Management . . 23722.2 The Optimal Replacement Policy 23822.3 A Simple Policy: FIFO 24022.4 Another Simple Policy: Random . 24222.5 Using History: LRU . . 24322.6 Workload Examples . . 24422.7 Implementing Historical Algorithms . 24722.8 Approximating LRU . 24822.9 Considering Dirty Pages . . 24922.10 Other VM Policies 25022.11 Thrashing . 25022.12 Summary . . 251References . 252
Homework . 25423 The VAX/VMS Virtual Memory System25523.1 Background 25523.2 Memory Management Hardware 25623.3 A Real Address Space . 25723.4 Page Replacement 25923.5 Other Neat VM Tricks . 26023.6 Summary . . 262References . 26324 Summary Dialogue on Memory Virtualization265THREEc2014, ARPACI-DUSSEAUEASYPIECESxviCONTENTSII Concurrency26925 A Dialogue on Concurrency27126 Concurrency: An Introduction27326.1 An Example: Thread Creation . . 27426.2 Why It Gets Worse: Shared Data . 27726.3 The Heart Of The Problem: Uncontrolled Scheduling . 27926.4 The Wish For Atomicity 28126.5 One More Problem: Waiting For Another . . 28326.6 Summary: Why in OS Class? 283References . 285
Homework . 28627 Interlude: Thread API28927.1 Thread Creation . 28927.2 Thread Completion . . 29027.3 Locks . 29327.4 Condition Variables . . 29527.5 Compiling and Running . . 29727.6 Summary . . 297References . 29928 Locks30128.1 Locks: The Basic Idea . 30128.2 Pthread Locks . . 30228.3 Building A Lock . 30328.4 Evaluating Locks 30328.5 Controlling Interrupts . 30428.6 Test And Set (Atomic Exchange) . 30528.7 Building A Working Spin Lock . . 30728.8 Evaluating Spin Locks 30928.9 Compare-And-Swap . 30928.10 Load-Linked and Store-Conditional . . 31028.11 Fetch-And-Add . 31228.12 Summary: So Much Spinning . . 31328.13 A Simple Approach: Just Yield, Baby . 31428.14 Using Queues: Sleeping Instead Of Spinning 31528.15 Different OS, Different Support . 31728.16 Two-Phase Locks 31728.17 Summary . . 318References . 319Homework . 32129 Lock-based Concurrent Data Struct
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
les pièces manquantes) 402 ALTAYA. STAR WARS. Vaisseaux de la série (16 pièces) 403 ALTAYA. STAR WARS. Vaisseaux de la série (9 pièces) 404 ALTAYA. STAR WARS. Vaisseaux de la série (18 pièces) 405 ALTAYA. STAR WARS. Vaisseaux de la série (19 pièces) TRAINS 406 Lot de trains HO (15 pièces) AUTOMOBI
Girls' Swimwear Set 1 12 OVER pieces 10 pieces 25 OVER pieces 55 OVER pieces 20 OVER pieces 40 OVER pieces 25 SF5228 Seaside Ice Cream Shop Cool your Sylvanians down on a hot summer day with the Seaside Ice Cream Shop. Complete with the Striped Cat mother in her uniform, this shop h
06/99 gen. EASY 620-DC-TC EASY 618-AC-RC u 4Functionsu 5 "easy" at a glance u 6Mountingu 6 ff. Connecting "easy" u 12 EASY 6. status display u 14, 23 ff. Circuit diagram elements u 16 System menu u 20 Menu languages u 22 Startup behaviour u 36 Text display (markers) u 44 Available memory cards u 44 EASY-SOFT u 45 Technical data u
2 Alderighi Signi Lieti 10 very easy, short pieces. The harmonies are traditional, the writing is highly pianistic and they make up excellent recital material. 2 Alexandrow Pieces for Children The whole collection consists of 8 sets of short pieces for complete beginners. If you are familiar with Kabalevsky’s pieces for children, this is similar.
Book 1 Kabalevsky: Waltz from 24 Pieces for Children, Op. 39, No. 13 Jumping from 24 Pieces for Children, Op. 39, No. 15 Folk Dance from 24 Pieces for Children, Op. 39, No. 17 Clowns from 24 Pieces for Children, Op. 39, No. 20 Waltz from 30 Pieces for Children, Op.
1 case 1 piece Subdural Evacuating Port 2 cases 25 pieces Electosurgical Pencil 12 bags 100 pieces 1 ML Blood Collection Tubes 8 boxes 100 pieces 1 ML Blood Collection Tubes 58 bags 100 pieces Minicollect Funnel Tubes 3 boxes 25 pieces Huparin Lock Flush (10 USP/ML) 1 bag 100 piec
www.free-shrimp-recipes.com and www.chicken-recipes-galore.com 2012 75. Crispy Parmesan Fish Fillets 76. Dijon Salmon 77. Easiest Crock Pot Beef Roast 78. Easy Beef N' Tater Casserole 79. Easy Chicken Pie 80. Easy Corn Dogs 81. Easy Enchiladas 82. Easy Garlic Chicken 83. Easy Lasagna 84. Easy Mac & Cheese 85. Easy Mexican Calzones 86.
Operating Systems, Embedded Systems, and Real-Time Systems Janez Puhan Ljubljana, 2015. CIP-CatalogingInPublication NationalandUniversityLibrary,Ljubljana 004.451(078.5)(0.034.2) PUHAN,Janez,1969-Operating Systems, Embedded Systems, and Real-Time Systems [Electronic
