文章目录
第一章 操作系统概述
1，操作系统定义：操作系统(Operating System)使计算机系统中的一个<mark>系统软件</mark>，是一些程序模块的集合，它能以尽量有效，合理的方式<mark>组织和管理计算机的软硬件资源</mark>，合理组织计算机的工作流程，控制程序的执行并向用户提供各种服务功能，使得计算机系统高效地运行。（没有广泛接受的标准定义）
2，操作系统中一些名词解释
| 名词 | 解释 |
|---|---|
| ROM（Read-Only Memory） | 只读内存 |
| RAM(Random Access Memory) | 随机存取器，也叫主存，是与CPU直接交换数据的内部存储器 |
| 进程（processs） | 加载到内存并执行的程序称为进程 |
| 用户模式（user mode） | 当系统执行用户应用时，系统处于用户模式 |
| 内核模式（kernel mode） | 当用户请求操作系统服务时，系统必须从用户模式进入内核模式，以满足请求 |
| 程序计数器（program counter） | 指定下一个所要执行的指令 |
| 系统调用（system call） | 提供操作系统服务接口 |
操作系统中存在中断，共享，并发，竞争等情况
1,中断处理过程
| 步骤 | 内容 |
|---|---|
| （1） | 设备给处理器发出一个中断信号 |
| （2） | 处理器处理完当前指令后响应中断，延迟非常短 |
| （3） | 处理器处理完当前至指令后检测到中断，判断出中断来源并向发送中断的设备发送确认中断信号，确认信号使得该设备将中断设备恢复到一般状态 |
| （4） | 处理器开始为软件处理中断做准备：保存中断点的执行程序上下文环境，包括程序状态字PSW，程序计数器PC的下一条指令位置，一些寄存器的值 |
| （5） | 处理器根据中断源查询中断向量表，获得与该中断相联系的处理程序入口地址，并将PC置成该地址，处理器开始一个新的指令周期，控制转移到中断处理程序 |
| （6） | 中断处理程序开始工作，检查I/O相关设备信息 |
| （7） | 中断处理结束，处理器检测到中断返回指令，被中断程序的上下文环境从系统堆栈中被恢复处理器状态恢复成原来的状态 |
| （8） | PSW和PC被恢复成中断前的值，处理器开始一个新的指令周期，中断处理结束 |
第二章：进程
进程（process）定义：进程是一个具有一定独立功能的<mark>程序或程序段</mark>在一组数据集合上的一次<mark>动态执行</mark>
进程=程序+执行
进程包括程序，数据和进程控制块
2.1进程状态
| 进程状态 | 说明 |
|---|---|
| 新的（new） | 进程正在创建 |
| 运行（running） | 指令正在执行 |
| 等待（wating） | 进程等待发生某个事件 |
| 就绪（ready） | 进程等待分配处理器 |
| 终止（terminated） | 进程已经完成执行 |
一次只能有一个进程在处理器上运行（running）；
但是多个进程可以处于等待或就绪状态。
2.1.3进程控制块(process Control Block)
PCB包括进程控状态，进程计数器，CPU计数器等等
2.1.4线程
一个进程至少有一个线程，一个进程可以运行多个线程，多个线程可共享数据
2.2进程调度
当有多个进程时，进程调度器（process scheduler)选择一个可用进程到CPU上执行，剩下的需要等待CPU空闲并重新调度。
2.2.1调度队列
进程在进入系统时，会被加入到作业队列（job queue),这个队列包括系统内的所有进程。
2.2.2上下文切换
中断（intirrput）导致CPU从执行当前任务改变到执行内核程序。
切换CPU到另一个进程需要保存当前进程状态和恢复另一个进程的状态为上下文切换（context switch)
2.3进程创建
2.3.1进程运行
大多数操作系统对进程的识别采用的是唯一的进程标识符（process identifier,pid)
3进程同步
3.1关于临界区问题名词解释
| 名称 | 解释 |
|---|---|
| 同步（process synchronization) | 系统中多个进程中发生的事件存在某种<mark>时序关系</mark>，需要相互合作，完成<mark>一项任务</mark> |
| 互斥 | 由于各进程共享资源，有些资源需要互斥使用，因此各进程间竞争使用这些资源，成为互斥 |
| 竞争条件（race condition) | 多个进程并发访问和操作同一数据并执行结果与特订访问顺序有关 |
| 进入区（rentry section） | 在进入临界区前，每个进程请求许可，实现这一请求的代码区称为进入区 |
| 临界区（critical section） | 进程执行到该区域时可能修改公共变量，特征：只允许一个进程在临界区执行 |
| 退出区（exit entry） | 进程执行完临界区代码后进入退出区 |
| 剩余区（remainder section) | 进程执行其它代码的区域 |
3.2临界区问题解决方案要满足的要求
①互斥（mutual exclusion）:如果进程Pi在临界区内执行，那么其他进程都不能在临界区内执行。
②同步（progress）：如果没有进程在临界区内执行，并且有进程需要进入临界区，那么只有那些不在剩余区执行的进程可以参加选择，以便确定谁能下一次进入临界区，而且这种选择不能无限推迟
③有限等待（bounded wating）：进程等待进入临界区的时间有范围，不会是无限大。
3.3解决临界区问题方法
①抢占式内核（preemptive kerbel）：允许处于内核模式的进程被抢占，处于内核模式的进程会一直运行，直到退出内核模式，阻塞或自愿放弃CPU控制。
②非抢占式内核（nopreemptive kerbel）:不允许处于内核模式下的进程被抢占
3.4.1Peterson解决方案（软件方法）
解释：设置两个进程共享数据项
int turn ;
boolean flag[2];
j=1-i;
两个进程P0和P1
过程
| 我的理解 | 官方解释 |
|---|---|
| ①初始化设置flag[i]也就是flag[0]为true，因为turn等于j等于1-i;所以turn==1；代表flag[0]想要申请进入临界区②此时，如果flag[j]也就是flag[1]等于true的话，并且turn等于1，那么语句就会一直在while循环中空转，<mark>注意，while循环与君判断条件后面是分号</mark>③直到P1退出临界区并执行flag[j]=false后，P0才能进入临界区执行 | 考虑进程P0，一旦它设置flag[0]=true，则P1不能进入临界区。如果P1已经进入临界区，那么flag[1]=true，P0被阻塞不能进入临界区。另一方面，互相阻塞也避免了。假设P0在while里被阻塞了，表示flag[1]为true且turn=1，则此时P1可以执行 |
缺点：1，只适用于两个线程 2，现代计算机体系结构不支持
3.4.2硬件同步（硬件方法）
方法一 —>中断屏蔽方法
进入临界区前执行"<mark>关中断</mark>"指令
离开临界区后执行"<mark>开中断</mark>"指令
缺点：不适用于多处理器（耗时）
方法二–>测试并设置指令
前提：test_and_set()时原子的（执行不可中断）
为每个临界资源设置一个lock，初始为false
解释：当一个临界资源未被使用时，lock等于false，程序可以执行while下面的语句，当lock等于true时，test_and_set(&lock)函数返回值为true，程序在while中空转
3.4.3互斥锁（mutex lock）（软件方法）
互斥锁：一个进程进入临界区时得到锁，在它退出临界区时释放锁，函数acquire()获得锁，函数release()释放锁，每个互斥锁都有一个布尔变量available,它表示锁是否可用
互斥锁实现要求qcquire（）和release（）的调用必须是原子地执行
进程互斥访问示例
缺点：忙等待（busy wating），一个进程在临界区中其他任何进程都必须等待
3.6信号量（semaphore）
信号量S是一个整型变量，它的初始化通过两个标准原子操作wait()和signal(),wait()也叫P操作，signal()也叫V操作
wait（）函数体定义
wati(S)
{
while(S<=0); //忙等待
S--；
}
signal()函数体定义
signal()
{
S++;
}
缺点：不满足让权等待（当进程不能进入自己的临界区时，应立即释放处理机，以免进程陷入“忙等”。）
3.4.5信号量的使用和实现
信号量使用改进(重新定义)
typedef struct
{
int value;
struct process *list;
}semaphore
//每一个信号量都有一个整数value和一个进程链表list，当一个进程必须等待信号量时，就被添加带进程链表，操作signal()从等待进程链表上取走进程，并加以唤醒
wait(semaphore *S)
{
S->value--;
if(S->value<0)
{
add this process to S->list;
block();
}
}
signal(semaphore *S)
{
S->value++;
if(S->value<=0)
{
remove a process P from S->list;
wakeup(P);
}
}
3.4.6死锁与饥饿
死锁：两个或多个进程无限等待一个事件，而该事件这些等待进程之一来完成，这些进程称为死锁
3.5经典同步问题
3.5.1生产者-消费者问题
3.5.2读者-作者问题
3.5.3哲学家就餐问题
3.6管程
管程定义：指关于贡献资源的数据及其在其上操作的一组过程或共享数据结构及其规定的所有操作（没听懂）
管程能够保证在任何时候最多只有一个线程（进程）操作管程中的代码
4进程调度
4.1 CPU-I/O执行周期
进程执行：包括周期进行CPU执行和I/O等待，进程在这两个状态下不断交替，进程执行从CPU执行开始，之后I/O执行，；接着另一个CPU执行，接着另一个I/O执行；
4.1.2 CPU调度程序
当CPU空闲时，操作系统就从队列中选择一个进程来执行并尾气分配CPU。
4.1.3抢占调度
需要CPU调度的四种情况
1，一个进程从运行态到等待状态
2，一个进程从运行状态到就绪状态
3，一个进程从等待状态到就绪状态
4，一个进程终止时
如果调度只发生在第1或4种情况，则调度是非抢占的，否则是抢占的，在非抢占调度下，一个进程在分配到CPU时，会一直运行直到终止或切换状态
4.1.4调度程序
调度程序功能：
1，切换上下文
2，切换到用户模式
3，跳转到用户程序的合适位置，以便重新启动程序
调度程序应尽可能快，调度程序停止一个进程而启动另一个进程所需要的时间称为调度延迟（dispatch latency）
4.2调度准则
| 名称 | 解释 |
|---|---|
| CPU 使用率 | 应使 CPU 尽可能地忙碌。从概念上讲，CPU 使用率从 0% 到 100%。对于一个实际系统，它的范围应从 40%（轻负荷系统）到 90%（重负荷系统）。 |
| 吞吐量 | 如果 CPU 忙于执行进程，那么工作就在完成。一种测量工作的方法称为吞吐量，它是在一个时间单元内进程完成的数量。对于长进程，吞吐量可能为每小时一个进程；对于短进程，吞吐量可能为每秒十个进程。 |
| 周转时间 | 从一个特定进程的角度来看，一个重要准则是运行这个进程需要多长时间。从进程提交到进程完成的时间段称为周转时间。周转时间为所有时间段之和，包括等待进入内存、在就绪队列中等待、在 CPU 上执行和 I/O 执行。 |
| 等待时间 | CPU 调度算法并不影响进程运行和执行 I/O 的时间，它只影响进程在就绪队列中因等待所需的时间。等待时间为在就绪队列中等待所花时间之和。 |
| 响应时间 | 对于交互系统，周转时间不是最佳准则。通常，进程可以相当早地产生输出，并且继续计算新的结果同时输出以前的结果给用户。因此，另一时间是从提交请求到产生第一响应的时间。这种时间称为响应时间，是开始响应所需的时间，而非输出响应所需的时间。周转时间通常受输出设备速度的限制。 |
4.3调度算法
4.3.1先到先服务调度
先到先服务调度（first-Come First_Served,FCFS）
先请求CPU的进程首先分配到CPU，当一个进程进入就绪队列时，他的PCB会被链接到队列尾部，当CPU空闲时，他会分配给队列头部的进程，并且这个运行进程从队列中移除
FSFS策略优点：简单，容易理解
FSFS策略缺点：平均等待时间长
京公网安备 11010502036488号