第一章 计算机系统概述
作业是用户提交的，进程是系统自动生成的。
访管指令（trap）属于用户态。
关于中断，OS完成的部分有：
1.初始化中断向量表
2.保存中断屏蔽字
3.提供中断服务（中断服务程序属于os）
硬件完成的有：
1.关中断
2.cpu变态
3.保存pc,psw
4.引出中断服务程序的地址
常见特权指令：
1.跟I/O设备操作有关的指令；
2.有关访问程序状态的指令；
3.存取特殊寄存器指令；
4.其他指令。
宏内核特点：性能强，内核集成的功能多，追求高性能，变态速度快，扩展性差
微内核特点：追求高可靠性和安全性，内核精简，扩展性强（基于c/s模式，挂载新服务器实现扩展），变态速度慢
第二章 进程与线程
2.1进程与线程
程序和进程：进程在运行期间可以执行多个程序，一个程序的多次运行可以生成多个不同的进程，一个程序的一次执行可以产生多个进程
并发进程会失去封闭性，并发进程共享变量，其执行结果与速度有关。
父进程和子进程是相互独立的，子进程相当于父进程的副本，可以并发执行，一开始子进程是共享父进程内存页的，但是一旦修改子进程，便会申请独立的虚拟地址空间。父进程终止的时候，子进程可能不会一并被终止。
进程:
程序的一次执行，具有动态性(动态性是进程最基本的特征)；
是进程实体的运行过程；
是除CPU之外的系统资源的分配单元，每一个进程都有它自己的地址空间。
进程实体:也可以理解为进程运行中的的一个快照，由PCB，程序段，数据段组成。
程序封闭性: 程序封闭性是指进程执行的结果只取决于进程本身，不受外界影响。也就是说，进程在执行过程中不管是不停顿的执行，还是走走停停，进程的执行速度不会改变它的执行结果。失去封闭性后，不同速度下的执行结果不同。
进程控制
进程控制肯定会做的事：
1.更新PCB中的信息
a. 所有的进程控制原语一定都会修改进程状态标志
b. 剥夺当前运行进程的CPU使用权必然需要保存其运行环境
c. 某进程开始运行前必然要恢复期运行环境
2. 将PCB插入合适的队列
3. 分配/回收资源
进程通信
三种方式：
- 共享存储
- 消息传递
直接通信：
间接通信：
- 管道通信
4.信号
线程:
线程是处理机的分配单元，也称为轻量级进程，是进程中的一个实体，是被系统独立调度和分派的基本单位，线程自己不拥有系统资源，只拥有一点在运行中必不可少的资源（ 程序计数器，一组寄存器和栈），但它可与同属一个进程的其他线程共享进程所拥有的全部资源。
线程的优点：
- （1）易于调度。
- （2）提高并发性。通过线程可方便有效地实现并发性。进程可创建多个线程来执行同一个程序的不同部分。
- （3）开销少。创建线程比创建进程要快，所需开销少，占用的资源也少；
- （4）充分发挥多处理器的功能。通过创建多线程进程，每个线程在一个处理器上运行，从而实现应用程序的并发性，使每个处理器都得到充分的运行。
线程的实现方式
1.用户级线程
特征：由应用程序直接控制，可由应用程序直接完成线程切换，操作系统察觉不到用户级线程的存在；
优点：切换线程开销小，支持每个进程定制自己的调度算法； 缺点：一个线程阻塞，整个进程阻塞。
2.内核级线程（内核级线程才是处理机分配的基本单位）
特征：操作系统可直接察觉到内核级线程，内核级线程由操作系统直接控制，线程的切换也在内核态执行
优点：各个线程可以分配到多个处理机上并行执行,并行能力强； 缺点：切换线程开销大
多线程模型：
引入内核级线程概念的用户级线程模型，本质一样
进程与线程的区别
（1）调度：线程作为处理器调度和分配的基本单位，而进程是作为拥有资源的基本单位
（2）并发性：不仅进程之间可以并发执行，同一个进程或不同进程的多个线程之间也可以并发执行
（3）拥有资源：进程是拥有资源的一个独立单位，有自己独立的地址空间；线程不拥有系统资源，但可以访问隶属于进程的资源，共享进程的地址空间.
（4）系统开销：在创建或撤消进程时，由于系统都要为之分配和回收资源，导致系统的开销明显大于创建或撤消线程时的开销。
2.2 处理机调度
高级调度：从外存找到作业，为其分配资源，创建进程，转入就绪队列
中级调度：节省内存，把进程转到外存挂起，就绪态和挂起态互相切换
低级调度：进程调度
2.3调度时机——什么事件会触发“调度程序”？
• 创建新进程
• 进程退出
• 运行进程阻塞
• I/O中断发生（可能唤醒某些阻塞进程）
• 非抢占式调度策略，只有运行进程阻塞或退出才触发调度程序工作
• 抢占式调度策略，每个时钟中断或k个时钟中断会触发调度程序工作
调度进程在没事干的时候就执行闲逛进程（无实际操作，空过）
2.5 调度算法(单处理机调度)
前三种算法适用于早期的批处理系统。
主要关心对用户的公平性、平均周转时间、平均等待时间等评价系统整体性能的指标，但是不关心“响应时间”，也并不区分任务的紧急程度，因此对于用户来说，交互性很糟糕。
1. 先来先服务(FCFS):
适用于CPU繁忙型作业
计算：
2. 短作业优先算法(SJF):
适用于I/O繁忙型作业
计算：
非抢占式：
抢占式：
3. 高响应比优先(HRRN):
无饥饿，优化了等待时间和运行时间
计算:
4. 时间轮转片调度算法(RR)
只用于进程调度，不用于作业调度
每次从就绪队列对头取一个进程上cpu执行，当时间片用完进程还没执行完就放入队尾
分时操作系统采用，不需要阻塞队列，时间片结束就回到就绪队列末尾
如果时间片太大会导致该调度算法退化为先来先服务调度算法，大大增加进程响应时间；
如果时间片太小会导致进程切换频繁，大大增加了系统处理进程切换的开销；
算法实现：
5. 优先级调度算法：
优先级：优先数最大，优先级越高（0最小，地位最低）
通常：系统进程优先级高于用户进程
前台进程优先级高于后台进程
操作系统更偏好I/O型进程（或称I/O繁忙型进程）注:与I/O型进程相对的是计算型进程（或称CPU繁忙型进程）
静态优先级算法：优先级在进程建立时就确定，后续不改变
动态优先级算法：建立进程的时候会先赋予一个优先级，优先级会根据进程的推进或等待时间的增加而改变（等待时间久的进程优先级会适度提高，运行时间长的进程会适度降低）
算法实现：
非抢占式：
抢占式：
6. 多级反馈队列调度算法
算法实现：
7. 多级队列调度算法：
2.6 多处理机调度
多处理机调度不仅需要考虑哪个就绪进程优先上处理机运行，还需要考虑上哪个处理机运行。
多处理机调度应追求的目标：
负载均衡：尽可能让每个cpu都同等忙碌
处理机亲和性：尽量让一个进程调度到同一个cpu上运行，以发挥Cache的作用(如果其中一个cpu的Cache里已经有该进程的数据缓存，直接让该cpu处理该进程，省的别的cpu再从主存里再取读一份数据)
方案一：
方案二：
2.3 同步与互斥
1.基本概念：
临界资源：一次仅允许一个进程使用的资源
进入区：负责检查是否可进入临界区，若可进入，则应设置正在访问临界资源的标志（可理解为“上锁”），以阻止其他进程同时进入临界区
临界区：访问临界资源的那段代码
退出区：负责解除正在访问临界资源的标志（可理解为“解锁”）
剩余区：做其他处理
进入区和退出区实现互斥的功能
可以被多个进程在任意时刻访问的则是 不可修改的代码（只读代码，如a=1;）
2.临界区互斥的实现方法：
1.软件实现：
法1(单标志法)：
turn表示允许进入临界区的进程号，如果进程号不符合则一直卡在死循环①；
该方法可能会违背空闲让进的规则，如：当前允许p0访问临界区，但是p0一直不进入临界区，p1就一直进不去临界区，要一直等到p0进程进入临界区后再退出才可使用。
原因就是谦让代码在循环里，自己不用，别人也用不了
法2(双标志先检查法)：
由于系统的并发性，该方法可能导致两个进程一同进入临界区。
该方法败在都没有谦让，见没人使用资源就直接进去使用了；
或者说败在没有把检查和上锁做到一气呵成，导致可能会有多个进程同时进入临界区。
法3(双标志后检查法)：
该方法败在两者过于谦让，导致两者都不去访问资源
法4(peterson算法):
假设语句执行顺序为1,6,2,7,3,8
1.p0,p1都想访问临界区;
2.p0愿意谦让给p1(turn=1);p1又谦让回给p0(turn=0)
3.p0见p1先让自己了,就先行进入临界区;p1见p0在使用就慢慢等待。
该算法解决了进程互斥问题，遵循了空闲让进、忙则等待、有限等待三个原则，但是依然未遵循让权等待的原则。(若第一时间不使用临界资源则立即释放)
汇总：
2.硬件实现：
1.中断屏蔽方法：只适用单处理机
2.TestAndSet(TSL指令):需要忙等，只适用于多处理机
lock为临界区锁，想要访问临界区资源的进程将一直循环检测临界区是否已经上锁，如果没有上锁则进入并上锁(由于是硬件实现，该过程不会中断，避免了两个进程同时进入临界区的情况)，用完资源以后就把锁打开。
3.Swap：需要忙等，只适用于多处理机
lock为临界区锁，实现思想和法2一样，在执行上swap指令会一直交换lock和old的值，一旦lock为false，就会被old换走，进程就可以入临界区资源，完事以后再把lock赋值为false。
3.互斥锁
特性：
- 需忙等，进程时间片用完才下处理机，违反“让权等待”
- 优点：等待期间不用切换进程上下文，多处理器系统中，若上锁的时间短，则等待代价很低(因为不切换进程，忙等的开销可能比切换另一个进程执行的开销还来得低)
- 常用于多处理器系统，一个核忙等，其他核照常工作，并快速释放临界区
- 不太适用于单处理机系统，忙等的过程中不可能解锁
4.信号量机制：
概念：
信号量其实就是一个变量，可以用一个信号量（可以是一个整数，也可以是更复杂的记录型变量）,来表示系统中某种资源的数量，比如：系统中只有一台打印机，就可以设置一个初值为1的信号量。
原语是一种特殊的程序段，其执行只能一气呵成，不可被中断。当原子操作无法完成时，会自动恢复到操作之前的状态。
一对原语：wait(S)原语(P操作)和signal(S)原语(V操作)，可以把原语理解为我们自己写的函数，函数名分别为wait和signal，括号里的信号量S其实就是函数调用时传入的一个参数。
1. 整形信号量
2. 记录型信号量(常考)：最好用，满足全部四个同步条件
3. 用信号量实现进程互斥、同步、前驱关系
实现进程互斥：
实现进程同步：
实现进程的前驱关系：
信号量Si=0，前V后P
总结：
5.经典问题
生产者-消费者问题
缓冲区是互斥访问的
实现互斥的p操作一定要在实现同步的p操作之后
读者-写者问题
有读者和写者两组并发进程，共享一个文件，当两个或两个以上的读进程同时访问共享数据时不会产生副作用，但若某个写进程和其他进程（读进程或写进程）同时访问共享数据时则可能导致数据不一致的错误。因此要求：①允许多个读者可以同时对文件执行读操作；②只允许一个写者往文件中写信息；③任一写者在完成写操作之前不允许其他读者或写者工作；④写者执行写操作前，应让已有的读者和写者全部退出。
哲学家问题：
法3：
、
哲学家进餐问题可以用于解决进程需要占用多个临界资源时的死锁问题。
6.管程
管程提供了一种高级的同步原语，它将共享资源和对资源的操作封装在一个单元中，并提供了对这个单元的访问控制机制。
相比于信号量机制，用管程编写程序更加简单，写代码更加轻松。
2.4 死锁
死锁，饥饿，死循环的区别
预防死锁产生的四个必要条件
静态资源分配法：一次性给足一个进程需要的所有资源.(破坏请求和保持条件)
有序资源分配法（打怪升级算法，属于破坏循环等待条件）
死锁定理用于检测资源分配图，若不可完全简化则发说明发送死锁
第四章：文件管理
何为句柄(HANDLE)?
句柄就是系统某个资源的引用标识,用户可以通过句柄间接访问和操作系统的资源.
在linux中,句柄就是fd(文件描述符).通过VFS(虚拟文件系统),linux中所有的资源,包括文件,设备,进程都可以用fd来表示.
用户程序
↓
句柄（fd / HANDLE）
↓
内核对象（file / socket / process）
↓
真实资源（磁盘 / 网络 / CPU 等）
在 Linux 文件系统中，文件由元数据(metadata)和数据(data)组成。文件的元数据存储在 inode 中，包括文件权限、大小、时间戳、链接计数以及数据块指针等信息；文件的实际内容存储在数据块(data block)中。
inode节点代表文件,多个文件名可以使用同一个inode编号,
进程在打开文件时,如int fd=open(“a.txt”);
系统内核会先通过a.txt的文件路径找到其inode节点,然后创建一个打开文件对象(这个打开文件对象会记录文件的偏移量,引用计数,inode指针等信息),放在系统统一的打开文件表中.随后系统内核会在该进程的文件描述符表中找到一个空表项,将该打开文件对象的指针填进去,最后把这个表项的下标返回给用户程序.
用户就可以通过这个fd对文件进行操作了.
如果是两个不同的进程打开同一个文件，打开文件表里会生成两个不同的打开文件对象，但都指向同一个inode节点。
一个打开文件对象的引用计数等于所有进程的文件描述表中指向这个打开文件对象的fd数量的总和
磁盘扫描算法：SCAN、C-SCAN 与
FCFS先来先服务
SSTF最短寻道时间优先
SCAN电梯算法
C-SCAN循环扫描：到达一端后直接返回另一头
LOOK按需扫描
PV大题解题：
1.看有几类进程，每类进程对应一个函数
2.每个函数内，用中文描述进程动作，注意动作是只发生一次还是一直发生
3.分析每个动作前，需要p什么？ 有p必有v，先写p,再写v
4.所有pv写完，在定义信号量和初始值，注意找到临界区资源（临界区资源需要互斥访问）。
5.检查多个p连续出现的地方是否会导致死锁，如果会死锁就适当调整顺序
6.读题检查是否满足题目条件
哲学家问题模板
对于连续p操作死锁的判定方法：
并发进程之间对相同的几个临界资源的连续p操作顺序不一致则会发生死锁。