主题
《面渣逆袭》操作系统 篇 · 第 3/6 章。原版 PDF（下载 / 打印）
并行和并发有什么区别？
并发就是在一段时间内，多个任务都会被处理；但在某一时刻，只有一个任务在执行。单核处理器做到的并发，其实是利用时间片的轮转，例如有两个进程A 和B ，A 运行一个时间片之后，切换到B ，B 运行一个时间片之后又切换到A 。因为切换速度足够快，所以宏观上表现为在一段时间内能同时运行多个程序。
并行就是在同一时刻，有多个任务在执行。这个需要多核处理器才能完成，在微观上就能同时执行多条指令，不同的程序被放到不同的处理器上运行，这个是物理上的多个进程同时进行。
什么是进程上下文切换？
对于单核单线程 CPU 而言，在某一时刻只能执行一条 CPU 指令。上下文切换 (ContextSwitch) 是一种将 CPU 资源从一个进程分配给另一个进程的机制。从用户角度看，计算机能够并行运行多个进程，这恰恰是操作系统通过快速上下文切换造成的结果。在切换的过程中，操作系统需要先存储当前进程的状态 ( 包括内存空间的指针，当前执行完的指令等等) ，再读入下一个进程的状态，然后执行此进程。
进程有哪些状态？
当一个进程开始运行时，它可能会经历下面这几种状态：
上图中各个状态的意义：
运行状态（Runing ）：该时刻进程占用 CPU ；
就绪状态（Ready ）：可运行，由于其他进程处于运行状态而暂时停止运行；
阻塞状态（Blocked ）：该进程正在等待某一事件发生（如等待输入/ 输出操作的完成）而暂时停止运行，这时，即使给它CPU 控制权，它也无法运行；
当然，进程还有另外两个基本状态：
创建状态（n ew ）：进程正在被创建时的状态；
结束状态（Exit ）：进程正在从系统中消失时的状态；
什么是僵尸进程？
僵尸进程是已完成且处于终止状态，但在进程表中却仍然存在的进程。
僵尸进程一般发生有父子关系的进程中，一个子进程的进程描述符在子进程退出时不会释放，只有当父进程通过 wait() 或 waitpid() 获取了子进程信息后才会释放。如果子进程退出，而父进程并没有调用
wait() 或 waitpid() ，那么子进程的进程描述符仍然保存在系统中。
什么是孤儿进程？
一个父进程退出，而它的一个或多个子进程还在运行，那么这些子进程将成为孤儿进程。孤儿进程将被
init 进程 ( 进程 ID 为 1 的进程) 所收养，并由 init 进程对它们完成状态收集工作。因为孤儿进程会被 init 进程收养，所以孤儿进程不会对系统造成危害。
进程有哪些调度算法？
进程调度就是确定某一个时刻CPU 运行哪个进程，常见的进程调度算法有：
先来先服务
非抢占式的调度算法，按照请求的顺序进行调度。有利于长作业，但不利于短作业，因为短作业必须一直等待前面的长作业执行完毕才能执行，而长作业又需要执行很长时间，造成了短作业等待时间过长。
另外，对I /O 密集型进程也不利，因为这种进程每次进行I /O 操作之后又得重新排队。
短作业优先
非抢占式的调度算法，按估计运行时间最短的顺序进行调度。长作业有可能会饿死，处于一直等待短作业执行完毕的状态。因为如果一直有短作业到来，那么长作业永远得不到调度。
优先级调度
为每个进程分配一个优先级，按优先级进行调度。为了防止低优先级的进程永远等不到调度，可以随着时间的推移增加等待进程的优先级。
时间片轮转
将所有就绪进程按 先来先服务的原则排成一个队列，每次调度时，把 CPU 时间分配给队首进程，该进程可以执行一个时间片。当时间片用完时，由计时器发出时钟中断，调度程序便停止该进程的执行，并将它送往就绪队列的末尾，同时继续把 CPU 时间分配给队首的进程。
时间片轮转算法的效率和时间片的大小有很大关系：因为进程切换都要保存进程的信息并且载入新进程的信息，如果时间片太小，会导致进程切换得太频繁，在进程切换上就会花过多时间。 而如果时间片过长，那么实时性就不能得到保证。
最短剩余时间优先
最短作业优先的抢占式版本，按剩余运行时间的顺序进行调度。 当一个新的作业到达时，其整个运行时间与当前进程的剩余时间作比较。如果新的进程需要的时间更少，则挂起当前进程，运行新的进程。
否则新的进程等待。
进程间通信有哪些方式？
管道：管道可以理解成不同进程之间的对白，一方发声，一方接收，声音的介质可是是空气或者电缆，进程之间就可以通过管道，所谓的管道就是内核中的一串缓存，从管道的一端写入数据，就是缓存在了内核里，另一端读取，也是从内核中读取这段数据。
管道可以分为两类：匿名管道和命名管道。匿名管道是单向的，只能在有亲缘关系的进程间通信；
命名管道是双向的，可以实现本机任意两个进程通信。
信号 ： 信号可以理解成一种电报，发送方发送内容，指定接收进程，然后发出特定的软件中断，操作系统接到中断请求后，找到接收进程，通知接收进程处理信号。
比如kill-91050就表示给PID 为1 050 的进程发送SIGKIL信号。Linux 系统中常用信号：
（1 ）SIGHUP ：用户从终端注销，所有已启动进程都将收到该进程。系统缺省状态下对该信号的处理是终止进程。
（2 ）SIGINT ：程序终止信号。程序运行过程中，按Ctrl+C 键将产生该信号。
（3 ）SIGQUIT ：程序退出信号。程序运行过程中，按Ctrl+\ 键将产生该信号。
（4 ）SIGBUS 和SIGSEGV ：进程访问非法地址。
（5 ）SIGFPE ：运算中出现致命错误，如除零操作、数据溢出等。
（6 ）SIGKILL ：用户终止进程执行信号。shell 下执行kill-9 发送该信号。
（7 ）SIGTERM ：结束进程信号。shell 下执行kill 进程p id 发送该信号。
（8 ）SIGALRM ：定时器信号。
（9 ）SIGCLD ：子进程退出信号。如果其父进程没有忽略该信号也没有处理该信号，则子进程退出后将形成僵尸进程。
消息队列：消息队列就是保存在内核中的消息链表，包括Posix 消息队列和SystemV 消息队列。
有足够权限的进程可以向队列中添加消息，被赋予读权限的进程则可以读走队列中的消息。消息队列克服了信号承载信息量少，管道只能承载无格式字节流以及缓冲区大小受限等缺点。
共享内存：共享内存的机制，就是拿出一块虚拟地址空间来，映射到相同的物理内存中。这样这个进程写入的东西，另外的进程⻢上就能看到。共享内存是最快的 IPC 方式，它是针对其他进程间通信方式运行效率低而专门设计的。它往往与其他通信机制，如信号量，配合使用，来实现进程间的同步和通信。
信号量：信号量我们可以理解成红绿灯，红灯行，绿灯停。它本质上是一个整数计数器，可以用来控制多个进程对共享资源的访问。它常作为一种锁机制，防止某进程正在访问共享资源时，其他进程也访问该资源。因此，主要作为进程间以及同一进程内不同线程之间的同步手段。
信号量表示资源的数量，控制信号量的方式有两种原子操作：
一个是P****操作，这个操作会把信号量减去 1 ，相减后如果信号量 <0 ，则表明资源已被占用，进程需阻塞等待；相减后如果信号量 >=0 ，则表明还有资源可使用，进程可正常继续执行。
另一个是V****操作，这个操作会把信号量加上 1 ，相加后如果信号量 <=0 ，则表明当前有阻塞中的进程，于是会将该进程唤醒运行；相加后如果信号量 >0 ，则表明当前没有阻塞中的进程；
P 操作是用在进入共享资源之前，V 操作是用在离开共享资源之后，这两个操作是必须成对出现的。
Socket ：与其他通信机制不同的是，它可用于不同机器间的进程通信。
优缺点：
管道：简单；效率低，容量有限；
消息队列：不及时，写入和读取需要用户态、内核态拷贝。
共享内存区：能够很容易控制容量，速度快，但需要注意不同进程的同步问题。
信号量：不能传递复杂消息，一般用来实现进程间的同步；
信号：它是进程间通信的唯一异步机制。
Socket ：用于不同主机进程间的通信。
进程和线程的联系和区别？
线程和进程的联系：
线程是进程当中的一条执行流程。
同一个进程内多个线程之间可以共享代码段、数据段、打开的文件等资源，但每个线程各自都有一套独立的寄存器和栈，这样可以确保线程的控制流是相对独立的。
线程与进程的比较如下：
调度：进程是资源（包括内存、打开的文件等）分配的单位，线程是 CPU 调度的单位；
资源：进程拥有一个完整的资源平台，而线程只独享必不可少的资源，如寄存器和栈；
拥有资源：线程同样具有就绪、阻塞、执行三种基本状态，同样具有状态之间的转换关系；
系统开销：线程能减少并发执行的时间和空间开销— — 创建或撤销进程时，系统都要为之分配或回收系统资源，如内存空间，I /O 设备等，OS所付出的开销显著大于在创建或撤销线程时的开销，进程切换的开销也远大于线程切换的开销。
线程上下文切换了解吗？
这还得看线程是不是属于同一个进程：
当两个线程不是属于同一个进程，则切换的过程就跟进程上下文切换一样；
当两个线程是属于同一个进程，因为虚拟内存是共享的，所以在切换时，虚拟内存这些资源就保持
不动，只需要切换线程的私有数据、寄存器等不共享的数据；
所以，线程的上下文切换相比进程，开销要小很多。
线程有哪些实现方式？
主要有三种线程的实现方式：
内核态线程实现：在内核空间实现的线程，由内核直接管理直接管理线程。
用户态线程实现：在用户空间实现线程，不需要内核的参与，内核对线程无感知。
混合线程实现：现代操作系统基本都是将两种方式结合起来使用。用户态的执行系统负责进程内部线程在非阻塞时的切换；内核态的操作系统负责阻塞线程的切换。即我们同时实现内核态和用户态线程管理。其中内核态线程数量较少，而用户态线程数量较多。每个内核态线程可以服务一个或多个用户态线程。
线程间如何同步？
同步解决的多线程操作共享资源的问题，目的是不管线程之间的执行如何穿插，最后的结果都是正确的。
我们前面知道线程和进程的关系：线程是进程当中的一条执行流程。所以说下面的一些同步机制不止针对线程，同样也可以针对进程。
临界区：我们把对共享资源访问的程序片段称为临界区，我们希望这段代码是互斥的，保证在某时刻只能被一个线程执行，也就是说一个线程在临界区执行时，其它线程应该被阻止进入临界区。
临界区不仅针对线程，同样针对进程。
临界区同步的一些实现方式：
- 锁
使用加锁操作和解锁操作可以解决并发线程/ 进程的互斥问题。
任何想进入临界区的线程，必须先执行加锁操作。若加锁操作顺利通过，则线程可进入临界区；在完成对临界资源的访问后再执行解锁操作，以释放该临界资源。
加锁和解锁锁住的是什么呢？可以是临界区对象，也可以只是一个简单的互斥量，例如互斥量是0无锁，1表示加锁。
根据锁的实现不同，可以分为忙等待锁和和无忙等待锁。
忙等待锁和就是加锁失败的线程，会不断尝试获取锁，也被称为自旋锁，它会一直占用CPU 。
无忙等待锁就是加锁失败的线程，会进入阻塞状态，放弃CPU ，等待被调度。
- 信号量
信号量是操作系统提供的一种协调共享资源访问的方法。
通常信号量表示资源的数量，对应的变量是一个整型（ sem ）变量。
另外，还有两个原子操作的系统调用函数来控制信号量的，分别是：
P 操作：将 sem 减 1 ，相减后，如果 sem<0 ，则进程/ 线程进入阻塞等待，否则继续，表明 P操作可能会阻塞；
V 操作：将 sem 加 1 ，相加后，如果 sem<=0 ，唤醒一个等待中的进程/ 线程，表明 V 操作不会阻塞；
P 操作是用在进入临界区之前，V 操作是用在离开临界区之后，这两个操作是必须成对出现的。
什么是死锁？
在两个或者多个并发线程中，如果每个线程持有某种资源，而又等待其它线程释放它或它们现在保持着的资源，在未改变这种状态之前都不能向前推进，称这一组线程产生了死锁。通俗的讲就是两个或多个线程无限期的阻塞、相互等待的一种状态。
死锁产生有哪些条件？
死锁产生需要同时满足四个条件：
互斥条件：指线程对己经获取到的资源进行它性使用，即该资源同时只由一个线程占用。如果此时还有其它线程请求获取获取该资源，则请求者只能等待，直至占有资源的线程释放该资源。
请求并持有条件：指一个 线程己经持有了至少一个资源，但又提出了新的资源请求，而新资源己被其它线程占有，所以当前线程会被阻塞，但阻塞 的同时并不释放自己已经获取的资源。
不可剥夺条件：指线程获取到的资源在自己使用完之前不能被其它线程抢占，只有在自己使用完毕后才由自己释放该资源。
环路等待条件：指在发生死锁时，必然存在一个线程— — 资源的环形链，即线程集合 {T0 ，T 1 ，
T2, … … ，T n} 中 T0 正在等待一 T1 占用的资源，T l1 正在等待 T2 用的资源，… … Tn 在等待己被 T0 占用的资源。
如何避免死锁呢？
产生死锁的有四个必要条件：互斥条件、持有并等待条件、不可剥夺条件、环路等待条件。
避免死锁，破坏其中的一个就可以。
消除互斥条件
这个是没法实现，因为很多资源就是只能被一个线程占用，例如锁。
消除请求并持有条件
消除这个条件的办法很简单，就是一个线程一次请求其所需要的所有资源。
消除不可剥夺条件
占用部分资源的线程进一步申请其他资源时，如果申请不到，可以主动释放它占有的资源，这样不可剥夺这个条件就破坏掉了。
消除环路等待条件
可以靠按序申请资源来预防。所谓按序申请，是指资源是有线性顺序的，申请的时候可以先申请资源序号小的，再申请资源序号大的，这样线性化后就不存在环路了。
活锁和饥饿锁了解吗？
饥饿锁：
饥饿锁，这个饥饿指的是资源饥饿，某个线程一直等不到它所需要的资源，从而无法向前推进，就像一个人因为饥饿无法成长。
活锁：
在活锁状态下，处于活锁线程组里的线程状态可以改变，但是整个活锁组的线程无法推进。
活锁可以用两个人过一条很窄的小桥来比喻：为了让对方先过，两个人都往旁边让，但两个人总是让到同一边。这样，虽然两个人的状态一直在变化，但却都无法往前推进。