![]()
问题一、操作系统的基本特征
1、并发
并发指一段时间内能同时运行多个程序，并行指同一时刻能运行多个指令。操作系统通过引入进程和线程，使得程序能够并发运行。
2、共享
共享是指系统中的资源可以被多个并发进程共同使用。它主要有两种共享方式：互斥共享和同时共享。多个应用并发执行的时候，宏观上要体现出它们在同时访问资源的情况，而微观上要实现它们的互斥访问。比如说我们说到的内存。
3、虚拟
虚拟技术把一个物理实体转换为多个逻辑实体。利用多道程序设计技术(程序的交替运行)，让每个用户都觉得有一个计算机专门为他服务。主要有两种虚拟技术：时间复用技术和空间复用技术。
时间复用技术是指多个进程能在同一个处理器上并发执行，让每个进程轮流占用处理器，每次只执行一小个时间片并快速切换。
空分复用技术值将物理内存抽象为地址空间，每个进程都有各自的地址空间。当需要一个地址空间时，如果没有那就执行页面置换算法。
4、异步
异步指进程不是一次性执行完毕，而是走走停停，以不可知的速度向前推进。但只要运行的环境相同，OS需要保证程序运行的结果也要相同。
问题二、进程与线程的本质区别、以及各自的使用场景(重要)
1、进程
进程是资源分配的基本单位。就好比是手机上的一个个应用程序。
2、线程
线程是独立调度的基本单位。一个进程中可以有多个线程，它们共享进程资源。
3、进程和线程的理解
QQ 和浏览器是两个进程，浏览器进程里面有很多线程，例如 HTTP 请求线程、事件响应线程、渲染线程等等，线程的并发执行使得在浏览器中点击一个新链接从而发起 HTTP 请求时，浏览器还可以响应用户的其它事件。
4、进程和线程的区别
(1)资源分配
进程是资源分配的基本单位，但是线程不拥有资源，多个线程可以共享进程资源。
(2)资源调度
在同一进程中，线程的切换不会引起进程切换，从一个进程中的线程切换到另一个进程中的线程时，会引起进程切换。就好比是打开了QQ，又打开了浏览器。
(3)系统开销
线程不占用系统资源，比进程开销更小效率更高。这是因为创建或撤销进程时，系统都要为之分配或回收资源，如内存空间、I/O 设备等，切换进程时候，还要保存CPU状态。
(4)对于一些要求同时进行而又共享某些变量的并发操作来说，只能用多线程，不能用多进程。
问题三：进程的几种状态
进程主要是三种状态。
(1)就绪。进程已经获得了除CPU以外的所有所需资源，等待分配CPU资源
(2)运行。已获得了CPU资源，进行运行。处于运行态的进程数<=CPU核心数
(3)阻塞。进程等待某些条件，在条件满足前无法执行
![]()
在这里我们最主要的是状态之间的切换，比如说阻塞状态是不能到运行状态的。
问题四：常见的进程同步方式和线程同步方式
1、进程同步的方式
(1)为什么要进程同步
多进程虽然提高了系统资源利用率和吞吐量，但是由于进程的异步性可能造成系统的混乱。进程同步的任务就是对多个相关进程在执行顺序上进行协调，使并发执行的多个进程之间可以有效的共享资源和相互合作，保证程序执行的可再现性。
(2)同步机制需要遵循的原则：
空闲让进：当没有进程处于临界区的时候，应该许可其他进程进入临界区的申请
忙则等待：当前如果有进程处于临界区，如果有其他进程申请进入，则必须等待，保证对临界区的互斥访问
有限等待：对要求访问临界资源的进程，需要在有限时间呃逆进入临界区，防止出现死等
让权等待：当进程无法进入临界区的时候，需要释放处理机，边陷入忙等
(3)进程同步的方式：原子操作、信号量、管程。
2、线程同步方式
(1)互斥(信号)量，每个时刻只有一个线程可以访问公共资源。只有拥有互斥对象的线程才能访问公共资源，互斥对象只有一个，一个时刻只能有一个线程持有，所以保证了公共资源不会被多个线程同时访问。
(2)信号量，允许多个线程同时访问公共资源。当时控制了访问资源的线程的最大个数。
(3)事件 in windows(条件变量 in linux)。通过通知的方式保持多线程的同步，还可以方便的实现多线程优先级的比较
(4)临界区。任意时刻只能有一个线程进入临界区，访问临界资源。
问题五、进程间的通信方式
windows和linux是不一样的。
![]()
问题六、进程任务调度算法的特点以及使用场景
(1)时间片轮转调度算法(RR)：给每个进程固定的执行时间，根据进程到达的先后顺序让进程在单位时间片内执行，执行完成后便调度下一个进程执行，时间片轮转调度不考虑进程等待时间和执行时间，属于抢占式调度。优点是兼顾长短作业;缺点是平均等待时间较长，上下文切换较费时。适用于分时系统。
(2)先来先服务调度算法(FCFS)：根据进程到达的先后顺序执行进程，不考虑等待时间和执行时间，会产生饥饿现象。属于非抢占式调度，优点是公平，实现简单;缺点是不利于短作业。
(3)优先级调度算法(HPF)：在进程等待队列中选择优先级最高的来执行。
(4)多级反馈队列调度算法：将时间片轮转与优先级调度相结合，把进程按优先级分成不同的队列，先按优先级调度，优先级相同的，按时间片轮转。优点是兼顾长短作业，有较好的响应时间，可行性强，适用于各种作业环境。
(5)高响应比优先调度算法：根据“响应比=(进程执行时间+进程等待时间)/ 进程执行时间”这个公式得到的响应比来进行调度。高响应比优先算法在等待时间相同的情况下，作业执行的时间越短，响应比越高，满足段任务优先，同时响应比会随着等待时间增加而变大，优先级会提高，能够避免饥饿现象。优点是兼顾长短作业，缺点是计算响应比开销大，适用于批处理系统。
问题七、死锁的原因、必要条件、死锁处理、手写死锁代码、java是如何解决死锁的
1、死锁的原因
在两个以上的并发进程中，如果每个进程都持有某种资源而又等待其他进程释放他们持有的资源，在未改变这种状态前，谁都无法推进，则发生了死锁。就好比是对方相互拿着自己需要的资源，都不释放自己的。
2、产生死锁的四个必要条件
(1)互斥。一个资源一次只能被一个进程占有
(2)请求与保持。一个进程因为请求资源而阻塞时，不释放自己持有的资源
(3)非剥夺。无法在进程结束前剥夺它对资源的所有权
(4)循环等待。若干进程收尾相接形成环形等待关系
3、死锁处理
(1)预防死锁。破坏后三个条件中的一个即可(互斥是非共享设备的特性，无法更改)：
(2)死锁避免。避免死锁并不是事先采取某种限制措施破坏死锁的必要条件，而是再资源动态分配过程中，防止系统进入不安全状态，以避免发生死锁，比如银行家算法、系统安全状态、安全性算法。
(3)死锁的检测与解除：资源分配图死锁定理死锁解除。
4、死锁代码
(1)使用信号量实现生产者-消费者
为了同步生产者和消费者的行为，需要记录缓冲区中物品的数量。数量可以使用信号量来进行统计，这里需要使用两个信号量：empty 记录空缓冲区的数量，full 记录满缓冲区的数量。其中，empty 信号量是在生产者进程中使用，当 empty 不为 0 时，生产者才可以放入物品;full 信号量是在消费者进程中使用，当 full 信号量不为 0 时，消费者才可以取走物品。
- #define N 100
- typedef int semaphore;
- semaphore mutex = 1;
- semaphore empty = N;
- semaphore full = 0;
-
- void producer() {
- while(TRUE) {
- int item = produce_item();
- down(&empty);
- down(&mutex);
- insert_item(item);
- up(&mutex);
- up(&full);
- }
- }
-
- void consumer() {
- while(TRUE) {
- down(&full);
- down(&mutex);
- int item = remove_item();
- consume_item(item);
- up(&mutex);
- up(&empty);
- }
- }
(2)使用管程实现生产者-消费者
- // 管程
- monitor ProducerConsumer
- condition full, empty;
- integer count := 0;
- condition c;
-
- procedure insert(item: integer);
- begin
- if count = N then wait(full);
- insert_item(item);
- count := count + 1;
- if count = 1 then signal(empty);
- end;
-
- function remove: integer;
- begin
- if count = 0 then wait(empty);
- remove = remove_item;
- count := count - 1;
- if count = N -1 then signal(full);
- end;
- end monitor;
-
- // 生产者客户端
- procedure producer
- begin
- while true do
- begin
- item = produce_item;
- ProducerConsumer.insert(item);
- end
- end;
-
- // 消费者客户端
- procedure consumer
- begin
- while true do
- begin
- item = ProducerConsumer.remove;
- consume_item(item);
- end
- end;
(3)读写问题
允许多个进程同时对数据进行读操作，但是不允许读和写以及写和写操作同时发生。一个整型变量 count 记录在对数据进行读操作的进程数量，一个互斥量 count_mutex 用于对 count 加锁，一个互斥量 data_mutex 用于对读写的数据加锁。
- typedef int semaphore;
- semaphore count_mutex = 1;
- semaphore data_mutex = 1;
- int count = 0;
-
- void reader() {
- while(TRUE) {
- down(&count_mutex);
- count++;
- if(count == 1) down(&data_mutex); // 第一个读者需要对数据进行加锁，防止写进程访问
- up(&count_mutex);
- read();
- down(&count_mutex);
- count
- if(count == 0) up(&data_mutex);
- up(&count_mutex);
- }
- }
-
- void writer() {
- while(TRUE) {
- down(&data_mutex);
- write();
- up(&data_mutex);
- }
- }
(4)哲学家就餐问题
五个哲学家围着一张圆桌，每个哲学家面前放着食物。哲学家的生活有两种交替活动：吃饭以及思考。当一个哲学家吃饭时，需要先拿起自己左右两边的两根筷子，并且一次只能拿起一根筷子。
下面是一种错误的解法，考虑到如果所有哲学家同时拿起左手边的筷子，那么就无法拿起右手边的筷子，造成死锁。
- #define N 5
-
- void philosopher(int i) {
- while(TRUE) {
- think();
- take(i); // 拿起左边的筷子
- take((i+1)%N); // 拿起右边的筷子
- eat();
- put(i);
- put((i+1)%N);
- }
- }
为了防止死锁的发生，可以设置两个条件：
- 必须同时拿起左右两根筷子;
- 只有在两个邻居都没有进餐的情况下才允许进餐。
- #define N 5
- #define LEFT (i + N - 1) % N // 左邻居
- #define RIGHT (i + 1) % N // 右邻居
- #define THINKING 0
- #define HUNGRY 1
- #define EATING 2
- typedef int semaphore;
- int state[N]; // 跟踪每个哲学家的状态
- semaphore mutex = 1; // 临界区的互斥
- semaphore s[N]; // 每个哲学家一个信号量
-
- void philosopher(int i) {
- while(TRUE) {
- think();
- take_two(i);
- eat();
- put_two(i);
- }
- }
-
- void take_two(int i) {
- down(&mutex);
- state[i] = HUNGRY;
- test(i);
- up(&mutex);
- down(&s[i]);
- }
-
- void put_two(i) {
- down(&mutex);
- state[i] = THINKING;
- test(LEFT);
- test(RIGHT);
- up(&mutex);
- }
-
- void test(i) { // 尝试拿起两把筷子
- if(state[i] == HUNGRY && state[LEFT] != EATING && state[RIGHT] !=EATING) {
- state[i] = EATING;
- up(&s[i]);
- }
- }
问题八：线程实现的两种方式，各有什么优缺点
![]()
问题九、内存管理的方式：段式、页式、段页式。比较他们的区别
操作系统中的内存管理有三种，段式页式段页式。
1、为什么需要三种管理方式
由于连续内存分配方式会导致内存利用率偏低以及内存碎片的问题，因此需要对这些离散的内存进行管理。引出了三种内存管理方式。
2、分页存储管理
(1)基本分页存储管理中不具备页面置换功能，因此需要整个程序的所有页面都装入内存之后才可以运行。
(2)需要一个页表来记录逻辑地址和实际存储地址之间的映射关系，以实现从页号到物理块号的映射。
(3)由于页表也是存储在内存中的，因此内存数据需要两次的内存访问(一次是从内存中访问页表，从中找到指定的物理块号，加上页内偏移得到实际物理地址;第二次就是根据第一次得到的物理地址访问内存取出数据)。
(4)为了减少两次访问内存导致的效率影响，分页管理中引入了快表，当要访问内存数据的时候，首先将页号在快表中查询，如果在快表中，直接读取相应的物理块号;如果没有找到，那么访问内存中的页表，从页表中得到物理地址，同时将页表中的该映射表项添加到快表中。
(5)在某些计算机中如果内存的逻辑地址很大，将会导致程序的页表项会很多，而页表在内存中是连续存放的，所以相应的就需要较大的连续内存空间。为了解决这个问题，可以采用两级页表或者多级页表的方法，其中外层页表一次性调入内存且连续存放，内层页表离散存放。相应的访问内存页表的时候需要一次地址变换，访问逻辑地址对应的物理地址的时候也需要一次地址变换，而且一共需要访问内存3次才可以读取一次数据。
3、分段存储管理
分页是为了提高内存利用率，而分段是为了满足程序员在编写代码的时候的一些逻辑需求(比如数据共享，数据保护，动态链接等)。
(1)分段内存管理当中，地址是二维的，一维是段号，一维是段内地址;
(2)其中每个段的长度是不一样的，而且每个段内部都是从0开始编址的。由于分段管理中，每个段内部是连续内存分配，但是段和段之间是离散分配的，因此也存在一个逻辑地址到物理地址的映射关系，相应的就是段表机制。段表中的每一个表项记录了该段在内存中的起始地址和该段的长度。段表可以放在内存中也可以放在寄存器中。
(3)访问内存的时候根据段号和段表项的长度计算当前访问段在段表中的位置，然后访问段表，得到该段的物理地址，根据该物理地址以及段内偏移量就可以得到需要访问的内存。由于也是两次内存访问，所以分段管理中同样引入了联想寄存器。
4、分段和分页的对比
(1)页是信息的物理单位，是出于系统内存利用率的角度提出的离散分配机制;段是信息的逻辑单位，每个段含有一组意义完整的信息，是出于用户角度提出的内存管理机制
(2)页的大小是固定的，由系统决定;段的大小是不确定的，由用户决定
(3)页地址空间是一维的，段地址空间是二维的
5、段页存储方式
先将用户程序分为若干个段，然后再把每个段分成若干个页，并且为每一个段赋予一个段名称。这样在段页式管理中，一个内存地址就由段号，段内页号以及页内地址三个部分组成。
段页式内存访问：系统中设置了一个段表寄存器，存放段表的起始地址和段表的长度。地址变换时，根据给定的段号(还需要将段号和寄存器中的段表长度进行比较防止越界)以及寄存器中的段表起始地址，就可以得到该段对应的段表项，从段表项中得到该段对应的页表的起始地址，然后利用逻辑地址中的段内页号从页表中找到页表项，从该页表项中的物理块地址以及逻辑地址中的页内地址拼接出物理地址，最后用这个物理地址访问得到所需数据。由于访问一个数据需要三次内存访问，所以段页式管理中也引入了高速缓冲寄存器。
问题十、虚拟内存的作用
1、虚拟内存存在的意义?
(1)既然每个进程的内存空间都是一致而且固定的，所以链接器在链接可执行文件时，可以设定内存地址，而不用去管这些数据最终实际的内存地址，这是有独立内存空间的好处
(2)当不同的进程使用同样的代码时，比如库文件中的代码，物理内存中可以只存储一份这样的代码，不同的进程只需要把自己的虚拟内存映射过去就可以了，节省内存
(3)在程序需要分配连续的内存空间的时候，只需要在虚拟内存空间分配连续空间，而不需要实际物理内存的连续空间，可以利用碎片。
2、虚拟内存和物理内存的关系
![]()
问题十一、页面置换算法
1、算法讲解
(1)最佳置换算法：理想的置换算法。置换策略是将当前页面中在未来最长时间内不会被访问的页置换出去。
(2)先进先出置换算法：每次淘汰最早调入的页面 。
(3)最近最久未使用算法LRU：每次淘汰最久没有使用的页面。使用了一个时间标志。
(4)时钟算法clock(最近未使用算法NRU)：页面设置一个访问位，并将页面链接为一个环形队列，页面被访问的时候访问位设置为1。页面置换的时候，如果当前指针所指页面访问为为0，那么置换，否则将其置为0，循环直到遇到一个访问为位0的页面
(5)改进型Clock算法：在Clock算法的基础上添加一个修改位，替换时根究访问位和修改位综合判断。优先替换访问为何修改位都是0的页面，其次是访问位为0修改位为1的页面。
(6)最少使用算法LFU：设置寄存器记录页面被访问次数，每次置换的时候置换当前访问次数最少的。LFU和LRU是很类似的，支持硬件也是一样的，但是区分两者的关键在于一个以时间为标准，一个以次数为标准。
(7)页面缓冲算法PBA：置换的时候，页面无论是否被修改过，都不被置换到磁盘，而是先暂留在内存中的页面链表里面，当其再次被访问的时候可以直接从这些链表中取出而不必进行磁盘IO，当链表中已修改也难数目达到一定数量之后，进行依次写磁盘操作。
2、java实现LRU算法
- public class LRU {
- public static void main(String[] args) {
- String[] inputStr = {"6", "7", "6", "5", "9", "6", "8", "9", "7", "6", "9", "6"};
- // 内存块
- int memory = 3;
- List<String> list = new ArrayList<>();
- for(int i = 0; i < inputStr.length; i++){
- if(i == 0){
- list.add(inputStr[i]);
- System.out.println("第"+ i +"次访问：\t\t" + ListUtils.listToString(list));
- }else {
- if(ListUtils.find(list, inputStr[i])){
- // 存在字符串，则获取该下标
- int index = ListUtils.findIndex(list, inputStr[i]);
- // 下标不位于栈顶时，且list大小不为1时
- if(!(list.get(list.size() - 1)).equals(inputStr[i]) && list.size() != 1) {
- String str = list.get(index);
- list.remove(index);
- list.add(str);
- }
- System.out.println("第" + i + "次" + "访问：\t\t" + ListUtils.listToString(list));
- }else{
- if(list.size()>= memory) {
- list.remove(0);
- list.add(inputStr[i]);
- System.out.println("第" + i + "次" + "访问：\t\t" + ListUtils.listToString(list));
- }else {
- list.add(inputStr[i]);
- System.out.println("第" + i + "次" + "访问：\t\t" + ListUtils.listToString(list));
- }
- }
- }
- }
- }
- }
问题十二、静态链接和动态链接
应用程序有两种链接方式，一种是静态链接，一种是动态链接。
1、基本概念
所谓静态链接就是在编译链接时直接将需要的执行代码拷贝到调用处，优点就是在程序发布的时候就不需要的依赖库，也就是不再需要带着库一块发布，程序可以独立执行，但是体积可能会相对大一些。
所谓动态链接就是在编译的时候不直接拷贝可执行代码，而是通过记录一系列符号和参数，在程序运行或加载时将这些信息传递给操作系统，操作系统负责将需要的动态库加载到内存中，然后程序在运行到指定的代码时，去共享执行内存中已经加载的动态库可执行代码，最终达到运行时连接的目的。
2、windows和linux区别
windows:
在windows上大家都是DLL是动态链接库，里面是一系列可执行的代码，开发过windows程序的人可能还知道有另外一种形式的库，就是LIB，大家可能普遍认为LIB就是静态库，至少我之前是这么认为的，但是在实际的开发过程中，纠正了我这个错误的想法。LIB形式的文件可能会有两种形式，这里并不排除第三种形式。1：包括符号表和二进制可执行代码，也就是传统意义上理解的静态库，可以被静态连接。2：只有符号表，也就是只有动态库的符号导出信息，通过这些信息可以在程序运行时定位到动态库中，最终实现动态连接。
linux:
在linux上大家也都知道SO是动态库，类似于windows下的DLL，实现方式也是大同小异，同时开发过linux下程序的人也都知道另外一种形式的库就是A库，同样道理普遍认为是和SO对立的，也就是静态库，不然没道理存在啊，呵呵。但是事实区却不是如此，A文件的作用和windows下的LIB文件作用几乎一样，也可能会有两种形式，和windows下的lib文件一样，在此就不在赘述。
3、静态链接库的优点
(1) 代码装载速度快，执行速度略比动态链接库快;
(2) 只需保证在开发者的计算机中有正确的.LIB文件，在以二进制形式发布程序时不需考虑在用户的计算机上.LIB文件是否存在及版本问题，可避免DLL地狱等问题。
4、动态链接库的优点
(1) 更加节省内存并减少页面交换;
(2) DLL文件与EXE文件独立，只要输出接口不变(即名称、参数、返回值类型和调用约定不变)，更换DLL文件不会对EXE文件造成任何影响，因而极大地提高了可维护性和可扩展性;
(3) 不同编程语言编写的程序只要按照函数调用约定就可以调用同一个DLL函数;
(4)适用于大规模的软件开发，使开发过程独立、耦合度小，便于不同开发者和开发组织之间进行开发和测试。
5、不足之处
(1) 使用静态链接生成的可执行文件体积较大，包含相同的公共代码，造成浪费;
(2) 使用动态链接库的应用程序不是自完备的，它依赖的DLL模块也要存在，如果使用载入时动态链接，程序启动时发现DLL不存在，系统将终止程序并给出错误信息。而使用运行时动态链接，系统不会终止，但由于DLL中的导出函数不可用，程序会加载失败;速度比静态链接慢。当某个模块更新后，如果新模块与旧的模块不兼容，那么那些需要该模块才能运行的软件，统统撕掉。这在早期Windows中很常见。
本文转载自微信公众号「愚公要移山」，可以通过以下二维码关注。转载本文请联系愚公要移山公众号。
![]()
