`
`
`OPERATING
`SYSTEMS
`
`Internais and Design Principles
`Savant: Edt'nn
`
`“A
`-. V
`
`m
`
` William Stallings
`
`Patent Owner, Bot M8 LLC - Ex. 2014, p. 1
`
`Patent Owner, Bot M8 LLC - Ex. 2014, p. 1
`
`

`

`OPERATING SYSTEMS
`INTERNALS AND DESIGN
`PRINCIPLES
`SEVENTH EDITION
`
`William Stallings
`
` Prentice Hall
` Boston Columbus Indianapolis New York San Francisco Upper Saddle River
` Amsterdam Cape Town Dubai London Madrid Milan Munich Paris Montreal Toronto
` Delhi Mexico City São Paulo Sydney Hong Kong Seoul Singapore Taipei Tokyo
`
`Patent Owner, Bot M8 LLC - Ex. 2014, p. 2
`
`

`

` Editorial Director: Marcia Horton
` Editor in Chief: Michael Hirsch
` Executive Editor: Tracy Dunkelberger
` Assistant Editor: Melinda Haggerty
` Editorial Assistant: Allison Michael
` Director of Marketing: Patrice Jones
` Marketing Manager: Yezan Alayan
` SenioMarketing Coordinator: Kathryn Ferranti
` Production Manager: Pat Brown
`
` Art Director: Jayne Conte
` Cover Designer: Bruce Kenselaar
` Media Director: Daniel Sandin
` Media Project Manager: Wanda Rockwell
` Full-Service Project Management/Composition:
` Shiny Rajesh/Integra Software Service Pvt. Ltd.
` Interior Printer/Bindery: Edwards Brothers
` Cover Printer: Lehigh-Phoenix Color
`
` Credits and acknowledgments borrowed from other sources and reproduced, with permission, in this textbook appear on
`appropriate page within text.
`
` Microsoft® and Windows® are registered trademarks of the Microsoft Corporation in the U.S.A. and other countries. Screen
`shots and icons reprinted with permission from the Microsoft Corporation. This book is not sponsored or endorsed by or
`affi liated with the Microsoft Corporation.
`
` Copyright © 2012, 2009, 2005, 2001, 1998 Pearson Education, Inc., publishing as Prentice Hall, 1 Lake Street,
`Upper Saddle River, New Jersey, 07458. All rights reserved. Manufactured in the United States of America. This publication
`is protected by Copyright, and permission should be obtained from the publisher prior to any prohibited reproduction,
` storage in a retrieval system, or transmission in any form or by any means, electronic, mechanical, photocopying, recording, or
`likewise. To obtain permission(s) to use material from this work, please submit a written request to Pearson Education, Inc.,
`Permissions Department, 1 Lake Street, Upper Saddle River, New Jersey, 07458.
`
` Many of the designations by manufacturers and sellers to distinguish their products are claimed as trademarks. Where those
`designations appear in this book, and the publisher was aware of a trademark claim, the designations have been printed in
`initial caps or all caps.
`
` Library of Congress Cataloging-in-Publication Data
`
`Stallings, William.
`Operating systems : internals and design principles / William Stallings. — 7th ed.
`
` p. cm.
`
`Includes bibliographical references and index.
`
`ISBN-13: 978-0-13-230998-1 (alk. paper)
`
`ISBN-10: 0-13-230998-X (alk. paper)
` 1. Operating systems (Computers)
`I. Title.
`QA76.76.O63S733 2011
`005.4'3 dc22
`
`
`2010048597
`
` 10 9 8 7 6 5 4 3 2 1—EB—15 14 13 12 11
`
` ISBN 10: 0-13-230998-X
` ISBN 13: 978-0-13-230998-1
`
`Patent Owner, Bot M8 LLC - Ex. 2014, p. 3
`
`

`

`8 CHAPTER 1 / COMPUTER SYSTEM OVERVIEW
`
` No artifact designed by man is so convenient for this kind of functional
`description as a digital computer. Almost the only ones of its properties
`that are detectable in its behavior are the organizational properties.
`Almost no interesting statement that one can make about on operating
`computer bears any particular relation to the specific nature of the hard-
`ware. A computer is an organization of elementary functional components
`in which, to a high approximation, only the function performed by those
`components is relevant to the behavior of the whole system.
`THE SCIENCES OF THE ARTIFICIAL , Herbert Simon
`
`LEARNING OBJECTIVES
` After studying this chapter, you should be able to:
`• Describe the basic elements of a computer system and their interrelationship.
`• Explain the steps taken by a processor to execute an instruction.
`• Understand the concept of interrupts and how and why a processor uses
`interrupts.
`• List and describe the levels of a typical computer memory hierarchy.
`• Explain the basic characteristics of multiprocessor and multicore organizations.
`• Discuss the concept of locality and analyze the performance of a multilevel
`memory hierarchy.
`• Understand the operation of a stack and its use to support procedure call and
`return.
`
` An operating system (OS) exploits the hardware resources of one or more proces-
`sors to provide a set of services to system users. The OS also manages secondary
`memory and I/O (input/output) devices on behalf of its users. Accordingly, it is
`important to have some understanding of the underlying computer system hardware
`before we begin our examination of operating systems.
` This chapter provides an overview of computer system hardware. In most
`areas, the survey is brief, as it is assumed that the reader is familiar with this subject.
`However, several areas are covered in some detail because of their importance to
`topics covered later in the book. Further topics are covered in Appendix C .
`
`1.1 BASIC ELEMENTS
`
` At a top level, a computer consists of processor, memory, and I/O components, with
`one or more modules of each type. These components are interconnected in some
`fashion to achieve the main function of the computer, which is to execute programs.
`Thus, there are four main structural elements:
`
`
`
`• Processor: Controls the operation of the computer and performs its data pro-
`cessing functions. When there is only one processor, it is often referred to as
`the central processing unit (CPU).
`
`Patent Owner, Bot M8 LLC - Ex. 2014, p. 4
`
`

`

`48 CHAPTER 2 / OPERATING SYSTEM OVERVIEW
`
`2.1 OPERATING SYSTEM OBJECTIVES AND FUNCTIONS
`
`
`
`
`
`
` An OS is a program that controls the execution of application programs and acts as
`an interface between applications and the computer hardware. It can be thought of
`as having three objectives:
`
`• Convenience: An OS makes a computer more convenient to use.
`• Efficiency: An OS allows the computer system resources to be used in an effi-
`cient manner.
`• Ability to evolve: An OS should be constructed in such a way as to permit the
`effective development, testing, and introduction of new system functions with-
`out interfering with service.
`
` Let us examine these three aspects of an OS in turn.
`
`The Operating System as a User/Computer Interface
` The hardware and software used in providing applications to a user can be viewed
`in a layered or hierarchical fashion, as depicted in Figure 2.1 . The user of those
`applications, the end user, generally is not concerned with the details of computer
`hardware. Thus, the end user views a computer system in terms of a set of applica-
`tions. An application can be expressed in a programming language and is developed
`by an application programmer. If one were to develop an application program as a
`set of machine instructions that is completely responsible for controlling the com-
`puter hardware, one would be faced with an overwhelmingly complex undertaking.
`To ease this chore, a set of system programs is provided. Some of these programs
`are referred to as utilities, or library programs. These implement frequently used
`functions that assist in program creation, the management of files, and the control of
`
`Application
`programming interface
`Application
`binary interface
`
`Instruction set
`architecture
`
`Application programs
`
`Libraries/utilities
`
`Operating system
`
`Execution hardware
`
`Software
`
`System interconnect
`(bus)
`
`Memory
`translation
`
`Hardware
`
`I/O devices
`and
`networking
`
`Main
`memory
`
`Figure 2.1
`
` Computer Hardware and Software Structure
`
`Patent Owner, Bot M8 LLC - Ex. 2014, p. 5
`
`

`

`94 CHAPTER 2 / OPERATING SYSTEM OVERVIEW
`
`and does so in an integrated, commercially viable fashion. SVR4 runs on processors
`ranging from 32-bit microprocessors up to supercomputers.
`
`BSD
` The Berkeley Software Distribution (BSD) series of UNIX releases have played
`a key role in the development of OS design theory. 4.xBSD is widely used in aca-
`demic installations and has served as the basis of a number of commercial UNIX
`products. It is probably safe to say that BSD is responsible for much of the popular-
`ity of UNIX and that most enhancements to UNIX first appeared in BSD versions.
` 4.4BSD was the final version of BSD to be released by Berkeley, with the
`design and implementation organization subsequently dissolved. It is a major
`upgrade to 4.3BSD and includes a new virtual memory system, changes in the ker-
`nel structure, and a long list of other feature enhancements.
` One of the most widely used and best documented versions of BSD is
`FreeBSD. FreeBSD is popular for Internet-based servers and firewalls and is used
`in a number of embedded systems.
` The latest version of the Macintosh OS, Mac OS X, is based on FreeBSD 5.0
`and the Mach 3.0 microkernel.
`
`Solaris 10
` Solaris is Sun’s SVR4-based UNIX release, with the latest version being 10. Solaris
`provides all of the features of SVR4 plus a number of more advanced features, such
`as a fully preemptable, multithreaded kernel, full support for SMP, and an object-
`oriented interface to file systems. Solaris is the most widely used and most successful
`commercial UNIX implementation.
`
`2.10 LINUX
`
`History
` Linux started out as a UNIX variant for the IBM PC (Intel 80386) architecture.
`Linus Torvalds, a Finnish student of computer science, wrote the initial version.
`Torvalds posted an early version of Linux on the Internet in 1991. Since then, a
`number of people, collaborating over the Internet, have contributed to the devel-
`opment of Linux, all under the control of Torvalds. Because Linux is free and the
`source code is available, it became an early alternative to other UNIX workstations,
`such as those offered by Sun Microsystems and IBM. Today, Linux is a full-featured
`UNIX system that runs on all of these platforms and more, including Intel Pentium
`and Itanium, and the Motorola/IBM PowerPC.
` Key to the success of Linux has been the availability of free software packages
`under the auspices of the Free Software Foundation (FSF). FSF’s goal is stable,
`platform-independent software that is free, high quality, and embraced by the user
`community. FSF’s GNU project 3 provides tools for software developers, and the
`
`3 GNU is a recursive acronym for GNU’s Not Unix. The GNU project is a free software set of packages
`and tools for developing a UNIX-like operating system; it is often used with the Linux kernel.
`
`Patent Owner, Bot M8 LLC - Ex. 2014, p. 6
`
`

`

`94 CHAPTER 2 / OPERATING SYSTEM OVERVIEW
`
`and does so in an integrated, commercially viable fashion. SVR4 runs on processors
`ranging from 32-bit microprocessors up to supercomputers.
`
`BSD
` The Berkeley Software Distribution (BSD) series of UNIX releases have played
`a key role in the development of OS design theory. 4.xBSD is widely used in aca-
`demic installations and has served as the basis of a number of commercial UNIX
`products. It is probably safe to say that BSD is responsible for much of the popular-
`ity of UNIX and that most enhancements to UNIX first appeared in BSD versions.
` 4.4BSD was the final version of BSD to be released by Berkeley, with the
`design and implementation organization subsequently dissolved. It is a major
`upgrade to 4.3BSD and includes a new virtual memory system, changes in the ker-
`nel structure, and a long list of other feature enhancements.
` One of the most widely used and best documented versions of BSD is
`FreeBSD. FreeBSD is popular for Internet-based servers and firewalls and is used
`in a number of embedded systems.
` The latest version of the Macintosh OS, Mac OS X, is based on FreeBSD 5.0
`and the Mach 3.0 microkernel.
`
`Solaris 10
` Solaris is Sun’s SVR4-based UNIX release, with the latest version being 10. Solaris
`provides all of the features of SVR4 plus a number of more advanced features, such
`as a fully preemptable, multithreaded kernel, full support for SMP, and an object-
`oriented interface to file systems. Solaris is the most widely used and most successful
`commercial UNIX implementation.
`
`2.10 LINUX
`
`History
` Linux started out as a UNIX variant for the IBM PC (Intel 80386) architecture.
`Linus Torvalds, a Finnish student of computer science, wrote the initial version.
`Torvalds posted an early version of Linux on the Internet in 1991. Since then, a
`number of people, collaborating over the Internet, have contributed to the devel-
`opment of Linux, all under the control of Torvalds. Because Linux is free and the
`source code is available, it became an early alternative to other UNIX workstations,
`such as those offered by Sun Microsystems and IBM. Today, Linux is a full-featured
`UNIX system that runs on all of these platforms and more, including Intel Pentium
`and Itanium, and the Motorola/IBM PowerPC.
` Key to the success of Linux has been the availability of free software packages
`under the auspices of the Free Software Foundation (FSF). FSF’s goal is stable,
`platform-independent software that is free, high quality, and embraced by the user
`community. FSF’s GNU project 3 provides tools for software developers, and the
`
`3 GNU is a recursive acronym for GNU’s Not Unix. The GNU project is a free software set of packages
`and tools for developing a UNIX-like operating system; it is often used with the Linux kernel.
`
`Patent Owner, Bot M8 LLC - Ex. 2014, p. 7
`
`

`

`576 CHAPTER 13 / EMBEDDED OPERATING SYSTEMS
`
`Software
`
`FPGA/
`ASIC
`
`Human
`interface
`
`A/D
`conversion
`
`Memory
`
`Processor
`
`Auxiliary
`systems
`(power,
`cooling)
`
`Diagnostic
`port
`
`D/A
`conversion
`
`Electromechanical
`backup and safety
`
`Sensors
`
`Actuators
`
`External
`environment
` Possible Organization of an Embedded System
`
`Figure 13.1
`
` Figure 13.1 , based on [KOOP96], shows in general terms an embedded system
`organization. In addition to the processor and memory, there are a number of
` elements that differ from the typical desktop or laptop computer:
`
`• There may be a variety of interfaces that enable the system to measure,
` manipulate, and otherwise interact with the external environment.
`• The human interface may be as simple as a flashing light or as complicated as
`real-time robotic vision.
`• The diagnostic port may be used for diagnosing the system that is being
` controlled—not just for diagnosing the embedded computer.
`• Special-purpose field programmable (FPGA), application specific (ASIC), or
`even nondigital hardware may be used to increase performance or safety.
`• Software often has a fixed function and is specific to the application.
`
`
`
`
`
`
`
`
`
`
`
`13.2 CHARACTERISTICS OF EMBEDDED OPERATING SYSTEMS
`
` A simple embedded system, with simple functionality, may be controlled by a
` special-purpose program or set of programs with no other software. Typically,
`more complex embedded systems include an OS. Although it is possible in
` principle to use a general-purpose OS, such as Linux, for an embedded system,
`constraints of memory space, power consumption, and real-time requirements
`typically dictate the use of a special-purpose OS designed for the embedded
` system environment.
`
`Patent Owner, Bot M8 LLC - Ex. 2014, p. 8
`
`

`

`578 CHAPTER 13 / EMBEDDED OPERATING SYSTEMS
`
`application code; (2) protection is not necessary, as discussed in the preceding
`bullet item; and (3) efficient control over a variety of devices is required.
`
` There are two general approaches to developing an embedded OS. The
`first approach is to take an existing OS and adapt it for the embedded applica-
`tion. The other approach is to design and implement an OS intended solely for
` embedded use. 2
`
`Adapting an Existing Commercial Operating System
` An existing commercial OS can be used for an embedded system by adding real-
`time capability, streamlining operation, and adding necessary functionality. This
`approach typically makes use of Linux, but FreeBSD, Windows, and other general-
`purpose operating systems have also been used. Such operating systems are typically
`slower and less predictable than a special-purpose embedded OS. An advantage of
`this approach is that the embedded OS derived from a commercial general-purpose
`OS is based on a set of familiar interfaces, which facilitates portability.
` The disadvantage of using a general-purpose OS is that it is not optimized
`for real-time and embedded applications. Thus, considerable modification may be
`required to achieve adequate performance. In particular, a typical OS optimizes for
`the average case rather than the worst case for scheduling, usually assigns resources
`on demand, and ignores most if not all semantic information about an application.
`
`Purpose-Built Embedded Operating System
` A significant number of operating systems have been designed from the ground up
`for embedded applications. Two prominent examples of this latter approach are
`eCos and TinyOS, both of which are discussed in this chapter.
` Typical characteristics of a specialized embedded OS include the following:
`
`• Has a fast and lightweight process or thread switch
`• Scheduling policy is real time and dispatcher module is part of scheduler
`instead of separate component.
`• Has a small size
`• Responds to external interrupts quickly; typical requirement is response time
`of less than 10 μs
`• Minimizes intervals during which interrupts are disabled
`• Provides fixed or variable-sized partitions for memory management as well as
`the ability to lock code and data in memory
`• Provides special sequential files that can accumulate data at a fast rate
`
` To deal with timing constraints, the kernel
`
`• Provides bounded execution time for most primitives
`• Maintains a real-time clock
`
`2 Much of the discussion in the remainder of Section 13.2 is based on course notes on embedded systems
`from Prof. Rajesh Gupta, University of California at San Diego.
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Patent Owner, Bot M8 LLC - Ex. 2014, p. 9
`
`