王道计算机考研 操作系统
P2 操作系统的功能和目标
用户和操作系统是相接的，也是可以直接交互的：因为即使没有安装软件也可以用操作系统干很多事情。
此处的定义划分有三个维度：
①由中间到两边
②由下到上
③由上到下
下面根据三个维度来介绍操作系统的功能和目标：
①作为系统资源的管理者
②作为用户和计算机硬件之间的接口
两种命令接口：
程序接口：
GUI
③作为最接近硬件的层次
总结：
P3操作系统的特征
①并发
并行：
②共享
- 互斥共享
- 同时共享
但是微观上，可能真的是在并行（比如打游戏时听歌，游戏的声音和歌的声音在声音输出设备微观上也是同时进行）
并发VS共享
③虚拟
两个关键词：（第三章）
- 虚拟存储技术
- “空分复用技术”and“时分复用技术”
④异步
总结：
P3操作系统的发展和分类
每一个阶段的优点都是上一个阶段的缺点
①手工操作阶段
②批处理阶段——单道批处理系统
③批处理阶段——多道批处理系统
多道批处理阶段需要多道程序并发进行，需要错做系统来进行管理，标志着操作系统正式形成
为什么多道批处理系统可以增加效率？
④分时操作系统
⑤实时操作系统
⑦其他操作系统
总结
P5 OS运行机制和体系结构
①运行机制
两种指令
代码和指令有什么区别？
指令：CPU能够识别、执行的做基本的命令。
两种处理器状态
CPU的两种状态是由程序状态字寄存器（PSW）某个标志位来表示当前处理器处于什么状态。
两种程序
根据程序是否能使用非特权指令，计算机系统把程序分为两种
小总结
②操作系统的内核
所有的进程切换和调度都是要基于计时功能实现
原子性：程序要么不执行，要么执行完毕
③操作系统体系结构
总结：
P6中断和异常
多道批处理阶段：
引入中断机制，实现多道程序并发执行
本质：发生中断就意味着需要操作系统接入，开展管理工作
【动态过程看视频】
进程1在用户态进行，当CPU收到计时器部件发送的中断信号，切换为核心态进行处理。
将CPU的使用权限交给操作系统，操作系统的内核对中断信号进行处理，OS决定进程1的时间片已经用完，换为进程2运行，然后OS会把CPU的使用权交还给用户进程，进程2就会在用户态下开始进行
★★重要★★
中断的分类：
总结：
P7系统调用
OS是硬件和用户之间的接口，向上层提供服简单易用的服务。
有两种接口：
- 命令接口——允许用户直接使用
- 程序接口（由一组系统调用组成）——允许用户通过程序间接使用
用户进程要使用共享资源，只能通过系统调用对操作系统发出请求，操作系统会对各个请求进行协调管理。
作用：保证系统的稳定性和安全性。
系统调用可以理解为供程序使用的特殊的函数。和我们编程常见的库函数有什么区别呢？
- 应用程序可以通过汇编语言的形式直接使用系统调用。
- 高级语言提供的库函数底层会为我们相应封装一些系统调用的功能，隐藏一些细节，使上层进行系统调用更加方便。
总结：
陷入指令=trap指令=访管指令
P8 进程
程序段存在内存的低地址位置，数据段存在内存的高地址位置
P12进程
OS为每一个进程分配一个PID
OS在背后还记录了进程的其他信息：
- 记录了为进程分配了哪些资源（分配多少内存、正在使用哪些IO设备）
- 记录了进程运行的情况（CPU使用时间、磁盘使用状况）
这些信息会被保存在一个数据结构进程控制块PCB
PCB中存在很多字段
我们只需知道，PCB中存储的都是操作系统对进程进行管理工作所需要的信息
一系列的指令序列就是以.exe格式的文件储存在计算机硬盘中
进程实体可以理解为进程某一时刻的快照，进程实体反映进程某一时刻的状态
进程是进程实体的运行过程，是系统进行资源分配和调度的一个独立单位。
比如，OS就是为每一个进程分配内存等资源，这就是以进程为单位。
PCB是给操作系统的，程序段、数据段是给进程自己用的，与进程自身的运行逻辑有关。
进程的特征
进程是程序的一次执行过程
总结：
在引入线程以后，进程就不再是接收调度的基本单位了，但是进程依然是获得资源的基本单位
P13进程的状态和状态的转换
本小节介绍进程所拥有的的各种状态以及它们在什么情况下进行转换；以及探究进程的组织方式
既然进程2接下来的指令无法继续进行下去，显然我们不应该让进程2一直占用CPU资源。
进程运行过程中可能需要等待某个时间发生的过程，比如：
- 某种系统资源的分配
- 等待其他进程的响应
在这个事件发生之前，进程无法继续执行下去，操作系统会让这个进程下CPU，进入“阻塞态”
当进程等待的资源获得时，操作系统就会让被阻塞的进程回到就绪态，这个进程就再次拥有了处理机运行的条件。
进程的结束：进行可以执行exit系统调用请求OS终止该进程。此时进程会进入“终止态”。
终止态产生的响应的行为：
- OS会让进程下CPU
- OS回收内存空间等资源，最后还要回收PCB
当终止进程的工作完成以后，进程就彻底消失了
总结一下进程状态转换的过程：
- 创建态
- 就绪态
- 运行态
- 阻塞态
- 终止态
进程五状态模型：
有的时候可以直接由运行态转换到就绪态，比如：
- 操作系统给运行态分配的时间片用完以后（时钟中断，进程本来在CPU上运行，CPU突然收到一个时钟中断的信号，进程就会被剥夺CPU的使用权）
- 处理机被抢断
OS 是如何记录进程的状态呢？
PCB中有一个状态字state
为了对同一个状态下进程进行统一管理，OS会将各个进程的PCB组织起来。
接下来探讨的就是进程的组织的问题。
链式方式
OS会管理一系列的队列，每个队列都会指向相应状态的进程PCB
索引方式
OS会给各种状态的进程建立相应的索引表，每一个索引表项又会指向相应的PCB
但是，大部分的OS都是使用的链式方式
P14进程控制
简单来说，进程控制就是实现进程状态转换
如何实现进程控制？
用原语来实现。
原语要求一气呵成，进程的控制通过原语来实现，也需要一气呵成。那为什么进程的控制要一气呵成呢？
如果不能一气呵成，就有可能出现OS中某些关键数据结构信息不统一的情况，这会影响OS进行别的管理工作。
刚好原语这种特殊的程序具有一气呵成，不能被中断的性质，所以就可以用原语这样的程序来实现一气呵成的功能。
那为什么原语不可中断呢？这是如何实现的呢？
通过“开中断指令”和“关中断指令”
CPU每进行完一条指令，都会检查是否有中断信号要进行处理。如果有，则暂停当前这段程序，转而执行相应的中断处理程序。
“开中断”和“关中断”都是特权指令，不允许普通的用户程序使用，只能让内核程序使用。
接下来讨论进程控制相关的原语。
①创建原语：创建一个进程时使用的原语。
首先，申请空白PCB（PCB是进程存在的唯一标志）。
为新进程分配所需资源。
初始化PCB。
将PCB插入就绪队列。
至此，进程由创建态进入到就绪态。
下面是一些典型的会创建进程的事件。
下面是将进程转换到终止态的撤销原语。
关于父进程与子进程：
常见的引起进程中止的事件：
P15进程通信
进程间通信(Inter-Process Communication,IPC)是指两个进程之间产生数据交互。
为什么进程通信需要操作系统的支持？
各个进程的地址空间是相互独立的，各个进程只能访问自己的内存地址空间（这么做是出于安全的考虑）。
方式一：共享存储
如果使用共享存储的方式，必须要保证对共享存储的访问是互斥的。
基于数据结构的共享：
基于存储区的共享：OS只是在内存中划出共享区域。数据的组织形式、存放位置都是由通信进程控制。
方式二：消息传递
直接消息传递
进程Q有一个消息队列
P进程在自己的空间构造
间接消息传递
P16线程
传统意义上，进程是程序的一次执行，无法实现一个进程同时处理很多事情。
传统的进程是程序执行流的最小单位。
人们有引入线程机制增加系统的并发度。
没有引入线程之前，一个进程对应一份代码，只能顺序地依次往下执行。
引入线程之后，每个进程可以有多个线程，各个线程有各自不同或者相同的代码。这些代码都会并发地被CPU处理，也会并发地依次处理下去。
引入线程以后，进程不再是CPU调度的基本单位。进程只作为除CPU之外的系统资源的分配单元。
引入线程机制以后，有什么变化？
线程有哪些属性？
线程只是处理机调度的基本单位
线程基本不拥有系统资源，而是共享进程的资源（包括内存地址空间）。也正是共享内存地址空间，同一进程中的线程间的通信甚至无需系统干预，系统开销也很小。同一进程中线程切换不会引起进程切换，不同进程线程切换会引起进程切换。切换线程系统开销很小，切换进程系统开销很大。
P17线程的实现方式和多线程模型
进程是资源分配的基本单位
从线程的角度看，线程其实就是一段代码逻辑。
1、线程的管理工作是由谁来完成的？
应用级线程的管理是由线程库来完成的，并不是操作系统来完成的。
2、线程切换是否需要CPU变态？
从代码上看，并不涉及请求操作系统服务，切成切换的管理是由线程库这样的应用程序自己完成的，在用户态下就能实现。
3、操作系统是否能意识到用户级线程的存在？
OS只能意识到进程的存在，意识不到进程内部的线程的。
4、优缺点
优点：用户级线程的切换在用户空间即可完
成，不需要切换到核心态，线程管理的系统
开销小，效率高
缺点：当一个用户级线程被阻塞后，整个进
程都会被阻塞，并发度不高。多个线程不可
在多核处理机上并行运行。
在用户级线程的条件下，CPU调度的基本单位依然是进程。进程只能被分配一个核心，因此这些线程并不能并行运行。
内核级线程：OS层面也可以看到线程
根据用户级线程和内核级线程的映射关系，可以划分为几种多线程模型
OS只是看得见内核级线程。因此，只有内核级线程超市处理机分配的单位。
回顾
P18线程的状态与转换
程序计数器：指明线程执行到哪里了
线程状态切换的时候，
下处理机：将线程的PC存入TCB中
上处理机：从PCB中取出PC的值放回PC寄存器中
线程表：将多个线程的TCB组织起来形成线程表
P19调度的概念和层次
调度：
一堆任务要处理，资源有限，确定某种规则来决定处理这些任务的顺序。
作业：一个具体的任务
用户向操作系统提交一个作业≈用户让OS处理一个任务（让OS启动一个程序）
暂时调到外存等待的进程状态为挂起状态。
低级调度——处理机调度
中级调度——内存调度
高级调度——作业调度
七状态模型：
挂起：进程映像调到外存
阻塞：进程映像还在内存中
P20进程调度的时机、切换和过程、方式
P22调度算法评价指标
P23
进程调度算法
短作业优先：
P26 进程同步与进程互斥
并发执行的进程有异步性。
有时我们必须保证进程是按我们想要的推进顺序来执行的，操作系统就需要提供进程同步的机制来实现这样的需求。
同步要解决的问题就是如何解决进程异步的问题。
同步亦称直接制约关系（进程间有直接的合作），指的是为完成某些任务而建立的多个进程需要协调工作次序而产生的制约关系。
资源的共享方式：
- 互斥共享方式
- 同时共享方式
我们把一段时间内只允许一个进程使用的资源称为临界资源。
进程互斥，间接制约关系（进程间没有直接的合作关系）
简称互斥的四个逻辑部分
- 进入区：检查是否可以进入临界区，若可以进入则上锁（加上正在访问临界资源的标志）。
- 临界区：访问临界资源的那段代码要放解除正在访问临界资源的标志）
- 剩余区
总结
P27进程互斥的软件实现方法
单标志法：
问题：是依次交替轮流使用。如果轮到对方来访问临界区，但是对方又不访问，就会出现临界区空闲，但又不允许p1访问的情况。
违背了“空闲让进”的原则
双标志先检查法：
看起来没有问题，但是当这两个进程并发执行的时候，就会出现问题。
按照1、5、2、6的顺序来执行的话，就会发生奇怪的事情。
问题：进入区的检查和上锁，两个处理不是一气呵成的。检查之后，上锁之前可能会发生进程切换。进而会出现两个进程都进入临界区的情况。违反了“忙则等待”的原则。
双标志后检查法：
Peterson算法
总结
P28进程互斥的硬件实现方法
- 不适用于多处理机，关中断指令只对执行关中断指令的处理机有用
- 不适用于用户进程，只能运行在操作系统内核态
总结：
P29互斥锁
多处理器的情况下，自旋等待的代价反而会很低
P30信号量机制
- 信号量是一种变量，用来表示系统中某种资源的数量
- 可以用系统提供的一对原语wait和signal来对信号量进行操作（简称PV操作）
wait的过程：
- 先表示想要消耗一个资源
- 如果没有资源了，则使用block原语将进程从运行态送进阻塞态；并把该进程挂入阻塞队列
signal的过程：
- 释放资源，value+1
- 如果还有进程等待这种资源（阻塞队列中还有进程），则使用wakeup原语唤醒等待队列中的一个原语，使其进入就绪态
整体过程：
信号量机制遵循了让权等待原则，（一个进程会使用block源与自我阻塞，主动放弃处理机）
总结：
P31用信号量机制实现进程的同步和互斥
用信号量机制实现进程的互斥
信号量表示资源的数量，互斥信号量mutex表示“进入临界区的名额”
- 划定临界区：哪一段代码是用来访问临界区资源
- 设置互斥信号量mutex（进临界区对mutex执行P操作，出临界区对mutex执行V操作）
注意：
- 要会自己定义记录型信号量，默认使semaphore
- 对于不同的临界资源，需要设置不同的互斥信号量
- PV操作必须成双成对（缺少p操作，就无法保证各个进程互斥的访问临界资源；缺少v操作，就会导致某些进程被阻塞以后一直无法被唤醒）
用信号量机制实现进程的同步
进程的同步：由于进程同步具有异步性，有时为了完成某一特定任务，需要进程按照特定的顺序来互相配合，有序推进。
刚开始设置P=0表示并没有这种资源。
在前操作之后执行V操作，早后操作之前执行P操作，只有先执行V（还有进程在等待这种资源，执行wakeup语句，唤醒阻塞队列中的一个进程）操作释放资源才能执行P操作之后的代码，这就保证了执行代码的顺序。
更复杂的情况：信号量机制实现前驱关系
总结
以上都是进程同步和互斥的理论，从下一讲开始会介绍几个经典的进程同步和互斥问题
P32 生产者消费者问题
缓冲区是临界区资源，各进程必须互斥地访问。
生产者、消费者共享一个初始为空、大小为n的缓冲区。
full：产品的数量（非空缓冲区的数量）缓冲区刚开始都是空的，设置full=0
empty：空闲缓存区，初始时全是空闲的，empty=n
mutex：“互斥信号量”，由于缓冲区为临界资源，各个进程必须互斥的访问，初始设为1
实现互斥的PV锁是在同一进程中进行；
实现同步关系的PV操作是在两个进程中实现的。对于full变量，现在生产者中执行V操作，增加一个产品；再在消费者那里执行P操作，消耗一个产品。
实现互斥的P操作一定要在实现同步的P操作之后，否则可能引起死锁；
V操作不会导致进程阻塞，因此两个V操作顺序可以互换。
生产者生产一个产品和和消费者使用产品这两个步骤可否放入临界区？
可以是可以，但是会导致一个进程对临界区上锁的时间增长，这样将不利于各个进程交替使用临界区资源。所以要让临界区的代码尽可能的短。
P33多生产者和多消费者问题
“多”：多类（不同生产者和消费者生产和消费的东西是不一样的）
先分析存在哪些互斥和同步关系：
互斥关系：对缓冲区（盘子）的访问要互斥
同步关系（先后顺序）：
1.先放后取
- 父亲先将苹果放入盘子后，女儿才能取苹果。
- 母亲将橘子放入盘子后，儿子才能取橘子。
2.儿子或女儿将盘子拿空以后，父亲或母亲才能放入水果。
确定PV操作大致顺序
实现互斥：在访问临界资源前后分别执行P操作和V操作
实现同步：前V后P
设置信号量
互斥关系设置初值为1的信号量（mutex=1）
apple=1；orange=0
plate=1
可不可以不要互斥信号量？
三个变量同一时刻最多只有一个能是1，因此任何时刻最多只有一个进程不会被阻塞
P38死锁
死锁产生的必要条件
什么时候会发生死锁？
死锁的处理策略：
见下一节
P39 死锁的处理策略——预防死锁
互斥条件：对互斥资源的争抢才会导致死锁。
P42内存
※如何实现逻辑地址到物理地址的转换
程序执行前需要先放到内存中才能被CPU处理
问题：程序的数据都存放在内存中，那该如何区分各个程序的数据存放在什么地方呢？
方法就是，进行编号。
每个存储单元的大小取决于计算机是按什么来编址。（按字编址、按字节编址）
默认进程相关内容从#0开始连续存放，指令中的参数直接给出变量的实际存放地址（物理地址）
但是如果不是从地址#0开始存放（逻辑地址），会影响指令的执行吗？
三种策略解决绝对地址和相对地址转化的问题
方法一：绝对装入
这种方式的灵活性很低（可移植性很低，在一台电脑上物理地址开始的地方不是另一台电脑上物理地址开始的地方）
方法二：可重定位装入
静态重定位
编译链接后的模块儿地址还是从0开始，模块装入内存时进行重定位
这种方式的特点是：
- 给作业分配的内存空间必须是连续的，而且是一次性分配全部需要的内存空间；
- 必须一次性装入
- 作业一旦进入内存，运行期间不能再移动。
动态重定位（现代操作系统使用的方法）
如果一个系统支持动态重定位，还需要一个重定位寄存器的支持。
刚开始往重定位寄存器中存放模块存放的起始地址。
CPU在对一个内存地址进行访问的时候，会把逻辑地址和重定位寄存器中存放的模块起始地址进行相加。
动态重定位是进程中的数据，在运行过程中发生移动是很方便的。（比如如果想让数据从200开始，只需要让重定位寄存器中的值改为200）
动态重定位具有很多优点：
（在之后学习过虚拟存储管理之后，就对这些性质有深入理解）
接下来从一个更宏观、更全局的角度来描述从写程序到程序运行的过程。
通过编译将源代码编译成若干个目标模块（即把高级语言翻译为机器语言）
目标模块中已经包含了代码所对应的指令。每一个模块的地址都是相互独立的逻辑地址
各个目标模块进行链接以后，就形成了装入模块（.exe）。装入模块具有完整的逻辑地址。
刚刚我们讲的逻辑地址到物理地址的转换就是在装入过程中发生。
接下来要介绍三种链接的方法：
采用动态链接的方法时，用到某一个模块儿时，才需要把某个模块调入内存。还需要用到其他模块的时候，在装入的过程中同时进行链接。整个都用不到的模块儿可以不装入内存。
P43内存的管理
问题提出：
- 操作系统该怎么管理哪些内存区域已经被分配出去，哪些还在空闲状态呢？
- 有很多空闲位置时，如果有一个新的进程想要放入内存当中，该放入什么位置呢？
- 一个进程运行结束之后，进程占用的内存空间应该如何回收呢？
1、因此操作系统要做的第一件事情就是负责内存空间的分配与回收。
2、操作系统需要提供某种技术，从逻辑上对内存空间进行扩充——虚拟技术
3、操作系统需要提供地址转换的功能，负责程序逻辑地址与物理地址的转换。
4、操作系统需要提供内存保护的功能。保证各个进程在各自存储空间内运行，互不干扰。
界地址寄存器：存放进程的最大逻辑地址。
重定位寄存器（基地址寄存器）
界地址寄存器（限长寄存器）
总结：
P45连续分配管理方式
（分配：具体见下一节）
内存的回收：
相邻合并
P46动态分区分配算法
P47 分页存储管理
页框/页帧/内存块/物理块：内存空间被分成的一个个大小相等的分区
页/页面：将进程的逻辑地址分为与页框大小相等的一个个部分
进程的页面与内存的页框有一一对应关系
那OS是怎么记录这种一一对应关系的呢？
