并发
为了完结一起运转多个程序的需求，人们创造了虚拟化CPU的操作体系，经过在CPU不同的时刻片上切换运转不同的程序，发生一种并行的假象，这种假象便是并发
并行 VS 并发：这两者的差异在于，并行是真实意义上的一起运转多个程序，比方多核CPU每个核一起履行不同的程序，而并发是同一个CPU在不一起间段运转不同程序，并不是真实的并行
进程相关
进程，便是一个运转中的程序，是OS为正在运转的程序供给的笼统。
进程有几种根本状况：运转、安排妥当、堵塞、创立、完毕，堵塞挂起、安排妥当挂起，其间相互转化的联系如下图所示，除安排妥当态和运转态可相互转化外，其他只能单向转化
安排妥当状况：可运转，但由于其他进程处于运转状况而暂时中止；针对安排妥当状况的【安排妥当挂起】：让暂时没有运转的进程换出到swap space节省内存空间
堵塞状况：等候某一事情而中止运转，就算给了CPU操控权也无法运转；针对堵塞状况的【堵塞挂起】：让堵塞进程在外存等候事情发生免除堵塞状况
挂起状况：堵塞状况的进程会占用物理内存，为了节省内存空间，将该进程的物理内存换出到磁盘中，此时进程不再占有物理内存，称之为挂起状况
进程的办理进程
插叙：进程操控块PCB是一个描绘进程的数据结构，包含了进程描绘、进程操控和办理信息，以及相关的资源分配清单和CPU相关信息
比方它包含程序计数器，仓库指针，内存分配状况，所翻开文件的状况，用来确保被中止的进程之后能够再次发动，一起它是以链表的形式组织起来的，比方安排妥当行列、堵塞行列，便利增删办理
-
创立进程：
- 请求一个空白PCB并填写部分信息；
- 为该进程分配必需的资源；
- 将PCB刺进到安排妥当行列，等候被调度运转
-
停止进程，三种方法：正常完毕、异常完毕、外界干预比方kill掉
- 查找需求停止的进程的 PCB；
- 假如处于履行状况，则当即停止该进程的履行，然后将 CPU 资源分配给其他进程；
- 假如其还有子进程，则应将该进程的子进程交给 1 号进程接管；
- 将该进程所具有的悉数资源都归还给操作体系；
- 将其从 PCB 地点行列中删除；
-
堵塞进程，进程需求等候时能够调用堵塞句子把自己堵塞等候，然后等候其他进程唤醒
- 找到将要被堵塞进程标识号对应的 PCB；
- 假如该进程为运转状况，则维护其现场，将其状况转为堵塞状况，中止运转；
- 将该 PCB 刺进到堵塞行列中去
-
唤醒进程，唤醒句子和堵塞句子是一一对应的
- 在该事情的堵塞行列中找到相应进程的 PCB；
- 将其从堵塞行列中移出，并置其状况为安排妥当状况；
- 把该 PCB 刺进到安排妥当行列中，等候调度程序调度；
特别的进程
-
看护进程：在后台运转的，没有操控终端与它相连的进程。它独立于操控终端，周期性地履行使命，linux的大大都服务器便是用看护进程的方法完结的
看护进程的创立进程
- 让程序在后台履行：调用fork()创立一个子进程，然后让父进程退出
- 在子进程中创立新会话：调用setsid()让子进程完全独立
- 改动当时目录为根目录（非必选）：调用chdir()防止占用可卸载的文件体系
- 重设文件权限掩码（非必选）：调用umask()防止继承的文件创立屏蔽字回绝某种权限，一起添加看护进程灵活性
- 封闭文件描绘符（非必选）：节约体系资源
- 开端履行看护进程的中心作业
-
僵尸进程：指现已退出、但还未让父进程发觉的子进程，意图是保存子进程的状况，便利父进程在需求的时分获取，弊端便是这个子进程将会持续占据内核资源
僵尸进程的停止方法
- 父进程调用堵塞式的
wait()或非堵塞式的waitpid()来停止僵尸子进程，但这会导致父进程挂起 - 父进程经过
signal函数以为处理信号SIGCHLD：子进程退出后父进程收到信号SIGCHLD，然后在回调函数中调用wait()或waitpid() - 父进程经过
signal(SIGCHLD,SIG_IGN)奉告内核，自己对子进程的退出不感兴趣，子进程退出后直接由内核回收
- 父进程调用堵塞式的
线程相关
线程，便是进程傍边的一条履行流程，相似于同享地址空间的独立进程
它和进程的一个首要差异是进行上下文切换时不需求切换当时运用的页表（由于同一个进程下的线程们同享地址空间）
插叙：OS事先为CPU预备好寄存器和程序计数器，别离用作缓存以及存储CPU正在履行的指令方位，这是CPU在运转任何使命前一切必要依靠的环境，这些环境就叫做CPU上下文
而在OS切换进程时，OS首先会保存当时的上下文信息，然后切换到对应进程的上下文，这个进程就叫做上下文切换，这种切换大致可分为：进程切换、线程切换、中止切换
线程同享资源有：文件描绘符表；每种信号的处理方法；当时作业目录；用户ID和组ID
线程非同享资源有：线程id；内核栈；用户空间栈；errno变量；信号屏蔽字；调度优先级
另一个首要差异在于栈，在单线程进程中只需一个栈位于地址空间的底部，而在多线程进程中，每个线程都有一个独立运转的栈
-
用户线程
在用户空间里运转的线程，由运用程序创立和办理的线程，所以它也只需用户等级的权限，当一个线程运转完毕后有必要等候它自动交出CPU操控权或免除
为什么不能自动打断线程？由于用户空间里并没有中止和切换线程的特权
插叙：针对这个问题，一方面能够经过非堵塞的IO多路复用技能，比方select、epoll等完结和谐多个用户线程之间的切换；另一方面也能够经过取得内核线程的支撑，比方后文的1:1模型、N:M模型等完结对用户线程的自动切换
由于它的切换不涉及到内核态和用户态的切换，切换的速度较快，一起它的完结和办理都和OS没有直接联系，所以能够用于不支撑线程技能的OS上
但由于OS实践上只给【进程】分配了时刻片，而它的诞生是进程自作主张地将自己又划分为了多个线程，所以每个线程取得的时刻片都较小，多线程运转下的速度较慢，也无法充分运用多核CPU的优势
操作体系只看得见【进程】，看不见进程划分出的用户线程，所以无法多核一起履行该进程下的多条线程，除非取得内核线程的支撑
-
内核线程
由OS办理它的创立、停止和调度的线程
可由OS直接将时刻片分配给它，所以多线程的进程能够取得更多的CPU运转时刻，且由于内核有强制中止、切换和调度线程的特权，所以假如某个线程被堵塞了是不需求等候它自动交出CPU的
但也由于它的创立切换和停止都是经过体系调用完结的，所以体系开支会比较大
-
轻量级进程LWP
能够将它理解为是内核支撑的用户线程，它与内核线程一对一映射，能够经过它为用户线程供给内核的支撑
依据用户线程和它的数量对应联系，能够分为如下三种模型：
-
1:1模型：一个LWP对应一个用户线程
可完结并行，当一个LWP堵塞时，不会影响到其他的LWP；但每一个用户线程都会跟一个内核线程对应，创立线程的开支会比较大
-
N:1模型：一个LWP对应多个用户线程
线程办理在用户态下完结，该形式中的用户线程对操作体系是不行见的；上下文切换时的效率较快，但无法充分运用多核也无法自动切换一个堵塞的用户线程
-
M:N模型：多个LWP对应多个用户线程
归纳了以上两种的长处，大部分状况下的线程上下文切换发生在用户空间，效率较高；也能较为充分地运用多核CPU的优势
-
单个进程怎么运转
在咱们了解了进程和线程的相关概念后，让咱们开端评论一个重要的问题，那便是为了构建让多个使命同享CPU一起运转的假象，咱们需求在坚持操作体系对CPU的操控权的状况下，尽或许地取得高性能
这就需求用到接下去评论的受限直接运转机制
这个机制望文生义分为两个部分：一个部分是”直接履行“，另一个部分是”受限“
直接运转：OS发动程序时创立好进程，然后跳转到进程入口点开端履行用户代码，直接在CPU上运转程序，用来完结高性能的需求
受限：但上面的这种直接运转需求加以必定的限制，防止OS失掉对进程们的操控权，但在某些状况下又有必要要答应它进行一些特权操作
比方在一些状况下，需求答应进程进行磁盘I/O或请求内存等操作
为此，操作体系引入了一种新的处理器形式：用户形式和内核形式
内核形式下运转的代码则能够履行一切类型的受限操作
而用户形式下用户运转的代码将受到限制，但操作体系答应内核小心肠向用户程序露出一些要害功能（也便是体系调用），让用户能够经过体系调用履行特权操作
履行特权操作的进程：
- 用户运用体系调用履行trap指令跳入内核中并进步特权等级
- 用户在内核中履行用户所希望的作业代码
- 当用户完结作业后OS履行return-from-trap指令
- 回到用户程序并下降特权等级
履行特权操作需求的操作体系支撑：
- OS在发动时需求经过特权指令初始化圈套表（trap table），经过圈套表奉告硬件在发生异常事情时需求运转哪些代码
- 由CPU记住圈套表的方位
- 硬件有必要确保有满足的寄存器存储调用者的信息，以便OS履行return-from-trap指令后能够回来到正确的方位
为什么需求圈套表呢？：假如由调用者奉告trap指令应该履行内核里的哪段代码，会使得程序员能够令内核运转任意代码序列，这将损坏操作体系的安全性
整个受限直接运转的流程图如下
多个进程怎么并发
前文提到，并发并不是真实的并行，而是经过CPU在不一起间片上切换履行不同的进程（线程）给各个进程（线程）营造出一种并行的假象，这儿就涉及到了两个首要的问题：怎么切换进/线程 以及 在什么时分切换进/线程
怎么切换进/线程？
先以进程为例，当OS决议切换进程时，它将为正在履行的进程保存一些资源
比方说虚拟内存、栈、大局变量等用户空间资源以及内核仓库、寄存器等内核空间资源，此处为OS明确地保存，这些资源指的便是【上下文】
并为即将履行的进程康复一些寄存器的值，经过切换栈使得当内核进入【切换代码调用】时是当时进程的上下文，而终究履行return-from-trap时将回来跳入到新进程的上下文中，然后完结进程的切换
进程切换进程：保存当时进程上下文到进程PCB中，并从下一个进程PCB取出上下文康复到CPU中
这就要求进程在运转完毕后将CPU的操控权交由给OS，才干让OS得以进行上下文切换，一般来说有两种方法让进程转交操控权
-
协作方法：当OS相信进程会合理运转时，它经过等候体系调用或某种非法操作的发生后，然后重获CPU操控权
-
非协作方法——时钟中止：当OS没有进程协作时，它在发动时经过特权指令发动时钟，并将时钟编程为每隔一段时刻就发生中止，当发生中止时硬件将保存运转进程的寄存器到内核栈，而OS从头取得CPU的操控权，它能够挑选切换进程，也能够挑选持续运转该进程
OS将在发动时就设置好硬件在发生时钟中止时需求调用的代码，然后让硬件得以顺利保存寄存器
此处为硬件的隐式保存，差异于前文OS明确地保存寄存器
而关于线程来说，不同进程下的线程切换与上文所述的进程上下文切换没有不同；同一个进程下的线程切换也十分相似，仅仅由于这些线程同享虚拟内存和大局变量等资源，在切换时只切换私有数据、寄存器等数据，开支较小
线程是调度的根本单位，进程是资源具有的根本单位，所以OS在进行使命调度时，实践上是在调度线程，而进程仅仅给线程供给资源，所以严格上来说，进程切换便是不同进程下的线程切换
在什么时分切换进/线程？
这其实便是在问怎么调度多个需求运转的进/线程，或者说进/线程间的调度算法是什么，当进程的状况发生变化的时分，都会触发OS的调度，比方说当进程从安排妥当态变成运转态时，OS会从安排妥当进程行列中挑选出一个来运转
假如硬件供给周期性的时钟中止，依据怎么处理中止能够将调度算法分红两类
抢占式算法：进程只运转一段时刻，到点了就挂起经过中止把CPU操控权回来给调度程序调度；
非抢占式算法：让进程运转到直到自己堵塞或退出才会调用其他程序
为了衡量不同进程调度侧战略的好坏，有如下几个指标
-
周转时刻：T周转=T完结 -T抵达，假如有n个进程需求完结，T均匀周转=(T周转1+T周转2+……)/n，应该防止进程等候时刻很长，而运转时刻很短，以下降周转时刻
-
公正性：应该防止一些使命长时刻占据CPU，而另一些使命却始终无法履行被“饿死”
可是周转时刻和公正性两个性能寻求往往是对立的，为了进程间的公正，就要求OS在一些时刻段阻止当时进程运转切换到另一些进程，这就进步了当时进程的周转时刻
-
呼应时刻：T呼应=T使命抵达-T首次运转，关于交互性比较强的运用，应该尽或许缩短它的呼应时刻
-
体系吞吐量：权衡长使命和短使命的运转完结数量
-
CPU运用率：进程因发生IO事情堵塞的时分应该及时切换进程，充分运用CPU
FIFO先进先出战略
望文生义，先安排妥当的进程先开端履行（First-In-First-Out），适用于CPU繁忙的体系
长处：简单且易于完结；当一切的使命时刻差距不大时，体现较好
缺点：当最早履行的进程时刻大大超过之后的进程，会导致之后的进程等候太多时刻，T均匀周转被拉高
SJF最短使命优先战略
在FIFO战略的基础上，假如多个进程一起抵达，优先履行耗时短的进程，有利于进步体系吞吐量，但对长使命不友好
缺点：假如多个进程抵达的时刻不同，若最早抵达的进程耗时最长，依旧会拉高T均匀周转
STCF最短完结时刻战略
每当新作业进入体系时，它会确定剩下作业和新作业中，谁的剩下完结时刻最少，然后抢占调度履行能够最快完结的作业
比方说一开端OS正在履行A进程，估计需求作业10min，这个时分来了进程B和C，这两个进程估计只需求作业1min
那么OS将经过中止取得CPU操控权，切换履行进程B（由于他的所需完结时刻最短），履行完B之后将持续切换履行C，终究才回来进程A履行
长处：这个战略就能够较好地处理FIFO战略和SJF战略在周转时刻上的缺点，确保每次都让短使命优先被处理掉
缺点：但假如只运用这种战略，将会导致呼应时刻被延长，对交互性特别不友好
以上面那种状况为例，A的呼应时刻为0，B的呼应时刻也为0（B刚抵达就开端运转），而C进程的呼应时刻为1min（幻想一下，你按下键盘一分钟之后电脑屏幕才呈现你按的字符）
MLFQ多级反应行列战略
在前文的评论中，咱们能够发现，下降周转时刻的中心在于优先运转短使命
但不论是SJF战略仍是STCF战略，想抵到达优先运转短使命这个意图，都需求预先知道各进程或许的作业时刻，可是这却是OS难以得知的，且以上战略在交互性方面的体现都不甚理想
而MLFQ多级反应行列战略则很好地处理了这两个问题
首先在MLFQ中有许多优先级不同的独立行列，每个行列下有多个作业
MLFQ经过观察这些作业履行时的行为动态地调整它们的优先级，而且总是先轮转履行最高优先级行列下的作业，其他详细规则如下：
-
当新作业进入体系时，放在最高优先级行列
-
当作业用完整个时刻片后，下降其优先级移入到下一个行列
意图：下降周转时刻，短使命将在高优先级行列被很快处理，而长使命将被下降优先级，下放到低优先级行列
-
若作业在其时刻片内自动开释CPU，则坚持优先级不变
意图：进步交互性，让不断出让CPU的进程坚持在高优先级行列，完结交互性作业的快速运转
-
一旦作业用完了它在某一级行列的时刻配额，无论抛弃了多少次CPU都降级
意图：维护OS，防止有进程总是在时刻片完毕前履行一次I/O，霸占CPU
-
每经过一段时刻S，就将体系中一切作业从头加入最高优先级行列
意图：确保公正性，防止有太多交互性作业或短使命不断占用高优先级行列，导致低优先级行列里的长使命被“饿死”
维护
当咱们经过进程、线程笼统了正在运转的程序，也经过比方受限直接运转机制、多级反应机制等开端建立了计算机的并发问题之后，一切都还没有完毕，怎么在并发的状况下确保程序不犯错变成了一个新的难题
考虑这么一种状况：咱们创立了A和B两个线程，在两个线程中都让一个大局变量nums自增1000次，咱们预期的nums终究成果将会是2000，可是当咱们实践这么做后会发现计算机给出的答案往往并不符合咱们的预期，这便是由于缺少了对并发的维护
为什么会犯错？：假如在线程A运转进程中发生了不合时宜的中止，比方A线程让nums变量变成1之后，还没有来得及将nums值保存到内存地址中，却马上发生了中止切换到了B线程；
B线程从内存地址中取出nums的值，由于A线程还没有更新保存，此时取到的nums仍为0，B线程将它自增变成1后存回地址中；
随后A线程康复运转，它并不知道在B线程所发生的事，而仅仅持续履行自己的终究一步：将自增为1的nums保存到内存地址中，可是在预期状况下，这个时分变量应该是2才对
像这样导致多个程序拜访同享资源的代码叫做临界区，多个履行线程都企图更新同享资源的状况叫做竞态条件，当程序由一个或多个竞态条件组成的时分，程序的输出常常因运转罢了，导致呈现成果的不确定性，而咱们希望计算机给出确定的成果
之所以会呈现这种不确定性，要害在于有多个进/线程一起拜访了临界区，且发生了不合时宜的中止，所以咱们在一个时刻段内应该只答应一个线程进入临界区操作同享资源，这便是互斥的概念
想要完结这种互斥，一般来说有两种方法，一种是：锁，另一种是：信号量
锁
锁，是一种变量，它有着多种状况，比方：available、free状况代表它可用，而held、acquire状况代表它正在被一个线程持有。
当一段临界区代码被上锁了之后，就只需获取了锁的线程能够进入临界区，而其他企图拜访临界区的线程都会由于获取锁失利而堵塞，然后完结了线程间的互斥
最常见的运用方法如下：
lock_t mutex;//锁是一种变量，运用前需求先声明 ... lock(&mutex);//给临界区加上锁，当某个线程运转到此处时会测验获取锁 arr++; //临界区代码，只需持有锁的线程能够拜访此处的代码 unlock(&mutex);//解锁，当某个线程运转到此处会开释掉它所持有的锁
OS运用了一些硬件原语来完结锁，比方说TestAndSet(测验并设置指令)，CompareAndSwap(比较并交流指令)，以及FetchAndAdd(获取并添加指令)，下面咱们逐个剖析这三种硬件原语是怎么完结锁的
硬件原语：一组特定的计算机硬件指令，在硬件层面将一些操作设置为原子性的，比方TestAndSet，将【测验】与【设置】两个操作设置为原子操作
TestAndSet怎么完结锁
int TestAndSet(int *old_ptr,int new){
int old=*old_ptr;
*old_ptr=new; //将old_ptr设置为新值
return old; //回来old_ptr的旧值
}
typedef struct lock_t{
int flag;
}lock_t;
void init(lock_t lock){
lock->flag=0;
}//初始化锁
void lock(lock_t lock){
while(TestAndSet(&lock->flag,1)==1) ;//空等候，自旋
}
void unlock(lock_t *lock){
lock->flag=0;
}
-
当flag为0值时阐明锁可被获取，flag值为1时阐明锁正在被人持有
-
当线程获取锁时：调用TestAndSet函数，由于flag值为0，所以它回来锁的旧值，会跳出while循环，一起设置flag的值为1；当线程离开临界区时，调用unlock()将flag清理为0
-
而当一个线程测验获取不行得的锁时，由于锁的值一直是1，TestAndSet函数返>回值一直都是1，所以它会一直在while循环里自旋
在lock()函数中的while循环下，假如什么都不做，就阐明线程因获取锁失利而堵塞的时分，会一直等候，这种锁被叫做自旋锁；而假如在while循环下把线程信息保存进TCB，并切换线程，这就变成了无等候锁（？互斥锁吧）
CompareAndSwap怎么完结锁
int CompareAndSwap(int *ptr,int expected,int new){
int actual=*ptr;
if(actual==expected) *ptr=new;
return actual;
}
void lock(lock_t *lock){
while(CompareAndSwap(&lock->flag,0,1)==1) ;
}
- 检测ptr是否与expected持平（即检测flag值是否为0，即锁可否被获取）
- 假如持平，则更新ptr的值为新值，然后回来ptr的旧值（假如回来的是0，阐明线程在测验获取锁的时分flag是0，可获取该锁；假如回来的是1，阐明现已有线程占有该锁了，就会在while循环里自旋等候
FetchAndAdd怎么完结锁
int FetchAndAdd(int *ptr){
int old=*ptr);
*ptr=old+1;
return old;
}
typedef struct lock_t{
int ticket;
int turn;
}lock_t;
void lock_init(lock_t *lock){
lock->ticket=0;
lock->turn=0;
}
void lock(lock_t *lock){
int myturn= FetchAndAdd(&lock->ticket);
while(lock->turn!=myturn) ;
}
void unlock(lock_t *lock){
FetchAndAdd(&lock->turn);
}
- FetchAndAdd的作用：将ptr自增，然后回来它的旧值
- 每次调用lock函数会使得ticket值自增，每次调用unlock函数会使得turn值自增
- 在lock函数里，假如ticket自增前的旧值与unlock持平，阐明现在没有线程在持有锁（ticket的值和turn持平，阐明调用lock函数的次数和unlock函数的次数是一样）
运用这种硬件原语完结的锁能够确保让一切线程都能抢到锁，只需一个线程取得了ticket值，那它终究就必定会被调度
不同类型的锁
经过以上方法，在lock函数里运用while() ;让线程空等候的锁都是自旋锁，加锁失利的线程将会自旋等候，直到锁可用停止
需求留意的是，假如在单核CPU上想要运用自旋锁，有必要调配抢占式的调度器，由于一个自旋的线程永远不会自动抛弃CPU操控权，这将会导致这个单核CPU一直在自旋
这种锁在多核体系中一般不会自动发生线程切换，适合异步、协程等在用户态切换请求的编程方法
可是假如有太多的线程竞赛一把锁，将会导致自旋过多，浪费CPU资源，因而咱们需求对自旋锁进行必定的改善：当一个线程加锁失利后，将其休眠，开释CPU资源并切换到其他线程，直到该线程所需求的锁被开释后才从头唤醒它，这便是互斥锁
可是这种锁也存在必定的开支的本钱，它会涉及到两次的线程上下文切换
第一次：当时线程加锁失利，切换到其他线程；第二次：锁可用后唤醒原线程，从其他线程切换回它
所以运用这种锁需求留意，它适用于被锁住的代码履行时刻较长，假如履行时刻较短的话，它单单是上下文切换的事情或许都比履行时刻要更长
归纳以上考虑，实践上，在Linux体系中采用了一种陈旧的锁计划：两阶段锁，OS设计者意识到自旋在处理很快就要开释锁的场景下效率较高，因而规则两阶段锁的第一阶段将会自旋一段时刻，假如自旋阶段加锁失利，才会让调用线程休眠
针对一些特定的运用场景，比方明确区分读写同享资源操作的场景下，还有读写锁的概念，完结的中心功能为：当写锁被线程持有时，将会堵塞其他线程获取读锁和写锁的操作；而当写锁未被持有时，可有多个线程一起持有读锁
即答应多个用户一起读取同享资源；且当有一个用户正在写资源时，不答应其他用户一起写或一起读，以防发生过错
依据完结不同，还能够分为读优先锁和写优先锁
- 读优先锁：当有线程调用写锁被堵塞时，该线程需求等候一切的读锁都被开释，才干加写锁成功
- 写优先锁：当有线程调用写锁被堵塞时，不论期间是否有多少线程又调用读锁，都会优先让该线程加写锁成功，堵塞其他线程加读锁的操作
但这两种方法其实都有一些问题，都有或许让读锁或写锁饿死，所以就又发生了公正读写锁，用行列把获取锁的线程排队，不论是读锁仍是写锁都按先入先出的准则加锁即可
锁的其他分类：
失望锁：互斥锁、自旋锁、读写锁都属所以失望锁：即以为多线程一起修正同享资源的概率很高，所以拜访同享资源前要先上锁
达观锁：先修正同享资源，再验证一下这段时刻是否有其他线程在修正资源，若有则抛弃本次操作，若没有则操作完结：即以为多线程一起修正资源的概率是比较小的。常运用于同享文档、Git等场景：总是让用户先编辑内容，在提交的时分经过版本号来判断是否发生冲突，这防止了加锁解锁的操作，但冲突重试的本钱较高
信号量
信号量是一个有整数值的目标，可由初始值决议其行为，有三个首要的操作函数，别离是用于初始化信号量sem的sem_init()，履行P操作的sem_post()，以及履行V操作的sem_wait()
- P操作：将信号量sem自增1，假如此时有线程正在等候唤醒，则唤醒一个等候线程
- V操作：将信号量sem自减1，假如自减后信号量<0，则堵塞当时线程进入休眠，等候其他线程履行P操作唤醒它
运用场景1：完结互斥锁
一般来说，信号量的初始值sem设置为多少，就意味着答应多少个线程在同一时刻内运用这个信号量，依据这个准则，能够将sem初始值设置为1完结互斥，这样的信号量叫做二值信号量（信号量只需持有 和 没有持有两种状况）
最常见的运用方法如下：
sem_t m; sem_init(&m,0,1); …… sem_wait(&m); arr++; sem_post(&m);
为什么信号量的初始值需求设置为1？
假定有两个线程想要进入临界区，线程1先调用sem_wait()将信号量减一变成0（相当于获取锁），它会持续往下走进入临界区；
假如现在线程2也想进入临界区调用sem_wait()，信号量再减一变成负数，会让线程2开端等候；
直到线程1完毕了临界区代码调用sem_post()将信号量加一，才会唤醒线程2（相当于开释锁）
运用场景2：完结读写锁
typedef struct _rwlock_t{
sem_t lock;
sem_t writelock;
int readers;
}rwlock_t;
void rwlock_init(rwlock_t *rw){
rw->readers=0;
sem_init(&rw->lock,0,1);
sem_init(&rw->writelokc,0,1);
}
void rwlock_acquire_readlock(rwlock_t *rw){
sem_wait(&rw->lock);
rw->readers++;
if(rw->readers==1) sem_wait(&rw->writelock);
//只需正在履行读操作的用户到达了1，就经过sem_wait()将写者锁堵塞
sem_post(&rw->lock);
}
void rwlock_release_readlock(rwlock_t *rw){
sem_wait(&rw->lock);
rw->readers--;
if(rw->readers==0) sem_post(&rw->writelock);
//只需没有用户正在履行读操作，就经过sem_post()将写者锁开释
sem_post(&rw->lock);
}
void rwlock_acquire_writelock(rwlock_t *rw){
sem_wait(&rw->writelock);
}
void rwlock_release_writelock(rwlock_t *rw){
sem_post(&rw->writelock);
}
-
lock变量：用于完结一个互斥锁，在rwlock_acquire_readlock()和rwlock_release_lock()两个函数中，确保增减readers数量 和 堵塞、开释写者锁两个操作是原子式的 -
writelock变量：用于限制写者锁只需在没有用户操作同享资源时才干获取 -
readers变量：用于记载正在进行读操作的用户有几个为什么是
if(rw->readers==1) sem_wait(rw->writelock);，而不是if(rw->readers>=1) sem_wait(rw->writelock);：由于想要堵塞写者锁的获取，只需求让rw->writelock为-1即可，假如是后者的写法，每次获取写者锁都会让rw->writelock自减，是不必要的操作以如上方法完结的读写锁是读优先锁，需求等候
rw->readers==0，也便是没有用户在读时才会让进程获取写锁，假如想要完结读写公正锁则需求添加一个额定的flag信号量，用来限制读者或写者无限涌入的优先特权
运用场景3：用作条件变量，完结多线程间的同步
首先介绍一下什么是同步：并发进程或线程在一些要害点上或许需求相互通信和等候，比方需求等候线程A完毕后才干进行线程B，这种相互制约的等候和互通信息便是同步
比方说主线程需求等候子线程中的一些条件建立，才干持续运转，这个用作条件的变量便是条件变量，想要完结这种条件变量，需求将信号量设置为0
条件变量自身不是锁，它用来自动堵塞一个线程，等候直到某个特别状况发生停止
sem_t s;
void child(void *arg){
……
sem_post(&s);//将s值自增1,作为一种信号传递给主线程，奉告子线程已履行完毕
return NULL;
}
int main(int argc,char* argv[]){
sem_init(&s,0,0);
……
pthread_t c;
Pthread_create(c,NULL,child,NULL); //创立一个线程
sem_wait(&s);
……
return 0;
}
为什么要将信号量设置为0？：确保主线程假如先于子线程调用时，履行到
sem_wait()就会被堵塞，只需等候子线程履行完毕后调用sem_post()将信号量增为1才干持续履行
接下来，让咱们考虑一种更杂乱的状况：生产者-顾客问题，也便是生产者将资源生产放到缓冲区，然后顾客从缓冲区取走资源的场景，比方HTTP中的数据缓冲区便是一个典型的生产者-顾客问题
想要处理这个问题，一共需求三个信号量：
- 互斥信号量mutex，初始值设为1，用于互斥拜访缓冲区，也便是在生产和取走数据的前后加上
sem_post(&mutex)和sem_wait(&mutex) - 资源信号量full，初始值为0，用于表明缓冲区有多少数据可供顾客取走，生产者生产资源后调用
sem_wait(&full)让full值自增，而顾客消费资源前调用sem_post(&full)先判断一下有没有资源能够取，没有则堵塞等候 - 资源信号量empty，初始值为MAX，用于表明缓冲区有多少空位可供生产者放东西，生产者生产资源前先调用
sem_post(&empty)检查是否有空位，顾客消费后调用sem_wait(&empty)让empty值自增
详细代码如下：
sem_t empty;
sem_t full;
sem_t mutex;
void *producer(void* arg){
for(int i=0;i<loops;i++){
sem_wait(&empty);//V操作先判断一下是否有空位
sem_wait(&mutex);
put(i);
sem_post(&mutex);
sem_post(&full);//P操作奉告被堵塞的顾客进程，有资源能够取了
}
}
void *consumer(void *arg){
for(int i=0;i<loops;i++){
sem_wait(&full);
sem_wait(&mutex);
int tmp=get();
sem_post(&mutex);
sem_post(&empty);
printf("%d\n",tmp);
}
}
为什么能够把
sem_wait(&mutex)放在sem_wait(&full)或sem_wait(&empty)之前，sem_post(&mutex)放在sem_post(&empty)或sem_post(&full)之后，扩大互斥域吗？不行！假定顾客获取了mutex，取走了数据后调用sem_post()唤醒了生产者，但生产者想要写入数据前需求等候mutex，而此刻持有mutex的顾客却在等候full，变成了死锁
运用场景4：处理“哲学家就餐”问题
什么是哲学家就餐问题？：几个哲学家围着一个圆桌，每2个哲学家之间有一把餐叉，每个哲学家时而思考时而吃饭，而只需左右手一起拿到餐叉的哲学家才干吃饭
这个问题的挑战在于，怎么确保没有死锁，没有哲学家饿死，且尽或许让更多哲学家一起吃饭（也便是完结更高的并发度）
最简单的计划便是：假定餐叉数组为forks[N]，给每个餐叉都设置一个初始值为1的信号量，在每个哲学家线程中都先后运用sem_post(forks[i]); sem_post(forks[(i+1)%N]);意为先让哲学家先测验拿起左手边的餐叉，再测验拿起右手边的餐叉，然后即可就餐
缺点：可是这种计划下假如发生了不合时宜的中止，比方说每个哲学家都只履行了sem_post(forks[i])就被中止去履行其他哲学家线程，这会导致每个哲学家都只拿起了一个餐叉，每个人都没得吃
这个计划的缺点在于，每个哲学家线程里都编程设定每个人都先同一手边的餐叉，比方都统一先拿左手边的餐叉。所以针对这个计划的改善也很简单：只需让每个哲学家线程获取餐叉的先后次序交织一下，比方说规则奇数位次的哲学家都先拿左手边在拿右手边，偶数次位的哲学家相反，这样就能够防止原计划的极端状况呈现。
常见的并发问题
关于并发中常呈现的问题，一般来说能够分为两类，第一类占据了并发问题的大都：非死锁问题，第二类便是死锁问题
非死锁问题
-
违背原子性：代码段本意是原子的，但履行中没有强制实施原子性，如下
Thread 1:: if (thd->proc_info){ ... fputs(thd->proc_info,...); ... } Thread 2:: thd->proc_info=NULL;- 假如线程1在fputs之前被线程2中止，thd->proc_info被置为NULL，再进行线程1程序将崩溃
- 修正该类问题：只需求在拜访同享变量前加锁，拜访后解锁即可
-
违背次序缺点：代码中A应该在B之前履行，但并没有强制完结这种次序性
Thread 1:: void init(){ ... mThread = CreateThread(mMain,...); ... } Thread 2:: void mMain(){ ... mState = mThread->State; ... }-
假如线程2在线程1之前履行，则mThread并没有被初始化就被运用，或许会呈现奇怪的问题
-
修正该类问题：运用条件变量，比方如下修正
Thread 1:: void init(){ ... mThread = CreateThread(mMain,...); sem_post(&m); ... } Thread 2:: void mMain(){ ... sem_t m; sem_init(&m,0,1); sem_wait(&m); mState = mThread->State; ... }
-
死锁问题
什么是死锁问题？
举个栗子，咱们有线程1和线程2两个作业线程，线程1持有了锁A后预备获取锁B，可是它被线程2中止了，线程2快一步持有了锁B，而它接下来却要等候锁A；然后导致两个线程在互持平候的状况，这便是一种典型的死锁问题
经过上面的例子，咱们能够发现，死锁问题的诞生有四个必要条件：
- 互斥：即线程所需求的资源是互斥的，比方锁
- 持有并等候：即线程持有了某个资源，又在等候其他资源，比方线程1抢到了锁A，等候锁B
- 非抢占：即线程已取得的资源除非它自动抛弃，否则不会被其他线程抢占
- 循环等候：即线程之间存在等候资源的环路，比方每个线程都持有一个锁，而这个锁由恰好是它接下去的一个线程所等候的
这四个条件只需一个不满足，就不会发生死锁问题，所以针对这四个条件，就有不同的死锁预防战略：
-
防止互斥：经过强壮的硬件指令，构造出不需求锁的数据结构，比方说经过先前的TestAndSet就能够完结两个操作的原子式履行
-
防止持有并等候：原子式地抢锁，确保任何线程在抢占任何锁前需求先抢到大局的prevention锁，比方线程1在持有了锁A后，就算被线程2中止，线程2也会由于没有prevention锁而无法获取锁B，然后让线程1能够顺利获取锁A和B
-
防止非抢占：也便是让线程获取资源屡次失利后，自动抛弃现已获取的资源后再重试，比方线程1第二次测验获取锁B失利后，将会开释锁A，然后线程2能够顺利取得锁A进行其后的作业
但这种状况或许会导致活锁问题：多个线程一直在重复履行这个开释-重试的作业，但彼此都一起抢锁失利，处理方法是：让线程完毕一次开释-重试操作后先随机等候一段时刻再重复该操作
-
防止循环等候：这也是最直接的一种针对战略：在获取锁时供给一个全序，让线程每次请求锁时都严格依照固定的次序，比方让线程1和线程2都是先获取锁A，再获取锁B，这样就算线程1被中止切换到线程2，线程2也无法获取锁A，不会发生死锁
除了死锁预防以外，在某些场景或许更适合死锁防止，也便是当咱们了解到需求在n个处理器上进行m个进程使命时，能够经过进程调度防止死锁，比方防止让例子中的线程1和线程2并发运转，尽管这必定程度上会献身了性能
- 运用抢占康复：挂起进程强行取走资源给另一个进程
- 运用回滚康复：复位到更早还没有取得所需资源的状况
- 运用kill康复：杀死循环等候环路中的一个或多个进程
