操作系统

第一章

操作系统的概念、功能和目标

1. 操作系统的概念：

   

   操作系统是指控制和管理整个计算机系统的硬件和软件资源，并合理地组织调度计算机的工作和资源的分配。（要注意操作系统也要管理硬件资源，不只是管理软件资源，比如操作系统要管理软件即应用程序占用CPU等，相当于是要管理CPU，操作系统能够管理硬件，能够管理应用程序这种软件！！）

   

   并且操作系统给上层用户和其他应用软件提供方便的接口和环境，操作系统是计算机系统中最基本的系统软件。

   操作系统负责管理和协调硬件软件资源。

2. 进程是一个程序的执行过程，执行前需要将该程序放到内存中，才能被CPU处理

   放到内存中的程序，可以理解为进程。程序是静态的，就是存放在硬盘上的静态代码，就叫做程序，要让程序跑起来，需要通过CPU，或者说，需要CPU来对这个程序进行处理，即通过CPU让这段程序跑起来，那么这个程序会放到内存中，才能被CPU进行处理，也就是“跑起来”。

3. 操作系统的功能和目标：

   • 操作系统作为**系统资源（硬件资源和软件资源）**的管理者：

     • 处理机管理

       进程需要等待CPU资源的分配

     • 文件管理

     • 设备管理

     • 存储器管理

   • 操作系统作为用户和计算机硬件之间的接口：

     • 命令接口

       允许用户直接使用

       • 联机命令接口
       • 脱机命令接口

     • 程序接口

       允许用户通过程序间接使用

       系统调用

     • GUI---图形用户界面

       现代操作系统中最流行的图形系统。

   • 操作系统作为最接近硬件的层次，需要在纯硬件的基础上实现什么功能：

     实现对硬件机器的拓展

     操作系统是软件，是系统软件。

4. 操作系统作为用户和计算机硬件之间的接口

   用户接口

   • 命令接口

     • 联机命令接口

       用户说一句，系统做一句

       联机命令接口 = 交互式命令接口，例如windows系统中的命令行。

     • 脱机命令接口

       用户说一堆，系统做一堆

       相当于是批处理命令接口。

   • 程序接口

     由一组系统调用组成，只能通过用户程序间接使用。

     在大多数情况下，程序接口和系统调用两个名词是相等的。

操作系统的四个特征

1. 操作系统有并发、共享、虚拟、异步这四个特征。

   其中并发和共享是两个最基本的特征，二者互为存在条件。

并发

1. 指两个或多个事件在同一时间间隔内发生，这些事件宏观上是同时发生的，但微观上是交替发生的

   并行：

   指两个或多个事件在同一时刻同时发生。

2. 一个单核处理器（CPU）在同一时刻只能执行一个程序，因此操作系统会负责协调多个程序交替执行，这些程序微观上是交替执行的，但是在宏观上看起来像是同时执行（并行）。

   这就是并发，微观上是交替执行，宏观上是并行执行，并行即同时。

   所以并不是采用多线程的方式就一定执行效率更高，执行更快，因为如果是单核CPU，那么在微观上仍然是并发执行，交替执行的，并不是真正意义上的并行执行，如果单核CPU采用多线程执行任务的方式，还存在线程的上下文切换，系统的资源限制和死锁等问题，造成多线程反而比单线程更慢。

   如果是多核CPU那么， 多线程在微观上才是真正意义上的并行执行。

   CPU密集型，那么并不是线程越多越好，因为相当于并不存在CPU会空闲的状况，所以线程数等于CPU核心数就可以，如果是IO密集型，那么就会出现大量CPU空闲的时间，为了提高CPU的执行效率，可以采用更多的线程数（CPU核心数的两倍）。

3. 即使有多核CPU，但是操作系统的并发性依然必不可少！！除非有多少核心，就只有多少任务数，那么就只需要多少个线程就能处理了，达到真正的并行，但是任务数或者线程数比核心多是很常见的情况。（在这种场景下，将线程和任务认为是一个东西是没有问题的，在Java线程池的部分，线程和任务不要认为是一个东西，任务本质是实现了Runnable或者说Callable接口的实现类对象，任务是要交给线程来执行的，如果线程达到核心线程数量的最大值，那么会去检查任务阻塞队列是否满，如果未满，则新任务会添加进阻塞队列，如果已满，再检查此线程池的最大线程数，如果未达到最大线程数，将此任务交给非核心线程执行，非核心线程是有存活时间的，如果已达到最大线程数，说明没有多的线程能够执行此任务，那么会执行拒绝策略。）

4. CPU有4个核心，意味着可以并行地执行4个任务，但是计算机同时运行超过4个任务的情况是存在的。所以并发必不可少，也就是微观上的并发执行，任务并发地占用CPU资源这种情况必不可少。

共享

1. 共享即资源共享，分为同时共享和互斥共享。

   共享是指系统中的资源可供内存中多个并发执行的进程共同使用。

2. 互斥共享：

   系统中的某些资源，虽然可以提供给多个进程使用，但一个时间段内只允许一个进程访问该资源。

   使用QQ和微信视频，同一时间段内摄像头只能分配给其中一个进程。

   同时共享：

   系统中的某些资源，允许一个时间段内多个进程“同时”对他们进行访问（宏观上是同时的）

   所谓的同时往往是宏观上的，而在微观上，这些进程可能是交替地对该资源进行访问的。微观上交替就是并发。（同时共享，微观上多个进程可能是真的同时访问资源）

3. 并发性是指计算机系统中同时存在着多个运行着的程序，这些程序在微观上是由CPU交替执行的（比如单核cpu，但是采用多线程的方式执行任务，那么就会出现微观上并发，宏观上并行）

   共享性是指进程可以同时访问系统资源，可以是一段时间段内只有一个进程能够访问，这叫互斥共享，可以是一段时间端内多个进程同时访问，这是同时共享。

   如果失去并发性，则系统中只有一个程序正在运行，则共享性失去存在的意义

   如果失去共享性，则多个进程不能同时访问硬盘资源，就无法实现同时发送文件，也就无法并发。

   所以共享性和并发性是相互依存的。

虚拟

1. 虚拟是指把一个物理上的实体变为若干个逻辑上的对应物，物理实体是实际存在的，而逻辑上对应物是用户感受到的。

   虚拟技术中的空分复用技术---虚拟存储器技术

   

2. 虚拟技术的时分复用技术---虚拟处理器技术

   

   处理器把大的时间段分为各个很小的时间片，通过时间片轮转的机制，交替为各个进程服务，这是时分复用技术，也就是虚拟处理器技术，而空分复用技术是虚拟存储器技术。

3. 显然，如果失去了并发性，则一个时间段内系统只需运行一道程序，那么就失去了实现虚拟性的意义了，因此没有并发性就谈不上虚拟性。

异步

1. 异步是指，在多道程序环境下，允许多个程序并发执行，但由于系统资源有限，进程的执行不是一贯到底的，而是走走停停，以不可预知的速度向前推进，这就是进程的异步性。

   因为并发，因为共享，多个进程同时访问某个系统资源，所以异步，不可预知的速度推进，如果同步，那么一个进程访问完此系统资源之后，才能另一个进程访问这个系统资源，接着下一个进程，这就是同步，速度是可预知的，没有共享性，没有并发，一个执行完之后下一个才执行。（这里的系统资源可以理解为CPU时间片。）

   显然，如果失去了并发性，那么系统只能串行地处理各个进程，虽然因为并发，进程在微观上仍然是被CPU串行处理的，但是有上下文切换，有程序计数器保存下一条字节码指令的执行地址，并不是一个进程完全执行完之后才会执行另一个进程，这涉及到CPU对多线程的执行策略，比如时间片轮转机制。但是串行就指的是一个进程执行完之后再执行另一个进程。

   只有系统拥有并发性，那么虚拟，共享，异步才有意义。因为正是因为并发性，使得共享性有意义，对系统资源的共享（比如CPU时间片），同时由于系统资源的限制，导致多个进程是走走停停（微观上仍是串行，但是是通过上下文切换），以不可预知的速度向前推进，导致了异步性。

   如果没有并发性，那么就是某个进程完全执行完之后（因为没有并发性！！），执行下一个进程，这就是同步的，不可能会导致异步性。一个进程的执行必须完全等上一个进程完全执行完之后才可以执行，因为没有并发，意味着没有宏观上的并行执行，必须一个接一个。

2. 如果进程由于没有获得某个需要的系统资源，导致进程无法执行，则进程会阻塞，直到获得系统资源，进程被唤醒，进入就绪状态，获得CPU时间片之后，进程继续执行。

3. 没有并发和共享，就谈不上虚拟和异步，因此并发和共享是操作系统两个最基本的特征。

操作系统的发展和分类

1. 计算机可以识别的是二进制的机器码，计算机只能之别0和1二进制数。

2. OS的发展和分类

   

3. 手工操作阶段

   主要缺点：用户独占全机，人机速度矛盾导致资源利用率低。

4. 单道批处理系统

   引入脱机输入、输出技术（用磁带完成），并监督程序负责控制作业的输入、输出。

   主要缺点：内存中仅能有一道程序运行，只有该程序运行结束之后，才能调入下一道程序，CPU有大量的时间是在空闲等待IO完成，资源利用率依旧很低。从这里可以看出，单道批处理系统的缺点就是不采用多线程的缺点或者说是系统不能并发执行进程，只能串行执行进程的缺点，导致CPU大量时间处于空闲状态，因为线程或者说进程正在执行IO操作，那么会阻塞，此时CPU处于空闲状态，因为进程或者线程阻塞了，CPU不能去执行别的线程或者进程或者任务，因为，串行执行！！所以要采用多线程，或者说要多线程的好处、并发执行程序的好处，就是让提高CPU的利用率，以免当某个进程IO阻塞的时候，CPU能够执行另一个进程或线程而不是处于空闲状态，提高了利用率，提高了系统的吞吐量。

5. 多道批处理系统

   主要优点：多道程序并发执行，共享计算机资源，资源利用率大幅提升，CPU和其他资源保持忙碌状态，提高了CPU执行效率，系统吞吐量增大。这就和前面说的单线程的缺点相对应，如果是单线程执行任务，如果执行了IO并阻塞，那么线程阻塞，CPU也只有跟着等待，如果是多线程，CPU可以把时间片分给别的线程，去执行别的任务，提高CPU的执行效率，不让CPU空闲等待，增大了系统吞吐量。

   Redis是采用单线程，就是因为redis所有操作都在内存范围内，不涉及内存和磁盘之间的IO，所以不存在线程会由于IO而阻塞的情况，CPU也不会因为线程阻塞而等待，也不需要多线程来提高系统的吞吐量。

6. 单道批处理技术

   

   多个程序串行执行，串行工作。

   多道批处理技术是多道程序并发执行。（但是并不是时间片轮转，而是一个进程的某项任务执行完之后，CPU再去执行另一个进程。）

   

   使系统资源利用率大幅度提升

   不同进程在各自的某些阶段，能够进行并行的工作，所以提高了系统资源利用率。

7. 分时（时间片）操作系统：

   计算机以时间片为单位轮流为各个用户/作业服务，各个用户可通过终端与计算机进行交互

   主要缺点：

   不能优先处理一些紧急任务，操作系统对各个用户/作业是完全公平的，循环地位每个用户/作业服务一个时间片，不区分任务的紧急性。（在这种场景下，任务和线程可以理解为同样的。）

8. 实时操作系统：

   优点：能够优先响应一些紧急任务，某些紧急任务不需时间片排队。

   在实时操作系统的控制下，计算机系统接收到外部信号后及时进行处理，并且要在严格的时限内处理完事件。实时操作系统的主要特点是及时性和可靠性。

   硬实时系统：必须在绝对严格的规定时间内完成处理

   软实时系统：能接收偶尔违反时间规定。

9. 

操作系统的运行机制和体系结构

运行机制

1. 指令：

   特权指令：如内存清零指令，不允许用户程序使用

   非特权指令：如加减乘除指令

   问题：CPU如何判断当前是否是可以执行特权指令？

   就是通过CPU的状态，CPU有两种状态，用户态和核心态。

2. 高级语言代码需要经过“翻译”得到机器语言指令或者说机器码，这是计算机能够识别的二进制码。这个过程在Java中是编译，但是不完全等同，因为Java是在JVM基础上运行，Java这种高级语言首先需要经过编译得到字节码文件，字节码也是二进制码，但是不等同于机器码。

   字节码虽然是二进制的，字节码文件是二进制文件，但是字节码并不能够直接运行在操作系统之上，因为字节码指令并非等价于能够被CPU所识别的机器指令（机器码），字节码文件内部包含的仅仅是一些能够被JVM识别的字节码指令、符号表，以及其他辅助信息

   那么，想让一个Java程序运行起来，JVM中执行引擎的任务就是将字节码指令解释、编译成为对应平台上的本地机器指令才可以，简单来说，JVM中的执行引擎充当了将高级语言翻译为机器语言的译者

   执行引擎部分有JIT即时编译器，还有解释器，还有垃圾回收器，其中解释器就是解释字节码指令并执行，JIT即时编译器就是将字节码指令再翻译成机器指令或者说机器码，这个机器指令是能够被计算机、CPU、或者说操作系统识别的二进制码（虽然字节码是二进制码，但是不能被操作系统识别，是能够被JVM识别，这是Java编程语言的特性），JIT即时编译器的作用就是将字节码翻译成机器码，这是一个二次编译的过程，也就是说第一次编译是从Java高级语言到字节码文件，第二次编译是在JVM的执行引擎，将字节码翻译成机器码。

3. 一条高级语言的代码翻译过来可能回对应多条指令

   

   简单来说，“指令”就是处理器（CPU）或者广义上说操作系统能识别、执行的最基本指令。

   比如：加法指令就是让CPU进行加法运算

4. 两种处理器状态：

   用户态（目态）：此时CPU只能执行非特权指令

   核心态（管态）：此时CPU可以执行特权指令和非特权指令

   用程序状态字寄存器PSW中某标志位来标识当前处理器处于什么状态，如0为用户态，1为核心态。

   有的程序需要使用特权指令，有的程序只能使用非特权指令。

5. 两种程序：

   内核程序：操作系统的内核程序是系统的管理者，既可以执行特权指令，也可以执行非特权指令，运行在核心态。

   应用程序：为了保证系统能安全运行，普通应用程序只能执行非特权指令，运行在用户态。

操作系统内核

1. 

   特权指令需要在核心态执行

   非特权指令既可以在核心态执行，也可以在用户态执行

   需要使用特权指令的程序称为内核程序

   只能使用非特权指令的程序称为应用程序

2. 操作系统最接近硬件的层次是操作系统内核

   另一部分是非内核功能，所以可以把操作系统分为内核功能和非内核功能

   

   原语是一种特殊的程序，是最接近硬件的部分，这种程序的运行具有原子性。

3. 内核是计算机上配置的底层软件（操作系统本身是系统软件，又分为内核和非内核两部分），是操作系统最基本最核心的部分，而实现操作系统内核功能的程序就是内核程序。

   

操作系统体系结构

1. 有的操作系统并不把对系统资源进行管理的功能划分为内核功能

   如果把对系统资源进行管理（处理器管理、存储器管理、设备管理、文件管理）的功能也划分为内核功能，则称这个内核是大内核

   如果不把系统资源管理功能划分为内核功能，则称内核是微内核。

2. 

   大内核的优点就是性能高，主要功能模块都运行在核心态，减少了处理器在核心态和用户态之间的切换！

   微内核：核心态只负责最核心的一些工作，优点是组织结构清晰，方便维护，缺点是效率低，因为微内核，并不是许多主要功能模块都在核心态，所以需要经常进行核心态和用户态之间的切换，导致效率低。

3. 操作系统内核功能或者说内核程序一定是运行在核心态。

4. 特权指令只能在核心态下执行

   内核程序只能在核心态下执行

中断和异常

中断机制的诞生

1. 早期的计算机中，各个程序只能串行执行，就是单道批处理系统，同一时刻，处理器只能处理一道程序，系统资源利用率低

   引入中断机制，实现了多道程序并发执行

   本质：发生中断就意味着需要操作系统介入，开展管理工作

2. CPU切换为核心态，对中断信号进行处理

   处理完后，再切换为用户态，执行进程

3. CPU可能会收到计时部件发送的中断信号，通知CPU现在已经过了一个时间片了，当CPU收到中断信号，那么CPU会立即切换到核心态（用户态和核心态是说的CPU状态），然后把CPU的使用权限交给操作系统，操作系统的内核就会开始对中断信号进行处理，操作系统内核发现刚才的中断信号是告诉CPU时间片已到，那么操作系统会进行进程1和进程2之间的切换，进程1的时间片用完，换进程2执行，在完成这一系列的管理工作后，操作系统会把CPU的使用权交给用户进程，接下来进程2就会获得CPU时间片，CPU也由核心态切换回了用户态，进程2在用户态下进行执行。

   

   

   

   

   

   ​ 进程2在用户态下执行

中断的概念和作用

1. 当中断发生时，CPU会立即进入核心态

   当中断发生后，当前运行的进程暂停运行，并由操作系统的内核对中断信号进行处理

   对于不同的中断信号，会进行不同的处理

   发生中断，由于操作系统的管理工作（比如进程切换、分配IO设备等）需要使用特权指令，因此CPU要从用户态转为核心态。

   中断可以使CPU从用户态切换为核心态，使操作系统获取计算机的控制权，有了中断，才能实现多道程序并发执行。

2. CPU用户态--核心态是通过中断实现的， 并且中断是唯一途径

   核心态到用户态的切换，是通过执行一个特权指令（因为核心态下本来就可以执行特权指令），将程序状态字的标志位设置为用户态

中断的分类

1. 内中断（异常、例外、陷入）

2. 外中断，也可以简单地称之为中断

3. 内中断和外中断的本质区别在于中断信号的来源是CPU的内部还是外部

   内中断的发生和当前CPU执行指令是有关系的，外中断的发生和当前CPU执行指令是没有关系的（比如说打印机在完成输出工作之后，向CPU发送的外部中断信号）。

4. 

5. 另一种分类方式

   

外中断的处理过程

1. 执行完每个指令之后，CPU都要检查当前是否有外部中断信号
2. 如果检测到外部中断信号，则需要保护被中断进程的CPU环境（如程序状态字PSW，程序计数器PC、各种通用寄存器），可以大致理解为要保存进程当前的一些中间结果，以便恢复之后，还可以从当前状态继续往下执行，可以理解为多线程环境下线程之间的上下文切换，程序计数器的作用就是保存下一条要执行的字节码指令的地址，所以程序计数器需要保存这个地址，用于上下文切换。
3. 根据中断信号类型转入相应的中断处理程序（内核程序，运行在CPU核心态，这是肯定的，因为中断发生时，CPU会立即进入核心态）
4. 恢复原进程的CPU环境并执行特权指令退出中断（设置程序状态字PSW的标志位），返回原进程继续往下执行。

系统调用

概述

1. 操作系统作为系统软件，管理系统资源，面向上层，对用户提供命令接口，对程序提供程序接口（其实也可以理解为对用户），程序接口就是一组系统调用组成

   可以把系统调用理解为操作系统提供给应用程序（程序员或编程人员）使用的接口，可以理解为一种可供应用程序调用的特殊函数，应用程序可以发出系统调用请求来获得操作系统的服务。

2. 操作系统为什么要提供系统调用功能？

   如果用户进程想要使用系统资源，那么通过操作系统提供的系统调用，比如用户继承想要使用打印机这种共享资源，只能通过系统调用对操作系统发出请求，操作系统会对各个请求进行协调管理

   系统调用就是程序接口，用户进程通过一组系统调用即程序接口，使用某个系统资源，因为是系统资源，所以系统调用后，CPU进入核心态，把控制权交给操作系统，操作系统对请求进行协调管理

   系统调用后，CPU会进入核心态，这是自愿中断，也就是内中断，与CPU当前执行的指令有关，是系统调用使用的访管指令或者陷入指令。

3. 什么是系统调用？

   应用程序通过系统调用请求操作系统的服务，系统中的各种共享资源都由操作系统同一掌管，因此在用户程序中，凡是与资源有关的操作（如存储分配、IO、文件管理等），都必须通过系统调用的方式向操作系统提出服务请求，由操作系统代为完成（系统调用后，CPU会进入核心态，系统调用会使用访管指令或者说陷入指令），因为操作系统就是管理系统资源的，包括硬件资源和软件资源，这样可以保证系统的稳定性和安全性。

系统调用分类

1. 

   系统调用相关处理涉及到对系统资源的管理，对进程的控制，这些功能需要执行一些特权指令，因此系统调用相关处理需要在核心态下进行。

系统调用与库函数的区别

1. 库函数的底层封装一些系统调用功能

   

   

   

系统调用背后的过程

1. 

   write这个库函数，就涉及到了系统调用。

   当执行陷入指令之后，CPU的控制权会交给操作系统，陷入指令就是访管指令，核心态就是管态。这属于系统调用，执行陷入指令，是内中断。

   很好理解，系统调用，就是会通过操作系统来执行一些功能，必定会进入核心态，而用户态到核心态只有一种方式，就是中断，系统调用会通过访管指令，实现内中断。

   内中断分为自愿中断（也叫做指令中断，也就是系统调用时使用的访管指令）、硬件故障（缺页）、软件中断

   内终端又分为陷入、故障和终止。

   自愿中断（访管指令引起的指令中断）属于陷入，缺页属于故障，软件中断比如整数除0属于终止。

2. int指令的参数x指明了系统的调用号，此处的int不是整数的意思，其实是interrupt的缩写

   

   传递系统调用参数 ----> 执行陷入指令（用户态）------> 执行系统调用相应服务程序（核心态）-----> 返回用户程序

   系统调用会使用访管指令（陷入指令），从而使CPU切换到核心态

3. 注意：

   • 陷入指令是在用户态执行的，执行陷入指令之后，立即引发一个内中断，这属于自愿中断，从而CPU进入核心态
   • 发出系统调用请求是在用户态，而对系统调用的相应处理，是在核心态下进行。
   • 陷入指令是唯一一个只能在用户态执行，而不可再核心态执行的指令。因为陷入指令即访管指令的目的就是进入核心态。
   • 凡是与资源（系统资源、共享资源）有关的操作、会直接影响到其他进程的操作，一定需要操作系统介入（需要操作系统来调度，来对请求协调管理），即需要通过系统调用来实现。

第二章

进程

进程的定义

1. 程序：就是一个指令序列

   早期的计算机（只支持单道程序），因此在计算机中，同一时间段内只能有一道程序，在这段时间段内，CPU只为这道程序服务

   内存中同一个时间段内只存在一个程序相关的数据，包括程序段和数据段两个部分，程序段保存的是代码本身，数据段存放的是程序运行过程中的中间数据

   

2. 引入多道程序技术之后

   

   为了方便操作系统管理，完成各程序并发执行，引入了进程、进程实体的概念

   操作系统为每个运行的程序（进程）配置一个数据结构，称为进程控制块（PCB），用来描述进程的各种信息（如程序代码存放位置、进程的状态）

   PCB、程序段、数据段三部分构成了进程实体（进程映像）

3. 一般情况下，我们把进程实体就简称为进程，例如，所谓创建进程，实质上是创建进程实体中的PCB，而撤销进程，实质上是撤销进程实体中的PCB

   注意：PCB是进程存在的唯一标志。

4. 从不同的角度，进程可以有不同的定义，比较传统典型的定义有：

   • 进程是程序的一次执行过程
   • 进程是一个程序及其数据在处理器上顺序执行时所发生的活动
   • 进程是具有独立功能的程序在数据集合上运行的过程，它是系统进行资源分配和调度的一个独立单位。

   所有的定义都强调进程是一个动态的过程

5. 引入进程实体的概念后，可把进程定义为：

   进程是进程实体（或者说静态程序）的运行过程，是系统进行资源分配和调度的一个独立单位。

   注意：严格来说，进程实体和进程并不一样，进程实体是静态的，进程则是动态的

进程的组成

1. 进程（进程实体）由程序段、数据段、PCB三部分组成

   

2. PCB的组成

   

   当进程被创建时，操作系统会为该进程分配一个唯一的、不重复的ID，用于区分不同的进程。

   当进程切换时，需要把进程当前的运行情况记录下来，保存在PCB中，如程序计数器的值表示了当前程序执行到哪一句。（在jvm中，程序计数器保存了下一条需要执行的字节码指令对应的地址！！）

   进程的管理者（操作系统）所需的数据都在PCB中！！

   程序段和数据段存放的是程序本身的运行所需的数据

进程的组织方式

1. 在一个系统中，通常有数十、数百乃至数千个PCB（进程控制块，描述进程的各种信息），为了能对他们加以有效的管理，应该用适当的方式把这些PCB组织起来

   进程的组成讨论的是一个进程内部由哪些部分构成的问题，而进程的组织讨论的是多个进程之间的组织方式的问题。

2. 

3. 进程的组织---链接方式（操作系统持有指针，指向不同队列）

   执行指针指向当前处于运行态（执行态）的进程

   就绪队列指针，指向当前处于就绪态的进程

   阻塞队列指针，指向当前处于阻塞态的进程，很多操作系统还会根据阻塞原因不同，再分为多个阻塞队列

   

4. 进程的组织---索引方式（操作系统持有指针，指向索引表，而不是队列）

   

   注意：链接方式，是指针指向队列，索引方式，是指针指向索引表

进程的特征

1. 进程和程序是两个截然不同的概念，相比于程序，进程拥有以下特征：

   • 动态性：进程是程序的一次执行过程，是动态地产生、变化、消亡的。（动态性也是进程最基本的特征）

   • 并发性：内存中有多个进程实体（映像），各进程可并发执行（并发就是宏观上并行，微观上串行，轮流被CPU执行，但是在宏观上，各进程好像是并行执行的。 ）

   • 独立性：进程是能独立运行、独立获得资源，独立接受调度的基本单位

   • 异步性：各进程按各自独立的、不可预知的速度向前推进（因为并发性，不是被CPU完全串行执行的，所以推进的速度是未知的），操作系统要提供“进程同步机制”来解决异步问题。

     异步性有可能导致运算结果的不确定性，所以需要依靠同步机制。

   • 结构型：每个进程（进程实体）会配置一个PCB，结构上看，进程由程序段、数据段、PCB组成

2. 在Java中，进程是作为资源分配的最小单位，线程才是接受调度的最小单位。

   对于操作系统来说，进程是资源分配和操作系统调度的一个独立单位

3. PCB是操作系统为了管理进程所创建的数据结构，PCB存放的数据是对进程的管理数据

进程的状态和转换

进程的状态

1. 进程是程序的一次执行，在这个执行过程中，有时进程正在被CPU处理，有时又需要等待CPU服务，可见，进程的状态是会有各种变化，为了方便对各个进程的管理，操作系统需要将进程合理地划分为几种状态。

2. 三种基本状态

   • 运行态---占有CPU，并在CPU上运行。注意：单核处理机环境下，每一个时刻最多只有一个进程处于运行态（双核环境下，可以同时有两个进程处于运行态即在微观上也是并行的，单核的话，如果有多个进程，那么在微观上就是串行执行的，在宏观上是并行的。）

   • 就绪态---已经具备运行条件，但是由于没有空闲CPU，而暂时不能运行。处于就绪态的进程，已经拥有了除处理器之外所有需要的资源，一旦获得处理器，即可立即进入运行态开始运行，即万事具备，只欠CPU

   • 阻塞态---因等待某一事件，而暂时不能运行（不是在等待CPU，而是等待除了CPU之外的其他事件，如果只是等待CPU，那么是就绪态）。如等待操作系统分配打印机、等待读磁盘操作的结果等，这些IO操作使得此进程阻塞，此进程必须等待IO操作完成，此时CPU处于空闲状态（这也是多线程或者说多任务的意义，在某个线程因为IO操作而阻塞的适合，不至于让CPU处于空闲状态而导致CPU利用率很低和系统吞吐量很低，如果采用多线程，这种情况下，CPU可以在某个线程因为IO操作而阻塞的时候，不处于空闲状态，而去执行其他线程，提高系统吞吐量）。

     CPU是计算机中最昂贵的部件，为了提高CPU的利用率，需要先将进程需要的其他资源分配到位，才能得到CPU的服务，也就是说，处于阻塞态的进程，是还没有获得除了CPU之外的其他资源。如果获得了除了CPU以外的其他资源，只差CPU，那么这个进程会处于就绪态。

     获得了CPU以外的其他所有需要的资源，会从阻塞态到就绪态，相当于Java中被唤醒！！

3. 进程的另外两种状态

   • 创建态（NEW，新建态）：进程正在被创建，操作系统为进程分配内存空间等系统资源，初始化PCB
   • 终止态（TERMINATED）：进程正在从系统中撤销，操作系统会回收进程所拥有的资源、撤销PCB

进程状态的转换

1. 

   注意：不能由阻塞态直接转换为运行态（必须先转换为就绪态），也不能由就绪态直接转换为阻塞态（因为进程进入阻塞态是进程主动请求的，必然需要进程在运行时才能发出这种请求。）

2. 

进程控制

基本概念

1. 进程控制的主要功能是对系统中的所有进程实施有效的管理，它具有创建新进程、撤销已有进程、实现进程状态转换比如阻塞、唤醒等功能。

   简化理解：反正进程控制就是要实现进程状态转换

   

2. 如何实现进程控制？

   

3. PCB所处的队列和PCB里的状态标志一定要是对应的，一致的，不然会产生系统错误，于是采用原语来实现进程控制，实现进程状态的转换，原语可以理解为一气呵成。

进程控制相关的原语

1. 用原语实现进程控制，原语的特点是执行期间不允许中断，只能一气呵成

   这种不可被中断的操作即原子操作

   原语采用“关中断指令”和“开中断指令”实现

   

   显然，关、开中断指令的权限非常大，必然是只允许在核心态下执行的特权指令

   原语也是只能运行在核心态的。

2. 进程控制会导致进程状态的转换

   无论哪个原语，要做的无非是三类事情：

   • 更新PCB中的信息（如修改PCB中的进程状态标志，将运行环境保存到PCB，从PCB恢复进程运行环境）
     • 所有的进程控制原语一定都会修改进程状态标志
     • 剥夺当前运行进程的CPU使用权必须需要保存其运行环境，以进行上下文切换
     • 某进程开始运行前必然要恢复其运行环境即上下文切换
   • 将PCB插入合适的队列，所插入的队列要与PCB里的信息保持一致，所以要通过原语来实现进程控制
   • 分配、回收资源，比如进程TERMINATED之后，需要回收内存这种系统资源！！ 当然可能还有这个进程执行所需要的其他资源

3. 

   

   

   

   注意：一定要注意，进程转换到运行态，一定要恢复进程运行环境，如果进程从运行态转换到阻塞态，那么要保护进程运行环境，进程运行环境保存到PCB。

   进程转换到阻塞态，是主动动作，所以一定是运行态---阻塞态，因为是进程主动申请的，从阻塞态是转换到就绪态，这个过程无需恢复进程运行环境，当进程从就绪态转换到运行态时，需从PCB恢复进程运行环境。

进程通信

概念

1. 进程通信指的就是进程之间的信息交换

   进程是资源分配的基本单位（包括内存地址空间），因此各进程拥有的内存地址空间相互独立

   为了保证安全，一个进程不能直接访问另一个进程的地址空间

   但是进程之间的信息交换又是必须实现的，比如说使用应用程序的时候的分享功能，将一个进程的数据信息和另一个进程进行通信，所以需要进程之间的通信

   为了保证进程间的安全通信，操作系统提供了一些方法---共享存储、消息传递和管道通信

共享存储

1. 两个进程不能直接访问对方的地址空间，所以操作系统会为两个进程分配一个共享空间，两个进程之间的通信就通过这个共享空间来完成。

   但是这两个进程对共享空间的访问必须是互斥的，这就是前面提到的互斥共享

   互斥共享就是系统中的某些资源，虽然可以提供给多个进程使用，但一个时间段内只允许一个进程访问该资源。

2. 互斥访问，一般是通过操作系统提供的工具实现的，操作系统只负责提供共享空间和同步互斥工具（如P、V操作）

3. 共享存储（共享空间）分为两种

   • 基于数据结构的共享

     共享空间中只能存放一种固定的数据结构，比如共享空间里只能放一个长度为10的数组，那么两个进程之间的通信，每一次只能通过这个长度为10的数组，这种共享方式速度慢、限制多，是一种低级通信方式。

   • 基于存储区的共享

     操作系统只负责为通信的进程提供存储空间，在内存中画出一块共享存储区，但是在这个共享空间中，两个进程交换的数据是什么形式，存放的位置都是由进程控制，而不是操作系统，相比之下，这种共享方式速度更快，是一种高级通信方式（相当于是说不会收到那么多限制）。

消息传递

1. 进程间的数据交换以格式化的消息为单位，进程通过操作系统提供的“发送消息/接收消息”两个原语进行数据交换。

   一个格式化的消息会包含消息头和消息体两个部分

   消息头包括：发送进程ID，接收进程ID，消息类型，消息长度等格式化的信息（计算机网络中发送的“报文”其实就是一种格式化的消息）

   

2. 消息传递分为两种

   • 直接通信方式

     把消息直接挂到接收进程的消息缓冲队列上，每一个进程会有一个消息缓冲队列，如果有另外一个进程想给这个进程发送消息的时候，发送进程首先会创建好消息头和消息体，通过发送原语发送给目标进程，消息就会挂到目标进程的消息缓冲队列的队尾。

     目标进程通过接收原语，依次把消息缓冲队列的消息取走

   • 间接通信方式

     消息要先发送到中间实体（信箱）中，因此也称为“信箱通信方式”

     

     信箱中的消息由哪个进程发送的，由哪个进程接收，都在消息头中

     通过发送原语，发送进程发送消息到信箱中

     同样，接收进程通过接收原语，从信箱中取消息

管道通信

1. 所谓的管道其实是一种特殊的共享文件。

   “管道”是指用于连接读写进程的一个共享文件，又名pipe文件

   其实就是在内存中开辟一个大小固定的缓冲区

   这个缓冲区的大小一般和内存页面是一样的

   

2. 一个管道只能采用半双工通信，某一时间段只能实现单向的传输，如果要实现双向同时通信，则需要设置两个管道。

   

3. 各个进程对管道的访问，需要互斥的进行，也是前面提到的互斥共享。

4. 数据以字符流的形式写入管道，当管道写满时，写进程的write()系统调用将导致写进程被阻塞，等待读进程将数据取走。

   当读进程将数据全部取走后，管道变空，此时读进程的read()系统调用将导致读进程阻塞

5. 如果没写满，就不允许读，如果没读空，就不允许写。

6. 数据一旦被读出，就从管道中抛弃，这就意味着读进程最多只能有一个，否则可能会有读错数据的情况

线程和多线程模型

概念

1. 在没有引入进程之前，系统中各个程序只能串行执行。

2. 有的进程，可能需要同时做很多事，而传统的进程只能串行地执行一系列程序（多个进程之间是并发的，但是一个进程内部的程序是串行执行的。），为此，引入了“线程”，来增加并发度。

   

   同一个进程中被分为了多个线程。

   多个线程之间，可以并发地执行！！之前一直说的都是进程之间的并发，但是引入了线程之后，多个线程之间，能够并发执行，也就是在宏观上多个线程是并行执行的，在微观上，是CPU交替执行这多个线程，也就是微观上是并发的，但是如果CPU是多核的，微观上也能够实现真正意义上的并行。

3. 引入了线程之后，线程成为了程序执行流的最小单位。进程是资源分配的最小单位，多个线程会共用进程的资源，但是线程是调度的最小单位。

   引入了线程之后，是多个线程并发地被CPU处理。

4. 线程可以理解为是轻量级的进程。

   线程是一个基本的CPU执行单元，也是程序执行流的最小单位。引入线程之后，不仅是进程之间可以并发，进程内的各线程之间也可以并发，从而进一步提升了系统的并发度，使得一个进程内也可以并发处理各种任务。

   引入线程后，进程只作为除CPU之外的系统资源的分配单元（如打印机、内存地址空间等都是分配给进程的，进程是资源分配的最小单位）

   CPU也算是系统资源，分配的最小单位是线程！！线程也需要得到CPU服务之后，才能执行。线程之间也存在上下文切换，线程的状态转换是由于CPU的轮转机制或者其他机制而导致CPU不继续服务当前线程，于是出现线程的状态转换，也存在要保存线程的运行环境，恢复运行环境这种上下文切换，和前面说的进程很类似。

引入线程机制后的变化

1. 

线程有哪些属性

1. 线程是处理器调度的单位
2. 多核CPU环境下，各个线程可占用不同的CPU
3. 每个线程都有一个线程ID，线程控制块（TCB）
4. 线程也有就绪、阻塞、运行三种基本状态
5. 线程几乎不拥有系统资源
6. 同一进程的不同线程间共享进程的资源
7. 由于共享内存地址空间，同一进程的线程间通信甚至无需操作系统干扰（因为同一进程中的线程共享内存地址空间）
8. 同一进程中的线程切换，不会引起进程切换
9. 不同进程中的线程切换，会引起进程切换
10. 切换同进程内的线程，系统开销很小
11. 切换进程，系统开销较大。（因为切换进程还要切换页表，页表是虚拟地址到物理地址的映射，线程不涉及到页表的切换）

线程的实现方式

1. 用户级线程

   用户级线程由应用程序通过线程库实现，所有的线程管理工作都由应用程序负责（包括线程切换）

   用户级线程中，线程切换可以在用户态下进行，无需操作系统干预

   在用户看来，是有多个线程，但是在操作系统内核看来，意识不到线程的存在，用户级线程对用户不透明，对操作系统透明。

   用户级线程就是从用户的视角可以看到的线程

2. 内核级线程

   内核级线程的管理工作是由操作系统内核完成，线程调度、切换等工作都由内核负责，因此内核级线程的切换必然需要在核心态下完成。

   内核级线程就是从操作系统内核视角能够看到的线程

3. 在同时支持用户级线程和内核级线程的系统中，可采用二者组合的方式，将n个用户级线程，映射到m个内核级线程上

   重点：操作系统只看得见内核级线程，因此只有内核级线程才是处理器分配的单位。

   

多线程模型

1. 在同时支持用户级线程和内核级线程的系统中，由几个用户级线程映射到几个内核级线程的问题引出了“多线程模型”问题

2. 多对一模型

   

   多个用户级线程映射到一个内核级线程。每个用户进程只对应一个内核级线程，内核级线程才是作为调度的基本单位

   优点：用户级线程的切换在用户空间即可完成，不需要切换到核心态，线程管理的系统开销小，效率高

   缺点：当一个用户级线程被阻塞后，会导致内核级线程阻塞，其他用户级线程也不能执行了， 整个进程会被阻塞，并发度不高。多个线程不可以在多核处理器上并行运行。因为内核级线程才是处理器调度的基本单位。（操作系统只看得见内核级线程）

3. 一对一模型

   

   一个用户级线程映射到一个内核级线程，每个用户进程有与用户级线程同数量的内核级线程

   优点：当一个线程被阻塞后，别的线程还可以继续执行，并发能力强，多线程可以在多核处理器上并行执行。

   缺点：一个用户进程会占用多个内核级线程，线程切换是由操作系统内核完成，需要切换到核心态，因此线程管理的成本高，开销大。

4. 多对多模型

   

   n个用户级线程映射到m个内核级线程，每个用户进程对应m个内核级线程

   克服了多对一模型并发度不高的缺点，又克服了一对一模型中一个用户进程占用太多内核级线程，开销太大的缺点。

处理机调度

基本概念

1. 线程是调度的最小单位（内核级线程）

2. 调度：

   当有一堆任务要处理，但由于资源有限，这些事情没法同时处理，这就需要确定某种规则来决定处理这些任务的顺序，这就是“调度”研究的问题

   这种说法下的任务也可以理解为线程。

3. 在多道程序系统中，进程的数量（线程的数量）往往是多于处理器的核心个数的，这样不可能同时并行地处理各个进程，如果线程数量和处理器核心数相同，那么在微观上是能做到真正的并行处理线程的。

   在这句话中，就是用进程或线程的描述来作为处理器处理的对象。

   在第二点，是说的任务作为处理器处理的对象，所以，可以将进程和任务理解为相同的事物。

4. 处理机调度，就是从就绪进程队列中按照一定的算法选择一个进程并将处理机分配给它运行，以实现进程的并发执行（微观上串行，宏观上并行，就是并发）。

三个层次

高级调度

1. 高级调度（作业调度），按一定的原则从外存上处于后备队列的作业中挑选一个或多个作业，给他们分配内存等必要资源，并建立相应的进程（建立PCB（进程控制块），PCB、数据段、程序段组成一个进程实体），以使它（们）获得竞争处理机的权利。能够竞争CPU，说明处于就绪队列，说明已经获得了除CPU以外其他需要的资源，当然包括内存。

2. 高级调度是外存和内存之间的调度。

   作业调入时会建立相应的PCB，作业调出时才撤销PCB，高级调度主要是指调入的问题。因为只有调入的时机需要操作系统来确定，但调出的时机必然是作业运行结束才调出。

中级调度

1. 引入了虚拟存储技术之后，可将暂时不能运行的进程调至外存等待，等它重新具备了运行条件且内存又稍有空闲时，再重新调入内存。

   这么做的目的时为了提高内存利用率和系统吞吐量。

   暂时调到外存等待的进程称为挂起状态，值得注意的是，进程控制块PCB不会一起调到外存，而是会常驻内存，PCB中会记录进程数据在外存中的存放位置，进程状态等信息，操作系统通过内存中的PCB来保持对各个进程的监控、管理。被挂起的进程PCB会被放到挂起队列中（操作系统会为处于挂起态的进程建立一个挂起队列，把这些进程的PCB用一个队列的方式组织起来）。

   在内存中才叫进程，因为这里说的内存是运行时内存，而外存是磁盘，可以理解为静态的，但是为什么又能存放到外存呢，就是虚拟存储技术，也就是虚拟技术中的空分复用技术

   就绪队列、阻塞队列存放的也是PCB

2. 中级调度（内存调度），就是要决定将哪个处于挂起状态的进程重新调入内存

   一个进程可能会被多次调出、调入内存，因此中级调度的发生频率要比高级调度更高。

3. 暂时调到外存等待的进程状态为挂起状态

   挂起态又可以分为就绪挂起、阻塞挂起两种状态

   就绪态的进程可能会由于内存空间不足，而被移到外存挂起，这叫就绪挂起

   阻塞态的进程同样可能会由于内存空间不足，被移到外存挂起，叫阻塞挂起

   

4. 注意：

   挂起和阻塞的区别，两种状态都是暂时不能获得CPU的服务，但是挂起态是将进程实体（映像）调到外存中去了，而阻塞态下的进程映像还在内存中。

   有的操作系统会把就绪挂起，阻塞挂起分为两个挂起队列，甚至会根据阻塞原因不同再把阻塞挂起进程进一步细分为多个队列。

低级调度

1. 低级调度（进程调度），其主要任务是按照某种方法和策略从就绪队列中选取一个进程，将处理器分配给它

2. 进程调度是操作系统中最基本的一种调度，在一般的操作系统中都必须配置进程调度。

   进程调度的频率很高，一般几十毫秒一次，只有这样，才能在宏观上看起来是并行执行的，实际上微观上是这些进程之间交替执行。

联系

1. 

进程调度

进程调度的时机

1. 进程调度就是低级调度，就是按照某种算法从就绪队列中选择一个进程为其分配处理机。

2. 什么时候需要进行进程调度和切换？

   • 当前运行的进程主动放弃处理机
     • 进程正常终止
     • 运行过程中发生异常而终止
     • 进程主动请求阻塞，通过系统调用，系统调用时会执行陷入指令或者说访管指令，从而进入核心态，这是内中断中的自愿中断，进程由运行态到阻塞态是主动行为。
   • 当前运行的进程被动放弃处理机
     • 分给进程的时间片用完
     • 有更紧急的事需要处理（如IO中断）
     • 有更高优先级的进程进入就绪队列

3. 不能进行进程调度和切换的情况

   • 在处理中断的过程中，中断处理过程复杂，与硬件密切相关，很难做到在中断处理过程中进行进程切换
   • 进程在操作系统内核程序临界区中（但是进程在普通临界区中是可以进行调度、切换的）
   • 在原子操作过程中（原语），原子操作不可中断，要一气呵成（原子操作是通过中断来完成的，所以一定是在核心态进行。）

4. 临界资源：一个时间段内只允许一个进程使用的资源，各进程需要互斥地访问临界资源

   临界区：访问临界资源那段代码

5. 内核程序临界区访问的临界资源，如果不尽快释放的话，极有可能映像到操作系统内核的其他管理工作，因此在访问内核程序临界区期间不能进行调度与切换

   普通临界区访问的临界资源不会直接影响操作系统内核的管理工作，因此在访问普通临界区时可以进行调度和切换，而且是很有必要进行进程的调度和切换来提高CPU的利用率和系统吞吐量。

进程调度的方式

1. 非剥夺调度方式，又称为非抢占方式，即只允许进程主动放弃处理机，在运行过程中即便有更紧迫的任务到达，当前进程依然会继续使用处理机，直到该进程终止或主动要求进入阻塞态。
2. 剥夺调度方式，又称抢占方式，当一个进程正在处理机上执行时，如果有一个更重要或更紧迫的进程需要使用处理机，则立刻暂停当前正在执行的进程，将处理机分配给更重要紧迫的进程。

进程的切换和过程

1. 狭义的进程调度指的是从就绪队列中选中一个要运行的进程

   进程切换是指一个进程让出处理机，由另一个进程占用处理机的过程。

   广义的进程调度包含了选择一个进程和进程切换两个步骤

2. 进程切换的过程主要完成了：

   • 对原来运行进程各种数据的保存，保存到PCB中

   • 对新的进程的各种数据的恢复

     这些进程的信息，运行环境的信息一般保存在进程控制块PCB中。

3. 不能简单地认为进程切换越频繁，并发度就越高

   进程切换是有代价的，因此如果过于频繁地进行进程调度、切换，必然会使整个系统的效率降低，使系统大部分时间都花在了进程切换上。

进程同步、互斥

概念

1. 进程具有异步性的特征，异步性是指，各并发执行的进程各自以独立的、不可预知的速度向前推进

2. 进程同步：

   并发性带来了异步性，有时需要通过进程同步解决这种异步问题

   有的进程之间需要相互配合地完成工作，各进程的工作推进需要遵循一定的先后顺序，就是通过同步，同步锁的实现通过同步代码块和同步方法， 也正是这个意思。

3. 我们把一个时间段内只允许一个进程使用的资源称为临界资源，对临界资源的访问，必须互斥地进行。

4. 

   注意：

   临界区是进程中访问临界资源的代码段

   进入区和退出区是负责实现互斥的代码段

5. 为了实现对临界资源的互斥访问，同时保证系统整体性能，需要遵循以下原则：

   • 空闲让进。临界区空闲时，可以允许一个请求进入临界区的进程立即进入临界区
   • 忙则等待。当已有进程进入临界区时，其他试图进入临界区的进程必须等待。
   • 有限等待（保证不会饥饿）。对请求访问的进程，应保证能在有限时间内进入临界区（保证不会饥饿）
   • 让权等待。当进程不能进入临界区时，应立即释放处理机，防止进程忙等待。

信号量机制

1. 用户进程可以通过使用操作系统提供的一对原语来对信号量进行操作，从而很方便地实现了进程互斥、进程同步。

   信号量其实就是一个变量（可以是一个整数，也可以是更复杂的记录型变量），可以用一个信号量来表示系统中某种资源的数量。

   

2. 整型信号量

   与普通整数变量的区别：对信号量的操作只有三种，即初始化，P操作、V操作

   

   也就是说，在进入区和退出区这两个代码区，分别使用P操作和V操作这两个原语操作来上锁和解锁。

   检查和上锁一气呵成，避免了并发、异步导致的问题。

   存在的问题：不满足让权等待的原则，会发生忙等。

3. 记录型信号量

   

   wait(S)和signal(S)可用于实现对系统资源的申请和释放

   S.value的初值表示系统中某种资源的数目

   对信号量S的一次P操作意味着进程请求一个单位的该资源，因此需要执行S.value--，表示该资源数减1，当S.value<0时，表示该类资源已分配完毕，因此进程应调用block原语进行自我阻塞，当前运行的进程从运行态到阻塞态，主动放弃处理机，并插入该类资源的等待队列，可见，该机制遵循了让权等待的原则，不会出现忙等现象，只要发现资源分配完毕，那么主动进入阻塞态，相当于是等待IO，进程进入阻塞态，都是主动的，是运行态主动到阻塞态，通过系统调用的访管指令或陷入指令，执行中断，于是阻塞，操作权限交给操作系统。

   对信号量S的一次V操作，意味着进程释放一个单位的该类资源，因此需要执行S.value++，表示资源数+1，若加1后仍然是小于等于0，说明仍然有进程因为等待该资源而处于阻塞态，因此应调用wakeup原语唤醒等待队列中的第一个进程（被唤醒进程从阻塞态到就绪态，等待CPU时间片，即可被CPU执行。）

4. 用信号量机制实现进程互斥

   • 分析并发进程的关键活动，划定临界区（如：对临界资源打印机的访问就应该放在临界区，临界区是代码）
   • 设置互斥信号量mutex，初值为1，临界区可以理解为是一种特殊的系统资源，因为要实现互斥，所以设置这种“系统资源”的数量初值为1，相当于是上锁
   • 在临界区之前执行P(mutex)
   • 在临界区之后执行V(mutex)

   注意：对不同的临界资源需要设置不同的互斥信号量，可以从Java多线程的角度来理解，同步锁对象一定要是同一个，多个线程要获得的是同一把锁，这样才有上锁的意义

   PV操作必须成对出现（上锁和解锁必须成对出现），缺少P就不能保证临界资源的互斥访问，因为P操作相当于是上锁，缺少V会导致资源永不被释放，V操作相当于是解锁

5. 用信号量实现进程同步：

   • 分析什么地方需要实现同步关系，找到需要执行同步关系的代码
   • 设置同步信号量S，初始值设置为0
   • 在“前操作”之后执行V（S）
   • 在“后操作”之前执行P（S）

   

管程

概念

1. 管程是一种高级同步机制，和之前学过的PV操作一样，也是用来实现进程的互斥和同步的
2. 引入管程的目的是为了更方便地实现进程互斥和同步

死锁

概念

1. 死锁：在并发环境下，**各进程（发生死锁一定是两个或以上）**因竞争资源而造成的一种互相等待对方手里的资源，导致各进程都阻塞，都无法向前推进的现象，就是“死锁”。发生死锁后若无外力干涉，这些进程都将无法向前推进。

进程死锁、饥饿、死循环的区别

1. 死锁：各进程互相等待对方手里的资源，导致各进程都阻塞，无法向前推进的现象。
2. 饥饿：由于长期得不到想要的资源，某进程无法向前推进的现象，比如：在短进程优先算法中，若有源源不断的短进程到来，则长进程将一直得不到处理机，从而发生长进程饥饿现象
3. 死循环：某进程执行过程中一直跳不出某个循环的现象。

死锁产生的必要条件

1. 互斥条件：只有对必须互斥使用的资源的争抢才会导致死锁（比如IO设备），像内存、扬声器这样可以同时让多个进程使用的资源是不会导致死锁的（因为进程不用阻塞等待这种资源）

2. 不可剥夺条件：进程所获得的资源在未使用完之前，不能由其他进程强行夺走，只能主动释放。

3. 请求保持条件：进程已经保持了至少一个资源，但又提出了新的资源请求，而该资源又被其他进程占有，此时请求进程被阻塞，但又对自己已有的资源保持不放。

4. 循环等待条件：存在一种进程资源的循环等待链，链中的每一个进程已获得的资源同时被下一个进程所请求。

   注意：发生死锁时，一定有循环等待，但是发生循环等待时未必死锁

   如果同类资源数大于1，则即使有循环等待，也未必发生死锁，但如果系统中每类资源都只有1个，那循环等待就是死锁的充分必要条件了。

什么时候会发生死锁

1. 对不可剥夺的资源的不合理分配，可能导致死锁。

死锁的处理策略

1. 预防死锁。破坏死锁产生的四个必要条件中的一个或几个
2. 避免死锁。用某种方法防止系统进入不安全状态，从而避免死锁（银行家算法）
3. 死锁的检测和解除。允许死锁的发生，不过操作系统会负责检测出死锁的发生，然后采取某种措施解除死锁。

死锁的处理

不允许死锁发生

静态策略：预防死锁

1. 死锁的产生必须满足四个必要条件，只要其中一个或几个条件不成立，死锁就不会发生

2. 破坏互斥条件

   互斥条件：只有对必须互斥使用的资源（互斥共享）的争抢，才会导致死锁

   如果把只能互斥使用的资源改造为允许共享使用（同时共享，宏观上并行，微观上仍然是串行的，是并发。），则系统不会进入死锁状态，比如：SPOOLing技术。操作系统可以采用SPOOLing技术将独占设备在逻辑上改为共享设备。

   缺点：并不是所有的资源都可以改造成可共享使用的资源，并且为了系统安全，很多地方必须保持这种互斥性。因此，很多时候都无法破坏互斥条件。

3. 破坏不剥夺条件

   方案一：当某个进程请求新的资源得不到满足时，它必须立即释放保持的所有资源，待以后需要时再重新申请。

   方案二：当某个进程需要的资源被其他进程所占有的时候，可以由操作系统协助，将想要的资源强行剥夺，这种方式一般考虑各进程的优先级（比如剥夺调度方式就是将处理机资源强行剥夺给优先级更高的进程使用）

   一种是自愿放弃，导致不用剥夺，一种是强行剥夺。

4. 破坏请求和保持条件

   可以采用静态分配方法，即进程在运行前一次性申请完它所需要的全部资源，在它的资源未满足前，不让它投入运行，一旦投入运行后，这些资源就一直归它所有，该进程就不会再请求别的资源了。

   缺点：有些资源可能只需要用很短的时间，因此如果进程的整个运行期间都一直保持着所有资源，就会造成严重的资源浪费，资源利用率极低。另外，该策略也有可能导致某些进程饥饿。

5. 破坏循环等待条件

   

   

6. 

动态策略：避免死锁

1. 安全序列，就是指如果系统按照这种序列分配资源，则每个进程都能顺利完成，只要能找出一个安全序列，系统就是安全状态，当然安全序列可能有多个。

2. 如果系统处于安全状态，就一定不会发生死锁，如果系统进入不安全状态，就可能发生死锁（处于不安全状态未必是发生了死锁，但发生死锁时，一定是在不安全状态）

   因此可以在资源分配之前预先判断这次分配是否会导致系统进入不安全状态（能否找到一个安全序列），以此决定是否答应资源分配请求。这是银行家算法的核心思想。

允许死锁发生

1. 如果系统中既不采取预防死锁的措施，也不采取避免死锁的措施，系统就很可能发生死锁，在这种情况下，系统应当提供两个算法：

   • 死锁检测算法：用于检测系统状态，以确定系统中是否发生了死锁
   • 死锁解除算法：当认定系统中已经发生了死锁，利用该算法可将系统从死锁状态中解脱出来。

2. 死锁的检测

   死锁定理：如果某时刻系统的资源分配图是不可完全简化的，那么此时系统死锁

3. 死锁的解除

   并不是系统中所有的进程都是死锁状态，用死锁检测算法化简资源分配图后，还连着边的那些进程就是死锁进程

   解除死锁的主要方法有：

   • 资源剥夺法：挂起（暂时放到外存上）某些死锁进程，并抢占它的资源，将这些资源分配给其他的死锁进程。但是应防止被挂起的进程长时间得不到资源而饥饿。
   • 撤销进程法（终止进程法）：强制撤销部分甚至全部死锁进程，并剥夺这些进程的资源。
   • 进程回退法。让一个或多个死锁进程回退到足以避免死锁的地步。

   如何决定对哪个进程进行资源剥夺或撤销或回退：

   • 进程优先级
   • 已执行多长时间
   • 还有多久能完成
   • 进程已经使用了多少资源
   • 进程是交互式的还是批处理式的

4. 

第三章

内存

概念

1. 内存是用于存放数据的硬件，程序执行前需要先放到内存中才能被CPU处理
2. 外存就是硬盘或者叫辅存
3. 硬盘是慢速的设备，而CPU是超快速的设备，所以CPU要处理的数据直接从外存中读取，CPU需要大量时间都在等待，CPU直接和外存的数据进行交互，会产生速度上的矛盾
4. 内存可以理解为是一种更快速地存放数据的硬件。
5. 内存地址从0开始，每个地址对应一个存储单元。

进程的运行原理---指令

1. 我们写的代码要翻译成CPU能识别的指令，这些指令会告诉CPU应该去内存的哪个地址存、取数据，这个数据应该做什么样的处理。但是对于Java来说，我们写的Java代码会编译成字节码文件，字节码也是二进制码，但是却不是CPU能够直接识别的二进制机器码，字节码对应于字节码指令，所以在JVM中的执行引擎部分，解释器会解释字节码指令并执行，同时JIT即时编译器会将字节码再次编译成CPU能直接识别的机器码，这是二次编译，所以说Java是半解释半编译的语言，解释器存在的原因是为了保证响应速度，因为编译是需要时间的，在JIT即时编译器编译热点代码的时候，解释器就能够直接解释字节码指令并执行了，保证了响应速度。

2. 实际上，编译时，指令中给出的地址参数都是逻辑地址，或者说相对地址。

   绝对地址又称物理地址

   编译：由编译程序将用户源代码编译成若干个目标模块（编译就是把高级语言翻译成机器语言）

   链接：由链接程序将编译后形成的一组目标模块，以及所需库函数链接在一起，形成一个完整的装入模块

   装入：由装入程序将装入模块装入内存运行。

3. 装入的三种方式

   • 绝对装入

     在编译时，如果直到程序将放到内存中的哪个位置，编译程序将产生绝对地址的目标代码，装入程序按照装入模块中的地址，将程序和数据装入内存

     绝对装入只适用于单道程序环境

   • 静态重定位

     由装入程序把逻辑地址转换为物理地址。

     静态重定位的特点是在一个作业装入内存时，必须分配其要求的全部内存空间，如果没有足够的内存，就不能装入该作业。作业一旦进入内存后，在运行期间就不能再移动，也不能再申请内存空间。

   • 动态重定位

     又称动态运行时装入。这种方式需要一个重定位寄存器支持

     重定位寄存器：存放装入模块存放的起始位置。

     允许程序在内存中发生移动。

     并且可将程序分配到不连续的存储区中：在程序运行前，只需装入它的部分代码即可投入运行，然后在程序运行期间，根据需要动态申请分配内存

4. 链接的三种方式

   

内存管理

概念

1. 操作系统作为系统资源的管理者，当然也需要对内存进行管理

2. 各种进程想要运行的时候，进程相关的数据都要放入内存当中，或者说进程实体要放入内存中，进程实体是由PCB、程序段和数据段组成。

3. 操作系统在内存管理的作用：

   • 操作系统需要负责内存空间的分配和回收

   • 操作系统需要提供某种技术（虚拟技术或者说空分复用技术）从逻辑上对内存空间进行扩充

     

   • 操作系统需要提供地址转换功能，负责程序的逻辑地址和物理地址的转换。

   • 操作系统需要提供内存保护功能，保证各进程在各自存储空间内的运行，互不干扰。

4. 逻辑地址到物理地址的转换，就是前面提到的装入的三种方式。

5. 内存保护可采取两种方法：

   • 在CPU中设置一对上下限寄存器，存放进程的上下限地址，进程的指令要访问某个地址时，CPU检查是否越界。
   • 采用重定位寄存器（又称基址寄存器）和界地址寄存器（又称限长寄存器）进行越界检查，重定位寄存器中存放的是进程的起始物理地址，界地址寄存器中存放的是进程的最大逻辑地址。进程的指令要访问某个地址时，CPU检查是否越界。

覆盖和交换

1. 覆盖技术，用来解决“程序大小超过物理内存总和”的问题

   覆盖技术的思想：将程序分为多个段（多个模块），常用的段常驻内存，不常用的段在需要时调入内存。

2. 程序一定要调入内存才能够被运行，进程就是一个程序的运行期，程序可以理解为静态的，必须调入内存才能够被CPU所执行，因为CPU是高速计算设备，而硬盘的IO速度很慢，这中间存在矛盾，所以一个程序在运行前必须被调入内存才能够被CPU执行，调入内存的程序可以说是程序的运行态，也就是进程。

3. 内存中分为一个固定区和若干个覆盖区

   需要常驻内存的段放在固定区中，调入后就不再调出

   不常用的段放在覆盖区，需要用到时调入内存，用不到时调出内存

   按照自身逻辑结构，让那些不可能同时被访问的程序段共享同一个覆盖区

   

   覆盖技术只用于早期的操作系统中，现在已经成为历史！！！

4. 交换技术

   当内存空间紧张时，系统将内存中某些进程暂时换出外存，把外存中某些已具备运行条件的进程换入内存（进程在内存与磁盘间动态调度。）

   处理机调度中的中级调度就是为了实现交换技术的调度策略。

   进程的PCB会保留在内存中，插入到挂起队列

   PCB一定是保留在内存中，因为挂起的进程在磁盘的什么位置在PCB有记录。

5. 具有对换功能的操作系统中，通常把磁盘空间分为对换区和文件区两部分。文件区主要用于存放文件，主要追求存储空间的利用率，因此对文件区空间的管理采用离散分配方式

   对换区空间只占磁盘的小部分，被换出的进程数据就存放在对换区，主要追求换入换出速度，采用连续分配方式。

   对换区的IO速度比文件区的更快

6. 什么时候应该交换内存中的进程到外存中，把外存中具备运行条件的进程交换进内存中？

   交换通常在许多进程运行且内存吃紧时进行，例如：在发现许多进程运行时经常发生缺页时，说明内存紧张，此时可以换出一些进程，如果缺页率明显下降，就可以暂停换出。

7. 可优先换出阻塞进程，可换出优先级低的进程，为了防止优先级低的进程在被调入内存后很快又被换出，有的系统还会考虑进程在内存中的驻留时间。

   PCB会常驻内存，不会被换出外存

8. 覆盖和交换的区别：

   • 覆盖是在同一个程序或进程中的
   • 交换是在不同进程或作业之间的。

连续分配管理方式

1. 单一连续分配

   在单一连续分配方式中，内存被分为系统区和用户区。

   系统区通常位于内存的低地址部分，用于存放操作系统的相关数据。

   用户区用于存放用户进程相关数据

   内存中只能有一道用户程序，用户程序独占整个用户区空间。

   不支持多个进程并发运行。

   没有外部碎片，有内部碎片

2. 固定分区分配

   将整个用户空间划分为若干个固定大小的分区，在每个分区中只装入一道作业

   没有外部碎片，有内部碎片

   • 分区大小相等

     

   • 分区大小不等

     

3. 动态分区分配

   又称可变分区分配，这种分配方式不会预先划分内存分区，而是在进程装入内存时，根据进程的大小动态地建立分区，并使分区的大小正好适合进程的需要。因此系统分区的大小和数目是可变的

   • 系统用什么样的数据结构记录内存的使用情况

     

   • 把一个新作业放入内存时，必须按照一定的动态分区分配算法，从空闲分区表（或空闲分区链）中选出一个分区分配给该作业

4. 动态分区分配没有内部碎片，但是有外部碎片

   内部碎片，分配给某进程的内存区域中，如果有些部分没有用上

   外部碎片，是指内存中的某些空闲分区由于太小而难以利用，即没有分配给进程的内存空间

   如果内存中空闲空间的综合本来可以满足某进程的要求，但由于进程需要的是一整块连续的内存空间，因此这些碎片不能满足进程的需求

   可以通过紧凑技术来解决外部碎片

动态分区分配算法

1. 首次适应算法

   每次都从低地址开始查找，找到第一个能满足大小的空闲分区

   如何实现：空闲分区以地址递增的次序排序，每次分配内存时从头（从低地址）顺序查找空闲分区链（或空闲分区表），找到大小能满足要求的第一个空闲分区。

2. 最佳适应算法

   为各进程分配的空间必须是连续的一整片区域，因此为了保证当大进程到来时能有连续的大片空间，可以尽可能多地留下大片的空闲区，即，优先使用更小的空闲区

   如何实现：空闲分区按容量递增次序链接，每次分配内存时顺序查找空闲分区链（或空闲分区表），找到大小能满足要求的第一个空闲分区。

   更小的空闲分区会移到链头的位置。

   缺点：每次都选最小的分区进行分配，会留下越来越多的、很小的、难以利用的内存块，因此这种方法会产生很多的外部碎片

3. 最坏适应算法

   和最佳适应算法相反

   算法思想：优先使用最大的连续空闲区，这样分配后剩余的空闲区就不会太小，更方便使用

   如何实现：空闲分区按容量递减次序链接，每次分配内存时顺序查找空闲分区链（或空闲分区表），找到大小能满足要求的第一个空闲分区。

   缺点：这种方式会导致较大的连续空闲区被迅速用完，如果之后有大进程到达，就没有内存分区可用了。

4. 邻近适应算法

   算法思想：首次适应算法每次都从链头开始查找的，这可能会导致低地址部分出现很多小的空闲分区（难以利用的分区），而每次分配查找时，都要经过这些分区，因此也增加了查找的开销，如果每次都从上次查找结束的位置开始检索，就能解决上述问题。

基本分页存储管理

介绍

1. 连续分配方式的缺点：

   固定分区分配，会产生大量的内部碎片，内存的利用率很低

   动态分区分配，会产生很多外部碎片

   如果允许将一个进程分散地装入到许多不相邻的分区中，便可充分地利用内存，而无需再进行“紧凑”（内存整理）

2. 非连续分配管理方式

   • 基本分页存储管理
   • 基本分段存储管理
   • 段页式存储管理

3. 基本分页存储管理的思想：

   把内存分为一个个相等的小分区，再按照分区大小把进程拆分成一个个小部分

4. 将内存空间分为一个个大小相等的分区，每个分区就是一个“页框”或页帧。

   每个页框有一个编号，即页框号。页框号从0开始。

   把用户进程的地址空间也分为与页框大小相等的一个个区域，称为页或页面，每个页面也有一个编号，即“页号”，页号也是从0开始

   也就是页或页面是进程分的，页框或者说页帧是内存分的。

   注：进程的最后一个页面可能没有一个页框那么大，因此，页框不能太大，否则可能产生过大的内部碎片

   操作系统以页框为单位，为各个进程分配内存空间，进程的每个页面分别放入一个页框中，也就是说，进程的页面与内存的页框有一一对应的关系。

   进程的各个页面不必连续存放，也不必按照先后顺序来，可以放到不相邻的各个页框中。

5. 如何实现逻辑地址到物理地址的转换？

   • 要算出逻辑地址对应的页号----逻辑地址 / 页面大小
   • 要知道该页号对应页面再内存中的起始地址----得到页号之后，根据页表的表项，找到块号，块号 * 内存块大小，得到对应页面在内存中的起始地址。
   • 要算出逻辑地址在“页面内”的偏移量----逻辑地址 % 页面大小
   • 物理地址 = 页面地址 + 页内偏移量

6. 为了能直到进程的每个页面在内存中存放的起始位置，操作系统要为每个进程建立一张页表。

   页面内的地址是连续的，各页面之间是离散的。

   一个进程对应一张页表

   一个进程的每一个页面，对应一个页表项

   每个页表项由页号和块号组成

   页表记录进程页面和**实际存放的内存块（块号）**之间的对应关系！！

   

   M号内存块的起始地址就是M * 内存块大小

   各块之间是离散的，但是每一块内是连续的。

基本地址变换机构

1. 基本地址变换机构---用于实现逻辑地址到物理地址转换的一组硬件机构。

   页表寄存器的作用：

   • 存放页表起始地址
   • 存放页表长度

2. 

具有快表的地址变换机构

1. 时间局部性：

   如果执行了程序中的某条指令，那么不久后这条指令很可能再次执行；如果某个数据被访问过，不久之后该数据很可能再次被访问

   空间局部性：

   一旦程序访问了某个存储单元，在不久之后，其附近的存储单元也很有可能被访问（因为很多数据在内存中都是连续存放的。 ）

2. 每次要访问一个逻辑地址，都需要查询内存中的页表（根据逻辑地址可以得到页号和页内偏移量，根据页号、页表起始地址和页表项长度，可以得到页号对应的页表项地址，得到页号对应的内存块号，根据内存块号和页面大小即每一个内存块的大小，可以得到该内存块在内存中的起始地址，根据起始地址和偏移量便可以得到物理地址）。

   由于局部性原理，可能连续很多次查到的都是同一个页表项地址。既然如此，能否利用这个特性减少访问页表的次数呢？

3. 快表，又称TLB即联想寄存器，是一种访问速度比内存快很多的高速缓冲存储器，用来存放当前访问的若干页表项，以加速地址变换的过程，与此对应，内存中的页表常称为慢表。

   页号、页表起始地址和页表项大小可以得到页号P对应的页表项地址！

4. 在查询慢表即内存中的页表之前，会先查询快表，理解为缓存

   

   若快表命中，就不需要再访问内存了，查询快表比内存快

5. 引入快表后，地址的变换过程

   

6. 由于查询快表的速度比查询页表（慢表）的速度快很多，因此只要快表命中，就可以节省很多时间，由于局部性原理，一般来说快表的命中率可以达到90%以上。

7. 对比

   

两级页表

1. 单级页表存在的问题

   • 问题1：页表必须连续存放，因此当页表很大时，需要占用很多个连续的页框---采用两级页表解决
   • 问题2：没有必要让整个页表常驻内存，因为进程在一段时间内可能只需访问某几个特定的页面。

   我们是如何解决进程在内存中必须连续存储的问题的？

   将一个进程分散地装入到许多不相邻的分区中，便可充分地利用内存

   同样，我们可以将很长的页表分组，使每一个内存块刚好可以放入一个分组，之前是将进程分成很多个页面，相当于将进程分组，现在页表太长了，那么就将页表分组。

   另外，要为离散分配的页表再建立一张页表，称为页目录表，或称外层页表，或称顶层页表。

   通过页目录表和页号，找到内存块号，通过此内存块号得到此内存块对应的二级页表的起始地址

2. 慢表也就是内存中的页表，当然是存储在内存中的，页表起始地址和页表长度存在页表寄存器中，进程运行的时候存储在页表寄存器中，没有被CPU执行的时候，存储在PCB中，所以页表存储在内存中，当然涉及到起始地址，这个地址存储在页表寄存器。

   快表不是存储在内存中的，访问快表的速度比内存快很多，是高速缓冲存储器。

3. 问题2的解决：

   可以在需要访问页面时才把页面调入内存（虚拟存储技术，页面是由进程分割而来的，把进程分成很多个部分），相当于需要进程某个部分时，才把这部分调入内存，进程分的部分就叫页面，内存分的部分就叫页框，可以在页表项中增加一个标志位，用于表示该页面是否已经调入内存。

   若想访问的页面不在内存中，则产生缺页中断（内中断，内中断分为自愿中断、硬件故障、软件中断），然后将目标页面从外存调入内存。

4. 两级页表的访存次数分析：（假设没有快表机构）

   • 第一次访存：访问内存中的页目录表
   • 第二次访存：访问内存中的二级页表
   • 第三次访存：访问目标内存单元

5. 如何实现地址变换

   • 按照地址结构将逻辑地址分为三部分
   • 从PCB中读出页目录表起始地址（页目录表也是在内存中的，当然有起始地址），根据一级页号查找到块号，根据内存块号找到下一级页表在内存中的存放位置（起始地址）
   • 根据二级页号查表，找到最终想访问的内存块号
   • 结合页内偏移量得到物理地址。

基本分段存储管理

介绍

1. 分段：

   进程的地址空间，按照程序自身的逻辑关系划分为若干个段，每个段都有一个段名

2. 内存分配规则：以段为单位进行分配，每个段在内存中占据连续空间，但各段之间可以不相邻

3. 分段系统的逻辑地址结构由段号（段名）和段内地址（段内偏移量）组成

   段号的位数决定了每个进程最多可以分为几个段

   段内地址位数决定了每个段的最大长度是多少

4. 操作系统需要为每个进程建立一张段映射表，简称段表

5. 在分页存储管理当中，每个页面的长度都是一样的，但是分段存储管理中，每个段的长度是不一样的，所以段表项比页表项多了一个段长

6. 每个段对应一个段表项，就像一个进程对应于一个页表，进程的每一页对应于一个页表项！！

   一个段表项，记录了该段在内存中的起始位置（基址）和段的长度

7. 各个段表项和各个页表项的长度是相同的。

   因此段号和页号可以是隐含的，不占存储空间。

8. 地址变换的过程：

   

9. 分页的主要目的是为了实现离散分配，提高内存利用率，分页仅仅是系统管理上的需要，完全是系统行为，对用户是不可见的。

   分段的主要目的是为了更好地满足用户需求，一个段通常包含着一组属于一个逻辑模块的信息，分段对用户是可见的，用户编程时需要显式地给出段名。

   页的大小固定，段的长度不固定，决定于用户编写的程序。

10. 不能被修改的代码称为纯代码或可重入代码，不属于临界资源，这样的代码是可以共享的，相当于只读。

    可修改的代码是不能共享的

    分段比分页更容易实现信息的共享和保护。

11. 与分页系统类似，分段系统中页可以引入快表机构，将近期访问过的段表项放到快表中

段页式管理方式

1. 分页、分段的优缺点分析

   	缺点	优点
   分页管理	不方便按照逻辑模块实现信息的共享和保护	内存空间利用率高，不会产生外部碎片，只有少量的内部碎片
   分段管理	如果段长过大，为其分配很大的连续空间会很不方便，另外，段式管理会产生外部碎片	很方便按照逻辑模块实现信息的共享和保护

2. 

3. 分段系统的逻辑地址结构由段号和段内地址（段内偏移量）组成

   

   段页式系统的逻辑地址结构由段号、页号、页内地址（页内偏移量）组成

   

   段号的位数决定了每个进程最多可以分几个段

   页号位数决定了每个段最大有多少页

4. 逻辑地址到物理地址的转换

   

虚拟内存

概念

1. 内存空间的扩充：

   • 覆盖技术

   • 交换技术（通过处理机调度的中级调度实现）

   • 虚拟存储技术（用到进程的某一部分，才调入内存，按页调入内存）

     可以在需要访问页面时，才把页面调入内存。

2. 传统存储管理方式

   

   特征：

   • 一次性：作业必须一次性全部装入内存后才能开始运行

     作业很大时，不能全部装入内存，导致大作业无法运行；

     当大量作业要求运行时，由于内存无法容纳所有作业，因此只有少量作业能运行，导致多道程序并发度下降。

   • **驻留性：一旦作业被装入内存，就会一直驻留在内存中，直至作业运行结束。**事实上，在一个时间段内，只需要访问作业的一小部分数据即可正常运行，这就导致了内存中会驻留大量的、暂时用不到的数据。

3. 高速缓冲技术的思想：

   将近期会频繁访问到的数据放到更高速的存储器中，暂时用不到的数据放在更低速存储器中

   

   快表机构就是将近期常访问的页表项副本放到更高速的高速缓冲寄存器中

4. 基于局部性原理，在程序装入时，可以将程序中很快会用到的部分装入内存，暂时用不到的部分留在外存，就可以让程序开始执行。

   在程序执行过程中，当所访问的信息不在内存时，由操作系统负责将所需信息从外存调入内存，然后继续执行程序。（当所访问的信息不在内存时，说明缺页，就是缺少进程的某一部分，进程分割为页面，缺少就时缺页，那么会发生缺页中断，这是内中断，属于硬件中断，中断之后，会使CPU立即进入内核态，将执行权由用户进程交给操作系统，操作系统把需要的页面即进程的某一部分调入内存，这就是中断，中断就是将执行权交给操作系统，操作系统执行相应的过程来满足程序运行。像进程运行时执行陷入指令发生自愿中断，因为涉及到系统调用，需要操作系统来完成某些事情，也是同理。原语是通过关中断和开中断来完成，级别很高，必须在内核态进行。）

   若内存空间不够，由操作系统负责将内存中暂时用不到的信息换出到外存。就是挂起，之前讲的中级调度，就是完成交换。交换出的进程会放到磁盘的交换区而不是文件区。内存又分为系统区和用户区。但是交换技术，讲的是进程之间，交换的是进程，这里的讲内存中暂时用不到的信息换出，指的是进程内部的页面，是属于进程内而不是进程间。

   在操作系统的管理下，在用户看来似乎有一个比实际内存大得多的内存，这就是虚拟内存。

   操作系统虚拟性，就是实际的物理内存大小没有变，只是在逻辑上进行了扩充。

   也就是内存中的进程只是这个进程的某一些页面，而不是一个完整的进程，通过调入调出页面来完成整个进程的执行。

5. 虚拟内存的特征：

   • 多次性：无需在作业运行时，一次性全部装入内存，而是允许被分成多次调入内存
   • 对换性：在作业运行时无需一直常驻内存，而是允许在作业（进程）运行过程中，将作业（进程的某些暂时用不到的页面）换入、换出。
   • 虚拟性：从逻辑上扩充内存的容量，使用户看到的内存容量远大于实际的容量。

6. 虚拟内存技术，允许一个作业分多次调入内存，如果采用连续分配方式，会不方便实现，因此，虚拟内存的实现需要建立在离散分配的内存管理方式基础上。

7. 操作系统需要提供请求调页（请求调段）功能

   操作系统需要提供页面置换（或段置换）功能

请求分页存储管理方式

1. 请求分页存储管理与基本分页存储管理的主要区别：

   在程序执行过程中，当所访问的信息不在内存时，由操作系统负责将所需信息（进程的页面）从外存调入内存，然后继续执行程序。

   若内存空间不够，由操作系统负责将内存中暂时用不到的信息换出到外存。

2. 页表机制：

   与基本分页管理相比，请求分页管理中，为了实现“请求调页”，操作系统需要知道每个页面是否已经调入内存；如果还没调入，那么也需要知道该页面在外存中存放的位置。

   当内存空间不够时，要实现页面置换，操作系统要通过**某些指标（页面置换算法）**知道该换出哪个页面，有的页面没有被修改过，就不需要浪费时间再写回外存，有的页面修改过，就需要将外存中的旧数据覆盖，因此操作系统也需要记录各个页面是否被修改的信息。

   

   请求页表项增加了四个字段

3. 缺页中断机构

   在请求分页系统中，每当要访问的页面不在内存时，便产生一个缺页中断，然后由操作系统的缺页中断处理程序处理中断。此时是发生IO操作，因为要将页面从外存调入内存。

   此时缺页的进程阻塞，放入阻塞队列，调页完成后，再将其唤醒，放回就绪队列。这里说的插入到队列里的都是PCB

   如果内存中有空闲块，则为进程分配一个空闲块，将所缺页面装入该块，并修改页表中相应的页表项。

   如果内存中没有空闲块，则由页面置换算法选择一个页面淘汰（从内存调到外存），若该页面在内存期间被修改过，则要将其写回外存，在内存期间未修改过的页面不用写回外存。

4. 缺页中断是因为当前执行的指令想要访问的目标页面未调入内存而产生的，因此属于内中断。

   一条指令在执行期间，可能产生多次缺页中断。

   

5. 

   • 只有写指令才需要修改修改位，并且，一般来说只需修改快表中的数据，只有要将快表项删除时才需要写回内存中的慢表，这样可以减少访存次数
   • 和普通的中断处理一样，缺页中断处理依然需要保留CPU现场
   • 需要用某种页面置换算法，来决定换出哪个页面
   • 换出、换入都需要启动慢速的IO操作。
   • 页面调入内存后，需要修改慢表的相应页表项，同时，需要将表项复制到快表中。

   请求调页时通过缺页中断进行！！缺页中断的目的就是请求操作系统调页。

页面置换算法

1. 用页面置换算法决定应该换出哪个页面

2. 页面换入换出需要磁盘IO，会有较大的开销，因此好的页面置换算法应该追求更少的缺页率

3. 页面置换算法

   • 最佳置换算法
   • 先进先出置换算法
   • 最近最久未使用置换算法
   • 时钟置换算法
   • 改进型的时钟置换算法

4. 最佳置换算法OPT

   每次选择淘汰的页面将是以后永不使用，或者在最长时间内不再被访问的页面，这样可以保证最低的缺页率。

   注意：发生了缺页中断，未必会发生页面置换，若还有可用的空闲内存块，就不用进行页面置换。只有内存不够用了才需要进行页面置换

   实际：操作系统无法提前预判页面访问序列，因此，最佳置换算法是无法实现的。 这是理想化的算法。

5. 先进先出置换算法FIFO

   每次选择淘汰的页面是最早进入内存的页面

   实现方法：把调入内存的页面根据调入的先后顺序排成一个队列，需要换出页面时，选择对头的页面即可。

   贝拉迪异常：当为进程分配的物理块数增大时，缺页次数不减反增的异常现象。

   只有FIFO算法会产生贝拉迪异常，另外，FIFO算法虽然实现简单，但是该算法与进程实际运行时的规律不适应，因为先进入的页面也有可能最经常被访问，因此算法性能差。

6. 最近最久未使用置换算法LRU

   每次淘汰的页面是最近最久未使用的页面

   实现方法：此进程对应的页表的页表项中，用访问字段记录该页面自上次被访问以来所经历的时间t

   当需要淘汰一个页面时，选择现有页面中t值最大的，即最近最久未使用的页面。

   

   此算法性能最接近最佳置换算法

   需要专门的硬件支持，算法开销大

7. 时钟置换算法CLOCK

   LRU算法是最接近OPT算法性能的，但是需要专门的硬件支持，算法开销大

   时钟置换算法是一种性能和开销比较均衡的算法

   

   

8. 改进型的时钟置换算法

   简单的时钟置换算法仅考虑到一个页面最近是否被访问过，事实上，如果被淘汰的页面没有被修改过，就不需要执行IO操作写回外存，只有被淘汰的页面被修改过时，才需要写回外存。

   因此，除了考虑一个页面最近有没有被访问过之外，操作系统还应考虑页面有没有被修改过，在其他条件都相同时，应优先淘汰没有被修改过的页面，避免IO操作。这就是改进型的时钟置换算法的思想。

   

   

   每一轮分别代表一个优先级

   第一优先级：最近没访问，且没修改过的页面

   第二优先级：最近没访问，但是修改过的页面

   第三优先级：最近访问过，没修改过的页面

   第四优先级：最近访问过，且修改过的页面。

9. 

页面分配策略

1. 驻留集：请求分页存储管理中，给进程分配的内存块（页框）的集合

   在采用了虚拟存储技术的系统中，驻留集的大小一般小于进程的总大小。

2. 驻留集大小

   固定分配：操作系统为每个进程分配一组固定数目的内存块，在进程运行期间不再改变

   可变分配：先为每个进程分配一定数目的物理块，在进程运行期间，可根据情况做适当的增加或减少。

3. 局部置换：发生缺页时只能选进程自己的物理块进程置换

   全局置换：可以将操作系统保留的空闲物理块分配给缺页进程，也可以将别的进程持有的物理块置换到外存，再分配给缺页进程。

   

4. 固定分配局部置换：

   系统为每个进程分配一定数量的物理块，在整个运行期间都不改变，若进程在运行中发生缺页，则只能从该进程在内存中的页面中选出一页换出，然后再调入需要的页面。

   这种策略的缺点是：很难在刚开始就确定应为每个进程分配多少个物理块才算合理

5. 可变分配全局置换：

   刚开始会为每个进程分配一定数量的物理块。操作系统会保持一个空闲物理块队列。当某进程发生缺页时，从空闲物理块中取出一块分配给该进程；若已无空闲物理块，则可选择一个未锁定的页面换出，再将该物理块分配给缺页的进程。

   采用这种策略时，只要某进程发生缺页，都将获得新的物理块，仅当物理块用完时，系统才选择一个未锁定的页面换出，被选择调出的页可能时系统中任何一个进程的页，因此这个被选中的进程拥有的物理块会减少，缺页率会增加。

6. 可变分配局部置换：

   刚开始会为每个进程分配一定数量的物理块，当某进程发生缺页的时候，只允许从该进程自己的物理块中选出一个进行换出。如果进程在运行中频繁地缺页，系统会为该进程多分配几个物理块，直至该进程缺页率趋于适当程度，反之，如果该进程缺页率很低，则会减少分配给该进程的物理块。

7. 何时调入页面

   

8. 从何处调入页面

   

9. 抖动现象：

   刚刚换出的页面马上又要换入内存，刚刚换入的页面马上又要换出内存，这种频繁的页面调度行为称为抖动。

   产生抖动的主要原因是进程频繁访问的页面数目高于可用的物理块数。

10. 工作集：

    指在某段时间间隔内，进程实际访问页面的集合。

    一般来说，驻留集的大小不能小于工作集的大小，否则进程运行过程中将频繁缺页（抖动）