本文最后更新于 2024-04-27，文章内容可能已经过时。

1.绪论:

1.1 操作系统定义:

操作系统是一直运行在计算机上的程序，通常狭义上被称为内核（Kernel）程序，其他程序则为系统程序和应用程序。

它是资源管理平台，运行程序的平台，也是为用户提供服务的平台.

1.2 计算机系统:

1.2.1 体系结构图:

1.2.2: 初始化:

1.2.3 中断:

一个事件的触发是通过硬件或软件中断来实现的

在实现操作系统功能时，中断是一个非常重要的实现机制

系统一旦发生中断，CPU会运行中断服务程序(Interrupt Service Routine)，且每个中断都有自己对应的中断服务程序 ISR

系统通过中断向量表（Interrupt Vector Table）来管理中断请求与中断服务程序之间的对应关系.

现代的操作系统一般被视为以中断驱动（InterruptDriven ）或事件驱动（ Event-Driven ）的系统

1.2.4 I/O结构:

CPU负责内存与本地缓冲器之间的数据传递.

设备控制器负责在其所控制的外部设备与本地缓冲存储之间进行数据传递.

I/O 操作结束后，设备控制器通过中断通知 CPU 表示 I/O结束.

如磁盘控制器每次传输数据时，通过中断通知CPU，表示I/O结束.

1.2.4.1 DMA:

DMA直接访问内存是在专门的硬件控制下，实现高速外部设备与主存储器之间自动成批交换数据，尽量减少CPU干预的I/O操作方式.

有利于高速 I/O设备传送数据，接近于内存速度.

1.2.4.2 I/O类型:

同步:

只有 I/O 结束后，用户程序才能获得控制权，即 I/O 进行期间，用户程序无法继续运行。

异步:

I/O 还没有结束的情况下，用户程序可以获得控制权，即 I/O进行期间，用户程序可以继续运行。

1.2.5 存储结构:

两级存储.

一级存储设备指内存（主存）CPU可以直接随机访问的唯一大容量存储设备，是易失存储设备。易失存储设备指的是断电后，数据会丢失的设备.

二级存储设备: 一般不易失的存储设备，一般是磁盘类.

1.2.6 处理器系统:

1.2.6.1 单处理器:

系统中只有一个通用处理器（CPU），用来处理来自用户进程的指令.

除了通用处理器，系统一般还包括其他专用处理器，如磁盘控制器、图形控制器等.

1.2.6.2 多处理器:

系统中有多个处理器，又称为并联系统(parallel systems、tightly-coupled systems)，多个处理器共享一个内存.

CPU之间通过共享内存来进行通讯.

操作系统可以运行在某一个CPU上或多个CPU上.

多处理器环境下，不管多处理器还是多核处理器、每个处理器都需要有自己的寄存器和高速缓存.

1.3 类型:

1.3.1 批处理系统:

而所谓批处理系统,就是在当发生 I/O 操作时，由操作员手动的调度另一个程序运行，从而提高CPU的使用率.

1.3.2 多道程序系统:

把操作员的工作内容写到操作系统里，由操作系统进行任务的调度.

当系统进行 I/O 操作时，调度器就会选择另一个任务并运行.

1.3.3 分时系统:

给每个任务赋予一个给定的时间片（time slot，time slice）CPU 在多任务之间相互切换，如20msec为单位切换另一个用户.

1.4 操作：

1.4.1 双重模式操作：

一个操作系统可以被多个用户、多个程序所共享。多个用户之间、多个程序之间可能相互影响。非法或不正确的操作会导致系统崩溃或破坏。如无限循环会导致其他程序无法运行，会导致系统失灵或崩溃。

所以操作系统需要有一个保护机制.

双重模式：用户模式和内核模式。

如系统调用（System Call），当用户程序调用系统调用函数的时候，操作系统的运行模式从用户模式转变成内核模式，如调用 printf() 函数.

两种模式之间通过类似api的方式进行连接，从而避免了操作系统损坏的问题。

1.5 管理:

1.5.1 进程管理：

进程是运行中的程序，是系统的运行单元。

1.5.2 内存管理：

管理内存中的数据的存储、指令的运行。

内存管理的主要目的就是提高内存的使用率，从而有效使用内存。

1.5.3 文件系统管理：

操作系统对存储设备的物理属性进行了抽象的定义，即文件，它是存储的逻辑单元。文件通常组成目录以方便使用。

1.5.3.1 I/O子系统：

I/O子系统的目的是针对用户隐藏具体硬件设备的特性，它包括以下几个部分:

一个包括缓冲(buffer)、高速缓存(cache)和假脱机(spooling)的内存管理部分
通用设备驱动器接口
特定硬件设备的驱动程序)

1.6 其他操作系统:

云计算:

2.操作系统结构:

2.1 系统服务:

操作系统以不同形式向程序和用户提供服务.

2.2 用户界面:

2.2.1 命令行界面:

CLI（Command Line Interface）允许用户直接输入操作系统完成的命令

有的在内核中实现，有的通过系统程序实现.

2.2.2 图形用户界面:

GUI.

用户界面友好的桌面接口

• 通常使用鼠标、键盘和监视器

• 图标代表文件、程序、系统功能等

许多系统同时包含CLI和GUI界面.

2.3 系统调用:

是操作系统服务的编程接口,面向程序.通常用高级语言编写.

程序通过应用程序接口(API)访问，而不是直接使用系统调用.

举个例子:

每个系统调用都有一个固有番号(System Call Number),操作系统通过一张系统调用番号表来管理系统调用接口.

作为开发者来说，不需要关心系统调用是怎么实现的，只需要掌握它的使用规则就可以.

一般系统调用被运行库(run-time support library)来管理，运行库提供API，开发者调用运行库提供的API即可.

2.3.1 参数传递:

2.4 系统程序:

提供一个方便的环境，以开发程序和执行程序.为用户使用操作系统服务, 如文件管理器: 创建、删除、复制、重命名、打印、转储、列出和操作文件和目录.

可以说是在操作系统向应用层提供除了api之外的另一种服务.

系统程序不属于内核，但属于操作系统的一部分.

如查看文件目录,查看电脑的状态信息,修改文件,通信等功能.

2.5 操作系统设计和实现:

设计目标:

具体实现:

2.6 结构类别:

2.6.1 简单结构:

早期操作系统，规模小，简单，功能有限，以MS-DOS为例，以最小的空间提供最多的功能.

它没划分模块，尽管MS-DOS有某种结构，其接口和功能层没有划分清楚.

2.6.2 层次结构:

优点是简化了系统设计和实现，便于调试和升级维护,缺点是层定义，效率差.

2.6.3 微内核结构:

2.6.4 模块结构:

大部分现代操作系统采用模块结构:

– 使用面向对象方法

– 每个核心部件分开

– 每个与其他组件的会话被称为接口

– 每个组件在需要时被加载到内核

总体而言,与层次结构差不多,但是更加灵活.

2.7 虚拟机:

通过软件模拟的具有完整硬件系统功能的、运行在一个完全隔离环境中的完整计算机系统.

物理计算机的资源被共享，以创建虚拟机.

虚拟机是研发操作系统的完美载体.

3.进程管理:

3.1 进程:

定义：执行中的程序.

程序是被动的实体,进程是主动的实体,当一个程序被载入到内存中时,这个程序就会变成进程.

一个进程一般由以下内容，即进程在内存中的结构形式。

代码段（code section）

又称文本段（text section），通过程序计数器和处理器寄存器

的内容来表示当前活动（current activity)

栈（stack)：

包含临时数据，如函数参数，返回地址，局部变量

数据段（data section）

包含全局变量

堆（heap）

在进程运行期间动态分配的内存

简单理解为:代码加数据,加堆栈.

3.2 进程控制块:

操作系统是通过“控制表”对系统中的每个资源进行管理.

每个进程在操作系统内用进程控制块（Process Control Block：PCB）来表示，

进程在操作系统中体现的数据结构。它包含许多与一个特定进程相关的信息.

父进程调用子进程,进程之间是树形结构.

3.3 进程状态:

3.4 进程调度:

3.4.1 进程调度队列:

多道程序类型(multiprogramming)的目的是无论何时都有进程在运行，从而使CPU的利用率达到最大。为此，CPU需要在多个可用进程之间进行快速切换，调度程序从多个可用进程中选择一个进程运行.

操作系统持有就绪队列和一组设备队列，进程可以在多个调度队列之间移动.

当进程分配到CPU并运行时（运行状态），也就是进程运行过程中，可能发生下面事件中的一种并进入到就绪状态：

1. 进程可能发出一个 I/O 请求，并被放到 I/O 队列

2. 进程可能创建一个新的子进程，并等待该子进程结束

3. 进程可能会由于等待中断而强制释放 CPU，并被放回到就绪队列

4. 用完时间片（time slice / time quantum)，并被放到就绪队列

调度程序:

在就绪队列里选择程序的时候.

3.4.2 上下文切换:

当CPU从当前进程切换到另一个进程时，系统必须保存当前进程的相关信息，以备被切换的进程恢复运行.

将CPU切换到另一个进程需要保存当前进程的状态，并恢复另一个进程状态，这一任务称为上下文切换.

3.5 进程操作:

3.5.1 进程创建:

选项:

1. 资源共享选项

① 父进程和子进程共享所有资源

② 子进程共享父进程的部分资源

③ 父进程和子进程不共享资源

2. 执行选项

① 父进程和子进程同时执行

② 父进程等待子进程结束

3. 地址空间选项

① 子进程完全复制父进程内容

② 子进程覆盖父进程内存空间

过程:

在系统内部创建进程控制块
分配内存
载入可执行文件（通过调用exec()系统调用）
初始化程序

举例:

pid_t fork(void);
//返回：success 返回两次 返回值为0 代表当前进程是子进程
//                     返回值为非负数 代表当前进程是父进程，返回值为子进程ID

// 获取子进程退出状态并返回死掉的子进程ID 
pid_t wait(int *stat_loc);
参数为null 表示任意子进程结束就可以继续运行

int main() {
2. pid_t pid;
3. /* fork another process */
4. pid = fork();
5. if (pid < 0) { /* error occurred */
6. fprintf(stderr, "Fork Failed");
7. exit(-1);
8. }
9. else if (pid == 0) { /* child process */
10. printf(“I am a Child\n”);
11. }
12. else { /* parent process */
13. /* parent will wait for the child to complete */
14. wait (NULL);
15. printf (“I am a Parent\n");
16. exit(0);
17. }
18. }

在上面这个例子中，child和parent是按照顺序输出的，因为父进程只有在子进程结束之后才会继续运行。

如果没有这一句，那么父进程和子进程的结束时间是不可预测的，可能子进程还没有结束，但是父进程已经运行到了else 所以输出顺序不知。

与之前c语言创建函数不同的是，那个程序是在一个进程中的，这个是两个不同的进程，注意区分。

3.5.2 进程终止:

进程完成最后语句，并使用 exit( ) 系统调用请求操作系统删除自身，并终止运行，这时，

进程可以通过 wait( ) 函数返回状态值给父进程并释放资源，资源被操作系统收回.

父进程可以用 abort( ) 系统调用终止子进程的执行.

如果一个进程终止，它的所有子进程也将终止，这种终止被称为级联终止（Cascading Termination）.

僵尸进程:

即在僵尸状态的进程，它是进程终止的特殊情况，即一个进程结束，但是他的父进程没有等待他(调用wait/waitpid)，那么他将成

为一个僵尸进程。

3.6 进程间通信:

系统内并发运行的进程可以是相互独立或协作工作，进程协作的理由有信息共享、提高运算速度、模块化、方便.

大部分进程都需要进行进程的通信,主要分为消息传递和共享内存两种方式.

3.6.1 消息传递:

一个进程传递消息给另一个进程,易于实现,但是需要内核的参与.适合传输少量的数据.

消息传递功能提供了两种操作：发送消息和接收消息。而且消息可以是定长的或变长的.

假设进程 P 和 Q 需要通信，首先需要建立通信线路(communication link)，并相互发送消息和接受消息.

3.6.1.1 直接通信:

需要通信的每个进程必须明确地命名通信的接受者和发送者.

就是知道对方进程的信息,直接与其联系.

在非对称寻址当中,一个进程可以接受多个进程发来的消息.

3.6.1.2: 间接通信:

操作系统拥有的邮箱（端口）是独立存在的，操作系统必须提供机制以允许进程进行如下操作:

创建或删除邮箱（端口）
通过邮箱（端口）发送和接受消息

世界标准邮箱（端口）如网页WEB使用80号端口，FTP使用21号端口，Telnet 使用 23号端口, ssh 使用22号等.

比如一个web后端项目打开了8080端口,那么其他进程只需要访问这个端口,就相当于和这个后端项目进行通信,可以获得其对应的信息.

再比如java后端代码和数据库之间的连接也是通过一个端口(一般是3306)来获取信息的.

3.6.1.3 同步和异步:

消息传递可以是同步或异步，又称为阻塞(blocking)或非阻塞(non-blocking).

简单来说,同步就是只能发消息,消息不接收就不能进行操作.

3.6.1.4 缓冲：

缓冲队列一共分为三种：零容量，有限容量，无限容量。

3.6.2 共享内存:

两个或者多个进程共享同一块区域的内存,使用时直接读取.

速度更快,不需要内核的干涉.但是存在一些问题:

1.每个进程都有自己受保护的内存地址空间,通常操作系统试图阻止一个进程访问另一个进程的内存

地址空间.为了实现共享内存、便于两个或多个进程可以访问内存，共享区域应取消这个限制.

2.必须保障不能有两个以上的进程同时向共享区域写入数据，即需要一个同步机制.

3.6.2.1 生产者-消费者问题:

共享内存典型范例为生产者进程产生信息以供消费者进程消费的问题，即生产者和消费者问题.

为了允许生产者进程和消费者进程能并发运行，必须要有缓冲区被生产者和消费者所使用，此缓冲区为共享内存区域，该区域的实现可以采用以下两种方式:

3.7 客户机与服务器系统间通信：

3.7.1 套接字：

套接字（Sockets）由IP地址和端口号连接组成.连接由一对套接字组成。

3.7.2 RPC:

远程过程调用(Remote Procedure Call:RPC)抽象化了通过网络连接的进程之间过程调用。

Stubs(存根)：远程过程的代理，隐藏了通信发生的细节,每个独立的远程过程都有一个存根.

3.7.3 RMI:

Remote Method Invocation:RMI类似于远程过程调用，是RPC的JAVA 特性。

与RPC的不同,RPC调用远程子程序或函数，RMI调用远程对象的方法,RPC参数传递方式是普通数据结构，RMI参数传递方式可以是对象.

3.8 管道:

进程之间进行通信的另一种方式，管道通信方式的中间介质是文件，通常称这种文件为管道文件。

如两个进程利用管道文件进行通信时，一个进程为写进程，另一个进程为读进程。

3.8.1 管道实现：

FIFO (First In, First Out)缓冲区就像一个队列，在队列的一端添加元素，并以相同的顺序从另一端退出，任何一个元素都不可能先于另一个元素前进。

Multiple Inputs-多输入管道：一个管道可以有多个输入,但除了先进先出，没有顺序的保证。

4.线程：

为了提高CPU的使用率，目前我们想到的办法是多道程序，即当一个进程阻塞时（比如发生I/O请求的时候）切换到另一个进程运行。这确实能提高CPU的使用率，但伴随着一些代价，比如上下文切换。

线程的出现就是为了解决只使用进程管理程序的高代价问题而出现的一种技术.

4.1 多线程进程：

一个进程可以拥有多个线程，而且线程之间共享以下内容：

代码段，全局变量
打开的文件标识符
工作环境，包括当前目录，用户权限等

每个线程是独立的调度对象,一个进程可以拥有单个或多个线程，并共享内存空间.

4.2 关系模型：

操作系统的服务与线程之间存在某种关系，这个关系我们叫做关系模型

4.2.1 线程分类：

与双重模式操作一样，线程也分为两类：

1. 用户线程

I. 用户线程受内核的支持

II. 用户线程是由用户层的线程库来管理，无需内核管理

III. 当前主要线程库有：(1)POSIX Pthreads, (2)Win32 Threads, (3)Java Threads

2. 内核线程

I. 内核线程是由内核来管理

II. 有内核来进行维护和调度

III. 当前通用的操作系统，如 Windows, Solaris, Linux, Tru64 UNIX, Mac OS X 等都是支持内核线程

4.2.2 一对一模型：

一个用户线程映射到一个内核线程的模型，Linux，Windows.

一对一模型的唯一的缺点是创建一个用户线程就需要创建一个内核线程，造成内核负担重。

4.2.3 多对一模型：

多个用户线程对应一个内核线程。

多对一模型的缺点是一个用户线程一但被阻塞，其他用户线程也会阻塞，即针对同一个内核线程服务的用户线程无法提供并发功能。

4.2.4 多对多模型：

多个用户线程对应着多个内核线程。

多对多模型没有以上缺点，当一个线程执行阻塞系统调用时，内核能调度另一个线程的执行，但需要提供调度机制。

4.2.5 混合模型：

4.3 线程库：

为程序员提供的、创建和管理线程的 API，主要有以下两种方法来实现。

非嵌入到内核的方式：

是在用户空间中提供一个没有内核支持的库，此库的所有代码和

数据结构都存在于用户空间中

嵌入到内核的方式

是操作系统直接支持的内核库，此时所有代码和数据结构都存在

于内核中.

4.4 多线程程序相关问题：

4.4.1 fork()和exec():

如果进程中的某一个线程调用 fork()，那么新进程会复制所有线程呢，还是只复制调用 fork()的线程呢？

如调用exec()，就复制一个,如不调用exec()，就复制全部.

4.4.2 线程取消:

线程完成任务之前终止线程的任务.

目标线程的取消可能发生“要取消的线程正在更新与其他线程

所共享的数据”，为此，提供以下两种取消方式：

异步取消（Asynchronous Cancellation）：一个线程立即终止

目标线程.

延迟取消（Deferred Cancellation）：目标线程不断地检查它

是否应终止.

4.4.3 信号处理:

信号是用来通知进程某个特定事件的发生，这需要操作系统提供

一种内核和进程之间的通信机制。信号有以下两种：

I. 同步信号(内部信号)：进程本身事件产生的信号，如访问非法内存、除

零等

II. 异步信号(外部信号)：进程之外事件产生的信号，如按CTRL+C键等

4.4.4 线程池:

线程池（thread pool）的主要思想是在进程开始时创建一定数量的线程，并放入到进程池中等待工作。

4.4.5 调度程序的激活:

5.CPU调度:

多道程序的目的是使CPU的使用率最大化.

一个进程的执行由CPU执行(CPU区间)和I/O等待(I/O区间)组成。进程在执行的过程中，不断在这两个状态之间的进行切换.

经过对大量进程进行分析，得出的结论显示进程一般由大量的短CPU区间（<8ms）和少量的长CPU区间组成.

1.I/O为主的程序里短CPU区间较多，

2.CPU为主的程序里长CPU区间较少.

每当CPU空闲时，调度程序(短期调度程序)从就绪队列中选择一个进程，并为之分配CPU.

可以采用各种不同的排序方式对就绪队列中的进程进行排序(可以理解为不同的调度算法).

5.1 非抢占调度和抢占调度:

非抢占调度（nonpreemptive）:

一旦把CPU分配给一个进程，直到该进程结束之前，不能把CPU分配给其他进程.

抢占调度（preemptive） :

进程在执行过程中，可以被其他进程抢占CPU使用权.

5.2 分派程序:

5.3 调度准则:

5.3.1 因素:

CPU使用率（CPU Utilization）：需要使CPU尽可能忙
吞吐量（Throughput）：指的是在一个时间单元内所完成的进程数量
周转时间（Turnaround Time) ：从进程提交到进程完成的时间段称为周转时间。周转时间为所有时间段之和，包括等待进入内存，在就绪队列中等待，在CPU上执行和I/O执行
等待时间（Waiting Time）：在就绪队列中等待的时间
响应时间（Response Time）：从提交请求到产生第一相应的时间。注意，它是开始响应所需要的时间，而不是输出响应所需要的时间（交互系统）

5.3.2 先到先服务:

哪个进程先来了,就调用那个进程.

平均等待时间就是所有进程的等待时间/进程数量.

由于上述问题,先到先服务算法不能很好的满足所有进程的需要.

5.3.3 最短作业优先:

选择CPU区间长度最短的进程，这里的CPU区间是进程的下一个CPU区间（也就是剩余CPU区间），而不是进程整个区间长度。可分为非抢占调度和抢占调度.

对于给定的一组进程，在平均等待时间上，最短作业优先调度算法是最优算法.

问题是预先知道下一个CPU区间(remaining execution time)的长度是有难度的。

非抢占式:

在一个进程结束后,从等待的进程里选择区间时间最小的进程开始运行.

抢占式:

在一个进程运行时,如果有区间时间更短的进程开始,就抢占当前的进程,在当前进程完成之后,在运行上一个进程.

每个进程都有它的优先级，通常用数字来表示进程的优先级，数字值越小它的优先级越高。

5.3.3.1 问题:

无限阻塞:

解决方案:增加进程的随着时间增加而增加的优先级.

5.3.4 轮换法:

给每个进程分配一个时间片(time slice, time quantum)。时间片一般是10-100毫秒.

系统每隔一个时间片发出一个时钟中断(clock interrupt)，并调度另一个进程执行.

如果进程在给定的时间片内提前结束，发生中断并调度另一个进程.

根据经验,时间片大于80%的CPU区间即可.

5.3.5 多级队列:

将就绪队列分为多个不同的队列,每个队列都有自己的调度算法,而不同队列之间也有响应的调度机制.

类似于分布式的思想.

5.3.6 多级反馈队列;

进程可以在多个队列之间移动.

5.4 多处理器调度:

5.4.1 介绍:

同构处理器:功能,结构相同.

异构处理器:功能,结构不同.

5.4.2 处理类型:

负载平衡（load balancing）:

保持所有处理器的工作负载均衡.

5.5 线程调度:

区分用户线程和内核线程，多线程系统的调度对象是线程.

5.6 实时调度:

进程有截止时间的要求.这种进程被称为实时任务.

算法:

6.进程同步:

多个进程同步工作时,需要共享数据,确保数据一致性.

避免发生进程之间竞争的关键问题是确保操作共享数据的代码段执行同步.

6.1 临界区问题:

1.确保单个进程在临界区执行.

2.确保其他进程也可以进入临界区.

6.2 Peterson`s 算法:

这段代码的意识是i想进入临界区.

首先设置其flag为true,然后用while语句进行等待,如果j依然在临界区,就不会继续进行下去,即程序不会继续进行.

然后i进入临界区,进行操作,然后再设置为false.

6.3 硬件同步:

许多系统拥有简单的,不可中断的指令,用他们来解决临界区问题.

6.3.1 有限等待原子指令:

6.4 信号量:

无忙等待的同步功能工具.

6.4.1 二进制信号量:

适用于单资源的共享,又称为互斥锁.

信号量的实现关键是保障 wait( ) (减)和 signal( ) (加)操作的原子执行，即必须保障没有两个进程能同时对同⼀信号量执⾏ wait( )和 signal( ) 操作。

6.4.2 无忙等待:

6.4.3 优化约束:

计数信号量可以适用于优化约束问题.

即把信号量设置为0,先开始的那个进程不需要减信号量,只需要在结束之后对信号量加一,表示已经被释放.

而后开始的进程需要在一开始减去信号量,在最后也不需要加上信号量.

P1:
do{
//write operation
signal (mutex);
} while (TRUE);


P2:
do{
wait (mutex);
// read operation
} while (TRUE);

6.5 死锁与饥饿:

两个或者多个线程无限的等待一个事件,而这些事件只能由这些等待的线程产生.

与死锁相关的另⼀个问题是饥饿问题:即进程在信号量内无限期的等待.

6.6 经典同步问题:

6.6.1 有限缓冲:

假定缓冲池中有 n 个缓冲项, 每个缓冲项能存⼀个数据项

1. ⽤信号量 empty: 表⽰空缓冲项的个数

2. ⽤信号量 full ：表⽰满缓冲项的个数

3. ⽤信号量 mutex : 提供对缓冲池的读写互斥

• 信号量 mutex 初始化为1

• 信号量 full 初始化为 0

• 信号量 empty 初始化为 n.

//生产者:
while (true) {
// produce an item
wait (empty); //empty>0, 只要有空缓冲项，就写
wait (mutex);
// add the item to the buffer
signal (mutex);
signal (full);
}

//消费者
while (true) {
wait (full); //full > 0, 只要缓冲项⾥有数据，就读
wait (mutex);
// remove an item from buffer
signal (mutex);
signal (empty);
// consume the removed item
}

6.6.2 读者-写者:

6.6.3 哲学家进餐:

6.7 管程:

⼀种⽤于多线程互斥访问共享资源的程序结构.

任⼀时刻最多只有⼀个线程执⾏管程代码.

6.7.1 组成:

用条件变量阻塞进程的运行.

7.死锁:

7.1 成因:

进程R1,R2 进入无限的等待,即出现了死锁.

7.2 资源分配图:

两种节点:进程节点和资源节点.

有向边:

如果资源分配图没有环,那么肯定没有死锁,如果有环,就可能发生死锁.

7.3 死锁预防:

7.3.1 占有等待:

确保当一个进程请求一个资源时，它不能占有其他资源。

实现的方法如下

A. 每个进程在执⾏前申请并获得所有资源

B. 进程只有在不占⽤资源时, 允许进程申请资源

就是已经占有资源的进程不能再占有其他的资源,从而避免了循环的问题.

7.3.2 非抢占:

7.4 避免死锁:

7.4.1 资源分配图:

需求边是进程指向资源的虚线.

申请边是进程指向资源的实线.

分配边是资源指向进程的实线.

对于申请,如果没有环(不算虚线).就会允许,否则不允许.

7.4.2 银行家算法:

由安全性算法和资源请求算法组成.

7.4.2.1 安全性算法:

伪代码如下:

Work = Available;
l For all i, Finish[i] = false;

For all i do
if ( Finish[i] == false && Needi £ Work)
Finish[ i ] = true
Work = Work + Allocationi
End for

IF for all i, Finish[i] == true
Then the system is safety
End IF

安全检查的是,能否使用当前的所有资源解决所有进程的问题.

所以work还要再加上当前进程已经占有的资源.

7.4.2.2 资源分配算法:

假设请求的资源是requesti.

Available = Available – Requesti;
Allocationi = Allocationi + Requesti;
Needi = Needi – Requesti

占用资源加,需要资源和可分配资源减少.相当于分配资源的过程.

每次资源分配之前都需要进行安全性检查.

7.5 死锁检测:

7.5.1 单个实例资源:

把资源分配图变成等待图.

等待图只有进程到进程的连线,把原先图中的资源去掉.

7.5.2 多个实例资源:

Work = Available
For all i do , 
IF Allocationi ¹ 0, Finish[i] = false;
ELSE Finish[i] = true;
End For
For all i do , 
IF Finish[i] == false && Requesti £ Work
Work = Work + Allocationi ;
Finish[i] = true;
End IF
If there is a i, Finish[i] == false
then the system is deadlock；
End For

7.6 死锁恢复:

7.6.1 终止进程

通过终止进程的方式恢复死锁.一次只终止一个进程直到取消死锁循环为止, 但要考虑:

7.6.2 抢占资源:

通过抢占资源以取消死锁，逐步从进程中抢占资源给其他进程使用，直到死锁被打破为止。

8.内存管理:

内存和寄存器是CPU唯一能直接访问的存储器,为了运行程序，必须把程序从磁盘载入到内存.

为确保进程只访问合法地址范围，一个进程使用的内存地址范围是由一对:

基地址寄存器(base register)
界限地址寄存器(limit register)

8.1 地址绑定:

地址绑定就是建立逻辑地址到物理地址的映射.

8.1.1 时机:

程序主要有编译,加载,执行三个过程,这三个过程都可以进行地址绑定.

8.2 动态加载:

直到被调用之前,程序不会载入内存.

内存使用率高,但是需要特别设计.由程序的设计者决定

8.3 静态/动态链接:

动态加载由操作系统决定.

• 常规编译
$ gcc -o main main.o bill.o fred.o
• 静态链接
$ gcc -o slmain main.o libfoo.a
• 动态链接
$ gcc -o dlmain main.c -L ./ -ltest

8.4 交换:

进程可以暂时从内存中交换到备份存储上(通常是快速磁盘)，当需要再次执行时再调回到内存.

在编译和加载时进行内存绑定的,交换后必须回到要原位.

在运行时进行内存绑定的,不需要回到原位.

8.5 内存分配方式:

为进程分配内存的方式.

8.5.1 连续分配:

每个进程位于连续的内存区域（多分区方法和可变分区方法）.

多分区方法:

多个大小固定的分区.这些分区可以是大小相同的,可以是大小不同的.

可变分区方法:

整个内存空间是就是一个大孔, 操作系统用表来记录已用和未用内存.

8.5.2 不连续分配:

帧：把物理内存划分为固定大小的块儿，称为帧。

页：把逻辑内存划分为固定大小的块儿，称为页。

一个页对应一个帧，当需要分配内存时，以页为单位分配内存.

帧是不连续的内存空间.

8.6 地址变换:

为了访问数据，需要两次访问内存,第一次查页表，第二次访问地址.

8.6.1 页表结构:

8.6.1.1 层次结构:

把逻辑地址编址设为多层次，即多层次的页表。

可以实现页表的不连续存储,节约内存空间.

8.6.1.2 哈希页表:

逻辑地址的定义为【虚拟页码，偏移量】把虚拟页码作为哈希值(key).

根据虚拟页码（哈希值）找到匹配的条目，并在链表里找到相对应的帧号.

8.6.1.3 反向页表:

为了减少页表消耗的内存空间而采用的方法即，整个系统只有一个页表，页表对于每个真正的内存页或帧才建立一个条目.

9.虚拟内存:

虚拟内存是内存管理的一种技术，它允许执行进程时不必,完全载入内存，可以部分程序载入到内存.

可以提供更有效的进程创建.

9.1 按需调页：

按照需要，调取页进入程序。

9.2 页置换：

1.找出一个牺牲的帧，并将其换出.

2.需要使用的页，将其换入.

页置换发生两次页传输（换入、换出），导致页处理时间加倍，增加了内存访问时间。

针对这个问题有两种解决方案：

1.每个页关联一个修改位（modify bit）

2.系统保留一个空闲帧缓冲池，当需要牺牲帧写出虚拟内存时，写出之前，从空闲帧缓冲池中先得到内存（即先分配后换出）。

页置换算法：

10.文件系统:

文件是逻辑外存的最小分配单元.大致分为数据和程序.

文件根据其类型具有不同的结构（格式）.

10.1 文件属性:

10.2 文件访问:

10.2.1 顺序访问:

文件信息按顺序，一个记录接着一个记录地加以处理.

10.2.2 直接访问:

文件由固定长度的逻辑记录组成
操作系统所提供的块儿号通常为相对块号，它是相对于文件开始的索引

10.2.3 目录结构:

• 每个磁盘分区可以创建一个文件系统

• 存储文件系统的一大块存储空间称为卷