操作系统同步艺术：《信号量小书》详解

5星 · 超过95%的资源需积分: 9 100 浏览量更新于2024-07-25 收藏 979KB PDF 举报

《小信号灯书》（The Little Book of Semaphores）是一本由Allen B. Downey撰写的操作系统深入学习教材，特别关注于同步（synchronization）这一关键概念。在计算机科学中，同步不仅限于使两个事件同时发生，而是涵盖了事件之间的各种关系，包括先后顺序、并发和依赖。它在处理多线程编程和并发控制中发挥着至关重要的作用，确保了资源的有效管理和程序执行的正确性。书中阐述了在操作系统环境下，如何通过信号量（semaphores）来实现进程间的同步和互斥访问。信号量是一种计数器机制，常用于解决并发操作中的竞争条件，如多个进程试图共享有限资源时的排队等待问题。它们可以用来控制对共享资源的访问权限，比如允许一次只有一个进程执行某个特定任务，或者限制同时访问特定数据结构的进程数量。在课程中，学生会学习到以下核心知识点： 1. **基本概念**：理解信号量的原理，包括初始值设置、取值操作（递增或递减）以及信号量类型（计数信号量和二进制信号量）。 2. **同步原语**：掌握信号量的同步操作，如P（wait）和V（signal）操作，以及它们在并发环境中的应用，如实现临界区（critical section）以保护共享资源。 3. **死锁与避免策略**：了解死锁的概念，包括死锁的四个必要条件，以及如何通过预防策略（如银行家算法）或避免策略（如资源预分配）来防止死锁的发生。 4. **信号量链和信号量数组**：学习更复杂的同步机制，如使用信号量链来管理多个等待队列，或通过信号量数组管理一组资源。 5. **高级同步技术**：涉及条件变量（condition variables）和事件（events）等高级同步工具，它们允许进程在满足特定条件后被唤醒。 6. **实践案例分析**：书中提供了丰富的代码示例和练习，帮助读者将理论知识应用到实际编程场景中，增强理解和技能。 7. **软件工程实践**：了解如何在软件开发过程中设计和实现有效的同步机制，以提升系统的性能、可靠性和可维护性。《小信号灯书》作为一本开源教材，作者鼓励读者探索并利用LaTeX源代码进行自我学习和定制，这使得本书成为操作系统教育和研究中一个不可或缺的资源。无论是作为课堂教材还是个人自学的参考书，它都为理解操作系统中同步和并发控制的核心原理提供了深入且易懂的指导。

4 Introduction

1.4 Non-determinism

Concurrent programs are often non-deterministic, which means it is not pos-

sible to tell, by looking at the program, what will happen when it executes.

Here is a simple example of a non-deterministic program:

Thread A

a1 print "yes"

Thread B

b1 print "no"

Because the two threads run concurrently, the order of execution depends

on the scheduler. During any given run of this program, the output might be

“yes no” or “no yes”.

Non-determinism is one of the things that makes concurrent programs hard

to debug. A program might work correctly 1000 times in a row, and then crash

on the 1001st run, depending on the particular decisions of the scheduler.

These kinds of bugs are almost impossible to ﬁnd by testing; they can only

be avoided by careful programming.

1.5 Shared variables

Most of the time, most variables in most threads are local, meaning that they

belong to a single thread and no other threads can access them. As long as

that’s true, there tend to be few synchronization problems, because threads

just don’t interact.

But usually some variables are shared among two or more threads; this

is one of the ways threads interact with each other. For example, one way

to communicate information between threads is for one thread to read a value

written by another thread.

If the threads are unsynchronized, then we cannot tell by looking at the

program whether the reader will see the value the writer writes or an old value

that was already there. Thus many applications enforce the constraint that

the reader should not read until after the writer writes. This is exactly the

serialization problem in Section 1.3.

Other ways that threads interact are concurrent writes (two or more writ-

ers) and concurrent updates (two or more threads performing a read followed

by a write). The next two sections deal with these interactions. The other

possible use of a shared variable, concurrent reads, does not generally create a

synchronization problem.

1.5.1 Concurrent writes

In the following example, x is a shared variable accessed by two writers.

Thread A

a1 x = 5

a2 print x

Thread B

b1 x = 7

1.5 Shared variables 5

What value of x gets printed? What is the ﬁnal value of x when all these

statements have executed? It depends on the order in which the statements are

executed, called the execution path. One possible path is a1 < a2 < b1, in

which case the output of the program is 5, but the ﬁnal value is 7.

Puzzle: What path yields output 5 and ﬁnal value 5?

Puzzle: What path yields output 7 and ﬁnal value 7?

Puzzle: Is there a path that yields output 7 and ﬁnal value 5? Can you

prove it?

Answering questions like these is an important part of concurrent program-

ming: What paths are possible and what are the possible eﬀects? Can we prove

that a given (desirable) eﬀect is necessary or that an (undesirable) eﬀect is

impossible?

1.5.2 Concurrent updates

An update is an operation that reads the value of a variable, computes a new

value based on the old value, and writes the new value. The most common kind

of update is an increment, in which the new value is the old value plus one. The

following example shows a shared variable, count, being up dated concurrently

by two threads.

Thread A

a1 count = count + 1

Thread B

b1 count = count + 1

At ﬁrst glance, it is not obvious that there is a synchronization problem here.

There are only two execution paths, and they yield the same result.

The problem is that these operations are translated into machine language

before execution, and in machine language the update takes two steps, a read

and a write. The problem is more obvious if we rewrite the code with a tempo-

rary variable, temp.

Thread A

a1 temp = count

a2 count = temp + 1

Thread B

b1 temp = count

b2 count = temp + 1

Now consider the following execution path

a1 < b1 < b2 < a2

Assuming that the initial value of x is 0, what is its ﬁnal value? Because

both threads read the same initial value, they write the same value. The variable

is only incremented once, which is probably not what the programmer had in

mind.

This kind of problem is subtle because it is not always possible to tell, look-

ing at a high-level program, which operations are performed in a single step and

which can b e interrupted. In fact, some computers provide an increment in-

struction that is implemented in hardware cannot be interrupted. An operation

that cannot be interrupted is said to be atomic.

剩余290页未读，继续阅读

询蟀儒

粉丝: 0
资源: 1

操作系统同步艺术：《信号量小书》详解

The Little Book Of Semaphores

信号量小书，第二版The Little Book of Semaphores, Second Edition

little_book_of_semaphore,带目录完全版

目标检测数据集：瓶子图像缺陷检测数据【VOC标注格式】

毕业设计论文SpringBoot健身馆网站.docx

基于MATLAB车牌识别代码界面版(1).zip

基于循环卷积神经网络RCNN的语音情感识别分类源码+数据集(识别语音输出情感).zip

毕业设计论文SpringBoot教师工作量计算系统.docx

三维点云分割-基于Pytorch实现的Open3D-PointNet算法-优质项目实战.zip

MongoDB查询语言：分片处理

最新资源