面试准备-操作系统

参考：

1. 《程序员面试笔试宝典》（何昊、叶向阳）

---

进程是系统进行资源分配和调度的一个独立单位。线程是进程的一个实体，是cpu调度和分配的基本单位。线程基本不拥有系统资源，只拥有必须的，但是同属于一个进程的其他线程可以共享进程所拥有的全部资源。

引入线程的4个优点：1）易于调度2）提高并发性3）开销小4）充分发挥多处理器的功能（每个线程都在一个处理器上运行，有助于并行）

线程与进程的区别？

1）一个线程只能属于一个进程，一个进程可以有多个线程，并且至少有1个

2）属于一个进程的所有线程共享进程的所有资源，不同进程相互独立

3）线程又称为轻量级进程，线程之前切换代价小，进程之间切换代价大

4）进程是程序的一次执行，线程可以理解为程序中一段程序片段的执行

5）每个进程有独立的内存空间，而线程共享其所属进程的内存空间

线程同步机制？

1）临界区：通过对多线程的串行化来访问公共资源或一段代码，速度快，适合控制数据访问

2）互斥量：只有拥有互斥对象的线程才有权限去访问系统的公共资源。因为互斥对象只有一个，所以能保证资源不会被多个线程访问

3）信号量：它允许多个线程在同一个时刻去访问同一个资源，但是会限制同一时刻访问该资源的最大线程数目

4）事件：用来通知线程有一些事件已经发生，从而启动后继任务

内核线程：操作系统内核可感知的线程

用户线程：是在用户程序中实现的线程。unix系统

用户线程的优点：（内核线程的优缺点与之相反、os可以使用混合方式实现线程）

1）可以在不支持线程的os中实现

2）创建和销毁线程、线程切换等线程管理的代价小

3）允许每个进程定制自己的调度算法，线程管理很灵活

4）线程能利用的表空间和堆栈空间比内核线程多

缺点：

1）同一进程中只能同时有一个线程在运行，如果有一个线程使用了系统调用而阻塞，那么整个进程都会被挂起

2）页面失效也会产生类似的问题

内存管理的方式：

1）块式管理：把主存分成一大块一大块的，当所需的程序片段不在主存时就分配一块主存空间，将程序片段load入。这样易于管理但是浪费空间

2）页式管理：把主存分成一页一页（比块式小），提高空间利用率

3）段式管理：把主存分段（比页小），这样提高空间利用率但是一个程序片段可能会分成几十段，导致计算每段的物理地址时浪费时间

4）段页式管理：先把主存分成若干段，每段再分页。段页式管理没取一次数据，要访问3次内存

分段和分页的区别：

1）页是信息的物理单位，分页是出于管理系统的需要；段是信息的逻辑单位，它含有一组意义相对完整的信息，分段是出于用户需要。

2）页的大小固定且由系统确定，将逻辑地址分为页号和页内地址两部分，是由机器硬件实现的。段的长度不固定，取决于用户编写的程序，通常由编译程序在对源程序进行编译时，根据信息的性质来划分。

3）分页的作业地址空间是单一的线性空间，分段的作业地址空间是二维的，需要给出段名+段内地址

虚拟内存：它使得应用程序认为它拥有一个连续完整的地址空间，允许程序员编写并运行比实际系统拥有的内存大得多的程序。实际上，它通常被分割成多个物理内存碎片，还有部分暂时存储在外部磁盘上，在需要时进行数据交换。

虚拟内存比实存的好处：

1）扩大地址空间：寻址空间比实际大

2）内存保护：每个进程运行在各自的虚拟内存地址空间，互不干扰。虚存还对特定的内存地址提供写保护，防止代码或数据被恶意篡改

3）公平分配内存：每个进程相当于有同样大小的虚存空间

4）当进程需要通信时，可采用虚存共享的方式实现

坏处：

1）虚存管理需要建立很多数据结构，而数据结构要占用额外的内存

2）虚拟地址到物理地址的转换，增加了指令的执行时间

3）页面的换入换出需要磁盘IO，耗时

4）如果一页中只有一部分数据，会浪费内存

内存碎片：是由多次进行内存分配造成的。很多空白段因为太小，不能满足用户需求而被放弃，这些小的空白段就是碎片

内碎片：是处于区域内部或页面内部的存储块，占用这些区域的进程不使用这个存储块，系统页因为进程在占有，无法使用，需要等到进程释放或结束。

外碎片：一些不属于任何进程的、因为太小且地址不连续导致系统无法分配给其他进程的空闲存储块。一般处于已分配区域或页面外部

一种特定的内存分配算法，很难同时解决内碎片和外碎片问题，只能根据应用特点进行取舍。

虚拟地址：是指由程序产生的、由段选择符和段内偏移地址组成的地址。不能直接访问物理内存，需要通过分段地址的变换处理才行

物理地址：是指现在CPU外部地址总线上的寻址物理内存的地址信号，是地址变换的最终结果

逻辑地址：是由程序产生的段内偏移地址。有时候直接把逻辑地址当成虚拟地址

线性地址：是指虚拟地址到物理地址变换之间的中间层，是处理器可寻址的内存空间（即线性地址空间）中的地址。如果启用了分页机制，线性地址再变换就产生物理地址，否则线性地址就是物理地址。

不同的逻辑地址可以映射到同一个线性地址上，不同的线性地址页可以映射到同一个物理地址上。

cache的替换算法：

1）随机算法RAND：随机产生一个要替换的块号，替换出去。优点：简单、容易实现、没有使用”历史经验“，因此不能提高cache命中率（正好读到有用的信息=命中）

2）先进先出FIFO：将最早进入Cache的子块替换。优点：容易实现，系统开销小；缺点：可以替换掉早来但常用的程序块，页不能提高命中率

3）最近最久未使用算法LRU：least recently used，字面意思，但也不能保证过去不常用的未来也不常用，而且实现复杂，开销大。常用的方法有：计数器法、寄存器栈法、硬件逻辑比较对法

4）最优替换算法OPT：OPTimal replacement。要实现的话是先让程序跑一遍，记录下实际的页地址流情况，根据这个找出它需要替换的页面。但这是理想型算法，可以作为评估标准，哪个的命中率与其相近就是好的

5）最近最少使用LFU：least frequently used 选择近期最少最少访问的页面作为被替换的页面。需要为每个页面设置一个很长的计数器，并且选择一个固定的时钟为每个计数器计数，在选择时，要从所有计数器中找到计数值最大的计数器。实现复杂

库函数调用是语言或者应用程序的一部分，运行在用户空间（如c库的system malloc）。系统调用是os的一部分，是在内核空间执行的，因此调用时需要把上下文环境切换到内核模式（如chdir write）。

静态链接是把要调用的函数直接链接到可执行文件中，所以一个exe文件会包含所需的所有代码。而动态链接没有拷贝所需代码，只写了所调用函数的描述信息，只有当应用程序被装入内存开始运行时，才会在应用程序和动态链接库（dll, dynamic link library）之间建立链接，os才能去执行dll中对应的代码。所以前者的exe可以拷贝到别的机子运行，后者未必可以，因为要保证dll存在+版本正确。

静态链接库：.lib （不能包含其他dll或lib）

动态链接库：.dll（能包含其他dll或lib）

核心态与用户态：当CPU处于核心态时，可以随时进入用户态；当CPU处于用户态时，只有系统调用和中断时才能切换到核心态。一般程序一开始都是运行于用户态，当程序需要使用系统资源时，就通过调用软中断进入核心态。

运行在核心态的程序可以访问的资源多，但是可靠性、安全性要求高，管理和维护比较复杂；用户态程序访问的资源有限，但是要求低，维护简单。

核心态实现的功能：CPU管理和内存管理、诊断和测试程序、输入输出管理、文件系统本身的管理。但用户数据的管理、编译器、网络管理的部分功能等都可以放在用户态。

内核在创建进程时，会为进程创建相应的堆栈。每个进程都有一个用户栈，存在于用户空间，一个内核栈，存在于内核空间。当进程在用户空间运行时，CPU堆栈指针寄存器里面的内容都是用户堆栈的地址；否则是内核栈空间地址。当进程陷入内核态时，进程所用的堆栈要从用户栈转到内核栈。此时先把用户态堆栈的地址保存在内核栈中（此时内核栈总是空的），然后将寄存器内容改为内核栈的地址。恢复到用户态时，直接恢复之前保存的用户栈地址。