慧记

主题

操作系统速成 ​

结构体系 ​

image-20241229213110750

第一章 操作系统绪论 ​

1.1 操作系统介绍 ​

1.1.1 定义 ​

操作系统是一组用于控制和管理，合理地对各类作业进行调度，以及方便用户使用的。

1.1.2 基本特征 ​

四大基本特征 ​

并发：是指两个或多个活动在同一给定的时间间隔中进行。

共享：是指计算机系统中的资源被多个进程所共用，

异步：进程以不可预知的速度向前推进。

虚拟：把一个物理上的实体变为若干个逻辑上的对应物

并发与并行 ​

并发指的是计算机在宏观过程中，是执行多个程序，但是在微观 过程中，处理器只执行了一个程序。

并行在同一时刻执行两个或多个程序。

换言之，同一时间间隔是并发，同一时刻是并行。

虚拟 ​

image-20241229214207560

1.1.3 主要功能 ​

处理机管理：主要功能包括进程控制、进程同步、进程通信、死锁处理、处理机调度等。

存储器管理：主要包括内存分配、地址映射、内存保护与共享和内存扩充等功能。

文件管理：主要功能包括文件存储空间的管理、目录管理及文件读写管理和保护等。

设备管理：主要包括缓冲管理、设备分配、设备处理和虚拟设备等功能。

1.1.4 发展 ​

手工操作阶段(此阶段无操作系统) ​
：人机速度矛盾
批处理阶段(操作系统开始出现) ​
  1. 单道批处理阶段:
:缓解人机速度矛盾；
:系统资源利用率依然低
  1. 多道批处理阶段(操作系统正式诞生)
:多道程序并发执行，资源利用率高
:不提供人机交互能力(缺少交互性)
分时操作系统(不可以插队，有了人机交互) ​
：提供人机交互(交互性)
：不能优先处理紧急事务
实时操作系统(可以插队) ​
  1. 硬实时系统:必须在被控制对象规定时间内完成(火箭发射)
  2. 软实时系统:可以松一些(订票)
：能优先处理紧急任务。

从可靠性看实时操作系统更强，从交互性看分时操作系统更强

1.2 概念 ​

1.2.1 两种指令 ​

特权指令：不允许用户程序使用（只允许操作系统使用）如I0指令、中断指令

非特权指令：普通的运算指令

1.2.2 两种程序 ​

内核程序：系统的管理者，可执行一切指令、运行在核心态

应用程序：普通用户程序只能执行非特权指令，运行在用户态

1.2.3 处理机状态 ​

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

核心态（又称管态、内核态）：可以执行所有指令

用户态到核心态：通过中断（是硬件完成的）

核心态到用户态：特权指令psw的标志位，0用户态，1核心态（仅做了解)

1.2.4 原语 ​

  1. 处在操作系统的最底层，是最接近硬件的部分

  2. 这些程序的运行具有原子性，其操作只能一气呵成

  3. 这些程序的运行时间都较短，而且调用频繁

1.2.5 中断和异常 ​

内中断 ​

异常，来自信号内部

  1. 自愿中断——指令中断
  2. 强迫中断
    1. 硬件中断
    2. 软件中断（eg: 0 /0）
外中断 ​

中断，信号来自内部

外设请求、人工干预（eg：打印机等）

1.2.6 系统调用 ​

系统给程序员（应用程序）提供的唯一接口，可获得OS的服务，在用户态发生核心态处理

1.2.7 体系结构 ​

体系结构：大内核、微内核

习题 ​

操作系统介绍 ​

image-20241229213348697

image-20241229214505636

image-20241229214515617

image-20241229214615320

image-20241229214637962

image-20241229214659161

image-20241229215505587

image-20241229215534703

image-20241229215557389

概念 ​

image-20241229221134761

image-20241229221206926

image-20241229221416046

image-20241229221628774

第二章 进程调度 ​

2.1 进程管理 ​

2.1.1 引入的目的 ​

2.1.2 定义 ​

是计算机中的程序关于某数据集合上的一次运行活动，是

2.1.3 组成 ​

PCB:保存进程运行期间相关的数据，是进程存在的唯一标志

程序段：能被进程调度到CPU的代码

数据段：存放数据

2.1.4 进程的状态 ​

状态种类 ​
  1. 运行态: 进程正在占用CPU
  2. 就绪态:进程已经处于准备运行的状态，即进程获得了除了处理机外的一切所需资源，一旦得到处理机即可开始运行
  3. 阻塞态:进程由于等待某一事件不能享用CPU
  4. 创建状态:进程正在被创建
  5. 结束状态:进程正在从系统消失
状态变化 ​

就绪态->运行态：处于就绪态的进程被调度后，获得处理机资源(分派处理机时间片)

运行态->就绪态：时间片用完或在可剥夺系统中有更高级的进程进入

运行态->阻塞态：进程需要的某一资源还没有准备好

阻塞态->就绪态：进程等待的事件到来时

image-20241231115214845

2.1.5 线程 ​

引入目的:

为了更好的使用多道程序并发执行，提高资源利用率和系统吞吐量

资源:

，基本不拥有任何系统特点

线程不是资源分配的最小单位，资源才是

2.2 处理机调度 ​

2.2.1 概念 ​

概念：是对处理机进行分配，即从就绪队列中按照定的算法(公平、高效)选择一个进程并将处理机分配给它运行，以实现进程并发地执行。

2.2.2 分类 ​

  1. 高级调度(作业调度
  2. 中级调度(内存对换）
  3. 低级调度（进程调度）

2.2.3 调度方式 ​

调度方式：剥夺式（抢占式）、非剥夺式（非抢占式）

image-20241231144242132

剥夺式（抢占式）例如：进程A、B，B的优先级大于A的优先级，并且A先开始运行，进入处理机，运行到30ms时，B进入，由于B的优先级大，B开始执行，B执行完成后，A继续执行

2.2.4 调度准则 ​

调度准则：CPU利用率系统吞吐量、周转时间、等待时间、响应时间

第二章 进程管理 | 慧记

2.2.5 算法 ​

算法：先来先服务、短作业优先、优先级调度算法、高响应比优先调度算法、时间片轮转、多级反馈队列调度算法

2.3 进程同步 ​

2.3.1 引入原因 ​

引入原因协调进程之间的相互制约关系

2.3.2 制约关系 ​

同步：亦称直接制约关系。是指为完成某种任务而建立的两个或多个进程，这些进程因为需要在某些位置上协调它们的工作次序而等待、传递信息所产生的制约关系。

互斥：t也称间接制约关系。当一个进程进入临界区使用临界资源时，另一个进程必须等待，当占用临界资源的进程退出临界区后，另进程才允许去访问此临界资源。

2.3.3 临界资源 ​

临界资源：一次仅允许一个进程使用的资源

例如打印机（A使用，B不能使用）

2.3.4 临界区 ​

临界区:在每个进程中访问临界资源的那段程序

2.3.5 临界区互斥 ​

原则 ​
  1. 空闲让进:如果有若干进程要求进入空闲的临界区，一次仅允许一个进程进入。
  2. 忙则等待：任何时候，处于临界区内的进程不可多于一个。如已有进程进入自己的临界区，则其它所有试图进入临界区的进程必须等待。
  3. 有限等待:进入临界区的进 程要在有限时间内退出，以便其它进程能及时进入自己的临界区。
  4. 让权等待:如果进程不能进入自己的临界区，则应让出CPU，避免进程出现“忙等”现象。
基本方法 ​

信号量、利用PV操作实现互斥

2.4死锁 ​

2.4.1 产生的原因 ​

产生的原因：非剥夺资源的竞争和进程的不恰当推进顺序

2.4.2 定义 ​

定义：多个进程因竞争资源而造成的一种僵局，如果没有外力，这些进程将无法推进

2.4.3 解决方法 ​

image-20241231151835520

习题 ​

进程管理 ​

image-20241231142109441

image-20241231142226160

image-20241231142339519

image-20241231142508874

处理调度机制 ​

image-20241231145433026

image-20241231145446612

image-20241231150027419

image-20241231150044867

image-20241231150136972

image-20241231150150350

进程同步 ​

image-20241231151300948

image-20241231151312271

image-20241231151324114

image-20241231151333252

死锁 ​

image-20241231151952385

对于互斥不摒弃，并且OS还比较支持(例如打印机)

image-20241231152123529

image-20241231152200982

image-20241231152429819

第三章 内存管理 ​

3.1 内存管理基本概念 ​

3.1.1 引入目的 ​

更好的支持多道程序的并发执行，提高系统性能

3.1.2 主要功能 ​

  1. 内存空间的分配与回收
  2. 存储的保护和共享:保证各道作业在各自的存储空间内运行，互不干扰
  3. 地址转换：在多道程序环境下，程序中的逻辑地址与内存中的物理地址不可能一致，因此存储管理必须提供地址变换功能，。
  4. 内存扩充：利用。

3.1.3 用户程序的主要处理阶段 ​

image-20241231162924982

3.1.4 相关概念 ​

程序的装入 ​

image-20241231163036646

image-20241231163058044

image-20241231163113637

程序的链接 ​

image-20241231163244101

地址空间 ​

image-20241231163305393

3.2 连续分配管理方式 ​

3.2.1 连续分配管理方式 ​

  1. 单一连续分配：分配到内存固定的区域(单用户/单任务的操作系统)
  2. 固定分区分配：分配到内存不同的固定区域，分区可以相等可以不等，但要求一定是固定。
  3. 动态分区分配
    1. 可变分区存储管理：按照程序的需要进行动态的划分
    2. 动态分区的分配策略算法:
      1. 首次适应：空闲分区以地址递增的次序链接。分配内存时顺序查找，找到大小能满足要求的一个空闲分区。
      2. 最佳适应：空闲分区按容量递增的方式形成分区链，找到第一个能满足要求的空闲分区。
      3. 最坏适应：空闲分区以容量递减的次序链接。找到第一个能满足要求的空闲分区，即挑选出最大的分区。
      4. 邻近适应：由首次适应算法演变而成。不同之处是，分配内存时从上次查找结束的位置开始继续查找。

3.3 非连续分配管理方式 ​

3.3.1 非连续分配管理方式 ​

概念 ​

最大的好处可以看到非连续三个字，是解决了动态分区，连续分区，单一分区中必须要连续分配的弊端，因为连续分配可能会出现很多的外部碎片，导致空间不能够充分利用。

基本分页式存储管理 ​

image-20241231164756994

基本分段式存储管理 ​

image-20241231164823200

3.4 内存扩容 ​

3.4.1 内存扩充 ​

覆盖(同一程序或进程中） ​

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

交换(不同进程/作业之间进行) ​

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

虚拟内存 ​

image-20241231170504974

image-20241231170554106

习题 ​

内存管理基本概念 ​

image-20241231163342826

连续分配管理方式 ​

image-20241231164447566

非连续分配管理方式（分页分段） ​

image-20241231165846055

image-20241231165836269

image-20241231165901873

虚拟内存 ​

image-20241231170637904

image-20241231170703195

第四章 文件系统 ​

4.1 文件与文件系统 ​

4.1.1 概念 ​

文件是以计算机硬盘为载体的存储在计算机上的信息集合

文件系统：就是操作系统中负责操作和管理文件的一整套设施，他实现文件的共享和保护，方便用户“按名存储”。

4.1.2 功能 ​

文件管理、目录管理、文件空间管理、文件共享和保护、提供方便的接口

4.2 文件的逻辑结构 ​

4.2.1 文件的逻辑结构 ​

无结构文件(即流式文件) ​

image-20241231172018571

有结构文件(记录式文件) ​

image-20241231172053004

4.3 目录 ​

4.3.1 目录和目录结构 ​

件控制块：在文件系统内部给每个文件唯一地设置一个文件控制块，它用于描述和控制文件的数据结构，与文件一一对应。 (本章节最重要概念)

目录结构：单级目录、二级目录、树形目录（像不像我们平时用的Windows操作系统？）、图形目录

4.4 文件实现 ​

4.4.1 文件分配方式 ​

连续分配、链接分配、索引分配，对应的结构是顺序结构，链式结构，索引结构。

4.4.2 文件存储空间管理 ​

（1）空闲表法（2）空闲链表法（3）位示图法

4.5 磁盘管理 ​

image-20241231173853553

题目 ​

文件与文件系统 ​

image-20241231171615454

image-20241231171635954

文件的逻辑结构 ​

image-20241231172214997

image-20241231172427535

在使用索引的情况下，查找流程通常分为两部分：首先查找索引，然后通过索引定位到具体的数据记录。对于索引查找，平均查找记录个数会更少，因为索引可以大大减少需要检查的记录数量。

100 组 / 2 + 100条 / 2

目录 ​

image-20241231173452864

文件实现 ​

image-20241231173742216

磁盘管理 ​

image-20241231173901227

第五章 设备管理 ​

5.1 设备管理 ​

5.1.1 设备管理的目标 ​

设备管理的目标：

使用方便、与设备无关、效率高、管理统一。

5.1.2 I/O设备 ​

分类 ​

存储设备或输入输出设备、块设备或字符设备、低速中速高速设备。

I/O控制方式 ​

image-20241231174607062

image-20241231174615342

5.2缓冲区 ​

5.2.1 引入缓冲区的目的 ​

  1. 缓和CPU与外设间速度不匹配的矛盾
  2. 提高CPU与外设之间的并行性
  3. 减少对CPU的中断次数

5.2.2 缓冲区的设置方式 ​

  1. 缓冲：当数据到达率与离去率相差很大时，可采用单缓冲方式。
  2. 双缓冲：当信息输入和输出率相同(或相差不大)时，可利用双缓冲区，实现两 者的并行
  3. 多缓冲：对于阵发性的输入、输出，为了解决速度不匹配问题，可以设立多个缓冲区

5.3 常用设备分配技术 ​

5.3.1 根据设备的使用性质 ​

独占设备：不能共享的设备，即：在一段时间内，该设备只允许一个进程独占。如打印机。

共享设备：可由若干个进程同时共享的设备。如磁盘机。

虚拟设备：是利用某种技术把独占设备改造成可由多个进程共享的设备。

5.3.2 针对三种设备采用三种分配技术 ​

  1. 独占分配技术：是把独占设备固定地分配给一个进程，直至该进程完成I/O操作并释放它为止。
  2. 共享分配技术：通常适用于高速、大容量的直接存取存储设备。由多个进程共享一台设备，每个进程只用其中的一部分。
  3. 虚拟分配技术：利用共享设备去模拟独占设备，从而使独占设备成为可共享的、快速I/O的设备。实现虚拟分配的最有名的技术是SPOOLing技术，也称作假脱机操作。

习题 ​

设备管理 ​

image-20241231174649029

image-20241231174718013

image-20241231174730619

缓冲区 ​

image-20241231174914832

常用设备分配技术 ​

image-20241231175212345

！！操作系统大题 ​

image-20241231203710254

PV操作 ​

现有一个具有n个缓冲区的缓冲池，Produce进程把它生产的消息放入一个缓冲区，Consumer进程可从一个缓冲区中取得一个消息消费。用信号量实现生产者和消费者之间的同步与互斥。请将下面的生产者和消费者算法补充完整。生产者和消费者对缓冲池互斥访问的信号量为SM，缓冲池的初值SB=n，缓冲池中消息个数 初值为SP=0。

image-20241231205805270

处理机调度 ​

image-20241231210542123

image-20241231210523007

image-20241231210535443

银行家算法 ​

image-20241231210855628

image-20241231210914623

页面地址计算 ​

image-20241231211217550

image-20241231211226390

image-20241231211313643

动态分区分配算法 ​

image-20241231211559775

最佳适应算法首次适应算法
image-20241231211649399image-20241231211742674

image-20241231211609891

磁盘调度算法 ​

image-20241231211938739

image-20241231212516126

image-20241231212629295

混合索引 ​

image-20241231212753940

image-20241231213011620

image-20241231213055022

Released under the MIT License.

Copyright © 2024 lihuibear