操作系统基础：并发篇（Operating Systems: Three Easy Pieces Part II）

需积分: 9 13 浏览量更新于2024-07-19 收藏 983KB PDF 举报

"Operating Systems: Three Easy Pieces 是一本广受欢迎的操作系统教材，专注于研究生级别的学习。本书分为三个部分，Part II 专门讨论并发性（Concurrency）。这部分内容旨在深入理解操作系统中的并发概念，如何管理和解决并发环境下的问题。" 在操作系统领域，并发性是至关重要的一个主题，它涉及到多个任务或进程在看似同一时刻执行的能力。在Part II《Concurrency》中，作者通过对话的形式，引入了并发的基本概念。教授以吃桃子为例，引出并发问题：当多个人同时想吃桌子上的桃子时，如果没有合适的机制，可能会出现竞争条件，导致某些人无法吃到桃子。这个问题揭示了并发编程的核心挑战之一——资源共享。在操作系统中，当多个进程或线程试图访问共享资源时，必须要有适当的同步机制来避免冲突。这些机制包括锁、信号量、条件变量等，它们用于控制对共享资源的访问，确保数据的一致性和完整性。教授和学生的对话中提到的“看到桃子并尝试抓住”的场景，实际上对应于计算机中的“读-修改-写”操作。如果多个进程同时进行这样的操作，就可能导致数据不一致。为了解决这个问题，操作系统采用了各种并发控制策略，如互斥（Mutual Exclusion）、死锁预防和检测、活锁和饥饿的避免等。此外，这部分教材可能还会涵盖以下知识点： 1. 进程与线程的概念：进程作为资源分配的单位，线程作为执行的单位，两者在并发执行中的区别和联系。 2. 并发模型：如时间片轮转、抢占式调度和非抢占式调度，以及它们如何影响系统的性能和响应时间。 3. 死锁：多个进程相互等待对方释放资源而形成的僵局，以及预防和恢复死锁的方法。 4. 分布式系统中的并发：在网络环境中，如何处理跨机器的并发问题，以及分布式一致性算法（如Paxos和Raft）。 5. 并行计算：探讨多核处理器和GPU等硬件设备如何支持并行计算，以及并行算法的设计原则。 Part II《Concurrency》不仅会介绍理论概念，还可能通过具体的示例和编程练习帮助读者理解和应用这些概念，使其能够设计和实现高效且安全的并发程序。这是一本操作系统学者和开发者不可或缺的经典参考书。

12 CONCURRENCY: AN INTRODUCTION

26.6 One More Problem: Waiting For Another

This chapter has set up the problem of concurrency as if only one type

of interaction occurs between threads, that of accessing shared variables

and the need to support atomicity for critical sections. As it turns out,

there is another common interaction that arises, where one thread must

wait for another to complete some action before it continues. This inter-

action arises, for example, when a process performs a disk I/O and is put

to sleep; when the I/O completes, the process needs to be roused from its

slumber so it can continue.

Thus, in the coming chapters, we’ll be not only studying how to build

support for synchronization primitives to support atomicity but also for

mechanisms to support this type of sleeping/waking interaction that is

common in multi-threaded programs. If this doesn’t make sense right

now, that is OK! It will soon enough, when you read the chapter on con-

dition variables. If it doesn’t by then, well, then it is less OK, and you

should read that chapter again (and again) until it does make sense.

26.7 Summary: Why in OS Class?

Before wrapping up, one question that you might have is: why are we

studying this in OS class? “History” is the one-word answer; the OS was

the ﬁrst concurrent program, and many techniques were created for use

within the OS. Later, with multi-threaded processes, application program-

mers also had to consider such things.

For example, imagine the case where there are two processes running.

Assume they both call write() to write to the ﬁle, and both wish to

append the data to the ﬁle (i.e., add the data to the end of the ﬁle, thus

increasing its length). To do so, both must allocate a new block, record

in the inode of the ﬁle where this block lives, and change the size of the

ﬁle to reﬂect the new larger size (among other things; we’ll learn more

about ﬁles in the third part of the book). Because an interrupt may occur

at any time, the code that updates these shared structures (e.g., a bitmap

for allocation, or the ﬁle’s inode) are critical sections; thus, OS design-

ers, from the very beginning of the introduction of the interrupt, had to

worry about how the OS updates internal structures. An untimely inter-

rupt causes all of the problems described above. Not surprisingly, page

tables, process lists, ﬁle system structures, and virtually every kernel data

structure has to be carefully accessed, with the proper synchronization

primitives, to work correctly.

OPERATING

SYSTEMS

[VERSION 0.91] WWW.OSTEP.ORG

14 CONCURRENCY: AN INTRODUCTION

References

[D65] “Solution of a problem in concurrent programming control”

E. W. Dijkstra

Communications of the ACM, 8(9):569, September 1965

Pointed to as the ﬁrst paper of Dijkstra’s where he outlines the mutual exclusion problem and a solution.

The solution, however, is not widely used; advanced hardware and OS support is needed, as we will see

in the coming chapters.

[D68] “Cooperating sequential processes”

Edsger W. Dijkstra, 1968

Available: http://www.cs.utexas.edu/users/EWD/ewd01xx/EWD123.PDF

Dijkstra has an amazing number of his old papers, notes, and thoughts recorded (for posterity) on this

website at the last place he worked, the University of Texas. Much of his foundational work, however,

was done years earlier while he was at the Technische Hochshule of Eindhoven (THE), including this

famous paper on “cooperating sequential processes”, which basically outlines all of the thinking that

has to go into writing multi-threaded programs. Dijkstra discovered much of this while working on an

operating system named after his school: the “THE” operating system (said “T”, “H”, “E”, and not

like the word “the”).

[GR92] “Transaction Processing: Concepts and Techniques”

Jim Gray and Andreas Reuter

Morgan Kaufmann, September 1992

This book is the bible of transaction processing, written by one of the legends of the ﬁeld, Jim Gray. It is,

for this reason, also considered Jim Gray’s “brain dump”, in which he wrote down everything he knows

about how database management systems work. Sadly, Gray passed away tragically a few years back,

and many of us lost a friend and great mentor, including the co-authors of said book, who were lucky

enough to interact with Gray during their graduate school years.

[L+93] “Atomic Transactions”

Nancy Lynch, Michael Merritt, William Weihl, Alan Fekete

Morgan Kaufmann, August 1993

A nice text on some of the theory and practice of atomic transactions for distributed systems. Perhaps a

bit formal for some, but lots of good material is found herein.

[SR05] “Advanced Programming in the UNIX Environment”

W. Richard Stevens and Stephen A. Rago

Addison-Wesley, 2005

As we’ve said many times, buy this book, and read it, in little chunks, preferably before going to bed.

This way, you will actually fall asleep more quickly; more importantly, you learn a little more about

how to become a serious UNIX programmer.

OPERATING

SYSTEMS

[VERSION 0.91] WWW.OSTEP.ORG

剩余133页未读，继续阅读

weixin_40451799

粉丝: 0
资源: 3

操作系统基础：并发篇（Operating Systems: Three Easy Pieces Part II）

Operating Systems: Three Easy Pieces

operating systems 0.91 three easy pieces

operating system: three easy pieces

Operating Systems: Three Easy Pieces 国外著名大学研究生操作系统课本(0.90版本)part III

Operating Systems: Three Easy Pieces 国外著名大学研究生操作系统课本(0.90版本)

威斯康星州大学研究生操作系统教程Operating Systems: Three Easy Pieces

Operating Systems : Three Easy Pieces

Operating Systems:Three Easy Pieces

Operating Systems: Three easy pieces

Operating Systems : Three Easy Pieces V1.0

最新资源