-
Notifications
You must be signed in to change notification settings - Fork 1
/
chapter07.html
1778 lines (1293 loc) · 50.3 KB
/
chapter07.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
<!DOCTYPE html>
<html>
<head>
<title>Synchronization Problems</title>
<meta http-equiv="Content-Type" content="text/html; charset=UTF-8"/>
<link href="css/slides.css" rel="stylesheet" type="text/css" />
</head>
<body>
<textarea id="source">
class: center, middle, title-slide
## CSCI 340 Operating Systems
<br>
## Chapter 7: Synchronization Problems
.author[
Stewart Weiss<br>
]
.license[
Copyright 2020 Stewart Weiss. Unless noted otherwise all content is released under a
[Creative Commons Attribution-ShareAlike 4.0 International License](https://creativecommons.org/licenses/by-sa/4.0/).
]
---
name: cc-notice
template: default
layout: true
.bottom-left[© Stewart Weiss. CC-BY-SA.]
---
name: tinted-slide
template: cc-notice
layout: true
class: tinted
---
name:toc
### Table of Contents
[Prerequisite Reading](#prereqs)<br>
[About This Chapter](#about-chapter)<br>
[Chapter Objectives](#objectives)<br>
[The Bounded Buffer Problem](#bounded-buffer-def)<br>
[What Makes This Problem Different?](#bb-versus-pc)<br>
[Problem Statement](#bounded-buffer-setup)<br>
[Semaphore Initialization](#bounded-buffer-semaphores)<br>
[Producer and Consumer Code](#bounded-buffer-solution)<br>
[The Readers-Writers Problem](#readers-writers-overview)<br>
[An Observation About Asymmetry](#asymmetry)<br>
[Readers-Writers: Solution Development](#development-1)<br>
[Writer Arrivals](#development-3)<br>
[Reader Arrivals](#development-4)<br>
[Alternative Preference Problems](#development-5)<br>
[Required Data Structures](#development-6)<br>
[Algorithms: The Writer Process](#development-6)<br>
[Algorithms: The Reader Process](#development-7)<br>
[Correctness](#correctness)<br>
[Reader-Writer Locks](#rwlocks)<br>
[The Dining Philosophers Problem: Background](#dining-philosophers-background)<br>
[The Dining Philosophers Problem Statement](#dining-philosophers-statement-1)<br>
---
### Table of Contents
[A Naïve Solution Using Semaphores](#dining-philosophers-sem-1)<br>
[A Deadlock-Free Solution](#dining-philosophers-better-1)<br>
[Why No Deadlock?](#dining-philosophers-sem-3)<br>
[The Complete Program](#code)<br>
[The Complete Program](#code)<br>
[Synchronization in the Early Linux Kernel](#linux-synch-early)<br>
[Synchronization in the Modern Linux Kernel](#linux-synch-current-1)<br>
[Spinlocks in Linux](#linux-synch-current-2)<br>
[Mutexes in Linux](#linux-synch-current-2)<br>
[Semaphores in Linux](#linux-sems)<br>
[Summary of Locking in Linux](#linux-summary)<br>
[POSIX Synchronization](#posix-synch)<br>
[POSIX Mutex Locks](#posix-synch-2)<br>
[POSIX Semaphores](#posix-synch-3)<br>
[POSIX Named Semaphores](#posix-synch-3)<br>
[POSIX Unnamed Semaphores](#posix-synch-4)<br>
[POSIX Condition Variables](#posix-synch-4)<br>
[POSIX Condition Variable Example](#posix-synch-5)<br>
[References](#references)<br>
<!--TOC_END-->
---
name: prereqs
### Prerequisite Reading
Before reading these slides, you should be familiar with
- Processes and concurrency ([Chapter 3](chapter03.html))
- Threads and the POSIX Threads API ([Chapter 4](chapter04.html))
- Process synchronization tools and primitives ([Chapter 6](chapter06.html))
---
name: about-chapter
### About This Chapter
Certain synchronization problems arise so frequently in the design and implementation of
concurrent systems that they deserve to be identified and studied.
Some synchronization problems are noteworthy because their solutions are
interesting.
In this chapter, we explore three such problems:
.lightbluebox[
- The Bounded Buffer problem
- The Readers-Writers problem(s)
- The Dining Philosophers problem
]
We also explore synchronization in the __Linux__ kernel and
POSIX synchronization tools.
As we did in Chapter 6,
we use the terms "process" and "thread" interchangeably,
---
name: objectives
### Chapter Objectives
Having read and understood the content of this chapter, you should be able to
- describe and provide correct solutions to the bounded buffer problem;
- describe various forms of the readers-writers problem and describe correct solutions
to them;
- describe the dining philosophers problem and describe solutions to it
that may not satisfy all desirable liveness properties;
- describe different methods used in the __Linux__ kernel to synchronize
processes executing kernel code;
- identify parts of the Pthreads API that can be used to implement solutions to
synchronization problems;
---
name: bounded-buffer
layout: false
class: center, middle, inverse
## The Bounded Buffer Problem
We begin with the __Bounded Buffer Problem__, which is a generalization of the
single producer-single consumer problem described in Chapter 3.
---
template: tinted-slide
layout: true
---
name: bounded-buffer-def
### The Bounded Buffer Problem
In Chapter 3 we introduced the .bluebold[Producer Consumer Problem], stated in
terms of a single producer and a single consumer.
In that problem, there was a shared, finite size pool of buffers.
The producer process could write data into an empty buffer,
and the consumer process could read data from a full buffer.
.center[
<img src="figures/prodconsumer.png" width=70% alt="producer-consumer">
]
The problem was how to design the producer and consumer so that, in their exchange
of data, no data is lost or duplicated, data is read by the consumer
in the order it is written
by the producer, and both processes make as much progress as possible.
We presented both .redbold[shared memory] and .redbold[message-passing] solutions.
--
The more general version of this problem allows for any number of
producer and consumer processes, all of which access a shared, finite size pool
of buffers, subject to the same criteria of correctness. It is called the
.bluebold[Bounded Buffer Problem].
.redbold[Here we provide only a shared memory solution using semaphores.]
---
name: bb-versus-pc
### What Makes This Problem Different?
Recall that the producer repeatedly executed a loop body of the form
```C
next_item = produce_new_item();/* produce an item and store into next_item */
while (((in + 1) % BUFFER_SIZE) == out) /* keep testing whether buffer is full */
; /* do nothing until buffer is not full */
/* buffer is not full, so write item into buffer[in] and advance in */
buffer[in] = next_item;
in = (in + 1) % BUFFER_SIZE; /* advance in */
}
```
With just a single producer, the instruction
```C
in = (in + 1) % BUFFER_SIZE;
```
ensured that .fixedblue[in] was the index of the next available buffer to use in the buffer pool.
--
This does not work when there are multiple producers, because it is a
.redbold[race condition]
on the variable .fixedblue[in].
A similar statement is true about .fixedblue[out] for consumers.
--
Therefore, accesses to these variables are critical sections and must be
synchronized. In the solution we present here, we use .redbold[semaphores] to achieve this.
---
name: bounded-buffer-setup
### Problem Statement
We make the following assumptions:
- There are .fixedblue[N] buffers, each of which can hold exactly one item.
- There are $p \ge 1$ producer processes and $c \ge 1$ consumer processes.
- After a producer fills a buffer, the buffer is considered to be .greenbold[full].
- After a consumer reads a buffer, the buffer is considered to be .greenbold[empty].
- .fixedblue[produce_item()] returns an item to be put into a buffer
- .fixedblue[consume_item(itemtype item)] consumes .fixedblue[item].
--
We present a solution to this problem that uses one binary semaphore and two counting
semaphores.
We use the same syntax for semaphore operations that we did in Chapter 6,
treating semaphores as objects and their operations as member functions.
This syntax does not correspond to a particular implementation of semaphores - it is
pseudocode.
---
name: bounded-buffer-semaphores
### Semaphore Initialization
The semaphores are initialized as follows:
```C
int N; /* Number of buffers */
semaphore mutex = 1; /* Binary semaphore, initially unlocked */
semaphore empty = N; /* Number of empty buffers, initially all are empty */
semaphore full = 0; /* Number of full buffers, initially none */
```
- The .fixedblue[mutex] semaphore provides mutual exclusion for all updates
to the buffers. Only one process at a time can modify a buffer.
- The .fixedblue[empty] semaphore counts the number of empty buffers. A producer
will issue a wait on it. If it is zero, the producer blocks. If not, it is decremented
and the producer continues.
- The .fixedblue[full] semaphore counts the number of full buffers. A consumer
will issue a wait on it. If it is .fixedblue[0], the consumer blocks. If not, it is decremented
and the consumer continues.
---
name: bounded-buffer-solution
### Producer and Consumer Code
.left-column[.left[.smaller[
```C
producer()
{
itemtype item; /* item produced */
while (true) {
/* produce item and store into item */
item = produce_item();
/* wait for an empty buffer */
empty.wait();
/* acquire mutex */
mutex.wait();
/* CS: write item into a empty buffer */
/* release mutex */
mutex.signal();
/* increment number of full buffers */
full.signal();
}
}
```
]]]
.right-column[.left[.smaller[
```C
consumer()
{
itemtype item; /* next item consumed */
while (true) {
/* wait for a full buffer */
full.wait();
/* acquire mutex */
mutex.wait();
/* CS: read item from a full buffer */
/* release mutex */
mutex.signal();
/* increment number of empty buffers */
empty.signal();
/* consume item */
consume_item(item);
}
}
```
]]]
--
.below-column[
- Notice the symmetry of the calls to the counting semaphores - producers
wait if there are no empty buffers; consumers wait if none are full.
- The code to write into and read from a buffer is not shown.
If the pool is an array of buffers, there would still be updates to variables .fixedblue[in]
and .fixedblue[out] inside the CS.
- The .fixedblue[mutex] semaphore operations provide the mutual exclusion.
- If the semaphores use FIFO queues, then bounded waiting is satisfied.
]
---
name: readers-writers-intro
layout: false
class: center, middle, inverse
### The Readers-Writers Problem
We explore a pervasive model of inter-process communication known as the
__Readers-Writers problem__, which models many concurrent systems of processes
in modern computer systems.
---
template: tinted-slide
layout: true
---
name: readers-writers-overview
### The Readers-Writers Problem
This problem was originally posed and solved by Courtois, Heymans, and Parnas in
1971.
We are given the following conditions:
- There are multiple processes, each of which accesses a .redbold[shared data set];
- Each process is either a .bluebold[reader], which means it reads but never
modifies the data, or it is a .bluebold[writer], which means it can read
and modify the data;
- Multiple readers are allowed to access the data concurrently;
- If a writer is modifying the data, no other process is allowed any access
to it until the writer finishes; .redbold[a writer must have exclusive access to the data.]
--
The challenge in the .bluebold[Readers-Writers Problem] is to design
algorithms for the readers and writers so that all of the the above constraints
are satisfied, and so that the system of processes is free of
deadlock and starvation.
--
We will develop a semaphore-based solution to this problem.
---
name: asymmetry
### An Observation About Asymmetry
In this problem, unlike the bounded-buffer problem, there is an asymmetry in
access to the shared data set:
- Readers do not need to access that data in mutual exclusion of each other.
- Writers must have mutual exclusion when accessing the data.
This is a form of .bluebold[categorical mutual exclusion]:
a process in the .greenbold[reader category] being in the critical section does not
exclude other processes in that same category, but the presence of a process
in the .greenbold[writer category] in the critical section excludes processes from all categories.
As a result of this asymmetry, the reader and writer algorithms will be very different.
---
name: development-1
### Readers-Writers: Solution Development
Imagine a room that stores a shared file or dataset. It has an entry door and an exit door.
Readers and writers alike must walk through the entry door to gain access to the room,
and must leave by the exit door.
--
A process cannot enter the room unless it is granted permission to do so.
Access control involves a procedure that every process follows when it tries to enter,
and another that it follows after it has entered the room and is ready to leave.
--
At the entry door there are two queues:
- a queue for readers
- a queue for writers.
If a reader is not allowed to enter the room for one
reason or another, it waits in the reader queue.
If a writer is not allowed to enter, it waits in the writer queue.
---
name: development-2
count: false
### Readers-Writers: Solution Development
When a process is granted permission to enter the room, whether it
waited in a queue or not,
it .greenbold[increments a counter] to indicate that it is entering the room. Because
readers and writers have asymmetrical constraints, we need
two counters:
- a counter for readers
- a counter for writers.
--
Because only one writer is allowed in the room at a time, the writer counter
has just two values: 0 and 1.
The reader counter can take on any non-negative value, since there is no
limit to the number of readers that can be in the room.
--
When a process leaves the room, it .greenbold[decrements the corresponding counter]
to indicate that it is leaving the room. This allows the access control system to
determine which process is allowed to enter the room next.
---
name: development-3
### Writer Arrivals
When a writer arrives, there are only two possibilities:
--
- If the room is empty when a writer arrives, it enters the
room without waiting.
- If the room is not empty and a writer arrives, it must wait in the writer
queue until it is given permission to enter.
--
It is not possible for the room to be empty and one or more queues to be
non-empty because if the room were empty because a process just left it, a process in
a queue would be allowed into the room. I.e., if there are waiting processes,
they do not delay in entering the room.
---
name: development-4
### Reader Arrivals
When a reader arrives there are many more possibilities:
--
- If the room is empty and the queues are empty when a reader arrives, it enters the
room without waiting.
--
- If a writer is in the room and a reader arrives, the reader must wait in the
reader queue until it is given permission to enter the room.
--
- If a reader is in the room and no writer is waiting, then an arriving reader
can enter the room without waiting.
--
- If a reader is in the room and one or more writers are waiting, and a reader
arrives, then we have a decision to make:
- do we make the arriving reader wait in the reader queue until the writers
have a turn to enter the room, or
- do we let the reader enter the room immediately, making the writers wait until
there are no readers in the room?
--
- If we allow arriving readers to enter the room .redbold[even though writers may be waiting], it
leads to a formulation of the problem known as the
.bluebold[First Readers-Writers Problem], also known as the
.bluebold[Weak Reader Preference Readers-Writers Problem].
---
name: development-5
### Alternative Preference Problems
The alternative to allowing arriving readers to enter even though writers are
waiting is to
.redbold[make the arriving reader wait in the reader queue until the writers have a turn to enter the room.]
This implies that it is possible for both the reader and writer queues to be
non-empty while a process is in the room, whether it is a reader or a writer.
--
This in turn implies that when a process leaves the room,
we must decide whether to let a reader or a writer into the room.
If waiting readers are given priority over waiting writers, we call it a
.bluebold[Strong Reader Preference Problem].
Otherwise it is called a .bluebold[Writer Preference Problem].
In these notes, we do not present solutions to either of these forms of the problem.
---
name: development-6
### Required Data Structures
We need two counters: a reader counter and a writer counter, which must be incremented
and decremented in mutual exclusion.
Since the writer counter is either 0 or 1, we use a binary semaphore, .fixedblue[writer_mutex],
to count active writers.
For the reader counter, we use an ordinary integer variable, named
.fixedblue[reader_count], and
protect accesses to it using a binary semaphore .fixedblue[reader_mutex].
They are therefore initialized as follows:
```C
semaphore writer_mutex = 1;
semaphore reader_mutex = 1;
int reader_count = 0;
```
No other data structures are needed for the First Reader Writer Problem's solution.
---
name: development-6
### Algorithms: The Writer Process
Writers have a very simple form.
The binary semaphore .fixedblue[writer_mutex] provides the implicit queuing
and the required mutual exclusion.
.left-column[
An arriving writer immediately calls .fixedblue[wait] on .fixedblue[writer_mutex].
If .fixedblue[writer_mutex] is unlocked (has the value 1),
it becomes locked and the writer enters the room, performs the write,
and then signals .fixedblue[writer_mutex] to unlock it upon exit.
If .fixedblue[writer_mutex] is locked, the writer is queued on it.
]
.right-column[
```C
Writer:
while ( true ) {
/* try to enter */
writer_mutex.wait();
/* perform write */
/* release the mutex */
writer_mutex.signal();
}
```
]
.below-column[
]
---
name: development-7
### Algorithms: The Reader Process
Readers are more complex. An arriving reader does one thing if there are no
readers in the room, and a different thing if there are already readers in the
room.
.left-column[
Increments and decrements to .fixedblue[reader_count] are critical sections that
are executed in mutual exclusion by each reader by
- calling .fixedblue[wait] on .fixedblue[reader_mutex],
- modifying .fixedblue[reader_count] , and
- calling .fixedblue[signal] on it when they are finished.
]
.right-column[
```C
Reader:
while ( true ) {
`reader_mutex.wait();`
reader_count += 1;
if ( 1 == reader_count )
writer_mutex.wait();
`reader_mutex.signal();`
/* perform read */
`reader_mutex.wait();`
reader_count -= 1;
if ( 0 == reader_count )
writer_mutex.signal();
`reader_mutex.signal();`
}
```
]
---
name: development-8
count: false
### Algorithms: The Reader Process
An arriving reader that discovers there are no readers currently reading
is like a pioneer; it has to pave the way for the readers that will follow its
path.
.right-column[
```C
Reader:
while ( true ) {
reader_mutex.wait();
reader_count += 1;
`if ( 1 == reader_count )`
`writer_mutex.wait();`
reader_mutex.signal();
/* perform read */
reader_mutex.wait();
reader_count -= 1;
if ( 0 == reader_count )
writer_mutex.signal();
reader_mutex.signal();
}
```
]
--
.left-column[
If, after .fixedblue[reader_count] is incremented, it is 1,
there are no readers currently in the room. Hence,
- Either a writer is writing or the room is empty.
- The reader calls .fixedblue[wait] on .fixedblue[writer_mutex].
If a writer is writing, the reader is blocked.
Otherwise the reader enters the room, locking .fixedblue[writer_mutex]
and blocking any arriving writer.
]
---
name: development-9
count: false
### Algorithms: The Reader Process
An arriving reader that discovers there are no readers currently reading
is like a pioneer; it has to pave the way for the readers that will follow its
path.
.right-column[
```C
Reader:
while ( true ) {
reader_mutex.wait();
reader_count += 1;
`if ( 1 == reader_count )`
`writer_mutex.wait();`
reader_mutex.signal();
/* perform read */
reader_mutex.wait();
reader_count -= 1;
if ( 0 == reader_count )
writer_mutex.signal();
reader_mutex.signal();
}
```
]
.left-column[
- If the reader is blocked, since it still holds the lock on
.fixedblue[reader_mutex],
all subsequently arriving readers "pile up" on the .fixedblue[reader_mutex] queue
when they call .fixedblue[wait].
When the writer leaves the room, the reader is unblocked from .fixedblue[writer_mutex],
locks it, and signals the .fixedblue[reader_mutex].
All waiting readers will follow, one after the other, into the room, because each of
these, after incrementing .fixedblue[reader_count], will find .fixedblue[reader_count] > 1
and will not call .fixedblue[writer_mutex.wait()].
]
---
name: development-10
count: false
### Algorithms: The Reader Process
When a reader finishes reading, it decrements the reader count. The last
reader out of the room needs to do something different from all previous exiting readers.
.right-column[
```C
Reader:
while ( true ) {
reader_mutex.wait();
reader_count += 1;
if ( 1 == reader_count )
writer_mutex.wait();
reader_mutex.signal();
/* perform read */
reader_mutex.wait();
reader_count -= 1;
`if ( 0 == reader_count )`
`writer_mutex.signal();`
reader_mutex.signal();
}
```
]
.left-column[
- After a reader finishes reading, it locks the .fixedblue[reader_mutex] semaphore,
and decrements .fixedblue[reader_count].
If .fixedblue[reader_count] is 0, it is the last reader out of the room.
This implies that it should allow waiting writers to enter the room, and therefore
it signals the .fixedblue[writer_mutex].
If no writers are waiting, it has no immediate effect. If one or more writers are waiting.
the first acquires the .fixedblue[writer_mutex] lock and enters the room.
]
---
name: correctness
### Correctness
Is this solution correct? Does it satisfy the conditions stated initially, as well as
progress and bounded waiting?
--
1. It guarantees that writers write in mutual exclusion.
--
2. It guarantees that any number of readers can be reading concurrently.
--
3. It guarantees that processes make progress - if no writer is writing, readers can read
immediately, and if no process is reading or writing, writers can write immediately.
--
4. Bounded waiting is not satisfied - a steady stream of readers can prevent a waiting writer
from writing. Eliminating this starvation requires changing how arriving readers
are treated.
---
name: rwlocks
### Reader-Writer Locks
The readers–writers problem models so many programming problems that a special type
of lock called a .greenbold[reader–writer lock] is provided in many libraries and
operating systems.
A .bluebold[reader-writer lock] is a lock that can allow multiple readers to enter a
critical section or just a single writer to enter.
- To acquire a reader–writer lock, the calling process must specify the mode of the lock:
- .bluebold[read mode]: the process wants only to read shared data, or
- .bluebold[write mode]: the process wants to modify shared data.
- A process trying to acquire a reader-writer lock in read mode succeeds if the lock
is not held by a writer.
- A process trying to acquire a reader-writer lock in write mode succeeds only if
no other process, reader or writer, is holding it.
The POSIX Threads library, for example, provides a type called a
.fixedblue[pthread_rwlock_t], which is a reader-writer lock, as well as many functions
that act on locks of that type.
The __Linux__ kernel also has several different reader-writer locks.
---
name: dining-philosophers-intro
layout: false
class: center, middle, inverse
### The Dining Philosophers Problem
We present and explore solutions to the __Dining Philosophers Problem__,
which is an interesting, challenging, and entertaining problem with not that much practical
application. There are valuable lessons to be learned from it.
---
template: tinted-slide
layout: true
---
name: dining-philosophers-background
### The Dining Philosophers Problem: Background
In 1965, for his course in "Cooperating Sequential Processes", Edsger Dijkstra
gave his students a synchronization problem to solve for their final exam, which he named
.bluebold[The Problem of the Dining Quintuple].super[1]. The problem was originally stated in
terms of tape drives and processes needing access to them.
In 1978, Tony Hoare, also a well-known computer scientist (the inventor of quicksort), dubbed
the problem the .bluebold[The Dining Philosophers Problem] and the new name stuck.super[2].
.footnote[
1 Edsger W. Dijkstra, EWD-1000 (PDF). E.W. Dijkstra Archive.
Center for American History, University of Texas at Austin.<br>
2 C.A.R. Hoare, "communicating Sequential Processes," _Communications of the ACM,
V. 21 (8), August 1978, pp. 666-677.
]
--
Over the years, the problem has been embellished and its statement has changed in minor
ways, but it is fundamentally the same.
---
name: dining-philosophers-statement-1
### The Dining Philosophers Problem Statement
.left-column[
The problem is as follows.
Five philosophers, numbered 0 through 4, spend their lives thinking and eating;
as if they executed this loop:
```C
while (alive)
{ think; eat }
```
They only eat spaghetti, and the spaghetti is difficult to eat, requiring two forks.
A circular table is set with one fork between adjacent plates of spaghetti,
a consequence of which is that two neighbors cannot eat at the same time.super[1].
]
.footnote[
1 Later statements of the problem replace spaghetti with rice, and forks with chopsticks.
]
.right-column[
.center[The Philosophers' Table<br><br>
<img src="figures/dining-philosophers.png" width=80% alt="dining philosphers problem">
]]
---
name: dining-philosophers-statement-2
count: false
### The Dining Philosophers Problem Statement
.left-column[
Philosophers eat only when they are hungry.
They have assigned seats at the table, so that,
when they are hungry, they sit down at their seats and try to eat.
One constraint is that a philosopher can pick up only one fork at a time,
and can put down only one fork at a time.
It is just like acquiring and releasing resources: it is always done sequentially.
Another constraint is that philosophers are independent - they do not interact
with their neighbors to coordinate their eating.
]
.right-column[
.center[The Philosophers' Table<br><br>
<img src="figures/dining-philosophers.png" width=80% alt="dining philosphers problem">
]]
---
name: dining-philosophers-statement-3
count: false
### The Dining Philosophers Problem Statement
Summarizing,
the challenge is to design an algorithm that each philosopher will follow that
allows all philosophers to eat, perhaps not as soon as they are hungry but soon thereafter,
subject to the following constraints:
--
1. Only one philosopher can hold a fork at any given time (forks are not shareable.)
2. Each must pick up and put down one fork at a time.
3. A philosopher that tries to eat eventually eats.
4. It must be possible for two philosophers to eat simultaneously.
--
Condition 3 implies that
- .redbold[the solution must be deadlock-free], for if there were any deadlock, it would
imply that two or more philosophers tried to eat but will never eat; and
- .redbold[there is no starvation], because by definition a process starves if it is trying to
acquire a resource that it will never obtain.
---
name: dining-philosophers-sem-1
### A Naïve Solution Using Semaphores
A fairly obvious solution that uses semaphores creates a binary semaphore for each fork.
Every philosopher tries to pick up the left fork and then the right fork. If a
fork is in use, the philosopher waits until it is free.
When finished eating, the forks are put down one at a time.
There are five shared binary semaphores:
```C
semaphore fork[5] = {1,1,1,1,1};
```
Each philosopher .fixedblue[i], for .fixedblue[i= 0,...,4], executes the following code: