常见的操作系统的面试问题

发布于 | 分类： .
字数统计

知乎专栏： https://zhuanlan.zhihu.com/p/23755202?refer=passer

1. 请分别简单说一说进程和线程以及它们的区别。参考

进程和线程的主要的区别就是它们是不同的操作系统的资源管理方式。

进程有自己独立的地址空间，有自己的资源，是持有资源的最小单位。一个进程崩溃后，由于系统的保护机制，不会影响到其他的进程。

线程有自己的堆栈和局部变量，但是线程没有独立的地址空间，一个线程崩溃了，就回导致他所在的进程也崩溃。

多进程的程序的健壮性比多线程的程序好，但是在进行进程的切换的时候，耗费的资源比较多，效率也更差一些。

但是，对于一些要求同时进行并且又要共享某些变量的并发操作，只能用线程，不能用进程。

可以这样总结：

  1. 一个程序至少要有一个进程，一个进程至少要有一个线程。
  2. 线程的划分尺度小于进程，使得多线程程序并发性高。
  3. 进程在执行过程中有独立的内存单元，但是多核线程共享进程的内存，极大地提高了程序的运行效率。
  4. 运行过程中的区别，每个独立的线程有一个程序运行入口，但是线程不能独立的执行，必须依存在动态程序中，由应用程序提供多个线程执行控制。
  5. 从逻辑角度来看，多线程的意义在于一个应用程序中，有多个执行部分可以同时执行。但操作系统并没有将多个线程看做多个独立的应用，来实现进程的调度和管理以及资源分配。这就是进程和线程的重要区别。
2. 线程同步的方式方式主要有哪些？参考

参考： http://blog.sina.com.cn/s/blog_5e3604840100ddgm.html

通常分为四种方式：

  1. 临界区

    在访问同一个资源的时候，可以使用临界区对象。临界区是一个访问共享资源的程序片段，这些共用的资源有无法被多个线程同时访问。当有线程进入临界区段时，其他的线程或者进程必须等待。

使用方式：

  1. 定义临界区对象CcriticalSection g_CriticalSection;
  2. 在访问共享资源（代码或变量）之前，先获得临界区对象，g_CriticalSection.Lock（）；
  3. 访问共享资源后，则放弃临界区对象，g_CriticalSection.Unlock（）；

  1. 事件

    事件机制，则允许一个线程在处理完一个任务后，主动唤醒另外一个线程执行任务。比如在某些网络应用程序中，一个线程如A负责侦听通信端口，另外一个线程B负责更新用户数据，利用事件机制，则线程A可以通知线程B何时更新用户数据。每个Cevent对象可以有两种状态：有信号状态和无信号状态。Cevent类对象有两种类型：人工事件和自动事件。
    自动事件对象，在被至少一个线程释放后自动返回到无信号状态；

  2. 互斥量

    采用互斥对象机制。 只有拥有互斥对象的线程才有访问公共资源的权限，因为互斥对象只有一个，所以能保证公共资源不会同时被多个线程访问。

    互斥不仅能实现同一应用程序的公共资源安全共享，还能实现不同应用程序的公共资源安全共享 .互斥量比临界区复杂。因为使用互斥不仅仅能够在同一应用程序不同线程中实现资源的安全共享，而且可以在不同应用程序的线程之间实现对资源的安全共享。

什么是线程的互斥？

实指对共享资源的约束访问。多线程环境中，某些资源只允许一个线程使用，这类资源成为临界资源，线程之间的关系就表现为互斥的。

什么是线程的同步？

指多线程通过特定的手段（如互斥量）来控制线程之间的执行顺序。

  1. 信号量

信号量机制即利用pv操作来对信号量进行处理。

什么是信号量？

信号量（semaphore）的数据结构为一个值和一个指针，指针指向等待该信号量的下一个进程。信号量的值与相应资源的使用情况有关。

  • 当它的值大于0时，表示当前可用资源的数量；
  • 当它的值小于0时，其绝对值表示等待使用该资源的进程个数。

注意，信号量的值仅能由PV操作来改变。

3. 进程之间的通信方式主要有哪些？参考
什么是进程间的互斥？

进程互斥是进程之间的间接制约关系。当一个进程进入临界区使用临界资源时，另一个进程必须等待。只有当使用临界资源的进程退出临界区后，这个进程才会解除阻塞状态。

举个例子，就是打印机的例子：比如进程B需要访问打印机，但此时进程A占有了打印机，进程B会被阻塞，直到进程A释放了打印机资源,进程B才可以继续执行。

什么是进程间的同步？

进程同步也是进程之间直接的制约关系，是为完成某种任务而建立的两个或多个线程，这个线程需要在某些位置上协调他们的工作次序而等待、传递信息所产生的制约关系。进程间的直接制约关系来源于他们之间的合作。（其实和线程的同步类似，也是在控制执行的顺序）

4. 什么是缓冲区溢出，可能是因为什么造成的，有什么危害？参考

先介绍下数据在计算机中是怎样存储的：

进程地址中间分布

为什么会出现缓冲区溢出？

因为按照冯·诺依曼存储程序原理，程序代码是作为二进制数据存储在内存的，同样程序的数据也在内存中，因此直接从内存的二进制形式上是无法区分哪些是数据哪些是代码的，这也为缓冲区溢出攻击提供了可能。

代码存储了用户程序的所有可执行代码，在程序正常执行的情况下，程序计数器（PC指针）只会在代码段和操作系统地址空间（内核态）内寻址。数据段内存储了用户程序的全局变量，文字池等。栈空间存储了用户程序的函数栈帧（包括参数、局部数据等），实现函数调用机制，它的数据增长方向是低地址方向。堆空间存储了程序运行时动态申请的内存数据等，数据增长方向是高地址方向。除了代码段和受操作系统保护的数据区域，其他的内存区域都可能作为缓冲区，因此缓冲区溢出的位置可能在数据段，也可能在堆、栈段。如果程序的代码有软件漏洞，恶意程序会“教唆”程序计数器从上述缓冲区内取指，执行恶意程序提供的数据代码！本文分析并实现栈溢出攻击方式。

栈溢出攻击方式

栈的主要功能是实现函数的调用。因此在介绍栈溢出原理之前，需要弄清函数调用时栈空间发生了怎样的变化。每次函数调用时，系统会把函数的返回地址（函数调用指令后紧跟指令的地址），一些关键的寄存器值保存在栈内，函数的实际参数和局部变量（包括数据、结构体、对象等）也会保存在栈内。这些数据统称为函数调用的栈帧，而且是每次函数调用都会有个独立的栈帧，这也为递归函数的实现提供了可能。

看看栈：

函数栈帧

如图所示，我们定义了一个简单的函数function，它接受一个整形参数，做一次乘法操作并返回。当调用function(0)时，arg参数记录了值0入栈，并将call function指令下一条指令的地址0x00bd16f0保存到栈内，然后跳转到function函数内部执行。每个函数定义都会有函数头和函数尾代码，如图绿框表示。因为函数内需要用ebp保存函数栈帧基址，因此先保存ebp原来的值到栈内，然后将栈指针esp内容保存到ebp。函数返回前需要做相反的操作——将esp指针恢复，并弹出ebp。这样，函数内正常情况下无论怎样使用栈，都不会使栈失去平衡。

sub esp,44h指令为局部变量开辟了栈空间，比如ret变量的位置。理论上，function只需要再开辟4字节空间保存ret即可，但是编译器开辟了更多的空间（这个问题很诡异，你觉得呢？）。函数调用结束返回后，函数栈帧恢复到保存参数0时的状态，为了保持栈帧平衡，需要恢复esp的内容，使用add esp,4将压入的参数弹出。

之所以会有缓冲区溢出的可能，主要是因为栈空间内保存了函数的返回地址。该地址保存了函数调用结束后后续执行的指令的位置，对于计算机安全来说，该信息是很敏感的。如果有人恶意修改了这个返回地址，并使该返回地址指向了一个新的代码位置，程序便能从其它位置继续执行。

下面是一个简单的小例子：

1
2
3
4
5
void fun(unsigned char *data)
{
    unsigned char buffer[BUF_LEN];
    strcpy((char*)buffer,(char*)data);//溢出点
}

这个函数没有做什么有“意义”的事情（这里主要是为了简化问题），但是它是一个典型的栈溢出代码。在使用不安全的strcpy库函数时，系统会盲目地将data的全部数据拷贝到buffer指向的内存区域。buffer的长度是有限的，一旦data的数据长度超过BUF_LEN，便会产生缓冲区溢出。

缓冲区溢出示例

由于栈是低地址方向增长的，因此局部数组buffer的指针在缓冲区的下方。当把data的数据拷贝到buffer内时，超过缓冲区区域的高地址部分数据会“淹没”原本的其他栈帧数据，根据淹没数据的内容不同，可能会有产生以下情况：

  1. 淹没了其他的局部变量。如果被淹没的局部变量是条件变量，那么可能会改变函数原本的执行流程。这种方式可以用于破解简单的软件验证。
  2. 淹没了ebp的值。修改了函数执行结束后要恢复的栈指针，将会导致栈帧失去平衡。
  3. 淹没了返回地址。这是栈溢出原理的核心所在，通过淹没的方式修改函数的返回地址，使程序代码执行“意外”的流程！
  4. 淹没参数变量。修改函数的参数变量也可能改变当前函数的执行结果和流程。
  5. 淹没上级函数的栈帧，情况与上述4点类似，只不过影响的是上级函数的执行。当然这里的前提是保证函数能正常返回，即函数地址不能被随意修改（这可能很麻烦！）。

如果在data本身的数据内就保存了一系列的指令的二进制代码，一旦栈溢出修改了函数的返回地址，并将该地址指向这段二进制代码的其实位置，那么就完成了基本的溢出攻击行为。

5. 什么是死锁，死锁出现的四个必要条件是什么？参考
什么是死锁？

死锁是指是指两个或两个以上的进程在执行过程中，由于竞争资源或者由于彼此通信而造成的一种阻塞的现象，若无外力作用，它们都将无法推进下去。此时称系统处于死锁状态或系统产生了死锁，这些永远在互相等待的进程称为死锁进程。（解释来自百度百科）

造成死锁的四个必要条件都是啥？
  1. 互斥条件。一个资源每次只能被一个进程使用。
  2. 请求与保持。一个进程因为请求其他资源请求不到，并且对已获得的资源保持不放。
  3. 非抢占。进程已经占有的资源，在执行完主动释放之前，不能被抢占或者剥夺。
  4. 循环等待。若干的进程因为资源分配形成了一种头尾相接的循环等待的资源的关系。
    锁的分类
    这一部分可以参考给的参考链接，个人觉得数据库中的死锁不是我想在这里讨论的内容。等以后或专门写篇博文讨论
6. 进程有哪几种状态？这几种状态之间互相转换的条件是什么？ 参考1

参考2
进程有三种基本的状态，分别是

  1. 就绪状态(ready)：当进程已经分配到除CPU以外的所有的必要资源，只要获得处理机就能立即执行，这时的状态成为就绪状态。在一个系统中处于就绪状态的进程可能有很多个，通常将它们排成一个队列，成为就绪队列。
  2. 执行状态：这种状态下，进程已经获得了CPU，其程序正在执行。在单处理机系统中，只有一个进程处于执行状态。在多处理机系统中，可能有多个进程处于执行状态。
  3. 阻塞状态：正在执行的进程由于发生某事件而暂时无法继续执行时，便放弃处理机而处于暂停状态，亦即进程的执行受到阻塞，把这种暂停状态称为阻塞状态，有时也称为等待状态或封锁状态。致使进程阻塞的典型事件有：请求I/O，申请缓冲空间等。通常将这种处于阻塞状态的进程也排成一个队列。有的系统则根据阻塞原因的不同而把处于阻塞状态的进程排成多个队列。
那三种状态之间是怎样转换的呢？

先看一张图：

进程状态之间的转换

一个进程在运行期间，不断地从一种状态转换到另一种状态，它可以多次处于就绪状态和执行状态，也可以多次处于阻塞状态。图3_4描述了进程的三种基本状态及其转换。

  1. 就绪→执行

    处于就绪状态的进程，当进程调度程序为之分配了处理机后，该进程便由就绪状态转变 成执行状态。

  2. 执行→就绪

    处于执行状态的进程在其执行过程中，因分配给它的一个时间片已用完而不得不让出处理机，于是进程从执行状态转变成就绪状态。

  3. 执行→阻塞

    正在执行的进程因等待某种事件发生而无法继续执行时，便从执行状态变成阻塞状态。

  4. 阻塞→就绪

    处于阻塞状态的进程，若其等待的事件已经发生，于是进程由阻塞状态转变为就绪状态。

    总之不会发生直接从就绪状态到阻塞状态，也不会发生从直接从阻塞状态到执行状态。

挂起状态：

在不少系统中进程只有上述三种状态，但在另一些系统中，又增加了一些新状态，最重要的是挂起状态。引入挂起状态的原因有：

  • (1) 终端用户的请求。当终端用户在自己的程序运行期间发现有可疑问题时，希望暂时使自己的程序静止下来。亦即，使正在执行的进程暂停执行；若此时用户进程正处于就绪状态而未执行，则该进程暂不接受调度，以便用户研究其执行情况或对程序进行修改。我们把这种静止状态称为挂起状态。

  • (2) 父进程请求。有时父进程希望挂起自己的某个子进程，以便考查和修改该子进程，或者协调各子进程间的活动。

  • (3) 负荷调节的需要。当实时系统中的工作负荷较重，已可能影响到对实时任务的控制时，可由系统把一些不重要的进程挂起，以保证系统能正常运行。

  • (4) 操作系统的需要。操作系统有时希望挂起某些进程，以便检查运行中的资源使用情况或进行记账。

加入挂起状态之后的状态转换图

延伸：如何创建进程和终止进程
  1. 首先要为一个新进程创建PCB(进程管理块),并且填写必要的管理信息。
  2. 把该进程转入就绪状态并插入就绪队列之中。当一个新进程被创建时，系统已为其分配了PCB，填写了进程标识等信息，但由于该进程所必需的资源或其它信息，如主存资源尚未分配等，一般而言，此时的进程已拥有了自己PCB，但进程自身还未进入主存，即创建工作尚未完成，进程还不能被调度运行，其所处的状态就是创建状态。 引入创建状态，是为了保证进程的调度必须在创建工作完成后进行，以确保对进程控制块操作的完整性。同时，创建状态的引入，也增加了管理的灵活性，操作系统可以根据系统性能或主存容量的限制，推迟创建状态进程的提交。对于处于创建状态的进程，获得了其所必需的资源，以及对其PCB初始化工作完成后，进程状态便可由创建状态转入就绪状态。

终止进程：

等待操作系统进行善后处理，然后将其PCB清零，并将PCB空间返还系统。当一个进程到达了自然结束点，或是出现了无法克服的错误，或是被操作系统所终结，或是被其他有终止权的进程所终结，它将进入终止状态。进入终止态的进程以后不能再执行，但在操作系统中依然保留一个记录，其中保存状态码和一些计时统计数据，供其它进程收集。一旦其它进程完成了对终止状态进程的信息提取之后，操作系统将删除该进程。

增加了创建状态和终止状态后，进程的三种基本状态及转换图衍变为五种状态及转换关系图：

进程状态之间的转化

  1. 分段和分页有什么区别？各自的工作原理？ 参考
8. 操作系统中的常见的调度策略有哪些？ 参考
  1. 先来先服务调度算法。
  2. 段作业（进程）优先算法。
  3. 优先级调度算法，包括抢占式的和非抢占式的。
  4. 高响应比优先调度算法。
  5. 时间片轮转法，也叫时间片轮询。
  6. 多级反馈队列调度算法。
9. 死锁的解决办法。很大的一块，从产生死锁的四个条件入手，其中还有一些很经典的算法，比如银行家算法，哲学家算法等等。参考

从造成死锁的四个条件入手，只要破坏了其中的一个，死锁就不会形成。

  1. 预防死锁。
  • 资源一次性分配：（破坏请求和保持条件）
  • 可剥夺资源：即当某进程新的资源未满足时，释放已占有的资源（破坏不可剥夺条件）
  • 资源有序分配法：系统给每类资源赋予一个编号，每一个进程按编号递增的顺序请求资源，释放则相反（破坏循环等待条件）
  1. 检测死锁：
    首先为每个进程和每个资源指定一个唯一的号码；然后建立资源分配表和进程等待表。

  2. 接触死锁。

    当发现有进程死锁后，便应立即把它从死锁状态中解脱出来，常采用的方法有：

  • 剥夺资源：从其它进程剥夺足够数量的资源给死锁进程，以解除死锁状态；
  • 撤消进程：可以直接撤消死锁进程或撤消代价最小的进程，直至有足够的资源可用，死锁状态.消除为止；所谓代价是指优先级、运行代价、进程的重要性和价值等。
算法推荐 之银行家算法

　　在避免死锁的方法中，允许进程动态地申请资源，但系统在进行资源分配之前，应先计算此次资源分配的安全性。若此次分配不会导致系统进入不安全状态，则将资源分配给进程；否则，令进程等待。

　 虽然并非所有的不安全状态都必然会转为死锁状态，但当系统进入不安全状态后，便有可能进而进入死锁状态；反之，只要系统处于安全状态，系统便可避免进入死锁状态。因此，避免死锁的实质在于：系统在进行资源分配时，如何使系统不进入不安全状态。

死锁状态一定是不安全的状态，但是不安全状态不一定是死锁状态。　

银行家算法中的数据结构：

  • 　　(1) 可利用资源向量Available。这是一个含有m个元素的数组，其中的每一个元素代表一类可利用的资源数目，其初始值是系统中所配置的该类全部可用资源的数目，其数值随该类资源的分配和回收而动态地改变。如果Available[j]=K，则表示系统中现有Rj类资源K个。
  • 　　(2) 最大需求矩阵Max。这是一个n×m的矩阵，它定义了系统中n个进程中的每一个进程对m类资源的最大需求。如果Max[i,j]=K，则表示进程i需要Rj类资源的最大数目为K。
  • 　 (3) 分配矩阵Allocation。这也是一个n×m的矩阵，它定义了系统中每一类资源当前已分配给每一进程的资源数。如果Allocation[i,j]=K，则表示进程i当前已分得R j类资源的数目为K。
  • 　　(4) 需求矩阵Need。这也是一个n×m的矩阵，用以表示每一个进程尚需的各类资源数。如果Need[i,j]=K，则表示进程i还需要R j类资源K个，方能完成其任务。

上面的三个矩阵的关系：==Need[i, j]=Max[i, j]-Allocation[i, j]==

银行家算法：

　　设Request i是进程Pi的请求向量，如果Request i[j]=K，表示进程P i需要K个R j类型的资源。当P i发出资源请求后，系统按下述步骤进行检查：

  1. 如果Request i[j] ≤ Need[i,j]，便转向步骤(2)；否则认为出错，因为它所需要的资源数已超过它所宣布的最大值。
  2. 如果Request i[j] ≤ Available[j]，便转向步骤(3)；否则，表示尚无足够资源，Pi须等待。
  3. 系统试探着把资源分配给进程P i，并修改下面数据结构中的数值：
  • Available[j]:= Available[j]-Request i[j]；
  • Allocation[i,j]:= Allocation[i,j]+Request i[j]；
  • Need[i,j]:= Need[i,j]-Request i[j]；
  1. 系统执行==安全性算法==，检查此次资源分配后系统是否处于安全状态。若安全，才正式将资源分配给进程Pi，以完成本次分配；否则，将本次的试探分配作废，恢复原来的资源分配状态，让进程Pi等待。

安全性算法：

  1. 　 设置两个向量：
  • 　　① 工作向量Work，它表示系统可提供给进程继续运行所需的各类资源数目，它含有m个元素，在执行安全算法开始时，Work:=Available。
  • 　　② Finish，它表示系统是否有足够的资源分配给进程，使之运行完成。开始时先做Finish[i]:=false；当有足够资源分配给进程时，再令Finish[i]:=true。
  1. 　 从进程集合中找到一个能满足下述条件的进程：
  • 　　① Finish[i]=false；
  • 　　② Need[i,j]≤Work[j]；若找到，执行步骤(3)，否则，执行步骤(4)。

  1. 　 当进程Pi获得资源后，可顺利执行，直至完成，并释放出分配给它的资源，故应执行：
    Work[j]:= Work[j]+Allocation[i,j]；
    Finish[i]:=true；
    go to step （2）；

  2. 　 如果所有进程的Finish[i]=true都满足，则表示系统处于安全状态；否则，系统处于不安全状态。

下面是一个银行家算法的实例。

==晚上回去整理==

算法推荐 之 哲学家算法

问题描述：一圆桌前坐着5位哲学家，两个人中间有一只筷子，桌子中央有面条。哲学家思考问题，当饿了的时候拿起左右两只筷子吃饭，必须拿到两只筷子才能吃饭。上述问题会产生死锁的情况，当5个哲学家都拿起自己右手边的筷子，准备拿左手边的筷子时产生死锁现象。

有三种解决办法：

  • 　　1、添加一个服务生，只有当经过服务生同意之后才能拿筷子，服务生负责避免死锁发生。

  • 　　2、每个哲学家必须确定自己左右手的筷子都可用的时候，才能同时拿起两只筷子进餐，吃完之后同时放下两只筷子。

  • 　　3、规定每个哲学家拿筷子时必须拿序号小的那只，这样最后一位未拿到筷子的哲学家只剩下序号大的那只筷子，不能拿起，剩下的这只筷子就可以被其他哲学家使用，避免了死锁。这种情况不能很好的利用资源。　

Python中对于并发编程，为了避免出现一些潜在的危险，给出的应对方式：
http://python3-cookbook.readthedocs.io/zh_CN/latest/chapters/p12_concurrency.html

  1. Windows下的内存是如何管理的？linux下内存是如何管理的？参考链接： http://blog.csdn.net/youngchang06hpu/article/details/8009947
  2. 描述实时系统的基本特性。
  3. 中断和轮询的特点。
  4. 什么是临界区？如何解决冲突？
  5. Linux文件属性有哪些？（共十位）
  6. 什么是中断？中断时CPU做什么工作？
  7. 你知道操作系统的内容分为几块吗？什么叫做虚拟内存？他和主存的关系如何？内存管理属于操作系统的内容吗？
  8. 线程是否具有相同的堆栈？dll是否有独立的堆栈？（DLL是什么呢？是动态链接库的意思，参考百度百科中的动态链接库，但是它是否有独立的堆栈呢？）