操作系统（四）——进程管理(下)
一、进程同步与互斥
1.进程同步的基本概念
多道程序环境下，进程是并发执行的，不同进程间存在着不同的相互制约关系。为了协调进程之间的相互制约关系，达到资源共享和进程协作，避免进程之间的冲突，引入了进程同步的概念。
（1）临界资源（critical resource）
对临界资源的访问，必须互斥的进行。每个进程中，访问临界资源的那段代码称为临界区。
为了保证临界资源的正确使用，可以把临界资源的访问过程分为四个部分。
1） 进入区。为了进入临界区使用临界资源，在进入区要检查可否进入临界区。
2） 临界区。进程中访问临界资源的那段代码。
3） 退出区。将正在访问临界区的标志清除。
4） 剩余区。代码中的其余部分。
（2）同步（synchronism）
同步也称为直接制约关系（直接制约关系：进程需等待来自其他进程的信息而产生的协作关系。进程间的相互联系是有意识的安排的，直接作用只发生在相关进程间），它是为完成某种任务而建立的两个或多个进程。这些进程因为需要在某些位置上协调他们的工作次序而等待、传递信息所产生的制约关系。进程间的直接制约关系就是它们之间的相互合作。
进程同步是指多个进程之间协调彼此的执行顺序，以便在共享资源的情况下保持数据的一致性和正确性。在多任务操作系统中，每个进程都有自己的执行时间片段，当多个进程同时访问共享资源时，可能会引发冲突和竞争条件，导致数据错误或不一致。为了解决这些问题，需要使用进程同步机制来确保进程之间的协调和同步。常见的进程同步方法包括信号量、互斥锁、条件变量等。
同步，就是并发进程/线程在一些关键点上可能需要互相等待与互通消息，这种相互制约的等待与互通信息称为进程/线程同步。
（3）互斥（mutual exclusion）
互斥亦称间接制约关系（进程的间接制约关系：是指进程独占分配到的部分或全部共享资源（共享变量）而产生的竞争关系。进程间要通过某种中介发生联系，是无意识安排的，可发生在相关进程之间，也可发生在无关进程之间）。当一个进程进入临界区使用临界资源时，另一个进程必须等待，当占用临界资源的进程退出临界区后，另一个进程才允许去访问此临界资源。
进程的互斥（间接作用）：由于各进程要求共享资源，而有些资源需要互斥使用，即多个进程不能同时使用同一个资源，因此各进程间竞争使用这些资源，进程的这种关系为进程的互斥。
进程同步的目的是为了协调多个进程或线程的执行顺序，以便它们能够按照一定的规则协作完成某个任务。例如，在生产者消费者模型中，生产者进程和消费者进程需要按照一定的顺序交替执行，以保证生产者生产的数据能够被消费者及时消费。为了实现这种协作，需要使用进程同步机制，如信号量、条件变量等，来确保进程之间按照一定的顺序进行协作。
2.进程互斥的基本方法
（1）软件实现方法
（2）硬件实现方法
中断屏蔽方法
当一个进程正在使用处理器执行他的临界区代码时，要防止去其他进程在进入其临界区访问的最简单方法就是禁止一切中断的发生，或称之为屏蔽中断、关中断。因为CPU只有在发生中断时引起进程的调度和切换，这样屏蔽中断就能保证当前运行进程将临界区代码顺利的执行完，然后再开中断。
这种方法限制了处理器交替执行程序的能力，因此执行的效率将会明显降低。对内核来说，当它执行更新变量或列表的几条指令期间关中断是很方便的，但将关中断的权力交给用户则很不明智，若一个进程关中断之后不再打开终端，则系统可能会因此终止。
硬件指令——TestAndSet指令
TestAndSet指令可以用于实现原子操作，以避免多个线程同时访问共享资源的问题。但是，如果多个线程同时使用TestAndSet指令来竞争同一个资源，可能会导致死锁。这是因为TestAndSet指令会不断地循环等待直到资源可用，而如果多个线程都在等待同一个资源，它们可能就会陷入无限循环，形成死锁。
但是，TestAndSet指令本身不会导致饥饿，因为它只是一个原子操作，不会导致其他线程无法访问资源。如果发生饥饿，通常是由于其他原因，例如调度算法或锁的实现方式不当。
硬件指令——Swap指令
Swap指令用于实现原子操作，可以用于交换两个变量的值。如果多个线程同时使用Swap指令来竞争同一个变量，可能会导致饥饿。这是因为每个线程都需要等待其他线程完成Swap操作，才能继续执行自己的操作。如果某个线程一直没有机会执行Swap操作，它可能会一直被阻塞，导致饥饿。
但是，Swap指令本身不会导致死锁。因为Swap操作是原子的，只有一个线程能够成功执行Swap操作，其他线程都会等待。如果多个线程同时等待Swap操作完成，它们可能会陷入无限循环，但不会形成死锁。
硬件方法优点：使用与任意数目的进程，不管是单处理器还是多处理器：简单、容易验证其正确性。可以支持进程内有多个临界区，只需要为每个临界区设立一个布尔变量。
硬件方法的缺点：进程等待进入临界区时要耗费处理器时间，不能实现让权等待。从等待进程中随机选择一个进入临界区，有的进程可能一直选不上，从而导致“饥饿”现象。
互斥锁（mutex lock）
互斥锁的实现是通过在代码中加入一段互斥代码区域，这段代码区域只能被一个线程访问。当一个线程进入互斥代码区域时，它会请求互斥锁，如果此时互斥锁已经被其他线程占用，则该线程将被阻塞，直到互斥锁被释放。
互斥锁的优点在于它可以确保所有线程对共享资源的访问是有序的，避免了数据混乱和数据竞争的问题。但是，由于每个线程在访问共享资源时都需要先获得互斥锁，如果互斥锁的使用不当会导致线程之间的竞争，从而降低程序的并发性能。因此，在使用互斥锁时需要特别注意其使用方式和使用场景。TSL指令、Swap指令、单标志法都是互斥锁的实现方式之一，但它们并不是严格意义上的互斥锁，因为它们只是互斥锁的一种实现方式，而不是互斥锁本身。
TSL指令（Test and Set Lock）是一种硬件机制，用于实现互斥锁。它是通过在计算机硬件层面上实现一个原子的读取和修改操作，来保证对共享资源的访问是互斥的。
Swap指令（Exchange指令）也是一种硬件机制，用于实现互斥锁。它是通过将两个内存地址中的值进行交换，来实现对共享资源的访问保护。
单标志法（One-Flag Lock）是一种软件实现的互斥锁，它通过一个标志位来实现对共享资源的访问保护。当一个线程想要访问共享资源时，它会先将标志位设置为“忙”，然后尝试访问共享资源，如果访问成功，则将标志位设置为“空闲”；如果访问失败，则一直等待，直到共享资源变为“空闲”。
因此，可以说TSL指令、Swap指令、单标志法都是互斥锁的实现方式之一，但它们并不是互斥锁本身。
3.信号量
前面的互斥算法都存在问题，它们是平等进程间的一种协商机制，需要一个地位高于进程的管理者来解决公有资源的使用问题。OS可从进程管理者的角度来处理互斥的问题，信号量就是OS提供的管理公有资源的有效手段。信号量的值代表可用资源实体的数量。
信号量结构是一种功能较强的机制，可用来解决互斥与同步的问题，它只能被两个标准原语wait和signal来访问，也可以记作p操作和v操作。（原语是指完成某种功能且不被分割不被中断执行的操作序列，有时也成为原子操作，通常可用硬件来实现完成某种功能的不可分割执行特性）
作用范围：互斥锁只能用于同一进程内的线程同步，而信号量可以用于不同进程之间的线程同步。
控制对象：互斥锁只用于对临界区资源的互斥访问，而信号量可以用于控制多个线程对多个共享资源的访问。
操作方式：互斥锁只有两种状态：锁定和解锁，而信号量有多种操作方式，如增加、减少、等待、唤醒等。
用途：互斥锁主要用于保护共享资源的原子性操作，而信号量则可以用于控制线程的执行顺序、进程间通信等。
综上所述，互斥锁和信号量虽然都是线程同步的工具，但在使用时需要根据实际情况选择合适的工具。
如果等待的对象是一个阻塞的资源，例如一个被其他线程占用的锁或者一个读写操作被阻塞的管道，那么等待操作就会阻塞。阻塞意味着当前线程会被挂起，直到等待的对象变为可用状态。
但是，如果等待的对象是一个非阻塞的资源，例如一个已经可用的锁或者一个非空的消息队列，那么等待操作就不会阻塞，当前线程会立即返回。
此外，还有一些等待方式可以避免阻塞，例如超时等待和轮询等待。超时等待指等待一定时间后如果等待的对象还未变为可用状态，就放弃等待并返回结果；轮询等待指在等待对象变为可用状态之前，不断地重复检查等待对象的状态，以避免长时间的阻塞。
综上所述，等待操作并不一定会阻塞，具体取决于等待的对象和等待方式。
（1）整型信号量
整型信号量被定义为一个用于表示资源个数的整型量S。
虽然忙等会消耗大量的CPU资源，但是在某些情况下它仍然是必要的，特别是在实时系统中，需要快速响应事件并且不能使用阻塞等待的方式。在非实时系统中，可以使用其他的同步机制，如条件变量、管程等来避免忙等。轮询和忙等在某些情况下可以表示相同的意思，但它们并不完全相同。
轮询是指不断地查询某个状态是否满足某个条件，如果满足条件则执行相应的操作。轮询可以是阻塞的，也可以是非阻塞的。在阻塞式轮询中，如果状态不满足条件，则会一直等待；在非阻塞式轮询中，如果状态不满足条件，则会立即返回，不会等待。
忙等是指在等待某个条件满足期间，不断地进行查询、检查，直到条件满足。忙等是一种阻塞式的轮询方式。在忙等期间，会一直占用CPU资源，直到条件满足为止。
因此，虽然轮询和忙等有相似之处，但它们的含义和实现方式并不完全相同。
（2）记录型信号量
避免忙等：如果没有等待队列，进程或线程只能通过忙等来等待信号量变为可用状态，这会占用大量的CPU时间，降低系统的性能。而等待队列可以让进程或线程在信号量不可用时挂起，只有在信号量可用时才会被唤醒，从而避免了忙等的情况。
公平性：等待队列可以保证多个进程或线程按照请求的顺序依次占用信号量，从而保证了公平性。如果没有等待队列，那么当信号量可用时，可能会随机选择一个进程或线程来占用信号量，这会导致某些进程或线程一直无法获取到信号量，从而降低系统的公平性。
可扩展性：等待队列可以支持多个进程或线程等待同一个信号量，从而增加了系统的可扩展性。如果没有等待队列，那么只能支持一个进程或线程等待一个信号量，这会使得系统的并发性能受到限制。
总之，等待队列是记录型信号量实现多进程或多线程同步的重要手段，它可以提高系统的性能、公平性和可扩展性。
数据类型：整型信号量是一个整数，通常用于计数或者标记资源的可用性；而记录型信号量是一个结构体，包含多个字段，可以记录更为复杂的状态信息。
值的取值范围：整型信号量的取值范围是整个整数范围，通常只有两个值：0和1。而记录型信号量的取值范围取决于结构体中包含的字段的取值范围，可以有更多的取值。
使用场景：整型信号量通常用于控制对某个共享资源的访问，例如限制并发访问数量；而记录型信号量可以用于更为复杂的场景，例如控制进程间的通信、同步和互斥等。
实现方式：整型信号量可以使用原子操作来实现，比较简单；而记录型信号量则需要更复杂的实现方式，例如使用互斥锁、条件变量、共享内存等。
综上所述，记录型信号量和整型信号量在功能和实现方式上存在较大的差异，开发者在使用时需要根据具体的场景选择适合的信号量类型。
（3）利用信号量实现进程互斥
信号量机制能很方便的解决进程互斥问题。
互斥的实现是不同进程对同一信号量进行P操作和V操作，一个进程在成功地对信号量执行了P操作后进入临界区，并在退出临界区后，由该进程本身对该信号量执行V操作，表示当前没有进程进入临界区，可让其他进程进入。
（4）利用信号量实现进程同步
需要注意的是，使用信号量机制实现进程同步时，需要保证所有进程或线程都使用相同的信号量，否则就无法实现正确的同步。同时，还需要避免死锁的情况，即当多个进程或线程互相等待对方释放锁时，就会出现死锁。
（5）利用信号量实现前驱关系
前驱图
信号量也可以用来描述程序之间或者语句之间的前驱关系。
1） 关系分析。找出问题中的进程数，并且分析它们之间的同步和互斥关系。同步、互斥、前驱关系直接按照上面例子中的经典范式改写。
2） 整体思路。找出解决问题的关键点，并且根据做过的题目找出解决的思路。根据进程的操作流程确定P操作、V操作的大致顺序。
3） 设置信号量。根据上面两步，设置需要的信号量，确定初值，完善整理。
（7）信号量集
一般信号量集是由多个二元信号量组成的集合，每个信号量只有两种状态，即0和1，用于实现基本的同步和互斥机制。一般信号量集中最常用的操作是P和V操作，分别用于对信号量的值进行减1和加1操作。
而AND信号量集则是由多个信号量组成的集合，每个信号量可以有多个状态，用于实现更加复杂的同步和互斥机制。AND信号量集中最常用的操作是Swait和Ssignal操作，可以对信号量集中的多个信号量进行操作，例如等待多个信号量中的任意一个信号量被触发，或让多个信号量的值达到某一个特定值。
因此，一般信号量集和AND信号量集在功能和应用场景上存在巨大的差异。一般信号量集适用于简单的同步和互斥机制，如控制进程和线程的访问顺序、实现互斥访问共享资源等。而AND信号量集则适用于更加复杂的同步和互斥机制，如解决多进程或多线程之间的同步和互斥问题、实现高级进程同步机制等。
综上所述，一般信号量集和AND信号量集是两种不同类型的信号量集，它们在功能和应用场景上存在较大差异，需要根据具体的应用需求进行选择。
PV操作只能对一个信号量进行操作，而Swait和Ssignal可以对信号量集中的多个信号量进行操作。例如，可以通过Swait操作等待多个信号量中的任意一个信号量被触发，而不是仅仅等待一个信号量被触发。
PV操作通常用于二元信号量，即只有0和1两种状态，而Swait和Ssignal可以处理更多的状态。例如，可以使用Swait操作等待信号量集中的一个信号量的值达到某一个特定值。
PV操作通常是原子操作，即在操作期间不会被其他进程或线程中断，而Swait和Ssignal操作通常不是原子操作，它们可能会被中断和恢复。因此，在使用Swait和Ssignal时，需要考虑并发和竞争条件，以避免死锁和竞态条件的问题。
总之，Swait和Ssignal是AND型信号量集中常用的操作方法，相较于PV操作具有更加灵活和多样的同步和互斥机制，可以满足更加复杂的应用场景。但是，在使用Swait和Ssignal时，需要仔细考虑并发和竞争条件，以避免死锁和竞态条件的问题。
4.经典同步与互斥问题
（1）生产者-消费者问题（the producer/consumer problem）
问题描述：一组生产者进程和一组消费者进程共享一个初始为空、大小为n的缓冲区，只有缓冲区没满时，生产者才能把消息放入到缓冲区，否则必须等待；只有缓冲区不为空时，消费者才能从中取出消息，否则必须等待。由于缓冲区是临界资源，它只允许一个生产者放入消息，或一个消费者从中取出消息。
问题分析：
1）关系分析。生产者和消费者对缓冲区互斥访问是互斥关系，同时生产者和消费者又是一个相互协作的关系，只有生产者生产之后，消费者才能消费，他们也是同步关系。
2）整理思路。这里比较简单，只有生产者和消费者两个进程，正好是这两个进程存在着互斥关系和同步关系。那么需要解决的是互斥和同步PV操作的位置。
3）信号量的设置。信号量mutex作为互斥信号量，它用于控制互斥访问缓冲池，互斥信号量初始为1；信号量full用于记录当前缓冲池中“满”缓冲区数，初值为0。信号量empty用于记录当前缓冲池中空缓冲区，初值为n。[互斥信号量mutex为1时，表示当前没有进程占用资源，可以直接访问临界区代码；互斥信号量mutex为0时，表示资源被另一个进程占用，当前进程需要等待，直到mutex不为0才能继续执行临界区代码。]
互斥信号量（Mutual Exclusion Semaphore）是一种同步原语，用于控制对共享资源的访问。它的值通常为1或0，0表示资源正在被占用，1表示资源空闲。在进程访问共享资源之前，需要先尝试将互斥信号量的值减1（原子操作），如果值变成了0，则表示资源正在被占用，该进程需要等待；否则，该进程获得了资源的使用权。
互斥锁（Mutex）也是一种同步原语，它也用于控制对共享资源的访问。它的作用是保证在同一时间只有一个线程可以访问共享资源。互斥锁在进程访问共享资源之前，需要先尝试获取锁，如果锁被其他线程占用，则当前线程需要等待；否则，当前线程获得了锁的所有权。
因此，互斥信号量和互斥锁都可以用于实现线程同步，它们的作用类似，但细节和实现方式有所不同。在一些操作系统和编程语言中，互斥信号量和互斥锁的实现方式可能不同。
互斥信号量和互斥锁都可以用于进程同步和线程同步。
在进程并发编程中，互斥信号量和互斥锁都是常用的同步机制，它们都可以用于控制对共享资源的访问，避免了进程或线程之间的竞争和冲突。无论是在进程级别还是线程级别，互斥信号量和互斥锁都可以防止多个进程或线程同时访问共享资源，从而保证程序的正确性和可靠性。
在一些操作系统和编程语言中，互斥信号量和互斥锁的实现方式可能不同，但它们的作用和原理是相似的。因此，根据具体的应用场景和需求，可以选择使用互斥信号量或互斥锁来实现进程或线程的同步和互斥访问。
（2）多生产者-多消费者问题
问题描述：桌子上有一只盘子，每次孩子能向其中放入一个水果。爸爸专向盘子中放入苹果，妈妈专向盘子中放入橘子，女儿专等吃盘子中的苹果，儿子专等吃盘子中的橘子。只有盘子为空时，爸爸或妈妈就可向盘子中放一只水果2；仅当盘子中有自己需要的水果时，儿子或女儿可以从盘子中取出。
1）关系分析。这里的关系略微复杂一些，首先由每次只能向其中放入一只水果可知爸爸和妈妈是互斥关系。爸爸和女儿、妈妈和儿子是同步关系，而且这两对进程必须连起来，儿子和女儿之间没有互斥和同步关系，因为他们是选择条件执行，不可能并发。
2）整理思路。这里有4个进程，实际上可以抽象为两个生产者和两个消费者被连接到大小为1的缓冲区上。
3）信号量设置。首先设置信号量plate为互斥信号量，表示是否允许想盘子放水果，初值为1，表示允许放入，且只允许放一只。信号量apple表示盘子里是否有苹果，初值为0，表示盘子中无2苹果；信号量orange表示盘子中是否有橘子，初始量为0，表示盘子中无橘子。
（3）吸烟者问题
问题描述：假设一个系统有三个吸烟者进程和一个供应者进程。每个抽烟者不停的卷烟并抽调他，但是要卷起并抽掉一支烟，抽烟者必须要有三种材料：烟草、纸和胶水。三个抽烟者中，第一个有烟草，第二个有纸，第三个有胶水。供应者进程无线地提供提供三种材料。
供应者每次将两种材料放到桌子上，拥有剩下那种材料的抽烟者卷一根烟并抽掉它，并给供应者一个信号告诉完成了，供应者就会放另外两种材料在桌子上，这种过程一直重复。
问题分析：
1）关系分析。供应者与三个抽烟者分别是同步关系。由于供应者无法同时满足两个或两个以上的抽烟者，三个抽烟者对抽烟这个动作是互斥关系。
2）整理思路。显然这里有四个进程。供应者作为生产者向三个抽烟者提供材料。
3）信号量设置。信号量offer1、offer2、offer3分别表示烟草和纸组合的资源、烟草和胶水组合的资源、纸和胶水组合的资源。信号量finish 用于互斥进行抽烟动作
（4）读者一写者问题（the readers-writers problem）
问题描述：有读者和写者两组并发进程，共享一个文件，当两个以上的读进程同事访问共享数据时不会产生副作用，但若某个写进程和其他进程（读进程或写进程）同时访问共享数据时则可能导致数据不一致的错误。因此要求：1）允许多个读者同时对文件执行读操作；2）只允许一个写者往文件中写信息；3）任一写者在完成写操作之前不允许其他读者或写者工作；4）写者执行完写操作前，应让已有的读者或写者全部退出。
问题分析：
1）关系分析。由题目分析读者和写者是互斥的，写者和写者也是互斥的，而读者和读者不存在互斥关系。
2）整理思路。两个进程，即读者和写者。写者和任何进程互斥，用互斥信号量p操作、v操作即可解决。读者的问题比较复杂，它必须实现与写者互斥的关系，还要实现和其他读者同步的关系。因此，简单的一对pv操作时无法解决的。那么在这里用到了一个计数器，用它来判断当前是否有读者读文件。当有读者的时候，写者是无法写文件的，此时读者会一直占用文件，当没有读者的时候，写者才可以写文件。同时这里不同读者对计数器的访问也是互斥的。
3）信号量的设置。首先设置信号量count为计数器，用来记录当前读者数量，初值为0；设置mutex为互斥信号量，用于保护更新count变量时的互斥；设置互斥信号量rw用于保证读者和写者的互斥访问。
读者优先策略
写者优先策略——只要有写者准备要写入，写者应尽快执行写操作，后来的读者就必须阻塞如果有写者持续不断写入，则读者就处于饥饿。
公平策略——由于读者优先策略和写者优先策略都会造成饥饿的现象。
优先级相同；
写者、读者互斥访问；
只能一个写者访问临界区；
可以有多个读者同时访问临界资源；
没有读者到达会导致读者队列为空，即 rCount==0，此时写者才可以进入临界区执行写操作。
而这里 flag 的作用就是阻止读者的这种特殊权限（特殊权限是只要读者到达，就可以进入读者队列）。
比如：开始来了一些读者读数据，它们全部进入读者队列，此时来了一个写者，执行 P(falg) 操作，使得后续到来的读者都阻塞在 flag 上，不能进入读者队列，这会使得读者队列逐渐为空，即 rCount 减为 0。
这个写者也不能立马开始写（因为此时读者队列不为空），会阻塞在信号量 wDataMutex 上，读者队列中的读者全部读取结束后，最后一个读者进程执行 V(wDataMutex)，唤醒刚才的写者，写者则继续开始进行写操作。
（5）哲学家进餐问题（the dining philosophers problem）
问题描述：一张圆桌上坐着五个哲学家，每两个哲学家之间的桌子上摆着一根筷子，桌子的中间是一碗米饭。哲学家们倾注毕生精力用于思考和进餐，哲学家在思考是，并不影响其他人。只有当哲学家饥饿的时候，才视图拿起左右两根筷子。如果筷子已经在他人手上，则需等待。饥饿的哲学家只有同时拿到了两根筷子才可以开始进餐，当进餐完毕后，放下筷子继续思考。
问题分析：
1）关系分析。五个哲学家与左右邻居对其中的筷子的访问是互斥关系。
2）整理思路。显然这五个进程，要解决的问题有两个：一个是让他们同时拿起两个筷子；而是对每个哲学家的动作执行规则，避免饥饿或者死锁现象发生。
3）信号量设置。定义互斥信号组chopsticks[5]={1,1,1,1,1}用于对五个筷子的互斥访问。
对哲学家按顺序0~4编号，哲学家i左边的筷子编号为i，哲学家右边的筷子编号为（i+1）%5。
解决方案一——让偶数编号的哲学家「先拿左边的叉子后拿右边的叉子」，奇数编号的哲学家「先拿右边的叉子后拿左边的叉子」。
解决方案二——
用一个数组 state 来记录每一位哲学家的三个状态，分别是在进餐状态、思考状态、饥饿状态（正在试图拿叉子）。
那么，一个哲学家只有在两个邻居都没有进餐时，才可以进入进餐状态。
第 i 个哲学家的左邻右舍，则由宏 LEFT 和 RIGHT 定义：
LEFT : ( i + 5 - 1 ) % 5
RIGHT : ( i + 1 ) % 5
比如 i 为 2，则 LEFT 为 1，RIGHT 为 3。
5.管程（Monitor, 监视器）
二、死锁
1. 死锁的概念
在多道程序系统中，由于多个进程的并发执行，改善了系统资源的利用率并提高了系统的处理能力。然而，多个进程的并发执行也带来了新的问题——死锁。所谓死锁是指多个进程因竞争资源而造成的一种僵局，若无外力作用，这些进程都将无法向前推进。
什么时候会发生死锁？
1）系统资源的竞争
通常系统中拥有的不可剥夺资源，其数量不足以满足多个进程运行的需要，似的进程在运行过程中会因争夺资源而陷入僵局。只有对不可剥夺资源的竞争才可能产生死锁，对可剥夺资源的竞争是不会引起死锁的。
2）进程推进顺序非法
进程在运行过程中，请求和释放资源的顺序不当，同样会导致死锁。
信号量使用不当也会造成死锁。进程间相互等待对方发来的消息，结果也会造成某些进程间无法继续向前推进。
3）死锁产生的必要条件
产生死锁必须同时满足以下四个条件，只要其中任一个条件不成立，死锁就不会发生。
互斥条件：进程要求对所分配的资源进行排他性控制，即在一段时间内某资源仅为一个进程所占用。此时若有其他进程请求该资源，则请求进程只能等待。
不剥夺条件：进程所获得的资源在未使用完毕之前，不能被其他进程强行夺走，即只能由获得该资源的进程自己来释放。
请求和保持条件：进程已经保持了至少一个资源，但又提出了新的资源请求，而该资源已被其他进程占有，此时请求进程被阻塞，但对自己已获得的资源保持不放。
循环等待条件：存在一种进程资源的循环等待链，链中每一个进程已获得的资源同时被链中下一个进程所请求。
死锁与饥饿的区别？
2.死锁的处理策略
3. 死锁的预防[静态策略]
① 破除资源互斥（Mutual Exclusion）条件，例如假脱机打印机技术允许若干个进程同时输出，唯一真正请求物理打印机的进程是打印机守护进程。
② 破除“请求与保持”(Request and Hold)条件：实行资源预分配策略，进程在运行之前，必须一次性获取所有的资源。缺点：在很多情况下，无法预知进程执行前所需的全部资源，因为进程是动态执行的，同时也会降低资源利用率，导致降低了进程的并发性。
③ 破除“不可剥夺”(Nonpreemptive)条件：允许进程强行从占有者那里夺取某些资源。当一个已经保持了某些不可被抢占资源的进程，提出新的资源请求而不能得到满足时，它必须释放已经保持的所有资源，待以后需要时再重新申请。这意味着进程已经占有的资源会被暂时被释放，或者说被抢占了。
④ 破除“循环等待”条件(Circlar Wait)：实行资源有序分配策略，对所有资源排序编号，按照顺序获取资源，将紧缺的，稀少的采用较大的编号，在申请资源时必须按照编号的顺序进行，一个进程只有获得较小编号的进程才能申请较大编号的进程。
4. 死锁的避免[动态策略]
死锁预防通过约束资源请求，防止4个必要条件中至少一个的发生，可以通过直接或间接预防方法，但是都会导致低效的资源使用和低效的进程执行。而死锁避免则允许前三个必要条件，但是通过动态地检测资源分配状态，以确保循环等待条件不成立，从而确保系统处于安全状态。所谓安全状态是指：如果系统能按某个顺序为每个进程分配资源（不超过其最大值），那么系统状态是安全的，换句话说就是，如果存在一个安全序列，那么系统处于安全状态。银行家算法是经典的死锁避免的算法。
安全状态
银行家算法
银行家算法是一种基于资源分配的死锁避免算法，它在资源分配前检查系统状态，通过计算安全序列来判断是否能够分配资源，从而避免死锁。在银行家算法中，每个进程都需要提前声明它所需要的资源数目和资源类型，同时还需要声明它所能够接受的最大资源数目。当一个进程请求资源时，银行家算法会检查该请求是否符合系统安全状态，如果符合，就会分配资源，否则就会等待资源。
相比之下，打破“循环等待条件”是一种死锁预防的方法，它是通过对资源的有序分配来打破资源之间的循环等待关系，从而避免死锁。在打破“循环等待条件”的过程中，通常需要指定资源的优先级和分配顺序，以确保资源分配的有序性。
因此，虽然银行家算法和打破“循环等待条件”都与死锁有关，但它们的解决问题的方式和核心思想是不同的。银行家算法通过安全序列的计算来避免死锁，而打破“循环等待条件”则是通过资源的有序分配来避免死锁。
5.死锁的检测
死锁预防策略是非常保守的，他们通过限制访问资源和在进程上强加约束来解决死锁的问题。死锁检测则是完全相反，它不限制资源访问或约束进程行为，只要有可能，被请求的资源就被授权给进程。但是操作系统会周期性地执行一个算法检测前面的循环等待的条件。死锁检测算法是通过资源分配图来检测是否存在环来实现，从一个节点出发进行深度优先搜索，对访问过的节点进行标记，如果访问了已经标记的节点，就表示有存在环，也就是检测到死锁的发生。
（1）如果进程-资源分配图中无环路，此时系统没有死锁。
（2）如果进程-资源分配图中有环路，且每个资源类中只有一个资源，则系统发生死锁。
（3）如果进程-资源分配图中有环路，且所涉及的资源类有多个资源，则不一定会发生死锁。
常见的死锁检测算法包括：
1.银行家算法（Banker's algorithm）：银行家算法是一种基于资源分配图的死锁检测算法。它通过模拟进程请求资源的情况，来判断系统是否会发生死锁。
2.图论算法：图论算法是一种基于有向图的死锁检测算法。它将系统中的资源和进程表示为节点，将资源的分配和请求关系表示为有向边，然后通过检测是否存在环来确定是否存在死锁。
3.等待图算法（Wait-for graph algorithm）：等待图算法是一种基于等待图的死锁检测算法。它将系统中的进程和资源表示为节点，将进程等待资源的关系表示为有向边，然后通过检测是否存在环来确定是否存在死锁。
这些死锁检测算法都有各自的优缺点，具体应用时需要根据实际情况进行选择。
资源获取环可以采用图来存储，使用有向图来存储。
线程 A 获取线程 B 已占用的锁，则为线程 A 指向线程 B。
运行过程中线程 B 获取成功的锁即为线程 B 已占用的锁（可以使用hook方法得到）。
检测的原理采用另一个线程定时对图进程检测是否有环的存在。
*利用工具排查死锁问题
java的jstack是jdk自带的线程对战分析工具，在linux下，可用pstack+gdb工具来定位死锁问题，pstack 命令可以显示每个线程的栈跟踪信息（函数调用过程），它的使用方式也很简单，只需要 pstack <pid> 就可以了。在定位死锁问题时，我们可以多次执行 pstack 命令查看线程的函数调用过程，多次对比结果，确认哪几个线程一直没有变化，且是因为在等待锁，那么大概率是由于死锁问题导致的。
6.死锁的恢复（解除）
死锁解除的常用方法就是终止进程和资源抢占，回滚。所谓进程终止就是简单地终止一个或多个进程以打破循环等待，包括两种方式：终止所有死锁进程和一次只终止一个进程直到取消死锁循环为止；所谓资源抢占就是从一个或者多个死锁进程那里抢占一个或多个资源。
综合方法
*三、乐观锁和悲观锁
1. 互斥锁与自旋锁
互斥锁是一种用于多线程编程中，防止多个线程同时执行同一段代码（临界区）的机制。它是一种保护共享资源的锁，一次只允许一个线程访问共享资源。当线程请求互斥锁时，如果锁没有被其他线程占用，则该线程可以获得锁并继续执行；如果锁已经被其他线程占用，则该线程会被阻塞，直到锁被释放为止。 互斥锁的实现通常使用了操作系统提供的原语（如mutex），可以跨进程使用，适用于多核、多进程的情况。
自旋锁是一种用于多线程编程中，等待锁释放时不阻塞线程而是循环检测锁状态的锁。当线程请求自旋锁时，如果锁没有被其他线程占用，则该线程可以获得锁并继续执行；如果锁已经被其他线程占用，则该线程会一直循环等待，直到锁被释放为止。 自旋锁的实现通常使用了操作系统提供的原语（如atomic指令），只能在同一进程内使用，适用于单核、多线程的情况。自旋锁的优点是等待锁的线程不会被阻塞，避免了线程切换的开销，缺点是对CPU资源的占用较高，如果等待锁的时间较长会浪费大量的CPU时间。
互斥锁加锁失败后，线程会释放 CPU ，给其他线程；
自旋锁加锁失败后，线程会忙等待，直到它拿到锁；
互斥锁是一种「独占锁」，比如当线程 A 加锁成功后，此时互斥锁已经被线程 A 独占了，只要线程 A 没有释放手中的锁，线程 B 加锁就会失败，于是就会释放 CPU 让给其他线程，既然线程 B 释放掉了 CPU，自然线程 B 加锁的代码就会被阻塞。
对于互斥锁加锁失败而阻塞的现象，是由操作系统内核实现的。当加锁失败时，内核会将线程置为「睡眠」状态，等到锁被释放后，内核会在合适的时机唤醒线程，当这个线程成功获取到锁后，于是就可以继续执行
互斥锁加锁失败时，会从用户态陷入到内核态，让内核帮我们切换线程，虽然简化了使用锁的难度，但是存在一定的性能开销成本——两次线程上下文切换的成本。
当线程加锁失败时，内核会把线程的状态从「运行」状态设置为「睡眠」状态，然后把 CPU 切换给其他线程运行；
接着，当锁被释放时，之前「睡眠」状态的线程会变为「就绪」状态，然后内核会在合适的时间，把 CPU 切换给该线程运行。
线程的上下文切换的是什么？当两个线程是属于同一个进程，因为虚拟内存是共享的，所以在切换时，虚拟内存这些资源就保持不动，只需要切换线程的私有数据、寄存器等不共享的数据。
所以，如果你能确定被锁住的代码执行时间很短，就不应该用互斥锁，而应该选用自旋锁，否则使用互斥锁。
自旋锁是通过 CPU 提供的 CAS 函数（Compare And Swap），在「用户态」完成加锁和解锁操作，不会主动产生线程上下文切换，所以相比互斥锁来说，会快一些，开销也小一些。
一般加锁的过程，包含两个步骤：
第一步，查看锁的状态，如果锁是空闲的，则执行第二步；
第二步，将锁设置为当前线程持有；
CAS 函数就把这两个步骤合并成一条硬件级指令，形成原子指令，这样就保证了这两个步骤是不可分割的，要么一次性执行完两个步骤，要么两个步骤都不执行。
比如，设锁为变量 lock，整数 0 表示锁是空闲状态，整数 pid 表示线程 ID，那么 CAS(lock, 0, pid) 就表示自旋锁的加锁操作，CAS(lock, pid, 0) 则表示解锁操作。
使用自旋锁的时候，当发生多线程竞争锁的情况，加锁失败的线程会「忙等待」，直到它拿到锁。这里的「忙等待」可以用 while 循环等待实现，不过最好是使用 CPU 提供的 PAUSE 指令来实现「忙等待」，因为可以减少循环等待时的耗电量。
自旋锁是最比较简单的一种锁，一直自旋，利用 CPU 周期，直到锁可用。需要注意，在单核 CPU 上，需要抢占式的调度器（即不断通过时钟中断一个线程，运行其他线程）。否则，自旋锁在单 CPU 上无法使用，因为一个自旋的线程永远不会放弃 CPU。
自旋锁开销少，在多核系统下一般不会主动产生线程切换，适合异步、协程等在用户态切换请求的编程方式，但如果被锁住的代码执行时间过长，自旋的线程会长时间占用 CPU 资源，所以自旋的时间和被锁住的代码执行的时间是成「正比」的关系，我们需要清楚的知道这一点。
自旋锁与互斥锁使用层面比较相似，但实现层面上完全不同：当加锁失败时，互斥锁用「线程切换」来应对，自旋锁则用「忙等待」来应对。
它俩是锁的最基本处理方式，更高级的锁都会选择其中一个来实现，比如读写锁既可以选择互斥锁实现，也可以基于自旋锁实现。
2. 读写锁
它由「读锁」和「写锁」两部分构成，如果只读取共享资源用「读锁」加锁，如果要修改共享资源则用「写锁」加锁。
所以，读写锁适用于能明确区分读操作和写操作的场景。
读写锁的工作原理是：
当「写锁」没有被线程持有时，多个线程能够并发地持有读锁，这大大提高了共享资源的访问效率，因为「读锁」是用于读取共享资源的场景，所以多个线程同时持有读锁也不会破坏共享资源的数据。
但是，一旦「写锁」被线程持有后，读线程的获取读锁的操作会被阻塞，而且其他写线程的获取写锁的操作也会被阻塞。
所以说，写锁是独占锁，因为任何时刻只能有一个线程持有写锁，类似互斥锁和自旋锁，而读锁是共享锁，因为读锁可以被多个线程同时持有。
知道了读写锁的工作原理后，我们可以发现，读写锁在读多写少的场景，能发挥出优势。
另外，根据实现的不同，读写锁可以分为「读优先锁」和「写优先锁」。
读优先锁期望的是，读锁能被更多的线程持有，以便提高读线程的并发性，它的工作方式是：当读线程 A 先持有了读锁，写线程 B 在获取写锁的时候，会被阻塞，并且在阻塞过程中，后续来的读线程 C 仍然可以成功获取读锁，最后直到读线程 A 和 C 释放读锁后，写线程 B 才可以成功获取写锁。
写优先锁是优先服务写线程，其工作方式是：当读线程 A 先持有了读锁，写线程 B 在获取写锁的时候，会被阻塞，并且在阻塞过程中，后续来的读线程 C 获取读锁时会失败，于是读线程 C 将被阻塞在获取读锁的操作，这样只要读线程 A 释放读锁后，写线程 B 就可以成功获取写锁。
读优先锁对于读线程并发性更好，但也不是没有问题。如果一直有读线程获取读锁，那么写线程将永远获取不到写锁，这就造成了写线程「饥饿」的现象。
写优先锁可以保证写线程不会饿死，但是如果一直有写线程获取写锁，读线程也会被「饿死」。
既然不管优先读锁还是写锁，对方可能会出现饿死问题，那么我们就不偏袒任何一方，搞个「公平读写锁」。
公平读写锁比较简单的一种方式是：用队列把获取锁的线程排队，不管是写线程还是读线程都按照先进先出的原则加锁即可，这样读线程仍然可以并发，也不会出现「饥饿」的现象。
互斥锁和自旋锁都是最基本的锁，读写锁可以根据场景来选择这两种锁其中的一个进行实现。
3. 乐观锁和悲观锁
互斥锁、自旋锁、读写锁，都是属于悲观锁。
悲观锁做事比较悲观，它认为多线程同时修改共享资源的概率比较高，于是很容易出现冲突，所以访问共享资源前，先要上锁。
那相反的，如果多线程同时修改共享资源的概率比较低，就可以采用乐观锁。
乐观锁做事比较乐观，它假定冲突的概率很低，它的工作方式是：先修改完共享资源，再验证这段时间内有没有发生冲突，如果没有其他线程在修改资源，那么操作完成，如果发现有其他线程已经修改过这个资源，就放弃本次操作。
放弃后如何重试，这跟业务场景息息相关，虽然重试的成本很高，但是冲突的概率足够低的话，还是可以接受的。
可见，乐观锁的心态是，不管三七二十一，先改了资源再说。另外，你会发现乐观锁全程并没有加锁，所以它也叫无锁编程。
这里举一个场景例子：在线文档。
我们都知道在线文档可以同时多人编辑的，如果使用了悲观锁，那么只要有一个用户正在编辑文档，此时其他用户就无法打开相同的文档了，这用户体验当然不好了。
那实现多人同时编辑，实际上是用了乐观锁，它允许多个用户打开同一个文档进行编辑，编辑完提交之后才验证修改的内容是否有冲突。
怎么样才算发生冲突？这里举个例子，比如用户 A 先在浏览器编辑文档，之后用户 B 在浏览器也打开了相同的文档进行编辑，但是用户 B 比用户 A 提交早，这一过程用户 A 是不知道的，当 A 提交修改完的内容时，那么 A 和 B 之间并行修改的地方就会发生冲突。
服务端要怎么验证是否冲突了呢？通常方案如下：
由于发生冲突的概率比较低，所以先让用户编辑文档，但是浏览器在下载文档时会记录下服务端返回的文档版本号；
当用户提交修改时，发给服务端的请求会带上原始文档版本号，服务器收到后将它与当前版本号进行比较，如果版本号不一致则提交失败，如果版本号一致则修改成功，然后服务端版本号更新到最新的版本号。
实际上，我们常见的 SVN 和 Git 也是用了乐观锁的思想，先让用户编辑代码，然后提交的时候，通过版本号来判断是否产生了冲突，发生了冲突的地方，需要我们自己修改后，再重新提交。
乐观锁虽然去除了加锁解锁的操作，但是一旦发生冲突，重试的成本非常高，所以只有在冲突概率非常低，且加锁成本非常高的场景时，才考虑使用乐观锁。
*快速面经
1. 进程间同步的方式有哪些？
1、临界区：通过对多线程的串行化来访问公共资源或一段代码，速度快，适合控制数据访问。
优点：保证在某一时刻只有一个线程能访问数据的简便办法。
缺点：虽然临界区同步速度很快，但却只能用来同步本进程内的线程，而不可用来同步多个进程中的线程。
2、互斥量：为协调共同对一个共享资源的单独访问而设计的。互斥量跟临界区很相似，比临界区复杂，互斥对象只有一个，只有拥有互斥对象的线程才具有访问资源的权限。
优点：使用互斥不仅仅能够在同一应用程序不同线程中实现资源的安全共享，而且可以在不同应用程序的线程之间实现对资源的安全共享。
缺点：
互斥量是可以命名的，也就是说它可以跨越进程使用，所以创建互斥量需要的资源更多，所以如果只为了在进程内部是用的话使用临界区会带来速度上的优势并能够减少资源占用量。
通过互斥量可以指定资源被独占的方式使用，但如果有下面一种情况通过互斥量就无法处理，比如现在一位用户购买了一份三个并发访问许可的数据库系统，可以根据用户购买的访问许可数量来决定有多少个线程/进程能同时进行数据库操作，这时候如果利用互斥量就没有办法完成这个要求，信号量对象可以说是一种资源计数器。
3、信号量：为控制一个具有有限数量用户资源而设计。它允许多个线程在同一时刻访问同一资源，但是需要限制在同一时刻访问此资源的最大线程数目。互斥量是信号量的一种特殊情况，当信号量的最大资源数=1就是互斥量了。
优点：适用于对Socket（套接字）程序中线程的同步。
缺点:
信号量机制必须有公共内存，不能用于分布式操作系统，这是它最大的弱点；
信号量机制功能强大，但使用时对信号量的操作分散， 而且难以控制，读写和维护都很困难，加重了程序员的编码负担；
核心操作P-V分散在各用户程序的代码中，不易控制和管理，一旦错误，后果严重，且不易发现和纠正。
4、事件： 用来通知线程有一些事件已发生，从而启动后继任务的开始。
优点：事件对象通过通知操作的方式来保持线程的同步，并且可以实现不同进程中的线程同步操作。
2. 线程同步的方式有哪些？
1、临界区：当多个线程访问一个独占性共享资源时，可以使用临界区对象。拥有临界区的线程可以访问被保护起来的资源或代码段，其他线程若想访问，则被挂起，直到拥有临界区的线程放弃临界区为止，以此达到用原子方式操 作共享资源的目的。
2、事件：事件机制，则允许一个线程在处理完一个任务后，主动唤醒另外一个线程执行任务。
3、互斥量：互斥对象和临界区对象非常相似，只是其允许在进程间使用，而临界区只限制与同一进程的各个线程之间使用，但是更节省资源，更有效率。
4、信号量：当需要一个计数器来限制可以使用某共享资源的线程数目时，可以使用“信号量”对象。
区别：
互斥量与临界区的作用非常相似，但互斥量是可以命名的，也就是说互斥量可以跨越进程使用，但创建互斥量需要的资源更多，所以如果只为了在进程内部是用的话使用临界区会带来速度上的优势并能够减少资源占用量 。因为互斥量是跨进程的互斥量一旦被创建，就可以通过名字打开它。
互斥量，信号量，事件都可以被跨越进程使用来进行同步数据操作。
3. 什么是临界区，如何解决冲突？
每个进程中访问临界资源的那段程序称为临界区，一次仅允许一个进程使用的资源称为临界资源。
解决冲突的办法：
如果有若干进程要求进入空闲的临界区，一次仅允许一个进程进入，如已有进程进入自己的临界区，则其它所有试图进入临界区的进程必须等待；
进入临界区的进程要在有限时间内退出。
如果进程不能进入自己的临界区，则应让出CPU，避免进程出现“忙等”现象。
4.什么是死锁？死锁产生的条件？如何处理死锁问题？
什么是死锁：
在两个或者多个并发进程中，如果每个进程持有某种资源而又等待其它进程释放它或它们现在保持着的资源，在未改变这种状态之前都不能向前推进，称这一组进程产生了死锁。通俗的讲就是两个或多个进程无限期的阻塞、相互等待的一种状态。
死锁产生的四个必要条件：（有一个条件不成立，则不会产生死锁）
互斥条件：一个资源一次只能被一个进程使用
请求与保持条件：一个进程因请求资源而阻塞时，对已获得资源保持不放
不剥夺条件：进程获得的资源，在未完全使用完之前，不能强行剥夺
循环等待条件：若干进程之间形成一种头尾相接的环形等待资源关系
常用的处理死锁的方法有：死锁预防、死锁避免、死锁检测、死锁解除、鸵鸟策略。
（1）死锁的预防：基本思想就是确保死锁发生的四个必要条件中至少有一个不成立：
① 破除资源互斥条件
② 破除“请求与保持”条件：实行资源预分配策略，进程在运行之前，必须一次性获取所有的资源。缺点：在很多情况下，无法预知进程执行前所需的全部资源，因为进程是动态执行的，同时也会降低资源利用率，导致降低了进程的并发性。
③ 破除“不可剥夺”条件：允许进程强行从占有者那里夺取某些资源。当一个已经保持了某些不可被抢占资源的进程，提出新的资源请求而不能得到满足时，它必须释放已经保持的所有资源，待以后需要时再重新申请。这意味着进程已经占有的资源会被暂时被释放，或者说被抢占了。
④ 破除“循环等待”条件：实行资源有序分配策略，对所有资源排序编号，按照顺序获取资源，将紧缺的，稀少的采用较大的编号，在申请资源时必须按照编号的顺序进行，一个进程只有获得较小编号的进程才能申请较大编号的进程。
（2）死锁避免：
死锁预防通过约束资源请求，防止4个必要条件中至少一个的发生，可以通过直接或间接预防方法，但是都会导致低效的资源使用和低效的进程执行。而死锁避免则允许前三个必要条件，但是通过动态地检测资源分配状态，以确保循环等待条件不成立，从而确保系统处于安全状态。所谓安全状态是指：如果系统能按某个顺序为每个进程分配资源（不超过其最大值），那么系统状态是安全的，换句话说就是，如果存在一个安全序列，那么系统处于安全状态。银行家算法是经典的死锁避免的算法。
（3）死锁检测：
死锁预防策略是非常保守的，他们通过限制访问资源和在进程上强加约束来解决死锁的问题。死锁检测则是完全相反，它不限制资源访问或约束进程行为，只要有可能，被请求的资源就被授权给进程。但是操作系统会周期性地执行一个算法检测前面的循环等待的条件。死锁检测算法是通过资源分配图来检测是否存在环来实现，从一个节点出发进行深度优先搜索，对访问过的节点进行标记，如果访问了已经标记的节点，就表示有存在环，也就是检测到死锁的发生。
（1）如果进程-资源分配图中无环路，此时系统没有死锁。
（2）如果进程-资源分配图中有环路，且每个资源类中只有一个资源，则系统发生死锁。
（3）如果进程-资源分配图中有环路，且所涉及的资源类有多个资源，则不一定会发生死锁。
（4）死锁解除：
死锁解除的常用方法就是终止进程和资源抢占，回滚。所谓进程终止就是简单地终止一个或多个进程以打破循环等待，包括两种方式：终止所有死锁进程和一次只终止一个进程直到取消死锁循环为止；所谓资源抢占就是从一个或者多个死锁进程那里抢占一个或多个资源。
（5）鸵鸟策略：
把头埋在沙子里，假装根本没发生问题。因为解决死锁问题的代价很高，因此鸵鸟策略这种不采取任何措施的方案会获得更高的性能。当发生死锁时不会对用户造成多大影响，或发生死锁的概率很低，可以采用鸵鸟策略。大多数操作系统，包括 Unix，Linux 和 Windows，处理死锁问题的办法仅仅是忽略它。
