操作系统|操作系统面试（概述）面试|操作系统

操作系统面试（概述）基本特征
并发并发是指宏观上一段时间内运行多个程序，而并行是真正意义上同一时刻同事运行多个程序
并行需要硬件的支持，如多流水线、多核处理器或者分布式系统
操作系统通过引入进程和线程，使得程序能够并发运行
共享共享是指系统中的资源可以被多个并发进程共同使用
共享可以分为互斥共享和同时共享
互斥共享的资源成为临界资源，例如打印机，在同一时刻只能有一个进程进行资源访问，需要使用同步机制保证互斥访问
虚拟虚拟技术把一个物理实体转换为多个逻辑实体
主要有两种虚拟技术：（时间）分复用技术与（空间）分复用技术
多个进程在同一处理器上并发执行使用了（时间）分复用技术，多个进程轮流在一个处理器其上执行一个小的时间片并进行快速切换。
虚拟内存使用了（空间）分复用技术，他将物理内存抽象为地址空间，每个进程都有自己的地址空间。地址空间的页被映射到物理内存，但是不需要全部在物理内存中，当使用到一个没有在物理内存中的页时，使用页面置换算法，将该页置换到内存中。
tips:页面置换算法

最优页面置换算法（OPT）：置换在未来最长时间访问的页面算法实现：
1. 缺页时，计算内存中每个逻辑页面的下一次访问时间
2. 选择未来最长时间不访问的页面
算法特征：
1. 缺页最少，是理想情况
2. 实际系统中无法实现
3. 无法预知每个页面在下次访问前的等待时间
4. 这个算法可以作为置换算法的性能评价依据
实际使用：在模拟器上运行某个程序，并记录每一次的页面访问情况，第二遍运行时使用最优算法。
先进先出（FIFO）页面置换算法：优先置换最早进入内存的页面算法实现：
1. 维护一个记录所有位于内存中的逻辑页面链表
2. 链表元素按驻留在内存的时间排序，链首最长，链尾最短
3. 出现缺页时，替换链首，新页面添加到链尾
算法特征
1. 实现简单
2. 性能较差，调出的页面可能是经常访问的
3. 进程分配物理页面数增加是，缺页并不一定减少（Belady现象）
4. 很少单独使用
tips：Belady现象：当所分配的物理块数增大而页故障数不减反增的异常现象，Belady现象的原因是FIFO算法的置换特征与进程访问内存的动态特征是矛盾的，即被置换的页面并不是进程不会访问的，因而FIFO并不是一个好的置换算法。
最近最久未使用（LRU）算法：选择长时间没有被引用的页面进行置换，如果某些页面长时间未被访问，则他们在将来还可能会长时间不访问。算法实现：
1. 缺页时，计算每个逻辑页面的上一次访问时间
2. 选择上一次使用到当前时间最长的页面
算法特征
最优置换算法的一种近似
LRU算法的可能实现的方法：
1. 页面链表
  1. 系统维护一个按最近一次访问时间排序的页面链表
  2. 链表首节点是最近刚刚访问过的页面
  3. 链表尾节点是最久未被使用的页面
  4. 访问内存是，找到相应页面放在链表首部
  5. 缺页时，替换链表尾部
2. 活动页面栈
  1. 访问页面时，将页号压入栈顶，并将相同页号的弹出
  2. 缺页时，置换栈底的页面
特征：开销比较大
4.时钟置换算法（Clock）：对页面的访问情况进行大致估计数据结构：
1. 在页表项中增加访问未，描述页面在过去一段时间的访问情况
2. 各页面组织成环形链表
3. 指针指向最先调入的页面
算法实现：
1. 访问页面时在页表项纪录页面访问情况
2. 缺页时，从指针出开始顺序查找未被访问的页面进行置换
算法特征：
时钟算法是LRU和FIFO的折中
时钟置换算法的实现：
1. 页面装入内存时，访问位初始化为0
2. 访问页面(读/写）时，访问位置1
3. 缺页时，从指针当前位置顺序检查环形链表
  1. 访问位为0，置换该页
  2. 访问位为1，访问位置0，并移动指针到下一个页面，直到找到可置换的页面
5.时钟算法的改进思路：
减少修改页的缺页处理开销
实现：
1. 在页面中增加修改位，并在访问时进行相应修改
2. 缺页时，修改页面标志位，以跳过有修改的页面
最不常用算法**（Least Frequently Used, LFU）** 基本思路：
缺页时，置换访问次数最少的页面
【操作系统|操作系统面试（概述）】算法实现：
1. 每个页面设置一个访问计数（多位计数）
2. 访问页面时，访问计数加1
3. 缺页时，置换计数最小的页面
算法特征：
1. 算法开销大
2. 开始时频繁使用。但以后不使用的页面很难置换
解决方法：计数定期右移、衰减

异步是指程序不是一次执行完毕，而是走走停停，以不可知的速度前进。
基本功能
1.进程管理进程控制、进程同步、进程管理、死锁处理、处理机调度等
2.内存管理内存分配、内存共享与保护、地址映射、虚拟内存等
3.文件管理文件存储空间的管理、文件目录管理、文件读写管理和保护
4.设备管理完成用户的I/O请求，方便用户使用各种设备，并提高设备的利用率
主要包括缓冲管理、设备分配、设备处理、虚拟设备等
系统调用
如果一个进程在用户态需要使用内核态的功能，就进行系统调用陷入内核，由操作系统代为完成。
[外链图片转存失败(img-I3LWJz27-1562162540111)(https://github.com/CyC2018/CS-Notes/blob/master/notes/pics/tGPV0.png?raw=true)]
inux 的系统调用主要有以下这些：

Task	Commands
进程控制	fork(); exit(); wait();
进程通信	pipe(); shmget(); mmap();
文件操作	open(); read(); write();
设备操作	ioctl(); read(); write();
信息维护	getpid(); alarm(); sleep();
安全	chmod(); umask(); chown();

大内核与微内核
1.大内核大内核是将操作系统功能作为一个紧密结合的整体放到内核。由于各模块共享信息，因此有很高的性能。
2.微内核由于操作系统不断复杂，因此将一部分操作系统功能移出内核，从而降低内核的复杂性。移出的部分根据分层的原则划分成若干服务，相互独立。
在微内核结构下，操作系统被划分成小的、定义良好的模块，只有微内核这一个模块运行在内核态，其余模块运行在用户态。
因为需要频繁地在用户态和核心态之间进行切换，所以会有一定的性能损失
[外链图片转存失败(img-3USZaFtS-1562162540112)(https://github.com/CyC2018/CS-Notes/blob/master/notes/pics/2_14_microkernelArchitecture.jpg?raw=true)]
中断分类
1.外中断由CPU执行指令以外的事件引起，如I/O完成中断，表示设备输入/输出处理已经完成，处理器能够发送下一个输入/输出的请求。此外还有时钟中断、控制台中断等
2.异常由于CPU指令执行的内部事件引起，如非法指令、地址越界、算术溢出等。
3.陷入在用户程序中使用系统调用
存中…(img-3USZaFtS-1562162540112)]
中断分类
1.外中断由CPU执行指令以外的事件引起，如I/O完成中断，表示设备输入/输出处理已经完成，处理器能够发送下一个输入/输出的请求。此外还有时钟中断、控制台中断等
2.异常由于CPU指令执行的内部事件引起，如非法指令、地址越界、算术溢出等。
3.陷入在用户程序中使用系统调用