一、操作系统概述

1. 什么是操作系统？

操作系统是控制和管理计算机软硬件资源，合理组织和调度计算机的工作任务和资源分配，进而为用户和其他软件，提供接口和环境的程序集合。

2. 简述操作系统的特征

• 并发：多个程序在同一个时间间隔内运行
• 共享：内存多个进程共享系统资源
• 虚拟：将一个物理实体抽象成多个逻辑对应物，分为空分复用和时分复用
• 异步：进程以不可预知的方式推进，但需要同步机制使每次运行结果相同
  并发性和共享性是操作系统的两个基本特性

3. 系统调用的作用
   系统调用是操作系统为用户程序使用内核功能提供的接口，将用户态转变到核心态，从而使用计算机的资源
4. 多道批处理系统的特点

内存中同时存放多道程序，宏观并行，微观串行

5. 分时操作系统的特点

同时性：允许多个终端同时使用一个计算机
交互性：方便进行人机交互
及时性：响应及时
独立性：用户独立操作互不干扰

6. 实时操作系统的特点

• 硬实时系统：必须在规定时间内完成对外部事件的处理
• 软实时系统：时间规定不需要严格执行

7. 甘特图的使用

cpu利用率 = cpu运行时间 / 作业完成总时间

二、进程管理

1. 简述进程的特征

• 动态性：
  进程是程序的一次执行过程，是动态的，拥有五种基本状态：创建、就绪、运行、终止、阻塞
• 并发性：
  多个进程可以同时存在于内存并发执行，提高资源利用率和系统吞吐量
• 独立性：
  进程是系统资源分配和管理的基本单位，每个进程实体拥有独立的地址空间
• 异步性：
  进程的执行是以不可预知的方式推进，但是要用同步机制保证执行结果的相同
• 结构性：
  进程实体由程序段、数据段和进程控制块组成，其中，PCB是进程存在的唯一标识

2. 进程五种基本状态的如何变化的？

就绪状态->运行状态：进程获得CPU资源
运行状态->就绪状态：1. 时间片用完 2.cpu被优先级更高的进程抢占
运行状态->阻塞状态：进程运行所需资源无法被满足
阻塞状态->就绪状态：进程需要的资源已经准备好

3. 简述线程

1. 动态性：
   线程是进程中的一个单一顺序的控制流，拥有五种基本状态：创建、就绪、运行、终止、阻塞
2. 并发性：
   线程属于进程，一个进程至少拥有一个线程，同一进程内的多个线程可以并发执行
3. 独立性：
   线程是CPU资源分配和调度的基本单位，同一进程内的多个线程共享进程的全部资源，但各自拥有自己线程控制块和堆栈环境
4. 低开销：
   同一个进程内的线程切换，不会引起进程切换，时空开销小
   不同进程内的线程切换，会引起进程的切换，时空开销大

线程的五种状态详解

试从调度性、并发性、拥有资源及系统开销方面，对进程和线程进行比较
1.调度性：
  进程是系统资源分配和管理的基本单位，在引入线程的OS中，线程是CPU资源分配和调度的基本单位
2.并发性：
  不同进程之间和同一个进程中的多个线程之间都可以并发，提高了系统的并发性
3.拥有资源：
  进程始终是拥有资源的一个基本单位，同一进程内的多个线程共享进程的全部资源，但各自拥有自己线程控制块和堆栈环境
4.开销：
 由于创建或撤销进程时，系统都要为之分配和回收资源开销大，但是同一个进程内的线程切换开销小

4. 简述进程间的通信方式
   
5. 简述三级调度及其联系

高级调度（作业调度）：从外存挑选作业进入内存并分配资源
中级调度（内存调度）：将暂时不用的进程调到我外存挂起，将要用的进程从外存调入就绪队列
低级调度（进程调度）：从就绪队列选取一个进程分配cpu资源
从执行次数来看，作业调度执行次数最少，进程调度执行次数最高
进程调度有两种基本方式，分为抢占式和非抢占式

6. 常见的调度算法

• 先来先服务算法FCFS 不可剥夺，对长作业有利，有利于CPU繁忙型作业
• 短作业优先调度算法SJF 长作业可能产生饥饿现象，有利于IO繁忙型，平均等待时间和周转时间最少
• 优先级调度算法
• 高响应比优先调度算法 要求服务时间相同时是FCFS，作业等待时间相同时是SJF
• 时间片轮转调度算法 绝对可抢占，运行完一个时间片排到就绪队列尾部
• 多级反馈队列调度算法
  开始时间=上个作业的完成时间
  等待时间=开始时间-提交时间
  完成时间=开始时间+运行时间
  周转时间 = 作业完成时间 - 作业提交时间
  平均周转时间 = 所有作业周转时间之和 / 作业数
  带权周转时间 = 作业周转时间 / 作业实际运行时间
  响应比 = 等待时间+要求服务时间 / 要求服务时间
  CPU是宝贵的资源，只要有作业就优先运行

7. 简述临界区和临界资源

临界资源是一次只允许一个进程使用的资源，而临界区是访问临界资源的那部分代码。

8. 简述进程的同步和互斥

同步是指为完成同一个任务而相互合作的进程间的直接制约关系（多个进程）
互斥是指进程因同一临界资源的争用而产生的间接制约关系

9. 如何防止两个进程同时进入临界区

• 空闲让进：当临界区空闲时，可以允许一个请求进程进入临界区
• 忙则等待：已有进程进入临界区，则其他试图进入的进程要等待
• 有限等待：正在请求的进程保证在有限时间内进入
• 让权等待：不能进入临界区的进程应当释放cpu资源

10. 简述管程的定义及作用

管程是对计算机软硬件资源抽象得到的数据结构进行控制和管理的程序
作用是保证了进程的互斥，解决临界区分散带来的管理和控制问题

信号量机制解决互斥和同步关系

• P操作调用wait函数减1，V操作调用signal函数加1
• 互斥访问是用 PV信号量夹紧对临界区操作的一个元动作
• 同步操作是进程间共同完成的对共享资源的访问

11. 生产者问题

问题描述：
	一组生产者进程和一组消费者进程共享一个初始为空、大小为n的缓冲区，
	只有缓冲区没满时，生产者才能把消息放入缓冲区，否则必须等待，
	只有缓冲区不空时，消费者才能从中取出消息，否则必须等待
分析：
	1.生产者和消费者对资源的产消是同步关系
	2.缓冲区是临界资源，需要进行PV操作互斥访问
	
代码：
	semaphore mutex = 1;		//临界互斥信号量，通常设初值为1
	semaphore empty = n;		//缓冲区空位数
	semaphore full = 0;			//缓冲区满位数
	producer(){ 
		while(1){ 
			produce data;
			P(empty);			//要用的资源进行P操作
			//对临界区的访问需要用互斥信号量进行PV夹紧
			P(mutex);			
			add data to buffer;	//数据放入缓冲区
			V(mutex);			
			//------------------------------------
			V(full);			//增加的资源进行V操作
		}
	}
	consumer(){ 
		while(1){ 
			produce data;
			P(full);			//要用的资源进行P操作
			//对临界区的访问需要用互斥信号量进行PV夹紧
			P(mutex);			
			add data to buffer;	//数据放入缓冲区
			V(mutex);			
			//------------------------------------
			V(empty);			//增加一个缓冲区空位
		}
	}

12. 读者写者问题

问题描述：
	读者和写者两组并发进程，共享一个文件
	1.允许多个读者可以同时对文件执行读操作
	2.写操作执行前，不允许其他读者或写者工作
	3.写操作执行时，不允许其他读者和写者工作

分析：
	1.写者和读者是互斥关系
	2.写者和写者也是互斥关系
	3.读者之间不存在互斥关系
写进程优先（读写公平算法）：
	int count = 0;			//读者数量
	semaphore mutex = 1;	//保护count更新时的互斥
	semaphore rw = 1;		//读写互斥信号量
	semaphore w = 1;		//写者优先
	writer(){
		while(1){ 
			P(w);			//禁止其他写者
			P(rw);			//禁止其他读者
			writing;
			V(rw);
			V(w);
		}
	}
	reader(){ 
		while(1){
			P(w);			//读前禁止其他写者
			//对读者数量的互斥访问
			P(mutex);		
			if(count == 0)	//第一个读进程读取共享文件时，组织写进程写入
				P(rw);
			count++;
			V(mutex)
			V(w);
			
			reading;
			
			P(mutex);
			count--;
			if(count == 0)
				V(rw);
			V(mutex);
		}
	}
	

13. 死锁产生的原因

不可剥夺资源的竞争和进程推进顺序的非法

14. 简述死锁产生的必要条件

• 互斥条件：进程请求的资源为临界资源
• 不剥夺条件：进程获取的资源不可被剥夺
• 请求并保持条件：进程可以保持已有资源并请求其他资源
• 循环等待条件：存在一种进程资源的循环等待链

15. 简述死锁避免的原理

• 允许进程动态的申请资源，但系统进行资源的分配前，会先用银行家算法计算此次分配后系统的状态，若进入不安全状态，则让进程等待，因为系统进入不安全状态会有可能发生死锁。

• 安全状态：找到一个资源分配顺序可以让所有进程顺序完成

• 银行家算法：采用预分配策略检查分配完成后系统是否处于安全状态

16. 解除死锁有哪些方法：

• 资源剥夺法：挂起死锁进程并剥夺其资源给其他进程
• 撤销进程法：强制撤销死锁进程并剥夺其资源
• 进程回退法：让一个或多个进程回退到足以避免自锁的地步

17. 某系统中有K个并发进程都需要N个同类资源，则该系统必然不会发生死锁的最小资源数是(N-1)*K + 1
18. 死锁检测的资源分配图

死锁定理：死锁状态 当且仅当 资源分配图不可完全简化
资源分配图简化指进程所需资源均满足则可以将进程相连的边去除

19. 某系统中有K个并发进程都需要N类同类资源，则该系统必然不会发生死锁的最少资源数为K * (N - 1) + 1
20. 银行家算法

Available：可利用资源序列 = 系统总资源序列 - 系统已分配资源序列
Max：某进程对资源的最大需求序列
Allocation：分配给每个进程的资源数
算法步骤

1. 求需求矩阵Need = Max - Allocatioin
2. Available与Need比较
3. 若Available>Need，则将该进程释放，并将其资源加到Available中