操作系统
内容援引自王道考研，感谢各路大神的原创分享，若笔记存在错误烦请批评指正~
概念
本质是系统软件，向上为用户和应用程序提供服务，向下扩展硬件。具有并发、共享、虚拟、异步的特征，实现了文件管理、内存管理、进程管理、进程调度和设备管理等功能。
命令接口（用于直接使用）、程序接口（用于通过程序间接使用，即系统调用）。
两种指令，特权指令和非特权指令；处理器两种状态，用户态和内核态；两种程序，用户程序和内核程序。用户程序运行在用户态，执行非特权指令；内核程序运行在内核态，执行非特权指令或特权指令。
操作系统的内核
内核提供时钟管理、中断处理、原语和系统资源管理等功能。并发性引入中断机制，发生中断后操作系统介入，处理器由用户态进入内核态（中断是处理器由用户态进入内核态的唯一途径）。根据中断信号来源将中断可分为内中断和外中断，常见的内中断包括系统调用、缺页中断、整数除零等，常见的外中断包括IO请求。
系统调用是操作系统提供给应用程序使用的接口，使应用程序使用系统调用获得操作系统服务。库函数是对系统调用的进一步封装。用户态下应用程序发起系统调用，执行陷入指令引发内中断，切换到内核态，执行系统调用相关的程序，切换回用户态。
进程
进程的组成
进程是程序的一次执行过程，是资源分配的基本单位，线程是处理器调度的基本单位。进程的组成包括PCB、程序段、数据段，PCB数据结构中包括进程描述信息（进程id，用户id）、进程管理和控制信息（进程状态和进程优先级）、资源分配清单（程序段指针、数据段指针、分配的硬件资源等）、寄存器值（用于进程切换恢复现场）。
进程的状态
进程的状态包括创建状态、就绪状态（缺处理器）、运行状态、阻塞状态（等待某资源或事件）、终止状态
进程控制
进程控制实现进程状态间切换，用原语实现（原语使用关中断和开中断实现）。进程控制需要修改PCB，将PCB插入合适的队列，分配或释放资源等。
引起进程切换的事件：当前进程主动阻塞、当前进程时间片用完、更高优先级的进程到达、当前进程终止。
进程通信
进程是资源分配的基本单位，进程内存地址彼此独立。可以通到管道、消息传递、共享存储三种方式实现进程间通信。
管道通信本质是在内存中开辟大小固定的缓冲区，各进程互斥访问管道，数据写入管道，写满write系统调用被阻塞；读进程读数据，读空read系统调用被阻塞。管道采用半双工通信，数据被读出则被丢弃，故只能有一个读进程。
消息传递包括直接通信和间接通信，直接通信是指消息直接挂在接收进程的消息缓冲队列，间接通信是指通过中间实体进行转发，如消息队列。
共享存储是指互斥访问共享存储区。
进程调度，选择进程+进程切换
处理机调度的三个层次，作业调度、内存调度和进程调度。作业调度是指从后备队列选择合适的作业由外存调入内存并创建进程；内存调度是从挂起队列选择合适进程由外存调入内存；进程调度是从就绪队列选择合适的进程分配处理机。由此引出进程的七状态模型，相比五状态模型添加了就绪挂起、阻塞挂起。
不能进行进程调度的场景，中断处理过程中、原子操作过程中。
常见的进程调度算法包括先来先服务FCFS、短作业优先SJF、高响应比优先HRRN、时间片轮转调度算法RR、优先级调度算法、多级反馈队列调度算法。
- FCFS考虑进程的等待时间，按进程到达的先后顺序分配处理机，对短进程不友好，不会导致进程饥饿。
- SJF考虑进程的要求服务时间，对长进程不友好，可能导致进程饥饿。
- HRRN综合考虑进程的等待时间和要求服务时间，为高响应比的进程分配处理机。
- 时间片轮转调度算法属于抢占式算法，各进程轮流执行一个时间片，不能区分任务的紧急程度。
- 优先级调度算法为优先级最高的进程分配处理机，可能导致进程饥饿。多级反馈队列调度算法设置多级就绪队列，各就绪队列优先级从高到低，时间片从小到大；新进程先进入第一级队列，按FCFS等待分配处理机，若时间片用完进程尚未结束，则进程进入下一级队列，若已在底层队列则重新进入底层队列；只有上层队列为空时才为下层队列的进程分配处理机；被抢占处理机的进程重新进入所属队列。
进程互斥
临界资源是指一段时间内只允许一个进程访问的资源,，临界区是指访问临界资源的代码。进程互斥是指对互斥的访问临界资源，需要遵循空闲让进、忙则等待、有限等待、让权等待。
- 空闲让进，临界区空闲时允许一个进程访问；
- 忙则等待，临界区正在被某进程访问时，其它试图访问的进程需要等待；
- 有限等待，等待的进程有限时间内进入临界区，避免发生进程饥饿；
- 让权等待，等待的进程释放处理机，避免忙等；
进程互斥的软件实现方法包括单标志法、双标志先检查、双标志后检查、Peterson算法。硬件实现方法包括中断屏蔽、TestAndSet指令和Swap指令。
信号量机制，包括整型信号量和记录型信号量。
- 整型信号量数值表示某资源数，
P操作对应wait原语，当该资源不够时循环等待，当该资源充分时占用资源；V操作对应signal原语，释放资源；由于P操作资源不够时循环等待，故整型信号量不满足让权等待原则。 - 记录型信号量，
P操作表示进程请求某资源，value--，若value<0表示资源已被分配完，则请求该资源的进程调用block原语自我阻塞，主动放弃处理机，并插入该资源的等待队列；V操作表示释放该类资源，检查value<=0是否成立，若成立表示有进程在等待该资源，调用wakeup原语唤醒等待队列中第一个进程。
typedef struct{
int value; // 剩余资源数
struct process *L // 等待队列
} semaphore;
void wait(semaphore s){
s.value--;
if(s.value < 0){
block(s.L);
}
}
void signal(semaphore S){
s.value++;
if(s.value <= 0){
wakeup(s.L);
}
}
信号量实现进程互斥，设置互斥信号量，初值为1，临界区前执行P操作，临界区后执行V操作；
信号量实现进程同步，为前驱关系设置同步信号量，初值为资源数，前操作后执行V操作，后操作前执行P操作；
管程 - 封装的思想
管程定义了代表共享资源的数据结构和对该共享数据结构实施操作的一组过程所组成的资源管理程序。管程保证了对共享资源的互斥访问，其互斥性由编译器支持。
线程
线程控制块TCB，同一进程下各线程共享进程资源，同一进程下线程切换不需要操作系统介入，同一进程的线程切换不会引起进程切换，不同进程下线程切换会引起进程切换。
线程实现方式包括用户级线程（线程管理不需要内核的支持）和内核级线程（线程管理需要内核支持），多线程模型包括一对一，多对一、多对多模型。
死锁
持有某资源且互相等待对方资源。死锁产生的必要条件，互斥访问、请求与保持（破坏：一次性申请所有资源）、不可剥夺（破坏：申请不到某资源，主动释放持有的资源）、循环等待（破坏：按序申请资源）。
死锁的处理策略
- 预防死锁见上文括号；
- 避免死锁即避免系统进入不安全状态（银行家算法，尝试分配该资源是否会进入不安全状态，会进入不安全状态则拒绝分配，否则进行分配）；
- 死锁的检测和解除；