计算机系统研究基础 英文版PDF电子书下载

Part Ⅰ General 3

1 Elements 3

1.1 Top Systems Conferences/Journals 3

1.2 How to Read a Research Paper 5

1.3 How to Write a Research Paper 6

1.3.1 Abstract 6

1.3.2 Introduction 6

1.3.3 Background Information/Problem Statement 6

1.3.4 Your Approach 6

1.3.5 Implementation 6

1.3.6 Performance Evaluation 7

1.3.7 Related Work 7

1.3.8 Conclusions 7

1.3.9 Acknowledgement 7

1.3.10 References 8

1.3.11 Most Common Mistakes in Paper Writing 8

1.4 How to Give a Presentation 9

1.4.1 General Approach 9

1.4.2 Understanding the Paper 10

1.4.3 Adapting the Paper for Presentation 10

1.4.4 Slides 11

1.4.5 The Dry-Run 12

1.4.6 To Memorize or not to Memorize? 13

1.4.7 You Are on the Stage 13

1.4.8 Interacting with the Audience and Dealing with Questions 14

1.5 Final Words:On Being a Scientist 14

References 15

2 Rules of Thumb 16

2.1 Rules of Thumb 16

2.2 Further Readings 17

References 17

Part Ⅱ Design 21

3 Bloom Filters 21

3.1 Introduction 21

3.2 Standard Bloom Filters 22

3.2.1 Basic Idea of Bloom Filters 22

3.2.2 False Positive Rate Estimation 23

3.2.3 Optimal Number of Hash Functions 23

3.2.4 Another Method of Implementing 24

3.3 Counting Bloom Filters 25

3.4 Compressed Bloom Filters 27

3.5 D-left Counting Bloom Filters 28

3.5.1 D-left Hashing 28

3.5.2 D-left Counting Bloom Filters 29

3.5.3 Performance 30

3.6 Spectral Bloom Filters 31

3.6.1 Basic Principle of SBF 31

3.6.2 SBF Frequency Query Optimization 33

3.7 Dynamic Counting Bloom Filters 33

3.8 Case Studies 34

3.8.1 Case Study 1:Summary Cache 35

3.8.2 Case Study 2:IP Traceback 36

3.9 Conclusion 36

References 37

4 Distributed Hash Tables 38

4.1 Introduction 38

4.2 An Overview of DHT 39

4.3 The Overlay Network of DHT 40

4.4 Chord:An Implementation of DHT 42

4.4.1 Topology of Chord 42

4.4.2 Key Lookup in Chord 42

4.4.3 Dynamic Updates and Failure Recovery 44

4.5 Case Study 1:Cooperative Domain Name System(CoDoNS) 46

4.5.1 Background and Motivation 46

4.5.2 Overview of the System 47

4.5.3 DHT in CoDoNS 47

4.5.4 Evaluation 48

4.6 Case Study 2:Cooperative File System(CFS) 48

4.6.1 Background and Motivation 48

4.6.2 Overview of the System 49

4.6.3 DHT in CFS 49

4.6.4 Evaluation 49

References 50

5 Locality Sensitive Hashing 52

5.1 Introduction 52

5.1.1 Basic Idea of LSH 52

5.1.2 The Origin of LSH 53

5.2 Overview 53

5.2.1 The Definition 53

5.2.2 Properties of LSH 54

5.2.3 Several LSH Families 54

5.2.4 Approximate Nearest Neighbor 58

5.3 Case Study 1:Large-Scale Sequence Comparison 60

5.3.1 Theory 60

5.3.2 Algorithm Complexity 61

5.3.3 Implementation Details 61

5.3.4 Results 62

5.4 Case Study 2:Image Retrieval 62

5.4.1 Motivation 62

5.4.2 The Problems of Existing Approaches 62

5.4.3 The System 63

5.4.4 Results 63

References 63

6 XOR Operations 65

6.1 Introduction 65

6.2 XOR Operation 65

6.2.1 Truth Table 66

6.2.2 Set Diagrams 66

6.3 XOR Properties 66

6.4 Compress with XOR 67

6.4.1 Case Study 1:XOR-linked list 67

6.4.2 Case Study 2:XOR swap algorithm 68

6.5 Fault Tolerance 68

6.5.1 Case Study 3:Hamming(7,4)code 68

6.5.2 Hamming Codes with Additional Parity 70

6.5.3 Case Study 4:RAID 70

6.6 Case Study 5:Feistel Cipher 71

6.7 Case Study 6:Kademlia 72

6.7.1 XOR Metric in Kademlia 73

6.7.2 Routing Table in Kademlia 74

6.7.3 Kademlia Protocol 74

6.8 Conclusion 75

References 76

7 Adaptation 77

7.1 Introduction 77

7.2 How Adaptation Works and Key Issues 78

7.2.1 How Does Adaptation Work? 78

7.2.2 Classification of Adaptation 80

7.3 Case Studies 83

7.3.1 Case Study 1:Adaption in Internet Routing System 83

7.3.2 Case Study 2:Adaptive Self-Configuration for Sensor Networks 87

References 90

8 Optimistic Replication 92

8.1 Introduction 92

8.2 Topic Description 94

8.2.1 Design Considerations 94

8.2.2 Techniques and Algorithms 95

8.3 Case Studies 100

8.3.1 Case Study 1:The Notes System 100

8.3.2 Case Study 2:The Bayou system 102

References 106

9 Reputation and Trust 107

9.1 Introduction 107

9.2 Reputation Systems:Challenges and Models 108

9.2.1 Challenges 108

9.2.2 Reputation Models 109

9.2.3 Threat Model 113

9.3 Comparison of Representative Work 114

9.4 Case Studies 116

9.4.1 Case Study 1:EigenTrust 117

9.4.2 Case Study 2:HOURS 117

9.5 Conclusion 118

References 118

10 Moving Average 120

10.1 Introduction 120

10.2 Topic Description 120

10.2.1 Simple Moving Average 121

10.2.2 Cumulative Moving Average 121

10.2.3 Weighted Moving Average 121

10.2.4 Exponential Weighted Moving Average 122

10.3 Case Study 1:Attacks Detection 123

10.3.1 Introduction of Denial of Service Attack 123

10.3.2 Anomalies Detection 124

10.3.3 SYN Flooding Detection 126

10.3.4 Other Methods 126

10.4 Case Study 2:Machine Monitoring Technique 127

10.5 Case Study 3:Data Cleaning in Wireless Sensor Networks 130

10.6 Conclusion 132

References 132

11 Machine Learning 134

11.1 Machine Learning Concepts 134

11.1.1 Concepts and History 135

11.2 Introduction of Machine Learning 136

11.2.1 A Typical Machine Learning Problem 136

11.2.2 Machine Learning in Computer Systems Research 139

11.3 Machine Learning Techniques 140

11.3.1 Category 140

11.3.2 Machine Learning Techniques and Algorithms 142

11.4 Case Studies 145

11.4.1 Case Study 1:Large-Scale System Problem Detection 145

11.4.2 Case Study 2:Snitch 146

11.5 Conclusion 147

References 148

Part Ⅲ Implementation 153

12 Asynchronous I/O 153

12.1 Motivation 153

12.2 I/O Multiplexing 155

12.3 Asynchronous I/O 158

12.3.1 Linux Asynchronous I/O 158

12.3.2 Windows Overlapped I/O 164

12.4 Conclusion 172

References 172

13 Multithreading 173

13.1 Background 173

13.2 The Concept of Thread 174

13.3 Hardware Support for Multithreading 175

13.3.1 Block Multithreading 175

13.3.2 Interleaved Multithreading 176

13.3.3 Simultaneous Multithreading 176

13.4 Multithreading Programming 176

13.4.1 POSIX Threads(Pthreads) 177

13.4.2 JAVA Threads 178

13.4.3 WIN32 Threads 178

13.4.4 Common APIs 180

13.5 Multithreading Synchronization 184

13.5.1 Multithreading Synchronization Problems 184

13.5.2 Mutual Exclusion 185

13.5.3 Solutions of Mutual Exclusion 186

13.5.4 Mutual Exclusion Cases 187

13.6 Case Studies 188

13.7 Conclusion 199

References 189

14 Virtualization 191

14.1 Virtualization Definitions 191

14.2 A Brief History of Virtualization 192

14.2.1 The Mainframe Virtualization 193

14.2.2 The x86 Virtualization 193

14.3 Why Virtualization? 194

14.4 Virtualization Capabilities 196

14.5 The Benefits of Virtualization 196

14.5.1 Increasing Utilization 196

14.5.2 Reducing Cost 197

14.5.3 Isolation 197

14.5.4 Improving Application Development Process 197

14.5.5 Business Continuity 198

14.5.6 Manageability,Scalability and Flexibility 198

14.6 Types of Virtualization 199

14.7 Virtualization Vendors and Products 201

14.8 Case Studies 201

14.8.1 Case Study 1:JVM 202

14.8.2 Case Study 2:VirtualPower 204

14.9 Issues of Virtualization 205

14.9.1 Issues of Adopting Virtualization 205

14.9.2 Issues of Providing Virtualization 206

References 208

Part Ⅳ Evaluation 213

15 Queueing Theory 213

15.1.1 Queueing Models 214

15.2 Fundamental Concepts 216

15.2.1 Useful Probability Distributions 216

15.2.2 Markov Chain 218

15.3 Queueing Systems 219

15.3.1 Markovian Queues 220

15.3.2 Non-Markovian Queues 224

15.4 Queueing Networks 226

15.5 Case Studies 227

15.5.1 Case Study 1:Telephone Systems 227

15.5.2 Case Study 2:A Barber Shop 227

References 229

16 Black Box Testing 230

16.1 Introduction 230

16.2 Black Box Testing Techniques 231

16.2.1 Equivalence Partitioning 231

16.2.2 Boundary Value Analysis 232

16.2.3 Decision Table Testing 232

16.2.4 Pairwise Testing 233

16.2.5 State Transition Tables 233

16.2.6 Use Case Testing 234

16.3 Other Methods of Software Testing 234

16.4 Case Studies 235

16.4.1 Case Study 1:Web Services 235

16.4.2 Case Study 2:MobileTest 239

References 242

17 Goodness-of-Fit 244

17.1 Introduction 244

17.2 General Topics in Goodness-of-Fit 245

17.2.1 Hypothesis Testing 246

17.2.2 Definition 247

17.2.3 Common Problems in Goodness-of-Fit Tests 247

17.2.4 Quantitative Goodness-of-fit Techniques 249

17.3 Chi-Square Test 249

17.3.1 Meaning of the Chi-Square Test 250

17.3.2 Definition of Chi-Square 251

17.4 Kolmogorov-Smirnov test 254

17.4.1 How Does K-S Test Work? 255

17.4.2 Comparison of Chi-Square and Kolmogorov-Smirnov Tests 261

17.5 Case Studies 262

17.5.1 Case Study 1:Object Characteristics of Dynamic Web Content 262

17.5.2 Case Study 2:Failures in High-Performance Computing Systems 263

References 263

Index 265