文件名称：The Little Book of Semaphores
文件大小：820KB
文件格式：PDF
更新时间：2012-10-15 03:17:22
sync Semaphore parallel
大量例子讲述Semaphore的应用。 1 Introduction 1 1.1 Synchronization . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.2 Execution model . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.3 Serialization with messages . . . . . . . . . . . . . . . . . . . . . 3 1.4 Non-determinism . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.5 Shared variables . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.5.1 Concurrent writes . . . . . . . . . . . . . . . . . . . . . . 4 1.5.2 Concurrent updates . . . . . . . . . . . . . . . . . . . . . 5 1.5.3 Mutual exclusion with messages . . . . . . . . . . . . . . 6 2 Semaphores 7 2.1 Definition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 2.2 Syntax . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 2.3 Why semaphores? . . . . . . . . . . . . . . . . . . . . . . . . . . 9 3 Basic synchronization patterns 11 3.1 Signaling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 3.2 Rendezvous . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 3.2.1 Rendezvous hint . . . . . . . . . . . . . . . . . . . . . . . 13 3.2.2 Rendezvous solution . . . . . . . . . . . . . . . . . . . . . 15 3.2.3 Deadlock #1 . . . . . . . . . . . . . . . . . . . . . . . . . 15 3.3 Mutex . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 3.3.1 Mutual exclusion hint . . . . . . . . . . . . . . . . . . . . 17 3.3.2 Mutual exclusion solution . . . . . . . . . . . . . . . . . . 19 3.4 Multiplex . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 3.4.1 Multiplex solution . . . . . . . . . . . . . . . . . . . . . . 21 3.5 Barrier . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 3.5.1 Barrier hint . . . . . . . . . . . . . . . . . . . . . . . . . . 23 3.5.2 Barrier non-solution . . . . . . . . . . . . . . . . . . . . . 25 3.5.3 Deadlock #2 . . . . . . . . . . . . . . . . . . . . . . . . . 27 3.5.4 Barrier solution . . . . . . . . . . . . . . . . . . . . . . . . 29 3.5.5 Deadlock #3 . . . . . . . . . . . . . . . . . . . . . . . . . 31 3.6 Reusable barrier . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 3.6.1 Reusable barrier non-solution #1 . . . . . . . . . . . . . . 33 3.6.2 Reusable barrier problem #1 . . . . . . . . . . . . . . . . 35 3.6.3 Reusable barrier non-solution #2 . . . . . . . . . . . . . . 37 3.6.4 Reusable barrier hint . . . . . . . . . . . . . . . . . . . . . 39 3.6.5 Reusable barrier solution . . . . . . . . . . . . . . . . . . 41 3.6.6 Preloaded turnstile . . . . . . . . . . . . . . . . . . . . . . 43 3.6.7 Barrier objects . . . . . . . . . . . . . . . . . . . . . . . . 44 3.7 Queue . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 3.7.1 Queue hint . . . . . . . . . . . . . . . . . . . . . . . . . . 47 3.7.2 Queue solution . . . . . . . . . . . . . . . . . . . . . . . . 49 3.7.3 Exclusive queue hint . . . . . . . . . . . . . . . . . . . . . 51 3.7.4 Exclusive queue solution . . . . . . . . . . . . . . . . . . . 53 3.8 Fifo queue . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55 3.8.1 Fifo queue hint . . . . . . . . . . . . . . . . . . . . . . . . 57 3.8.2 Fifo queue solution . . . . . . . . . . . . . . . . . . . . . . 59 4 Classical synchronization problems 61 4.1 Producer-consumer problem . . . . . . . . . . . . . . . . . . . . . 61 4.1.1 Producer-consumer hint . . . . . . . . . . . . . . . . . . . 63 4.1.2 Producer-consumer solution . . . . . . . . . . . . . . . . . 65 4.1.3 Deadlock #4 . . . . . . . . . . . . . . . . . . . . . . . . . 67 4.1.4 Producer-consumer with a finite buffer . . . . . . . . . . . 67 4.1.5 Finite buffer producer-consumer hint . . . . . . . . . . . . 69 4.1.6 Finite buffer producer-consumer solution . . . . . . . . . 71 4.2 Readers-writers problem . . . . . . . . . . . . . . . . . . . . . . . 71 4.2.1 Readers-writers hint . . . . . . . . . . . . . . . . . . . . . 73 4.2.2 Readers-writers solution . . . . . . . . . . . . . . . . . . . 75 4.2.3 Starvation . . . . . . . . . . . . . . . . . . . . . . . . . . . 77 4.2.4 No-starve readers-writers hint . . . . . . . . . . . . . . . . 79 4.2.5 No-starve readers-writers solution . . . . . . . . . . . . . 81 4.2.6 Writer-priority readers-writers hint . . . . . . . . . . . . . 83 4.2.7 Writer-priority readers-writers solution . . . . . . . . . . . 85 4.3 No-starve mutex . . . . . . . . . . . . . . . . . . . . . . . . . . . 87 4.3.1 No-starve mutex hint . . . . . . . . . . . . . . . . . . . . 89 4.3.2 No-starve mutex solution . . . . . . . . . . . . . . . . . . 91 4.4 Dining philosophers . . . . . . . . . . . . . . . . . . . . . . . . . 93 4.4.1 Deadlock #5 . . . . . . . . . . . . . . . . . . . . . . . . . 95 4.4.2 Dining philosophers hint #1 . . . . . . . . . . . . . . . . . 97 4.4.3 Dining philosophers solution #1 . . . . . . . . . . . . . . 99 4.4.4 Dining philosopher¡¯s solution #2 . . . . . . . . . . . . . . 101 4.4.5 Tanenbaum¡¯s solution . . . . . . . . . . . . . . . . . . . . 103 4.4.6 Starving Tanenbaums . . . . . . . . . . . . . . . . . . . . 105 4.5 Cigarette smokers problem . . . . . . . . . . . . . . . . . . . . . . 107 4.5.1 Deadlock #6 . . . . . . . . . . . . . . . . . . . . . . . . . 111 4.5.2 Smokers problem hint . . . . . . . . . . . . . . . . . . . . 113 CONTENTS vii 4.5.3 Smoker problem solution . . . . . . . . . . . . . . . . . . 115 4.5.4 Generalized Smokers Problem . . . . . . . . . . . . . . . . 115 4.5.5 Generalized Smokers Problem Hint . . . . . . . . . . . . . 117 4.5.6 Generalized Smokers Problem Solution . . . . . . . . . . . 119 5 Less classical synchronization problems 121 5.1 The dining savages problem . . . . . . . . . . . . . . . . . . . . . 121 5.1.1 Dining Savages hint . . . . . . . . . . . . . . . . . . . . . 123 5.1.2 Dining Savages solution . . . . . . . . . . . . . . . . . . . 125 5.2 The barbershop problem . . . . . . . . . . . . . . . . . . . . . . . 127 5.2.1 Barbershop hint . . . . . . . . . . . . . . . . . . . . . . . 129 5.2.2 Barbershop solution . . . . . . . . . . . . . . . . . . . . . 131 5.3 Hilzer¡¯s Barbershop problem . . . . . . . . . . . . . . . . . . . . . 133 5.3.1 Hilzer¡¯s barbershop hint . . . . . . . . . . . . . . . . . . . 134 5.3.2 Hilzer¡¯s barbershop solution . . . . . . . . . . . . . . . . . 135 5.4 The Santa Claus problem . . . . . . . . . . . . . . . . . . . . . . 137 5.4.1 Santa problem hint . . . . . . . . . . . . . . . . . . . . . . 139 5.4.2 Santa problem solution . . . . . . . . . . . . . . . . . . . 141 5.5 Building H2O . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143 5.5.1 H2O hint . . . . . . . . . . . . . . . . . . . . . . . . . . . 145 5.5.2 H2O solution . . . . . . . . . . . . . . . . . . . . . . . . . 147 5.6 River crossing problem . . . . . . . . . . . . . . . . . . . . . . . . 148 5.6.1 River crossing hint . . . . . . . . . . . . . . . . . . . . . . 149 5.6.2 River crossing solution . . . . . . . . . . . . . . . . . . . . 151 5.7 The roller coaster problem . . . . . . . . . . . . . . . . . . . . . . 153 5.7.1 Roller Coaster hint . . . . . . . . . . . . . . . . . . . . . . 155 5.7.2 Roller Coaster solution . . . . . . . . . . . . . . . . . . . . 157 5.7.3 Multi-car Roller Coaster problem . . . . . . . . . . . . . . 159 5.7.4 Multi-car Roller Coaster hint . . . . . . . . . . . . . . . . 161 5.7.5 Multi-car Roller Coaster solution . . . . . . . . . . . . . . 163 6 Not-so-classical problems 165 6.1 The search-insert-delete problem . . . . . . . . . . . . . . . . . . 165 6.1.1 Search-Insert-Delete hint . . . . . . . . . . . . . . . . . . 167 6.1.2 Search-Insert-Delete solution . . . . . . . . . . . . . . . . 169 6.2 The unisex bathroom problem . . . . . . . . . . . . . . . . . . . . 170 6.2.1 Unisex bathroom hint . . . . . . . . . . . . . . . . . . . . 171 6.2.2 Unisex bathroom solution . . . . . . . . . . . . . . . . . . 173 6.2.3 No-starve unisex bathroom problem . . . . . . . . . . . . 175 6.2.4 No-starve unisex bathroom solution . . . . . . . . . . . . 177 6.3 Baboon crossing problem . . . . . . . . . . . . . . . . . . . . . . 177 6.4 The Modus Hall Problem . . . . . . . . . . . . . . . . . . . . . . 178 6.4.1 Modus Hall problem hint . . . . . . . . . . . . . . . . . . 179 6.4.2 Modus Hall problem solution . . . . . . . . . . . . . . . . 181 viii CONTENTS 7 Not remotely classical problems 183 7.1 The sushi bar problem . . . . . . . . . . . . . . . . . . . . . . . . 183 7.1.1 Sushi bar hint . . . . . . . . . . . . . . . . . . . . . . . . . 185 7.1.2 Sushi bar non-solution . . . . . . . . . . . . . . . . . . . . 187 7.1.3 Sushi bar non-solution . . . . . . . . . . . . . . . . . . . . 189 7.1.4 Sushi bar solution #1 . . . . . . . . . . . . . . . . . . . . 191 7.1.5 Sushi bar solution #2 . . . . . . . . . . . . . . . . . . . . 193 7.2 The child care problem . . . . . . . . . . . . . . . . . . . . . . . . 194 7.2.1 Child care hint . . . . . . . . . . . . . . . . . . . . . . . . 195 7.2.2 Child care non-solution . . . . . . . . . . . . . . . . . . . 197 7.2.3 Child care solution . . . . . . . . . . . . . . . . . . . . . . 199 7.2.4 Extended child care problem . . . . . . . . . . . . . . . . 199 7.2.5 Extended child care hint . . . . . . . . . . . . . . . . . . . 201 7.2.6 Extended child care solution . . . . . . . . . . . . . . . . 203 7.3 The room party problem . . . . . . . . . . . . . . . . . . . . . . . 205 7.3.1 Room party hint . . . . . . . . . . . . . . . . . . . . . . . 207 7.3.2 Room party solution . . . . . . . . . . . . . . . . . . . . . 209 7.4 The Senate Bus problem . . . . . . . . . . . . . . . . . . . . . . . 211 7.4.1 Bus problem hint . . . . . . . . . . . . . . . . . . . . . . . 213 7.4.2 Bus problem solution #1 . . . . . . . . . . . . . . . . . . 215 7.4.3 Bus problem solution #2 . . . . . . . . . . . . . . . . . . 217 7.5 The Faneuil Hall problem . . . . . . . . . . . . . . . . . . . . . . 219 7.5.1 Faneuil Hall Problem Hint . . . . . . . . . . . . . . . . . . 221 7.5.2 Faneuil Hall problem solution . . . . . . . . . . . . . . . . 223 7.5.3 Extended Faneuil Hall Problem Hint . . . . . . . . . . . . 225 7.5.4 Extended Faneuil Hall problem solution . . . . . . . . . . 227 7.6 Dining Hall problem . . . . . . . . . . . . . . . . . . . . . . . . . 229 7.6.1 Dining Hall problem hint . . . . . . . . . . . . . . . . . . 231 7.6.2 Dining Hall problem solution . . . . . . . . . . . . . . . . 233 7.6.3 Extended Dining Hall problem . . . . . . . . . . . . . . . 234 7.6.4 Extended Dining Hall problem hint . . . . . . . . . . . . . 235 7.6.5 Extended Dining Hall problem solution . . . . . . . . . . 237 8 Synchronization in Python 239 8.1 Mutex checker problem . . . . . . . . . . . . . . . . . . . . . . . 240 8.1.1 Mutex checker hint . . . . . . . . . . . . . . . . . . . . . . 243 8.1.2 Mutex checker solution . . . . . . . . . . . . . . . . . . . 245 8.2 The coke machine problem . . . . . . . . . . . . . . . . . . . . . . 247 8.2.1 Coke machine hint . . . . . . . . . . . . . . . . . . . . . . 249 8.2.2 Coke machine solution . . . . . . . . . . . . . . . . . . . . 251 9 Synchronization in C 253 9.1 Mutual exclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . 253 9.1.1 Parent code . . . . . . . . . . . . . . . . . . . . . . . . . . 254 9.1.2 Child code . . . . . . . . . . . . . . . . . . . . . . . . . . 254 9.1.3 Synchronization errors . . . . . . . . . . . . . . . . . . . . 255 CONTENTS ix 9.1.4 Mutual exclusion hint . . . . . . . . . . . . . . . . . . . . 257 9.1.5 Mutual exclusion solution . . . . . . . . . . . . . . . . . . 259 9.2 Make your own semaphores . . . . . . . . . . . . . . . . . . . . . 261 9.2.1 Semaphore implementation hint . . . . . . . . . . . . . . 263 9.2.2 Semaphore implementation . . . . . . . . . . . . . . . . . 265 9.2.3 Semaphore implementation detail . . . . . . . . . . . . . . 267 A Cleaning up Python threads 271 A.1 Semaphore methods . . . . . . . . . . . . . . . . . . . . . . . . . 271 A.2 Creating threads . . . . . . . . . . . . . . . . . . . . . . . . . . . 271 A.3 Handling keyboard interrupts . . . . . . . . . . . . . . . . . . . . 272 B Cleaning up POSIX threads 275 B.1 Compiling Pthread code . . . . . . . . . . . . . . . . . . . . . . . 275 B.2 Creating threads . . . . . . . . . . . . . . . . . . . . . . . . . . . 276 B.3 Joining threads . . . . . . . . . . . . . . . . . . . . . . . . . . . . 277 B.4 Semaphores . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 278