操作系统面试题

操作系统

字数统计: 4.6k阅读时长: 16 min

 2020/03/12 

操作系统高频题

题目和答案均来自网络，本人只整理和修改了部分内容，如有侵权告知后必删。答案不一定准确，仅供参考。

OS基础

OS四个特征？

参考：OS特征

用户态到内核态的转化原理？

中断。当外围设备完成用户请求的操作后，会向CPU发出相应的中断信号，这时CPU会暂停执行下一条即将要执行的指令转而去执行与中断信号对应的处理程序，如果先前执行的指令是用户态下的程序，那么这个转换的过程自然也就发生了由用户态到内核态的切换。比如硬盘读写操作完成，系统会切换到硬盘读写的中断处理程序中执行后续操作等。
系统调用。这是用户态进程主动要求切换到内核态的一种方式，用户态进程通过系统调用申请使用操作系统提供的服务程序完成工作，比如前例中fork()实际上就是执行了一个创建新进程的系统调用。而系统调用的机制其核心还是使用了操作系统为用户特别开放的一个中断来实现，例如Linux的int 80h中断。
异常。当CPU在执行运行在用户态下的程序时，发生了某些事先不可知的异常，这时会触发由当前运行进程切换到处理此异常的内核相关程序中，也就转到了内核态，比如缺页异常。

中断的作用，中断的实现过程？

中断作用：
- 可以使CPU和外设同时工作，使系统可以及时地响应外部事件
- 可以允许多个外设同时工作，大大提高了CPU的利用率
- 可以使CPU及时处理各种软硬件故障
中断实现：中断处理过程

用户态和内核态的区别？

内核态与用户态是操作系统的两种运行级别,当程序运行在3级特权级时，就可以称之为运行在用户态，因为这是最低特权级，是普通的用户进程运行的特权级，大部分用户直接面对的程序都是运行在用户态；反之，当程序运行在0级特权级时，就可以称之为运行在内核态。运行在用户态下的程序不能直接访问操作系统内核数据结构和程序。当我们在系统中执行一个程序时，大部分时间是运行在用户态下的，在其需要操作系统帮助完成某些它没有权力和能力完成的工作时就会切换到内核态。
这两种状态的主要差别是：处于用户态执行时，进程所能访问的内存空间和对象受到限制，其所处于占有的处理机是可被抢占的；而处于核心态执行中的进程，则能访问所有的内存空间和对象，且所占有的处理机是不允许被抢占的。

执行一个系统调用时，OS发生的过程，越详细越好？

执行用户程序(如:fork)
根据glibc中的函数实现，取得系统调用号并执行int $0x80产生中断。
进行地址空间的转换和堆栈的切换，执行SAVE_ALL。（进行内核模式）
进行中断处理，根据系统调用表调用内核函数。
执行内核函数。
执行RESTORE_ALL并返回用户模式

函数调用和系统调用的区别？

内存管理

内存分区？

固态分区，分区大小固定，但并不一定相同
可变分区，分区大小动态变化，首先适配、最佳适配、最差适配

虚拟内存？使用虚拟内存的优点？什么是虚拟地址空间？

虚拟内存是一种内存管理技术，它会使程序自己认为自己拥有一块很大且连续的内存，然而，这个程序在内存中不是连续的，并且有些还会在磁盘上，在需要时进行数据交换
优点：弥补物理内存大小的不足
缺点：占用一定的硬盘空间，加大了对硬盘的读写
虚拟地址空间是对于一个单一进程的概念，这个进程看到的将是地址从0000开始的整个内存空间。虚拟存储器是一个抽象概念，它为每一个进程提供了一个假象，好像每一个进程都在独占的使用主存。每个进程看到的存储器都是一致的，称为虚拟地址空间。从最低的地址看起：程序代码和数据，堆，共享库，栈，内核虚拟存储器。

缺页中断，页表寻址？

分页存储机制，一个进程对应一个页表，对应很多页。执行进程时并不是所有页装入内存中，部分装入内存，当需要的那页不存在内存中，将发生缺页中断，将需要的那页从外存中调入内存中
页寻址方案

逻辑地址=（页号，页偏移）

物理地址=（帧号，帧偏移）

其中，页偏移=帧偏移

页表Page Table：LA->PA。页表存放的是对应的页号和帧号。由OS建立。页表还会有一些标志位（对应的物理页是否存在、可读、可写等）。
页面置换。OPT，FIFO，LRU，CLOCK，LFU

LRU的实现？

基本思路：双向链表+unordered_map。双向链表：用于O(1)内插入删除；unordered_map：用于O(1)内查询。元素使用一对pair表示key和value。

当需要插入新的数据项的时候，如果新数据命中，则把该节点放到链表头部；如果不存在，则将新数据放在链表头部（若缓存满了，则将链表尾部的节点删除，再插入头部）

// 也可以使用pair<int,int> key_value表示
class LRUNode {
public:
    LRUNode(int pageNumber, int timestamp) : pageNumber(pageNumber), timestamp(timestamp) {}

    int pageNumber;	// key
    int timestamp;	// value
};

// 参考：https://leetcode.com/problems/lru-cache/discuss/46223/O(1)-unordered_map-%2B-list-%2B-splice
class LRUCache {
public:
    LRUCache(int size) : maxSize(size) {}

    int get(int pageNumber){
    	if(cacheMap.find(pageNumber)==cacheMap.end()) return -1;

    	// move to front
    	cacheList.splice(cacheList.begin(),cacheList,cacheList[pageNumber]);
    	return cacheMap[key]->timestamp;
    }

    void put(int pageNumber, int timestamp) {
        if (cacheMap.find(pageNumber) == cacheMap.end()) { // if not in list, add to list head
            if (cacheList.size() == maxSize) {
                cacheMap.erase(cacheList.back().pageNumber);
                cacheList.pop_back();
            }
            cacheList.push_front(LRUNode(pageNumber, timestamp));
            cacheMap[pageNumber] = cacheList.begin();
        } else { // if already in list, move to list head
            cacheMap[pageNumber]->timestamp = timestamp;
            cacheList.splice(cacheList.begin(), cacheList, cacheMap[pageNumber]);
            cacheMap[pageNumber] = cacheList.begin();
        }
    }

private:
    int maxSize;
    std::list<LRUNode> cacheList;
    std::unordered_map<int, std::list<LRUNode>::iterator> cacheMap;
};

参考：LeetCode 146

Linux是如何避免内存碎片的？

在固定式分区分配中, 为将一个用户作业装入内存, 内存分配程序从系统分区表中找出一个能满足作业要求的空闲分区分配给作业, 由于一个作业的大小并不一定与分区大小相等, 因此, 分区中有一部分存储空间浪费掉了. 由此可知, 固定式分区分配中存在内碎片.
在可变式分区分配中, 为把一个作业装入内存, 应按照一定的分配算法从系统中找出一个能满足作业需求的空闲分区分配给作业, 如果这个空闲分区的容量比作业申请的空间容量要大, 则将该分区一分为二, 一部分分配给作业, 剩下的部分仍然留作系统的空闲分区。由此可知，可变式分区分配中存在外碎片.
伙伴系统
依据可移动性组织页，避免内存碎片

伙伴系统相关？

TODO

进程和线程

页和段的区别？

页是信息的物理单位，分页是由于系统管理的需要。段是信息的逻辑单位，分段是为了满足用户的要求。
页的大小固定且由系统决定，段的长度不固定，决定于用户所编写的程序。

什么是进程？

定义：一个具有一定独立功能的程序在一个数据集合上的一次动态执行过程
进程可以认为是程序执行的一个实例，进程是系统进行资源分配的最小单位，且每个进程拥有独立的地址空间；
一个进程无法直接访问另一个进程的变量和数据结构，如果希望去访问另一个进程的资源，需要使用IPC，比如：管道、消息队列等
线程是进程的一个实体，是进程的一条执行路径；比进程更小的独立运行的基本单位，线程也被称为轻量级进程，一个程序至少有一个进程，一个进程至少有一个线程；

进程和作业/程序的区别？

定义：进程是一个具有一定独立功能的程序在一个数据集合上的一次动态执行过程。程序是静态的。
程序是产生进程的基础，进程是程序功能的体现
程序的每次运行构成不同的进程（比如输入数据每次可能不同）
多对多的映射关系：通过多次执行，一个程序可对应多个进程；通过调用关系，一个进程可包括多个程序。
进程有核心态/用户态，进程具有并发性。

进程与线程区别？

进程是资源分配单位，线程是CPU调度单位
进程具有一个完整的资源平台，线程只独享必不可少的资源
线程同样具有就绪、阻塞和执行三种基本状态，同样可以相互转换，同样可以并发执行。
线程能减少并发执行的时间和空间开销：
- 线程创建时间更短（不用创建那么多资源）
- 线程终止时间更短（不用考虑其他资源释放问题）
- 同一进程内线程切换时间更短（各线程拥有同一个页表，切换进程时需要切换页表）
- 同一进程内各线程共享内存、文件资源、代码段、数据段等资源（但也有独立的堆栈、寄存器、PC），可直接进行不通过内核的通信（直接通过内存地址通信）

协程Coroutine是什么？

是一种比线程更加轻量级的存在。正如一个进程可以拥有多个线程一样，一个线程可以拥有多个协程；协程不是被操作系统内核管理，而完全是由程序控制。
协程的完成可以靠yeild关键字（如python等语言）。协程执行过程中，在子程序内部可中断，然后转而执行别的子程序，在适当的时候再返回（如python的next()）来接着执行。从而可以让两个或多个子程序异步执行。
优势：
- 极高的执行效率，因为子程序切换由程序自身控制
- 协程只有一个线程，不需要锁机制

参考：python协程

进程状态转换图？

参考：进程状态变化模型

进程的创建过程？需要哪些函数？需要哪些数据结构?

参考：进程创建加载
linux上创建线程一般使用的是pthread库，实际上linux也给我们提供了创建线程的系统调用，就是clone

孤儿进程和僵尸进程的区别？怎么避免这两类进程？守护进程？

孤儿进程：一个父进程退出，而它的一个或多个子进程还在运行，那么那些子进程将成为孤儿进程。孤儿进程将被init进程(进程号为1)所收养，并由init进程对它们完成状态收集工作。
僵尸进程：如果子进程exit退出，而父进程并没有调用wait或waitpid获取子进程的状态信息，那么子进程的进程描述符等资源仍然保存在系统中。
守护进程：指在后台运行的特殊进程，它独立于控制终端，周期性地执行某种任务或等待处理某些发生的事件。目的是为了避免执行过程中的信息在任何终端上显示并且进程也不会被任何终端所产生的终端信息所打断。

守护进程父进程可以是init进程（比如fork两次），也可以不是。
孤儿进程没有什么危害。

僵尸进程会一直占用进程ID，大量的僵尸进程会使得进程ID不够用，无法创建新的进程。僵尸进程避免：
- 信号机制：子进程退出时向父进程发送SIGCHILD信号，父进程处理SIGCHILD信号。在信号处理函数中调用wait进行处理僵尸进程。
- fork两次：子进程1再产生一个子进程2后立刻退出，这时子进程2变为孤儿进程（主动变孤儿），而通过init进程可以处理僵尸进程。
  
  这种主动的创建孤儿进程，也是一种守护进程！
杀死僵尸进程：
- kill掉其父进程即可，让init进程处理僵尸进程

参考：孤儿进程与僵尸进程

守护进程怎么实现？

定义：指在后台运行的特殊进程，它独立于控制终端，周期性地执行某种任务或等待处理某些发生的事件。目的是为了避免执行过程中的信息在任何终端上显示并且进程也不会被任何终端所产生的终端信息所打断。
启动方式：
- 可以在Linux系统启动时从启动脚本/etc/rc.d中启动
- 可以由作业规划进程crond（本身也是一个守护进程）启动
- 可以通过用户终端shell执行
实现：
- 父进程（shell或者启动进程）执行fork并exit退出
- 为脱离调用会话session，子进程调用setsid函数创建新的会话
- 子进程调用chdir函数，让根目录 ”/” 成为子进程的工作目录
- 子进程调用umask函数，设置进程的umask为0，从而允许读写权限
- 子进程关闭由父进程继承来的文件描述符，需要时再打开

参考：守护进程

线程安全？如何实现？

如果每次运行结果多线程和单线程运行的结果是一样的（确定性+可重现性），就是线程安全的。
线程安全问题都是由全局变量及静态变量引起的。
若每个线程中对全局变量、静态变量只有读操作，而无写操作，一般来说，这个全局变量是线程安全的；若有多个线程同时执行写操作，一般都需要考虑线程同步，否则的话就可能影响线程安全。
对于线程不安全的对象我们可以通过如下方法来实现线程安全:
- 互斥锁
- 非阻塞同步：如果没有其他线程争用共享数据，那操作就成功了；如果共享数据有争用，产生冲突，那就再采取其他措施(最常见的措施就是不断地重试，直到成功为止)
- 线程本地化：为每一个线程创造一个共享变量的副本来（副本之间是无关的）

调度

同步互斥

线程同步的方式？怎么用？

定义：在线程之间通过同步建立起执行顺序的关系。

主要四种方式，临界区、互斥对象、信号量、事件对象；其中临界区和互斥对象主要用于互斥控制，信号量和事件对象主要用于同步控制：

临界区：在任意一个时刻只允许一个线程对共享资源进行访问，在一个线程进入后，其他线程将被挂起。
互斥对象：和临界区很像，只有拥有互斥对象的线程才有访问公共资源的权限，互斥对象只有一个。线程处理完任务后将线程交出。
信号量：允许多个线程在同一时刻访问同一资源，但限制同一时刻线程数目。两个原子操作：
- P()：sem-1。
  
  如果sem<0，阻塞；否则继续。
  
  （P操作类似于获取锁，然后判断后，需要负责一些调度工作）
- V()：sem+1。
  
  如果sem<=0，唤醒一个等待的P（队列中选一个）
  
  （V操作类似于释放锁，然后判断后，需要负责一些调度工作）
事件对象：通过通知操作的方式来保持线程的同步（设置一个bool类型状态值）

参考：Event

递归锁？

互斥锁定义
Mutex可以分为递归锁(recursive mutex)和非递归锁(non-recursive mutex)。可递归锁也可称为可重入锁(reentrant mutex)，非递归锁又叫不可重入锁(non-reentrant mutex)。二者唯一的区别：同一个线程可以多次获取同一个递归锁，不会产生死锁。而如果一个线程多次获取同一个非递归锁，则会产生死锁。