O perating s ystems t hree e asy p ieces

29 Lock-based Concurrent Data Structures

311

29.1 Concurrent Counters

. . . . . . . . . . . . . . . . . . . . . . 311

29.2 Concurrent Linked Lists

. . . . . . . . . . . . . . . . . . . . 316

29.3 Concurrent Queues

. . . . . . . . . . . . . . . . . . . . . . . 319

29.4 Concurrent Hash Table

. . . . . . . . . . . . . . . . . . . . . 320

29.5 Summary

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 322

References

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 323

30 Condition Variables

325

30.1 Definition and Routines

. . . . . . . . . . . . . . . . . . . . . 326

30.2 The Producer/Consumer (Bound Buffer) Problem

. . . . . . 329

O

PERATING

S

YSTEMS

[V

ERSION

0.80]

WWW

.

OSTEP

.

ORG

---

C

ONTENTS

xvii

30.3 Covering Conditions

. . . . . . . . . . . . . . . . . . . . . . 337

30.4 Summary

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 338

References

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 339