操作系统

什么是死锁？

王道操作系统P114

死锁是指多个进程因竞争资源而造成一种僵局（互相等待），若无外力作用，这些进程都无法向前推进。

例如，某计算机系统只有一台答应及和一台输入设备，进程P1正占用输入设备，同时又提出使用答应及的请求，但此时打印机正被进程P2所占用，而P2在未释放打印机之前，又提出请求使用正被P1占用着的输入设备。这样两个进程相互无休止地进行下去，均无法继续执行，此时两个进程陷入死锁状态。

• 死锁预防：破坏死锁产生的四个必要条件，只要其中任一条件不成立，死锁就不会发生。

  • 互斥条件：进程要求对锁分配的资源（如打印机）进行排他性控制，即在一段时间内某资源仅为一个进程所占用。此时若有其他进程请求该资源，则请求进程只能等待。

  • 不剥夺条件：进程所获得的资源在未使用完毕之前，不能被其他进程强行夺走，即只能由获得该资源的进程自己来释放（只能是主动释放）。

  • 请求和保持条件：进程已经保持了至少一个资源，但由提出了新的资源请求，而该资源已被其他进程占有，此时请求进程被阻塞，但对自己已获得的资源保持不放。

    为了破坏请求和保持条件，采用预先静态分配方法，即进程在运行前一次申请完它所需要的全部资源，在它的资源未满足前，不把它投入运行。

  • 循环等待条件：存在一种进程资源的循环等待链，链中每一个进程已获得的资源同时被链中下一个进程所请求。

    为了破坏循环等待条件，采用顺序资源分配法。首先给系统中的资源编号，规定每个进程必须按编号递增的顺序请求资源，同类资源一次申请完。

• 死锁避免：银行家算法

• 死锁检测与解除：资源分配图、死锁定理

JAVA中如何确保N个线程可以访问N个资源，但同时又不导致死锁？

https://www.nowcoder.com/questionTerminal/7192c9454277483d8711a7b4237a0bbe

多线程产生死锁需要四个条件，分别是互斥性，保持和请求，不可剥夺性还有要形成闭环，这四个条件缺一不可，只要破坏了其中一个条件就可以破坏死锁，其中最简单的方法就是线程都是以同样的顺序加锁和释放锁，也就是破坏了第四个条件。

怎么理解操作系统里的内存碎片，有什么解决办法？

内存碎片分为：内部碎片和外部碎片。

内部碎片就是已经被分配出去（能明确指出属于哪个进程）却不能被利用的内存空间；

内部碎片是处于区域内部或页面内部的存储块。占有这些区域或页面的进程并不使用这个存储块。而在进程占有这块存储块时，系统无法利用它。直到进程释放它，或进程结束时，系统才有可能利用这个存储块。

单道连续分配只有内部碎片。多道固定连续分配既有内部碎片，又有外部碎片。

外部碎片指的是还没有被分配出去（不属于任何进程），但由于太小了无法分配给申请内存空间的新进程的内存空闲区域。

外部碎片是出于任何已分配区域或页面外部的空闲存储块。这些存储块的总和可以满足当前申请的长度要求，但是由于它们的地址不连续或其他原因，使得系统无法满足当前申请。

使用伙伴系统算法。

王道操作系统P144 连续分配管理方式

固定分区分配是最简单的一种多道程序存储管理方式，它将用户内存空间划分为若干个固定的区域，每个分区只装入一道作业。当程序小于固定分区大小时，也占用了一个完整的内存分区空间，这样分区内部有空间浪费，这种现象称为内部碎片。

动态分区分配不预先将内存划分，而是在进程装入内存时，根据进程的大小动态地建立分区，并使分区的大小正好适合进程的需要。动态分区在开始分配时是很好的，但是之后会导致内存中出现许多小的内存块。随着时间的推移，内存中会产生越来越多的碎片，这些小的内存碎片称为外部碎片。克服外部碎片可以通过紧凑技术来解决。

什么是页式存储？

王道操作系统 P147 非连续分配管理方式

页式存储的好处

非连续分配允许一个程序分散地装入到不相邻的内存分区中。在连续分配管理方式中我们发现，即使内存有超过1GB的空虚空间，但如果没有连续的1GB的空间，需要1GB空间的作业仍然是无法运行的；但如果采用非连续分配管理方式，作业所要求的1GB内存空间可以分散地分配在内存的各个区域，当然，这也需要额外的空间去存储它们（分散区域）的索引，使得非连续分配方式的存储密度低于连续存储方式。

固定分区会产生内部碎片，动态分区会产生外部碎片，这两种技术对内存的利用率都比较低。我们希望内存的使用能尽量避免碎片的产生，这就引入的分页的思想：把主存空间划分为相等且固定的块，块相对较小，作为主存的基本单位。每个进程也以块为单位进行划分，进程在执行时，以块为单位逐个申请主存中的块空间。

分页的方法从形式上看，像分区相等的固定技术，分页管理不会产生外部碎片。但它又有本质的不同点：块的大小相对分区要小很多，而且进程也按照块进行划分，进程运行时按块申请主存可用空间并执行。这样，进程只会在为最后一个不完整的块申请一个主存块空间时，才产生主存碎片，所以尽管会产生内部碎片，但是这种碎片相对于进程来说也是很小的，每个进程平均只产生半个块大小的内部碎片（也是页内碎片）。

基本分页存储管理方式

分页存储管理的逻辑地址结构：页号P、页内偏移量W

页表项：页号P、块号b

页号根据页表查到块号，与页内偏移量拼接，得到物理地址。

基本分段存储管理方式

分段系统中的逻辑地址结构：段号S、段内偏移量W

段表项：段号S、段长C、基址b

段号根据段表查到基址，加上段内偏移量，得到物理地址。

段页式管理方式

段页式系统的逻辑地址结构：段号S、页号P、页内偏移量W

段号根据段表查到页表的起始地址。页号根据页表查到块号，与页内偏移量拼接，得到物理地址。

缺页中断

王道P175 虚拟内存管理

在请求分页系统中，每当所要访问的页面不在内存时，便产生一个缺页中断，请求操作系统将所缺的页调入内存。此时应将缺页的进程阻塞（调页完成唤醒），如果内存中有空闲块，则分配一个块，将要调入的页装入该块，并修改页表中相应页项，若此时内存中没有空闲块，则要淘汰某页（若被淘汰页在内存期间被修改过，则要将其写回外存）。

缺页中断作为中断同样要经历，诸如保护CPU环境、分析中断原因、转入缺页中断处理程序、恢复CPU环境等几个步骤。但与一般的中断相比，它有一下两个明显的区别：

• 在指令执行期间产生和处理中断信号，而非一条指令执行完后，属于内部中断。
• 一条指令在执行期间，可能产生多次缺页中断。

页面置换算法

王道操作系统P176 页面置换算法

• 最佳(OPT)置换算法

  最佳置换算法所选择的被淘汰页面将是以后永不使用的，或者是在最长时间内不再被访问的页面，这样可以保证获得最低的缺页率。

• 先进先出(FIFO)置换算法

  优先淘汰最早进入内存的页面，亦即在内存中驻留时间最久的页面。

  FIFO算法会产生当所分配的物理块数增大而页故障数不增反减的异常现象，称为Belady异常。只有FIFO算法可能出现Belady异常，而LRU和OPT算法永远不会出现Belady异常。

• 最近最久未使用(LRU)置换算法

  它认为过去一段时间内未访问过的页面，在最近的将来可能也不会被访问。该算法未每个页面设置一个访问字段，来记录页面自上次被访问以来所经历的时间，淘汰页面时选择现有页面中值最大的予以淘汰。

• 时钟(CLOCK)置换算法

  又称为最近未用(NRU)算法。给每一帧关联一个附加位，称为使用位。当某一页首次装入主存时，该帧的使用位设置为1；当该页随后再被访问到时，它的使用位也被置为1。当需要替换一页时，操作系统扫描缓冲区，以查找使用位被置为0的一帧。当遇到一个使用位为1的帧时，操作系统就将该位重新置为0。

进程的通信

王道操作系统P32

共享存储、消息传递、管道通信

进程切换和线程切换

王道操作系统P30

对于通常的进程，其创建、撤销以及要求由系统设备完成的I/O操作都是利用系统调用而进入内核，再由内核中相应处理程序予以完成的。进程切换同样是在内核的支持下实现的，因此可以说，任何进程都是在操作系统内核的支持下运行的，是与内核紧密相关的。

进程切换是指处理及由一个进程的运行转到另一个进程上运行，这个过程中，进程的运行环境产生了实质性的变化。进程切换的过程如下：

1. 保存处理机上下文，包括程序计数器和其他寄存器。
2. 更新PCB信息。
3. 把进程的PCB移入相应的队列，如就绪、在某事件阻塞等队列。
4. 选择另一个进程执行，并更新其PCB。
5. 更新内存管理的数据结构。
6. 恢复处理机上下文。

如何理解僵尸进程，如何解决僵尸进程

http://www.nowamagic.net/librarys/veda/detail/1994

僵尸进程是指一个已经终止、但是其父进程尚未对其进行善后处理获取终止进程的有关信息的进程，这个进程被称为“僵尸进程”(zombie)。

kill与kill -9的区别

https://blog.csdn.net/yushouxiang2014/article/details/82876405

默认参数下，kill 发送SIGTERM（15）信号给进程，告诉进程，你需要被关闭，请自行停止运行并退出。

kill -9 发送SIGKILL信号给进程，告诉进程，你被终结了，请立刻退出。

TERM(或数字9）表示“无条件终止”；

因此 kill - 9 表示强制杀死该进程；与SIGTERM相比，这个信号不能被捕获或忽略，同时接收这个信号的进程在收到这个信号时不能执行任何清理。