UNIX systems programming: communication, concurrency and threads

Cover......Page 1
Contents......Page 6
I: Fundamentals......Page 20
 1 Technology’s Impact on Programs......Page 22
  1.1 Terminology of Change......Page 23
  1.2 Time and Speed......Page 24
  1.3 Multiprogramming and Time Sharing......Page 26
  1.4 Concurrency at the Applications Level......Page 28
  1.5 Security and Fault Tolerance......Page 32
  1.6 Buffer Overflows for Breaking and Entering......Page 33
  1.7 UNIX Standards......Page 37
  1.8 Additional Reading......Page 39
 2 Programs, Processes and Threads......Page 40
  2.1 How a Program Becomes a Process......Page 41
  2.2 Threads and Thread of Execution......Page 42
  2.3 Layout of a Program Image......Page 43
  2.4 Library Function Calls......Page 45
  2.5 Function Return Values and Errors......Page 48
  2.6 Argument Arrays......Page 50
  2.7 Thread-Safe Functions......Page 57
  2.8 Use of Static Variables......Page 59
  2.9 Structure of Static Objects......Page 61
  2.10 Process Environment......Page 67
  2.11 Process Termination......Page 70
  2.12 Exercise: An env Utility......Page 73
  2.13 Exercise: Message Logging......Page 74
  2.14 Additional Reading......Page 75
 3 Processes in UNIX......Page 78
  3.1 Process Identification......Page 79
  3.2 Process State......Page 80
  3.3 UNIX Process Creation and fork......Page 83
  3.4 The wait Function......Page 90
  3.5 The exec Function......Page 97
  3.6 Background Processes and Daemons......Page 103
  3.7 Critical Sections......Page 105
  3.8 Exercise: Process Chains......Page 106
  3.9 Exercise: Process Fans......Page 107
  3.10 Additional Reading......Page 108
 4 UNIX I/O......Page 110
  4.2 Reading and Writing......Page 111
  4.3 Opening and Closing Files......Page 121
  4.4 The select Function......Page 126
  4.5 The poll Function......Page 135
  4.6 File Representation......Page 138
  4.7 Filters and Redirection......Page 147
  4.8 File Control......Page 151
  4.9 Exercise: Atomic Logging......Page 154
  4.10 Exercise: A cat Utility......Page 160
  4.11 Additional Reading......Page 162
 5 Files and Directories......Page 164
  5.1 UNIX File System Navigation......Page 165
  5.2 Directory Access......Page 171
  5.3 UNIX File System Implementation......Page 177
  5.4 Hard Links and Symbolic Links......Page 181
  5.5 Exercise: The which Command......Page 192
  5.6 Exercise: Biffing......Page 193
  5.7 Exercise: News biff......Page 196
  5.8 Exercise: Traversing Directories......Page 198
  5.9 Additional Reading......Page 200
 6 UNIX Special Files......Page 202
  6.1 Pipes......Page 203
  6.2 Pipelines......Page 207
  6.3 FIFOs......Page 211
  6.4 Pipes and the Client-Server Model......Page 215
  6.5 Terminal Control......Page 222
  6.6 Audio Device......Page 233
  6.7 Exercise: Audio......Page 238
  6.8 Exercise: Barriers......Page 240
  6.11 Additional Reading......Page 242
 7 Project: The Token Ring......Page 244
  7.1 Ring Topology......Page 245
  7.2 Ring Formation......Page 246
  7.3 Ring Exploration......Page 253
  7.4 Simple Communication......Page 255
  7.5 Mutual Exclusion with Tokens......Page 256
  7.6 Mutual Exclusion by Voting......Page 257
  7.7 Leader Election on an Anonymous Ring......Page 258
  7.8 Token Ring for Communication......Page 260
  7.9 Pipelined Preprocessor......Page 262
  7.10 Parallel Ring Algorithms......Page 265
  7.11 Flexible Ring......Page 269
  7.12 Additional Reading......Page 270
II: Asynchronous Events......Page 272
 8 Signals......Page 274
  8.2 Generating Signals......Page 275
  8.3 Manipulating Signal Masks and Signal Sets......Page 280
  8.4 Catching and Ignoring Signals—sigaction......Page 286
  8.5 Waiting for Signals—pause, sigsuspend and sigwait......Page 292
  8.6 Handling Signals: Errors and Async-signal Safety......Page 302
  8.7 Program Control with siglongjmp and sigsetjmp......Page 305
  8.8 Programming with Asynchronous I/O......Page 307
  8.10 Exercise: Spooling a Slow Device......Page 318
  8.11 Additional Reading......Page 319
 9 Times and Timers......Page 320
  9.1 POSIX Times......Page 321
  9.2 Sleep Functions......Page 333
  9.3 POSIX:XSI Interval Timers......Page 334
  9.4 Realtime Signals......Page 339
  9.5 POSIX:TMR Interval Timers......Page 343
  9.6 Timer Drift, Overruns and Absolute Time......Page 348
  9.7 Additional Reading......Page 358
 10 Project: Virtual Timers......Page 360
  10.1 Project Overview......Page 361
  10.2 Simple Timers......Page 363
  10.3 Setting One of Five Single Timers......Page 366
  10.4 Using Multiple Timers......Page 376
  10.5 A Robust Implementation of Multiple Timers......Page 382
  10.7 mycron, a Small Cron Facility......Page 386
  10.8 Additional Reading......Page 387
 11 Project: Cracking Shells......Page 388
  11.1 Building a Simple Shell......Page 389
  11.2 Redirection......Page 393
  11.3 Pipelines......Page 395
  11.4 Signal Handling in the Foreground......Page 399
  11.5 Process Groups, Sessions and Controlling Terminals......Page 405
  11.6 Background Processes in ush......Page 410
  11.7 Job Control......Page 417
  11.8 Job Control for ush......Page 421
  11.9 Additional Reading......Page 424
III: Concurrency......Page 426
 12 POSIX Threads......Page 428
  12.1 A Motivating Problem: Monitoring File Descriptors......Page 429
  12.2 Use of Threads to Monitor Multiple File Descriptors......Page 430
  12.3 Thread Management......Page 434
  12.4 Thread Safety......Page 450
  12.5 User Threads versus Kernel Threads......Page 452
  12.6 Thread Attributes......Page 455
  12.7 Exercise: Parallel FileCopy......Page 462
  12.8 Additional Reading......Page 463
 13 Thread Synchronization......Page 466
  13.2 Mutex Locks......Page 467
  13.3 At-Most-Once and At-Least-Once-Execution......Page 480
  13.4 Condition Variables......Page 484
  13.5 Signal Handling and Threads......Page 492
  13.6 Readers and Writers......Page 497
  13.8 Deadlocks and Other Pesky Problems......Page 502
  13.9 Exercise: Multiple Barriers......Page 504
  13.10 Additional Reading......Page 505
 14 Critical Sections and Semaphores......Page 506
  14.1 Dealing with Critical Sections......Page 507
  14.2 Semaphores......Page 510
  14.3 POSIX:SEM Unnamed Semaphores......Page 513
  14.4 POSIX:SEM Semaphore Operations......Page 515
  14.5 POSIX:SEM Named Semaphores......Page 521
  14.6 Exercise: License Manager......Page 526
  14.7 Additional Reading......Page 528
 15 POSIX IPC......Page 530
  15.1 POSIX:XSI Interprocess Communication......Page 531
  15.2 POSIX:XSI Semaphore Sets......Page 533
  15.3 POSIX:XSI Shared Memory......Page 544
  15.4 POSIX:XSI Message Queues......Page 554
  15.5 Exercise: POSIX Unnamed Semaphores......Page 561
  15.6 Exercise: POSIX Named Semaphores......Page 562
  15.7 Exercise: Implementing Pipes with Shared Memory......Page 563
  15.8 Exercise: Implementing Pipes with Message Queues......Page 566
  15.9 Additional Reading......Page 567
 16 Project: Producer Consumer Synchronization......Page 568
  16.1 The Producer-Consumer Problem......Page 569
  16.2 Bounded Buffer Protected by Mutex Locks......Page 570
  16.3 Buffer Implementation with Semaphores......Page 574
  16.4 Introduction to a Simple Producer-Consumer Problem......Page 579
  16.5 Bounded Buffer Implementation Using Condition Variables......Page 583
  16.6 Buffers with Done Conditions......Page 584
  16.7 Parallel File Copy......Page 592
  16.8 Threaded Print Server......Page 594
  16.9 Additional Reading......Page 599
 17 Project: The Not Too Parallel Virtual Machine......Page 600
  17.1 PVM History, Terminology, and Architecture......Page 601
  17.2 The Not Too Parallel Virtual Machine......Page 603
  17.3 NTPVM Project Overview......Page 604
  17.4 I/O and Testing of Dispatcher......Page 610
  17.5 Single Task with No Input......Page 619
  17.6 Sequential Tasks......Page 620
  17.7 Concurrent Tasks......Page 623
  17.9 Termination and Signals......Page 624
  17.11 Additional Reading......Page 625
IV: Communication......Page 626
 18 Connection-Oriented Communication......Page 628
  18.2 Communication Channels......Page 629
  18.3 Connection-Oriented Server Strategies......Page 633
  18.4 Universal Internet Communication Interface (UICI)......Page 637
  18.5 UICI Implementations of Different Server Strategies......Page 640
  18.6 UICI Clients......Page 643
  18.7 Socket Implementation of UICI......Page 648
  18.8 Host Names and IP Addresses......Page 660
  18.9 Thread-Safe UICI......Page 668
  18.10 Exercise: Ping Server......Page 671
  18.11 Exercise: Transmission of Audio......Page 672
  18.12 Additional Reading......Page 674
 19 Project: WWW Redirection......Page 676
  19.2 Uniform Resource Locators (URLs)......Page 677
  19.3 HTTP Primer......Page 679
  19.4 Web Communication Patterns......Page 684
  19.5 Pass-through Monitoring of Single Connections......Page 691
  19.6 Tunnel Server Implementation......Page 693
  19.7 Server Driver for Testing......Page 694
  19.8 HTTP Header Parsing......Page 695
  19.9 Simple Proxy Server......Page 698
  19.10 Proxy Monitor......Page 699
  19.11 Proxy Cache......Page 702
  19.12 Gateways as Portals......Page 703
  19.13 Gateway for Load Balancing......Page 704
  19.14 Postmortem......Page 705
  19.15 Additional Reading......Page 709
 20 Connectionless Communication and Multicast......Page 710
  20.1 Introduction to Connectionless Communication......Page 711
  20.2 Simplified Interface for Connectionless Communication......Page 712
  20.3 Simple-Request Protocols......Page 716
  20.4 Request-Reply Protocols......Page 721
  20.5 Request-Reply with Timeouts and Retries......Page 727
  20.6 Request-Reply-Acknowledge Protocols......Page 733
  20.7 Implementation of UICI UDP......Page 734
  20.8 Comparison of UDP and TCP......Page 743
  20.9 Multicast......Page 744
  20.10 Exercise: UDP Port Server......Page 748
  20.11 Exercise: Stateless File Server......Page 749
  20.12 Additional Reading......Page 751
 21 Project: Internet Radio......Page 752
  21.1 Project Overview......Page 753
  21.3 UDP Implementation with One Program and One Receiver......Page 754
  21.4 UDP Implementation with Multiple Programs and Receivers......Page 765
  21.5 UDP Implementation of Radio Broadcasts......Page 766
  21.7 TCP Implementation Differences......Page 769
  21.8 Receiving Streaming Audio Through a Browser......Page 774
  21.9 Additional Reading......Page 778
 22 Project: Server Performance......Page 780
  22.2 Server Architectures......Page 781
  22.4 Single-Client Driver......Page 786
  22.5 Multiple-Client Driver......Page 790
  22.7 Thread-worker-pool Strategy......Page 793
  22.9 Process-worker Pool......Page 794
  22.10 Influence of Disk I/O......Page 795
  22.11 Performance Studies......Page 799
  22.12 Report Writing......Page 809
  22.13 Additional Reading......Page 811
Appendices......Page 814
  A.1 Manual Pages......Page 816
  A.2 Compilation......Page 819
  A.3 Make files......Page 826
  A.4 Debugging Aids......Page 828
  A.5 Identifiers, Storage Classes and Linkage Classes......Page 831
  A.6 Additional Reading......Page 833
 B: Restart Library......Page 834
  C.1 Connection-Oriented UICI TCP Implementation......Page 844
  C.2 Name Resolution Implementations......Page 848
  C.3 Connectionless UICI UDP Implementation......Page 853
  D.1 Local Atomic Logging......Page 860
  D.2 Remote Logging......Page 865
 E: POSIX Extensions......Page 878
Bibliography......Page 880
 C......Page 890
 P......Page 891
 U......Page 892
 X......Page 893
 A......Page 894
 C......Page 895
 E......Page 897
 F......Page 898
 I......Page 899
 L......Page 900
 M......Page 901
 P......Page 902
 R......Page 905
 S......Page 906
 T......Page 910
 U......Page 911
 Z......Page 912