OS 常见面试题目

发表于 | 更新于 | 分类于 | 评论数：

字节对齐

许多计算机系统对基本数据类型的合法地址做出了一些限制，要求某种类型对象的地址必须是某个值K的整数倍，这种对齐能够简化处理器和内存系统之间接口的硬件设计。
比如说一个处理器总是从内存中读取8个字节，那么地址就为8的倍数。
一般是K字节基本对象的地址必须是K的倍数。这就是为什么空类的大小是一个字节！！！因为空类中补充了一个char类型的数据，它不需要对齐！！！

中断和异常

异常和异常是控制流终中的突变，用来相应处理器状态中的某些变化。什么是控制流？控制指令执行的序列。
中断提供了一种方式，使处理器转而去做正常控制流之外的代码。

中断和异常通常被定义为改变处理器执行指令顺序的事件。
中断是异步的，通常是其他硬件（比如IO）设备依照CPU时钟信号随机产生的。
异常是同步的，指令执行时由CPU控制单元产生的，可能是除零。（异常）
Intel x86把同步和异步中断分别称为异常和中断。

用户态进入内核态

  1. 系统调用。
  2. 异常。
  3. 中断。

mutex和信号量，读写锁的区别[5]

mutex和信号量它们都可以用来实现同步操作，而信号量可以大于1，而mutex不能大于1。还有就是信号量可以由不同的进程释放，而mutex只能由获得锁的进程释放。
mutex和读写锁的区别，读写锁的并行性更高，而mutex要不就是加锁，要不就是不加锁。而读写锁可以是读锁，可以是写锁，还可以是不加锁。
自旋锁和mutex的区别，自旋锁在没有获取锁之前，是忙等状态，它只能被持有一小段时间，否则就会影响性能。自旋锁一般用在非抢占式内核中，它们会阻塞中断。
条件量可以和mutex结合使用。
屏障。
可以用mutex实现读写锁。。。具体的思路是，当有人读时，就要阻塞写锁，但是可以加写锁。有人写时，就要阻塞读锁。

动态链接和静态链接的区别

静态链接在编译的时候就把用到的目标模块复制到可执行文件中。
而动态链接在编译的时候，只是链接器复制了一些重定位和符号表信息，使得它们在运行时可以解析对动态链接库中代码和数据的引用。加载器加载程序时，会先加载动态链接器，然后动态链接器通过执行重定位和完成链接。

netstat

netstat监控网络连接，路由表等，网络接口等。
netstat默认打印所有打开的socket连接。
-a, --all展示所有的listening和没有listening的sockets。
-l, --listening，展示所有listening的socket，默认情况下是忽略的。
-p, --program，每一个socket属于哪一个程序和pid。
-n, --numeric，数值展示host，port和用户名。
-t, --tcp
-u, --udp
-r打印路由表。
-i打印网络接口。

lsof

列出打开的文件。

ip

ip address，查看ip地址。
ip link，查看网络设备。

原子操作

原子操作指的是由多步组成的操作，要么执行完所有步骤，要不一步也不执行。

程序和线程

程序是一个存储在硬盘上的可执行文件。
程序的执行实例被称为进程，它是操作系统对一个正在运行的程序的一个抽象。

进程和线程的区别

  1. 进程是资源分配和调度的最小单位，而线程是CPU调度的最小单位。引入线程后，系统并发性更高。
  2. 进程拥有独立的地址空间，若干代码段，数据段，文件，主存以及至少一个线程。
  3. 一个进程内的多个线程共享该进程的所有资源，线程自己拥有很少的资源，比如线程ID，寄存器，线程私有数据，线程栈。
  4. 进程调度需要上下文切换，开销大。
  5. 同一进程内的线程切换，仅交换线程拥有的一小部分资源，效率高。不同进程的线程切换会引发进程调度。
  6. 线程中通常要进行同步操作，当多个线程共享线相同的内存时，需要使用同步操作确保他们看到一致的视图。
  7. 进程之间交换信息要使用进程间通信。
  8. 一个进程结束后所有线程都将终止。
  9. 而一个线程结束通常不会影响其他线程（如果调用了exit就会终止所有线程。）

进程都有哪些资源

寄存器
堆
栈
数据段
代码段
文件描述符
锁
信号

进程都有哪些区域

可执行代码
初始化数据
未初始化数据
堆
栈

进程创建

怎么创建一个进程。调用fork复制进程的数据空间，代码段，堆和栈的副本。现在的fork利用写时复制，这些区域由父进程和子进程共享，内核将它们的访问权限修改为只读，如果父进程和子进程中的任何一个试图修改这些区域，内核只为修改的那篇区域（通常是一页）制作一个副本，原来的页仍是受到保护的，当其他进程试图写入时，内核会检查写进程是不是这个页的唯一属主，如果是，他把这个页标记为对这个进程是可写的。通过使用一个引用计数记录共享相应页的进程数目。

task_struct包含PID，mm_struct（页表），可执行文件的名字，程序计数器等。
调用fork函数时，内核为新进程创建一个各种各样的数据结构，并给他分配一个唯一的PID，为了给这个进程创建虚拟内存，它创建了当前进程的mm_struct，area_struct和页表的副本。他将两个进程中的每个页面都标记为只读，并将两个进程中的area_struct都标记为私有的copy on write。
当fork在新进程返回时，新进程的虚拟内存和调用fork之间进程的虚拟内存相同。当这两个进程中的任意一个进程写操作的时候，COW就会创建新页面。因此，也就为每个进程保持了私有地址空间。

fork和vfork区别，clone

  1. fork采用copy-on-write[4]，而vfork在调用exec之前和父进程共享数据。
  2. fork不对子进程的执行顺序做任何要求，而vfork要求子进程先运行，父进程挂起，知道子进程调用了exec或者exit之后，父进程恢复运行。
  3. clone可以指定要复制的内容。

进程执行

进程，是一个程序的执行实例。
每个进程都由一个进程描述符表示，这个描述符包含有关进程当前状态的信息。当内核暂停一个进程的执行时，它在进程描述符中保存好几个寄存器的内容：

  • 程序计数器和栈指针寄存器
  • 通过寄存器
  • 包含CPU状态信息的处理器控制寄存器
  • 内存管理寄存器。

进程描述符用一个结构体task_struct表示。这个结构体中包含tty_struct，fs_struct，files_struct, mm_struct和signal_struct以及其他更多。

进程状态

进程描述符中的状态域描述了进程当前可能所处的状态，有五种：

  1. 运行状态
  2. 中断
  3. 不可中断
  4. 停止
  5. 僵死状态。

进程切换

为了控制进程的执行，内核必须有能力挂起正在CPU上运行的进程，并恢复以前挂起的某个进程的执行，这种行为被称为进程切换。linux中进程切换的主要内容：

  1. 地址空间。（快表和页表）。
  2. 硬件上下文，寄存器，程序计数器。

进程结束

使用exit，使用return ，使用Exit，进程的最后一个线程调用pthread_exit。
调用abort，进程接收到某些信号，最后一个线程对cancel做出请求。

进程通信

独立进程访问同一个对象的方法。使用共享内存，然后使用信号量，记录锁，或者读写锁进行进行保护。
如何传递一个字符串？使用FIFO？

线程都有哪些资源

私有的：程序计数器，栈空间和寄存器。

线程创建

pthread_create。

线程结束

pthread_exit
cancel
从启动例程返回。

线程同步

互斥量
读写锁
条件变量
屏障

协程

一个进程

死锁

什么是死锁

两个或多个进（线）程在运行过程中相互请求其他进（线）程拥有且不释放的资源，造成所有的进程或者线程都无法继续前进。

产生死锁的原因

  1. 资源竞争。资源类型：可抢占资源，不可抢占资源。
  2. 加锁的顺序不合适。

产生死锁的必要条件

  1. 互斥条件：每个资源是不可共享的。
  2. 请求和保持：进程因请求某个资源而阻塞时，保持已经获得的资源不放。
  3. 不剥夺：进程获得的资源没有使用完前，不能被其他进程强行剥夺，只能由获得资源的进程自己释放。
  4. 循环等待：A等待B，B等待A。

解决死锁的方法

  1. 忽略死锁问题，假设系统永远不死锁。
  2. 保证系统永远不进入死锁状态。
    • 死锁预防
    • 死锁避免
  3. 允许系统进入死锁状态，并且可以从死锁恢复。
    • 死锁检测
    • 死锁恢复

忽略死锁

鸵鸟算法，假设死锁永不发生。死锁在计算机中很少出现，预防死锁的代码调高。

死锁预防（静态资源分配）

对应死锁产生的后三个必要条件。资源的互斥条件不能改变。

  1. 破坏请求和保持条件：资源一次性分配，只要有有一个资源得不到分配，就不给这个进程分资源。资源利用率低，但是容易实现。
  2. 破坏不可剥夺条件：超时放弃已有的锁。
  3. 破坏循环等待条件：对所有资源进行排序，以确定的顺序获得锁。

死锁避免（动态资源分配）

允许进程动态的申请资源，一次申请部分资源。系统在进行资源分配之前，先计算资源分配的安全性，如果此次分配不会导致系统进入不安全状态（可能死锁），就将资源分配给进程。
银行家算法。
n表示进程数据，m表示资源类型。
可用资源向量。
最大需求矩阵。
分配矩阵。
需求矩阵。
当一个进程申请资源时，首先判断它的请求是不是小于avaiable，如果小于，就需要等到。否则，假设将资源分配给这个进程，然后修改相应的数据结构。执行安全性算法。
安全性算法是：

死锁检测

系统进行资源分配后，计算资源的安全性，如果此次分配会导致死锁，就采取恢复措施，否则继续。

死锁恢复

  1. 剥夺资源使系统恢复。
  2. 撤销进程使得系统恢复。

页式内存管理

原理

页框和页面

页框也叫物理块。将物理存储空间划分成大小相等的若干块。大小为2的整数幂，在512字节到8192字节之间。
页面。将进程的逻辑地址空间划分成与物理块大小相同的若干片。
为进程分配内存时，以块为单位将进程的若干页分别装入多个可以不相邻的物理块中。

地址空间

假设进程使用的逻辑空间是线性的，逻辑地址空间的大小是0到2的m次方(m是地址空间的位数）。每个进程使用相同的逻辑空间。!!!注意，页式内存管理的逻辑地址空间和段页式内存管理的逻辑地址空间是不一样。
假设每个页面的大小是2的n次方。逻辑地址空间中的地址是addr，
页号§：addr / 2的n次方。（总共有2的m次方/2的n次方个页）
页内偏移(d)：add % 2的n次方。

页表

  1. 记录进程的逻辑页和主存中物理块的对应关系，实现从页号到物理块的地址映射。
  2. 进程地址空间中的每一页在页表中有一个条目（page table entry, PTE)，指出该逻辑在主存中的物理块号。
  3. 页表存放在主存中，页表的主存地址与页表的长度在PCB中。
  4. 控制寄存器用来存放：
    • 页表基址寄存器：指向页表。
    • 页表长度寄存器：页表长度。

地址转化

  1. 将页表的初始地址和页表长度送入控制寄存器。
  2. 比较PC上的页号是否大于控制寄存器中的页表长度。
  3. 将页号和控制寄存器中的页表起始地址相加，得到页号在页表中的位置。（就相当于一个数据，判断当前要访问的元素下标是否越界，不越界的话，取得地址）。

上述过程是通过硬件完成的。
获得页表在主存中的位置后，将该主存块号乘上页面大小加上PC上的偏移量，得到在主存中的物理地址。

快表和联想寄存器

在地址变换单元中设置的专用缓冲存储器。用来存放页表的一部分。快表的组成：
页号，块号，访问位，状态位。
在查询时，先使用快表进行查询，没有找到时，继续使用主存进行正常的地址变换，直到形成访问主存的绝对地址。
然后将相应的逻辑页号和物理块号，写入快表中状态为为0的一行中。如果没有这样的，就把它写入访问位为0的某一行，同时置状态位和访问位为1。

多级页表

如果一个进程可以访问32位大小的逻辑空间，页的大小为4KB（2的12次方）。那么一个页表需要包含2的32次方/2的12次方=2的20次方个表项，假设一个表项4B，那么需要4MB连续物理空间存储页表。
解决方法，再分页，即多级页表。

页式管理的主存分配

页表是每个进程一张。

段式内存管理

原理

为什么引入段式管理？

  1. 方便编程。
  2. 信息共享。
  3. 信息保护。
  4. 动态增长。
  5. 动态链接。

分段

按照程序自身的逻辑关系将地址空间划分成若干部分。每个段都有自己的名字。每个段都从0开始编制。

每个逻辑地址都分为段号和段内偏移。
段式存储分配以段为单位进行，为作业的每一个分段分配一个连续的主存空间，各段之间可以不连续。

段表

  1. 用于记录进程分段和物理存储空间的对应关系，实现从逻辑分段到物理内存的地址映射。
  2. 每个逻辑分段对应一个table entry，指出该逻辑分段在主存中的起始地址和段的长度。（注意页表中存放的是页号和块号）。
  3. 段表存放于主存。段表的主存起始和段表长度保存在进程控制块中。
  4. 控制寄存器。
    • 段表基址寄存器：指向段表。
    • 段表长度寄存器：段表长度。

段式管理的主存分配

存在外碎片。
分段方法：
首次适应法。
最佳适应法。
最坏适应法。

段式和页式管理的比较

  1. 段是信息的逻辑单位，它是根据用户需要进行划分的。
  2. 页是信息的物理单位，为了管理主存方便，对用户是透明的。
  3. 段的大小不固定，由它的功能确定的。
  4. 页的大小固定，由系统决定。
  5. 段式管理向用户提供的是二维地址空间。
  6. 而页式管理用户提供的是一维地址空间，确定其页号和页内偏移是由机器硬件实现的。
  7. 页式管理产生内碎片
  8. 段式管理产生外碎片。

页面置换算法

  1. 最佳算法。从主存中移除永远不再需要的页面，如果没有这样的页面，选择接下来最长时间不再使用的那个。（需要我们有未卜先知的能力）。
  2. 先进先出。总是替换最先进来的那个。
  3. 最近最少未使用。每次将当前访问的数据放在最前面，当发生未命中的时候，替换最近未使用的那个。
  4. 时钟算法（最近未用）。给每一帧附一个附加位。某一帧第一次被使用的时候，使用位设置为1，下一次如果扫描到它，而不是使用它的话，就把1置换成0。如果现在是0，要使用它，就把它置换为1。

进程调度算法

  1. 先来先服务（FCFS)。非抢占式的，易于实现，效率不高，性能不好，有利于长作业，但是不利于短作业。
  2. 短作业优先（SJF）。可以剥夺，也可以不剥夺。
    每次从作业队列中挑选服务时间最短的作业进行处理。非抢占式的，有限照顾短作业，具有很好的性能，降低平均等待时间，提高吞吐量。但是不利于长作业，长作业出现饥饿状态。不能用于实时系统。
    不剥夺的话，就是最短剩余时间优先。首先按照作业时间最短的作业运行，如果运行时有新的作业到达，并且它的服务时间比当前作业的剩余服务时间短，就发生抢占。抢占式的，因为频繁抢占和进程切换，系统开销大，算法实现代价高，一般用于实时系统。
  3. 高响应比。优先运行运行时间短，等待时间长的进程。非抢占式的，每次选择响应比最高的作业运行。可以避免饥饿。
  4. 优先级调度算法。可以剥夺，也可以非剥夺。为每个进程指定一个优先级。
  5. 时间片轮转法。用于分时系统的进程调度，采用剥夺方式。不利于IO频繁的作业。
  6. 多级队列调度算法。

window和linux都采用基于抢占的优先级调度算法。

IO数据传输的控制方式

  1. 程序查询方式。
  2. 程序中断方式。
  3. 直接存储器访问。
  4. 通道方式。

磁盘调度算法

  1. 先来先服务。容易实现，公平合理。但是完全不考虑队列中各个请求情况，使得磁头频繁移动。
  2. 最短寻道时间优先（SSTF）。在移动磁头时，总是选择移动磁头距离最小的磁道。可能会导致饥饿问题。
  3. 扫描法SCAN和循环扫描法CSCAN。
    SCAN磁头不断的从一端移动到另一端，到头返回。（电梯算法）
    CSCAN，从一端移动到另一端时，立即返回它开始的地方。
  4. 查询法LOOK和循环查询法C-LOOK。
    SCAN和CSCAN都是将磁头从一端移动到另一端。
    而LOOK和CLOOK是移动到最远的请求上的那个磁道，如果前进方向上没有请求，就反向移动。

参考文献

1.《APUE》第三版
2.https://stackoverflow.com/questions/200469/what-is-the-difference-between-a-process-and-a-thread
3.https://www.geeksforgeeks.org/difference-between-process-and-thread/
4.https://www.cnblogs.com/Rofael/archive/2013/04/13/3019153.html
5.https://blog.csdn.net/tt_love9527/article/details/82107549