Ian Wienand - Computer Science from the Bottom Up

Computer Science from the Bottom Up

Ian Wienand

A PDF version is available at . A EPUB version is available at The original souces are available at bottomupcs

This work is licensed under the Creative Commons AttributionShareAlike License. To view a copy of this license, visit or send a letter to Creative Commons, 559 Nathan Abbott Way, Stanford, California 94305, USA.

Table of Contents

Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 Welcome . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 Philosophy . . . . . . . . . . . . . . . . . . . . . . 12 Why from the bottom up?. . . . . . . . . . . 13 Enabling Technologies . . . . . . . . . . . . . 13

Chapter 1. General Unix and Advanced C . . . . . . . . . . . . . . . 13 1 Everything is a file! . . . . . . . . . . . . . . . . . . . . . 13 2 Implementing abstraction . . . . . . . . . . . . . . . . . 15 2.1 Implementing abstraction with C. . 15 2.2 Libraries . . . . . . . . . . . . . . . . . . . . . 20 3 File Descriptors . . . . . . . . . . . . . . . . . . . . . . . . . 20 3.1 The Shell . . . . . . . . . . . . . . . . . . . . 24 3.1.1 Redirection . . . . . . . . . 24 3.1.2 Implementing pipe . . . 25

Chapter 2. Binary and Number Representation . . . . . . . . . . 27 1 Binary -- the basis of computing . . . . . . . . . . . . 27 1.1 Binary Theory. . . . . . . . . . . . . . . . . 27 1.1.1 Introduction . . . . . . . . 27 1.1.2 The basis of computing . 28 1.1.3 Bits and Bytes. . . . . . . 29 1.1.3.1 ASCII . . . 29 1.1.3.2 Parity . . . 30 1.1.3.3 16, 32 and 64 bit computers . .

Copyright ? 2004?2022 Ian Wienand

1

Computer Science from the Bottom Up

30 1.1.3.4 Kilo, Mega

and Giga Bytes . 30 1.1.3.5 Kilo, Mega and Giga Bits . . 32 1.1.3.6 Conversion . 32 1.1.4 Boolean Operations . . 33 1.1.4.1 Not . . . . . 33 1.1.4.2 And . . . . . 33 1.1.4.3 Or . . . . . . 33 1.1.4.4 Exclusive Or (xor) . . . . . . . 34 1.1.5 How computers use boolean operations . . . . 34 1.1.6 Working with binary in C . . . . . . . . . . . . . . . . . . 34 1.2 Hexadecimal. . . . . . . . . . . . . . . . . . 35 1.3 Practical Implications . . . . . . . . . . 37 1.3.1 Use of binary in code . . . 37 1.3.2 Masking and Flags . . . 37 1.3.2.1 Masking . 37 1.3.2.2 Flags . . . . 39 2 Types and Number Representation . . . . . . . . . . 41 2.1 C Standards . . . . . . . . . . . . . . . . . . 41 2.1.1 GNU C . . . . . . . . . . . . 42 2.2 Types . . . . . . . . . . . . . . . . . . . . . . . 42 2.2.1 64 bit . . . . . . . . . . . . . 44 2.2.2 Type qualifiers . . . . . . 46 2.2.3 Standard Types . . . . . 46 2.2.4 Types in action . . . . . . 47 2.3 Number Representation. . . . . . . . . 50 2.3.1 Negative Values . . . . . 50 2.3.1.1 Sign Bit . . 50 2.3.1.2 One's Complement . . . 50 2.3.1.3 Two's Complement . . . 51

2.3.1.3.1 Signextension 52

2.3.2 Floating Point . . . . . . . 52 2.3.2.1 Normalised Values . . . . . . 56

2

Computer Science from the Bottom Up

2.3.2.1.1 Normalisation Tricks 56

2.3.2.2 Bringing it together . . . . 58

Chapter 3. Computer Architecture . . . . . . . . . . . . . . . . . . . . 64 1 The CPU . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64 1.1 Branching. . . . . . . . . . . . . . . . . . . . 65 1.2 Cycles . . . . . . . . . . . . . . . . . . . . . . . 65 1.3 Fetch, Decode, Execute, Store . . . . 65 1.3.1 Looking inside a CPU . . . 66 1.3.2 Pipelining . . . . . . . . . . 68 1.3.2.1 Branch Prediction . . . 69 1.3.3 Reordering . . . . . . . . . 69 1.4 CISC v RISC . . . . . . . . . . . . . . . . . . 70 1.4.1 EPIC . . . . . . . . . . . . . . 71 2 Memory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72 2.1 Memory Hierarchy . . . . . . . . . . . . . 72 2.2 Cache in depth . . . . . . . . . . . . . . . . 73 2.2.1 Cache Addressing. . . . 76 3 Peripherals and buses . . . . . . . . . . . . . . . . . . . . 78 3.1 Peripheral Bus concepts. . . . . . . . . 78 3.1.1 Interrupts . . . . . . . . . . 78 3.1.1.1 Saving state . . . . . . . 79 3.1.1.2 Interrupts v traps and exceptions . . 80 3.1.1.3 Types of interrupts . . . 80 3.1.1.4 Non-maskable interrupts . . . 81 3.1.2 IO Space . . . . . . . . . . . 81 3.2 DMA . . . . . . . . . . . . . . . . . . . . . . . . 81 3.3 Other Buses . . . . . . . . . . . . . . . . . . 82 3.3.1 USB . . . . . . . . . . . . . . 82 4 Small to big systems . . . . . . . . . . . . . . . . . . . . . 84 4.1 Symmetric Multi-Processing . . . . . 84 4.1.1 Cache Coherency . . . . 84 4.1.1.1 Cache exclusivity in SMP systems . . 86 4.1.2 Hyperthreading . . . . . 86 4.1.3 Multi Core . . . . . . . . . 87 4.2 Clusters . . . . . . . . . . . . . . . . . . . . . 87 4.3 Non-Uniform Memory Access . . . . 88

3

Computer Science from the Bottom Up

4.3.1 NUMA Machine Layout . 89

4.3.2 Cache Coherency . . . . 91 4.3.3 NUMA Applications . . 91 4.4 Memory ordering, locking and atomic operations . . . . . . . . . . . . . . . . . . . 92 4.4.1 Processors and memory

models . . . . . . . . . . . . . . 96 4.4.2 Locking . . . . . . . . . . . . 96

4.4.2.1 Locking difficulties. . . 96

4.4.2.2 Locking strategies . . . 97

4.4.3 Atomic Operations . . . 98 Chapter 4. The Operating System . . . . . . . . . . . . . . . . . . . . . 98

1 The role of the operating system . . . . . . . . . . . . 98 1.1 Abstraction of hardware . . . . . . . . 98 1.2 Multitasking . . . . . . . . . . . . . . . . . . 99 1.3 Standardised Interfaces . . . . . . . . . 99 1.4 Security . . . . . . . . . . . . . . . . . . . . 100 1.5 Performance . . . . . . . . . . . . . . . . . 100

2 Operating System Organisation. . . . . . . . . . . . 101 2.1 The Kernel . . . . . . . . . . . . . . . . . . 102 2.1.1 Monolithic v Microkernels . . . . . . . . 103 2.1.1.1 Modules . . . 104 2.1.2 Virtualisation . . . . . . 104 2.1.2.1 Covert Channels. . . 108 2.2 Userspace. . . . . . . . . . . . . . . . . . . 108

3 System Calls. . . . . . . . . . . . . . . . . . . . . . . . . . . 109 3.1 Overview . . . . . . . . . . . . . . . . . . . 109 3.1.1 System call numbers . . . 109 3.1.2 Arguments . . . . . . . . 109 3.1.3 The trap . . . . . . . . . . 109 3.1.4 libc . . . . . . . . . . . . . . 110 3.2 Analysing a system call . . . . . . . . 110 3.2.1 PowerPC . . . . . . . . . . 112 3.2.2 x86 system calls . . . . 118

4 Privileges . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123 4.1 Hardware . . . . . . . . . . . . . . . . . . . 123 4.1.1 Privilege Levels . . . . 123 4.1.1.1 386 protection model . . . . . 124 4.1.1.2 Raising Privilege . . . 125

4

Computer Science from the Bottom Up

4.1.1.3 Fast System Calls . . . . . . 125

4.2 Other ways of communicating with the kernel . . . . . . . . . . . . . . . . . . . . . . 129 4.2.1 ioctl. . . . . . . . . . . . . . 129

4.3 File Systems . . . . . . . . . . . . . . . . . 129 Chapter 5. The Process . . . . . . . . . . . . . . . . . . . . . . . . . . . . 129

1 What is a process? . . . . . . . . . . . . . . . . . . . . . . 129 2 Elements of a process . . . . . . . . . . . . . . . . . . . 130

2.1 Process ID . . . . . . . . . . . . . . . . . . 130 2.2 Memory . . . . . . . . . . . . . . . . . . . . 130

2.2.1 Code and Data . . . . . 131 2.2.2 The Stack . . . . . . . . . 131 2.2.3 The Heap . . . . . . . . . 136 2.2.4 Memory Layout . . . . 137 2.3 File Descriptors . . . . . . . . . . . . . . 138 2.4 Registers . . . . . . . . . . . . . . . . . . . 138 2.5 Kernel State . . . . . . . . . . . . . . . . . 138 2.5.1 Process State . . . . . . 139 2.5.2 Priority . . . . . . . . . . . 139 2.5.3 Statistics. . . . . . . . . . 139 3 Process Hierarchy . . . . . . . . . . . . . . . . . . . . . . 139 4 Fork and Exec . . . . . . . . . . . . . . . . . . . . . . . . . 140 4.1 Fork . . . . . . . . . . . . . . . . . . . . . . . 140 4.2 Exec . . . . . . . . . . . . . . . . . . . . . . . 141 4.3 How Linux actually handles fork and exec . . . . . . . . . . . . . . . . . . . . . . . 141 4.3.1 clone . . . . . . . . . . . . 141

4.3.1.1 Threads. . . . 141

4.3.1.2 Copy on write . . . . . . 143

4.4 The init process . . . . . . . . . . . . . . 144 4.4.1 Zombie example . . . . 145

5 Context Switching . . . . . . . . . . . . . . . . . . . . . . 146 6 Scheduling . . . . . . . . . . . . . . . . . . . . . . . . . . . . 146

6.1 Preemptive v co-operative scheduling . . . . . . . . . . . . . . . . . . 146

6.2 Realtime . . . . . . . . . . . . . . . . . . . . 147 6.3 Nice value . . . . . . . . . . . . . . . . . . 147 6.4 A brief look at the Linux Scheduler . .

148 7 The Shell . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 149 8 Signals . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 150

8.1 Example . . . . . . . . . . . . . . . . . . . . 151 Chapter 6. Virtual Memory . . . . . . . . . . . . . . . . . . . . . . . . . 154

1 What Virtual Memory isn't. . . . . . . . . . . . . . . . 154 2 What virtual memory is . . . . . . . . . . . . . . . . . . 154

2.1 64 bit computing . . . . . . . . . . . . . 155

5

 ................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download