Operating System Design

Contents

xixPreface

xxiiiAbout The Author

1Chapter 1 Introduction and Overview

1.1 Operating Systems 1

1.2 Approach Used In The Text 3

1.3 A Hierarchical Design 3

1.4 The Xinu Operating System 5

1.5 What An Operating System Is Not 6

1.6 An Operating System Viewed From The Outside 7

1.7 Remainder Of The Text 8

1.8 Perspective 8

1.9 Summary 9

11Chapter 2 Concurrent Execution And Operating System Services

2.1 Introduction 11

2.2 Programming Models For Multiple Activities 12

2.3 Operating System Services 13

2.4 Concurrent Processing Concepts And Terminology 13

2.5 Distinction Between Sequential And Concurrent Programs 15

2.6 Multiple Processes Sharing A Single Piece Of Code 17

2.7 Process Exit And Process Termination 19

2.8 Shared Memory, Race Conditions, And Synchronization 20

2.9 Semaphores And Mutual Exclusion 24

2.10 Type Names Used In Xinu 26

2.11 Operating System Debugging With Kputc And Kprintf 27

2.12 Perspective 28

2.13 Summary 28

viii Contents

31Chapter 3 An Overview Of The Hardware and Run-Time Environment

3.1 Introduction 31

3.2 Physical And Logical Organizations Of The E2100L 32

3.3 Processor Organization And Registers 33

3.4 Bus Operation: The Fetch-Store Paradigm 34

3.5 Direct Memory Access 34

3.6 The Bus Address Space 35

3.7 Contents Of Kernel Segments KSEG0 and KSEG1 36

3.8 Bus Startup Static Configuration 37

3.9 Calling Conventions And The Run-Time Stack 38

3.10 Interrupts And Interrupt Processing 40

3.11 Exception Processing 41

3.12 Timer Hardware 42

3.13 Serial Communication 42

3.14 Polled vs. Interrupt-Driven I/O 43

3.15 Memory Cache And KSEG1 43

3.16 Storage Layout 44

3.17 Memory Protection 45

3.18 Perspective 45

49Chapter 4 List and Queue Manipulation

4.1 Introduction 49

4.2 A Unified Structure For Linked Lists Of Processes 50

4.3 A Compact List Data Structure 51

4.4 Implementation Of The Queue Data Structure 53

4.5 Inline Queue Manipulation Functions 55

4.6 Basic Functions To Extract A Process From A List 55

4.7 FIFO Queue Manipulation 57

4.8 Manipulation Of Priority Queues 60

4.9 List Initialization 62

4.10 Perspective 63

4.11 Summary 64

67Chapter 5 Scheduling and Context Switching

5.1 Introduction 67

5.2 The Process Table 68

5.3 Process States 71

5.4 Ready And Current States 72

5.5 A Scheduling Policy 72

5.6 Implementation Of Scheduling 73

Contents ix

5.7 Implementation Of Context Switching 76

5.8 State Saved In Memory 76

5.9 Context Switch On A MIPS Processor 77

5.10 An Address At Which To Restart A Process 80

5.11 Concurrent Execution And A Null Process 81

5.12 Making A Process Ready And The Scheduling Invariant 82

5.13 Deferred Rescheduling 83

5.14 Other Process Scheduling Algorithms 85

5.15 Perspective 86

5.16 Summary 86

89Chapter 6 More Process Management

6.1 Introduction 89

6.2 Process Suspension And Resumption 89

6.3 Self-Suspension And Information Hiding 90

6.4 The Concept Of A System Call 91

6.5 Interrupt Control With Disable And Restore 93

6.6 A System Call Template 94

6.7 System Call Return Values SYSERR And OK 95

6.8 Implementation Of Suspend 95

6.9 Suspending The Current Process 97

6.10 Suspend Return Value 97

6.11 Process Termination And Process Exit 98

6.12 Process Creation 101

6.13 Other Process Manager Functions 106

6.14 Summary 108

111Chapter 7 Coordination Of Concurrent Processes

7.1 Introduction 111

7.2 The Need For Synchronization 111

7.3 A Conceptual View Of Counting Semaphores 113

7.4 Avoidance Of Busy Waiting 113

7.5 Semaphore Policy And Process Selection 114

7.6 The Waiting State 115

7.7 Semaphore Data Structures 116

7.8 The Wait System Call 117

7.9 The Signal System Call 118

7.10 Static And Dynamic Semaphore Allocation 119

7.11 Example Implementation Of Dynamic Semaphores 120

7.12 Semaphore Deletion 121

7.13 Semaphore Reset 123

x Contents

7.14 Coordination Across Parallel Processors (Multicore) 124

7.15 Perspective 125

7.16 Summary 125

129Chapter 8 Message Passing

8.1 Introduction 129

8.2 Two Types Of Message Passing Services 129

8.3 Limits On Resources Used By Messages 130

8.4 Message Passing Functions And State Transitions 131

8.5 Implementation Of Send 132

8.6 Implementation Of Receive 134

8.7 Implementation Of Non-Blocking Message Reception 135

8.8 Perspective 135

8.9 Summary 136

139Chapter 9 Basic Memory Management

9.1 Introduction 139

9.2 Types Of Memory 139

9.3 Definition Of A Heavyweight Process 140

9.4 Memory Management In A Small Embedded System 141

9.5 Program Segments And Regions Of Memory 142

9.6 Dynamic Memory Allocation In An Embedded System 143

9.7 Design Of The Low-Level Memory Manager 144

9.8 Allocation Strategy And Memory Persistence 144

9.9 Keeping Track Of Free Memory 145

9.10 Implementation Of Low-Level Memory Management 146

9.11 Allocating Heap Storage 148

9.12 Allocating Stack Storage 151

9.13 Releasing Heap And Stack Storage 153

9.14 Perspective 156

9.15 Summary 156

159Chapter 10 High-Level Memory Management and Virtual Memory

10.1 Introduction 159

10.2 Partitioned Space Allocation 160

10.3 Buffer Pools 160

10.4 Allocating A Buffer 162

10.5 Returning Buffers To The Buffer Pool 164

10.6 Creating A Buffer Pool 165

10.7 Initializing The Buffer Pool Table 167