UNIX Systems for Modern Architectures

Curt Schimmel is an Operating System Architect who has ported and enhanced the UNIX kernel for a wide variety of systems, ranging from microprocessors to multiprocessor supercomputers, and has been involved in the design of new hardware systems to efficiently support the UNIX environment. A former member of AT&T Bell Laboratories' UNIX development team, he is now with Silicon Graphics, Inc., an industry leader in high performance multiprocessor UNIX systems. 0201633388AB04062001

Preface.


Notational Conventions.


Introduction.


1. Review of UNIX Kernel Internals.


Introduction.



Processes, Programs, and Threads.



The Process Address Space.



Context Switch.



Memory and Process Management System Calls.



Summary.



Exercises.



Further Reading.

I. CACHE MEMORY SYSTEMS. @CHAPTER 2. Introduction to Cache Memory Systems.



Memory Hierarchies.



Cache Fundamentals.



Direct Mapped Caches.



Two-Way Set Associative Caches.



n-Way Set Associative Caches.



Fully Associative Caches.



Summary of n-Way Set Associative Caches.



Cache Flushing.



Uncached Operation.



Separate Instruction and Data Caches.



Cache Performance.



How Cache Architectures Differ.



Exercises.



Further Reading.

3. Virtual Caches.


Virtual Cache Operation.



Problems with Virtual Caches.



Managing a Virtual Cache.



Summary.



Exercises.



Further Reading.

4. Virtual Caches with Keys.


The Operation of a Virtual Cache with Keys.



Managing a Virtual Cache with Keys.



Virtual Cache Usage in MMUs.



Summary.



Exercises.



Further Reading.

5. Virtual Caches with Physical Address Tags.


The Organization of a Virtual Cache with Physical Tags.



Managing a Virtual Cache with Physical Tags.



Summary.



Exercises.



Further Reading.

6. Physical Caches.


The Organization of a Physical Cache.



Managing a Physical Cache.



Multilevel Caches.



Primary Virtual Cache with Secondary Physical Cache.



Summary.



Exercises.



Further Reading.

7. Efficient Cache Management Techniques.


Introduction.



Address Space Layout.



Cache Size Bounded Flushing—Delayed Cache Invalidations.



Cache-Aligning Data Structures.



Summary.



Exercises.



Further Reading.

II. MULTIPROCESSOR SYSTEMS.

8. Introduction to Multiprocessor Systems.


Introduction.



The Tightly Coupled, Shared Memory, Symmetric.



Multiprocessor.



The MP Memory Model.



Mutual Exclusion.



Review of Mutual Exclusion on Uniprocessor.



UNIX Systems.



Problems Using UP Mutual Exclusion Policies on MPs.



Summary.



Exercises.



Further Reading.

9. Master-Slave Kernels.


Introduction.



Spin Locks.



Deadlocks.



Master-Slave Kernel Implementation.



Performance Considerations.



Summary.



Exercises.



Further Reading.

10. Spin-Locked Kernels.


Introduction.



Giant Locking.



Multithreading Cases Requiring No Locks.



Coarse-Grained Locking.



Fine-Grained Locking.



Effects of Sleep and Wakeup on Multiprocessors.



Summary.



Exercises.



Further Reading.

11. Semaphored Kernels.


Introduction.



Deadlocks.



Implementing Semaphores.



Coarse-Grained Semaphore Implementations.



Multithreading with Semaphores.



Performance Considerations.



Summary.



Exercises.



Further Reading.

12. Other MP Primitives.


Introduction.



Monitor.



Eventcounts and Sequencers.



The MP Primitives of SVR4.2 MP.



Comparison of MP Synchronization Primitives.



Summary.



Exercises.



Further Reading.

13. Other Memory Models.


Introduction.



Dekker's Algorithm.



Other Memory Models.



Total Store Ordering.



Partial Store Ordering.



The Store Buffer as Part of the Memory Hierarchy.



Summary.



Exercises.



Further Reading.

III. MULTIPROCESSOR SYSTEMS WITH CACHES.

14. Introduction to MP Cache Consistency.


Introduction.



The Cache Consistency Problem.



Software Cache Consistency.



Summary.



Exercise.



Further Reading.

15. Hardware Cache Consistency.


Introduction.



Write-Invalidate Protocols.



Write-Update Protocols.



Consistency of Read-Modify-Write Operations.



Hardware Consistency for Multilevel Caches.



Other Main Memory Architectures.



Effects on the Software.



Hardware Consistency for Nonsequential Memory Models.



Performance Considerations for Software.



Summary.



Exercises.



Further Reading.

Appendix A: Architecture Summary.
Appendix B: Answers to Selected Exercises.
Index. 0201633388T04062001