面试总结-操作系统

操作系统面试总结

操作系统的分页分段

分页存储

• 思想：将程序的逻辑地址空间划分为固定大小的页(page)，而物理内存划分为同样大小的页框(page frame)或物理块，每个物理块的大小一般取2的整数幂。程序加载时，可将任意一页放人内存中任意一个页框，这些页框不必连续，从而实现了离散分配。该方法需要CPU的硬件支持，来实现逻辑地址和物理地址之间的映射。在页式存储管理方式中地址结构由两部构成，前一部分是页号，后一部分为页内地址w（位移量）。
• 逻辑地址道物理地址变化原理：CPU中的内存管理单元(MMU)按逻辑页号通过查进程页表得到物理页框号，将物理页框号与页内地址相加形成物理地址。
• 优点：没有外碎片，提高内存的利用率。一个程序不必连续存放。便于改变程序占用空间的大小(主要指随着程序运行，动态生成的数据增多，所要求的地址空间相应增长)。
• 缺点：无论数据有多少，都只能按照页面大小分配，容易产生内部碎片。无法体现程序逻辑。页长与程序的逻辑大小不相关。不利于编程时的独立性，并给换入换出处理、存储保护和存储共享等操作造成麻烦。 分段存储
• 思想：将用户程序地址空间分成若干个大小不等的段，每段可以定义一组相对完整的逻辑信息。存储分配时，以段为单位，段与段在内存中可以不相邻接，也实现了离散分配。通常，程序员把子程序、操作数和常数等不同类型的数据划分到不同的段中（写c程序时会用到），并且每个程序可以有多个相同类型的段。段表本身也是一个段，可以存在辅存中，但一般是驻留在主存中。 在为某个段分配物理内存时，可以采用首先适配法、下次适配法、最佳适配法等方法。在回收某个段所占用的空间时，要注意将收回的空间与其相邻的空间合并。
• 地址映射: 在分段存储中，整个进程的地址空间是二维的，即其逻辑地址由段号和段内地址两部分组成。
• 优点：分段对程序员可见。段的逻辑独立性使其易于编译、管理、修改和保护，也便于多道程序共享。段长可以根据需要动态改变，允许自由调度，以便有效利用主存空间。方便编程，分段共享，分段保护，动态链接，动态增长。
• 缺点：主存空间分配比较麻烦。外部碎片。由于段长不一定是2的整数次幂，因而不能简单地像分页方式那样用虚拟地址和实存地址的最低若干二进制位作为段内地址，并与段号进行直接拼接，必须用加法操作通过段起址与段内地址的求和运算得到物理地址。

分页存储和分段存储的区别

1. 页是信息的物理单位，分页是为实现离散分配方式，以消减内存的外零头，提高内存的利用率；段则是信息的逻辑单位，它含有一组其意义相对完整的信息，分段的目的是为了能更好地满足用户的需要。
2. 页的大小固定且由系统决定，由系统把逻辑地址划分为页号和页内地址两部分，是由机器硬件实现的，因而在系统中只能有一种大小的页面；而段的长度却不固定，决定于用户所编写的程序，通常由编译程序在对源程序进行编译时，根据信息的性质来划分。
3. 分页的作业地址空间是一维的，即单一的线性地址空间，程序员只需利用一个记忆符，即可表示一个地址；而分段的作业地址空间则是二维的，程序员在标识一个地址是，即需给出段名，又需给出段内地址。
4. 分页信息很难保护和共享、分段存储按逻辑存储所以容易实现对段的保存和共享。

段页存储

程序员按照分段系统的地址结构将地址分为段号与段内位移量，地址变换机构将段内位移量分解为页号和页内位移量。

为实现段页式存储管理，系统应为每个进程设置一个段表，包括每段的段号，该段的页表始址和页表长度。每个段有自己的页表，记录段中的每一页的页号和存放在主存中的物理块

它首先将程序按其逻辑结构划分为若干个大小不等的逻辑段，然后再将每个逻辑段划分为若干个大小相等的逻辑页。主存空间也划分为若干个同样大小的物理页。辅存和主存之间的信息调度以页为基本传送单位，每个程序段对应一个段表，每页对应一个页表。

段页式系统中，作业的地址结构包含三部分的内容：段号，页号，页内位移量

CPU访问时，段表指示每段对应的页表地址，每一段的页表确定页所在的主存空间的位置，最后与页表内地址拼接，确定CPU要访问单元的物理地址。

段页存储管理方式综合了段式管理和页式管理的优点，但需要经过两级查表才能完成地址转换，消耗时间多。

• 过程：检查是否越界。利用段表始址和段号来求出该段所对应的段表项在段表中的位置，得到该段的页表始址。读出该页所在的物理块号b。构建物理地址。
• 优点：提供了大量的虚拟存储空间。有效地利用主存，为组织多道程序运行提供了方便。
• 缺点：增加了硬件成本、系统的复杂性和管理上的开销。存在系统抖动的风险。存在内碎片。各种表占用更多的空间。

Linux自旋锁

线程同步

http://bestmind.space/posts/%E5%B8%B8%E8%A7%81C-%E9%9D%A2%E8%AF%95%E9%A2%98/ 线程同步和线程互斥的区别 线程同步的方式:互斥锁、读写锁(共享-独占锁)、条件变量和信号量

进程间通信

进程间的通信方式 管道、有名管道、信号、共享内存、消息队列、信号量、套接字、文件. (1)管道( pipe )：管道是一种半双工的通信方式，数据只能单向流动，而且只能在具有亲缘关系的进程间使用。 管道是单向的、先进先出的、无结构的、固定大小的字节流，它把一个进程的标准输出和另一个进程的标准输入连接在一起。写进程在管道的尾端写入数据，读进程在管道的首端读出数据。数据读出后将从管道中移走，其它读进程都不能再读到这些数据。分为普通管道、流管道、命名管道。 (2)命名管道(named pipe):命名管道也是半双工的通信方式，它克服了管道没有名字的限制，并且它允许无亲缘关系进程间的通信。命令管道在文件系统中有对应的文件名，命名管道通过命令mkfifo或系统调用mkfifo来创建。 (3)信号:信号是一种比较复杂的通信方式，用于通知接收进程某个事件已经发生。除了用于进程通信外，进程还可以发送信号给进程本身。 (4)消息队列：克服了信号传递信息少、管道只能承载无格式字节流以及缓冲区大小的限制。由消息链表的结构实现。 (5)信号量(semophore):信号量是一个计数器，可以用来控制多个进程对共享资源的访问。它常作为一种锁机制，防止某进程正在访问共享资源时，其他进程也访问该资源。因此，主要作为进程间以及同一进程内不同线程之间的同步手段。 (6)共享内存：映射一段能被其他进程所访问的内存，这段共享内存由一个进程创建，但多个进程都可以访问。共享内存是最快的IPC方式，它是针对其他进程间通信方式运行效率低而专门设计的。它往往与其他通信机制，如信号量配合使用，来实现进程间的同步和通信。 (7)套接字: 与其他通信机制不同的是，它可用于不同机器间的进程通信。但是将通信转移到了应用层。

select、poll、epoll的区别

死锁

指两个或两个以上的进程在执行过程中，由于竞争资源或者由于彼此通信而造成的一种阻塞的现象，若无外力作用，它们都将无法推进下去。

死锁产生的四个必要条件: 互斥条件:一个资源每次只能被一个进程使用 不可剥夺条件:进程已获得的资源，在末使用完之前，不能强行剥夺 请求与保持条件:一个进程因请求资源而阻塞时，对已获得的资源保持不放 循环等待条件:若干进程之间形成一种头尾相接的循环等待资源关系.

死锁避免

银行家算法：检查申请者对资源的最大需求量，如果系统现存的各类资源可以满足申请者的请求，就满足申请者的请求。这样申请者就可很快完成其计算，然后释放它占用的资源，从而保证了系统中的所有进程都能完成，所以可避免死锁的发生。

死锁解除

1) 资源剥夺法。挂起某些死锁进程，并抢占它的资源，将这些资源分配给其他的死锁进程。但应防止被挂起的进程长时间得不到资源，而处于资源匮乏的状态。 2) 撤销进程法。强制撤销部分、甚至全部死锁进程并剥夺这些进程的资源。撤销的原则可以按进程优先级和撤销进程代价的高低进行。 3) 进程回退法。让一（多）个进程回退到足以回避死锁的地步，进程回退时自愿释放资源而不是被剥夺。要求系统保持进程的历史信息，设置还原点。

进程有哪几种状态？

就绪状态：进程已获得除处理机以外的所需资源，等待分配处理机资源； 运行状态：占用处理机资源运行，处于此状态的进程数小于等于CPU数； 阻塞状态： 进程等待某种条件，在条件满足之前无法执行；

操作系统中进程调度策略有哪几种？

FCFS(先来先服务，队列实现，非抢占的)：先请求CPU的进程先分配到CPU

SJF(最短作业优先调度算法)：平均等待时间最短，但难以知道下一个CPU区间长度

优先级调度算法(可以是抢占的，也可以是非抢占的)：优先级越高越先分配到CPU，相同优先级先到先服务，存在的主要问题是：低优先级进程无穷等待CPU，会导致无穷阻塞或饥饿；解决方案：老化

时间片轮转调度算法(可抢占的)：队列中没有进程被分配超过一个时间片的CPU时间，除非它是唯一可运行的进程。如果进程的CPU区间超过了一个时间片，那么该进程就被抢占并放回就绪队列。

多级队列调度算法：将就绪队列分成多个独立的队列，每个队列都有自己的调度算法，队列之间采用固定优先级抢占调度。其中，一个进程根据自身属性被永久地分配到一个队列中。

多级反馈队列调度算法：与多级队列调度算法相比，其允许进程在队列之间移动：若进程使用过多CPU时间，那么它会被转移到更低的优先级队列；在较低优先级队列等待时间过长的进程会被转移到更高优先级队列，以防止饥饿发生。

虚拟内存

为什么有虚拟内存：对于进程而言，逻辑上似乎有很大的内存空间，实际上其中一部分对应物理内存上的一块(称为帧，通常页和帧大小相等)，还有一些没加载在内存中的对应在硬盘上 缺页：如果虚拟内存的页并不存在于物理内存中，会产生缺页中断，从磁盘中取得缺的页放入内存，如果内存已满，还会根据某种算法将磁盘中的页换出。

页面置换算法： FIFO先进先出算法：在操作系统中经常被用到，比如作业调度（主要实现简单，很容易想到）；

LRU（Least recently use）最近最少使用算法：根据使用时间到现在的长短来判断；

LFU（Least frequently use）最少使用次数算法：根据使用次数来判断；

OPT（Optimal replacement）最优置换算法：理论的最优，理论；就是要保证置换出去的是不再被使用的页，或者是在实际内存中最晚使用的算法。

多线程中栈与堆是公有的还是私有的

一般来说栈是私有的，堆是公有的。 但是在多线程中，可以为特定的线程创建私有的堆。

进程是资源分配的最小单位，线程是CPU调度的最小单位

进程是资源分配的基本单位。所有与该进程有关的资源，都被记录在进程控制块PCB中。以表示该进程拥有这些资源或正在使用它们。进程也是抢占处理机的调度单位，它拥有一个完整的虚拟地址空间。当进程发生调度时，不同的进程拥有不同的虚拟地址空间，而同一进程内的不同线程共享同一地址空间。 与进程相对应，线程与资源分配无关，它属于某一个进程，并与进程内的其他线程一起共享进程的资源。 线程只由相关堆栈（系统栈或用户栈）寄存器和线程控制表TCB组成。寄存器可被用来存储线程内的局部变量，但不能存储其他线程的相关变量。 因此一个简单的解释就是：进程拥有PCB，而多个线程共享一个进程的PCB。

进程和线程的区别

进程与线程的一个简单解释 地址空间和其它资源（如打开文件）：进程间相互独立，同一进程的各线程间共享。某进程内的线程在其它进程不可见。 通信：进程间通信IPC，线程间可以直接读写进程数据段（如全局变量）来进行通信——需要进程同步和互斥手段的辅助，以保证数据的一致性。 调度和切换：线程上下文切换比进程上下文切换要快得多。 在多线程OS中，进程不是一个可执行的实体。

进程的基本状态

状态：运行、阻塞、挂起阻塞、就绪、挂起就绪 状态之间的转换： 准备就绪的进程，被CPU调度执行，变成运行态； 运行中的进程，进行I/O请求或者不能得到所请求的资源，变成阻塞态； 运行中的进程，进程执行完毕（或时间片已到），变成就绪态； 将阻塞态的进程挂起，变成挂起阻塞态，当导致进程阻塞的I/O操作在用户重启进程前完成（称之为唤醒），挂起阻塞态变成挂起就绪态，当用户在I/O操作结束之前重启进程，挂起阻塞态变成阻塞态； 将就绪（或运行）中的进程挂起，变成挂起就绪态，当该进程恢复之后，挂起就绪态变成就绪态；

const char * const task_state_array[]

Linux 的启动流程

BIOS->主引导记录->操作系统->加载内核(/boot):载入内核文件->启动初始化进程：运行第一个程序 /sbin/init，初始化系统环境。->确定运行级别:运行这些开机启动的程序。->加载开机启动程序->用户登录->进入 login shell->打开 non-login shell

Linux 的启动流程-阮一峰