操作系统期末复习

第一章-操作系统引论

操作系统的作用

1. 作为计算机硬件系统之间的接口
2. 系统资源的管理者
3. 实现对计算机资源的抽象

操作系统的发展过程

未配置操作系统的计算机系统

1. 人工操作，用户独占全机，资源浪费
2. 脱机输入输出（Off-Line I/O）方式。

单道批处理系统

1. 这里批处理指的是把很多作业放在一个磁带上，一次性输入给计算机
2. 解决了人机矛盾(每执行一道程序都要手动装载)和cpu与I/O设备速度不匹配矛盾。提高了系统的吞吐量。
3. 缺点：系统资源利用率低（I/O请求成功前CPU空闲）。

多道批处理系统

1. 用户提交的作业都放在外存上，形成“后备队列”。
2. A在执行I/O请求时B进行作业，防止CPU空闲。
3. 多道：从1和2可以看出内存中可以同时存在多个程序，故为多道。
4. 好处：资源利用率高（显而易见，指CPU、存储器、设备和数据利用率高）、系统吞吐量大（指系统在单位时间完成的作业数量提升）
5. 缺点：平均周转时间长、无交互能力

这里注意，提交任务是在外存形成队列，而执行时多道指的是内存中可以有多道程序运行。

分时系统

1. 分时系统出现是为了满足人机交互的需求
2. 分时：采用轮转方式，每隔一段时间片调度下一个作业运行。
3. 分时系统的作业直接进入内存（要注意）。
4. 关键问题：及时接受、及时处理。

实时操作系统

这个我们RM电控用的就是RTOS。

1. “实时”指的是“及时”而非“实时计算”。
2. 实时系统规定了任务时间，如果规定时间内完不成则不再执行该任务，转而执行下一任务。
3. 好处是任务之间不会相互影响，比如一个执行很慢的任务和n个执行很快的任务，实时操作系统不会因为一个很慢的任务影响其他任务执行。而且具有可预测性，实时操作系统比如处理数据传输，那么就可以预测下一帧什么时候传来数据，因此可以做一个缓存加速读取（一般可以用来做视频帧处理）。

微机操作性系统

1. DOS是单用户单任务操作系统
2. UNIX是多用户多任务操作系统

操作系统的基本特性

操作系统的基本特性是：并发、共享、虚拟、异步。

并发

并发是指在内存中放多道作业，在很小的时间间隔内轮流执行多个作业，宏观上看起来在一段时间内执行了多道程序，微观上每个时间点只有一个程序在执行。

并行

一个时间点有多个程序在执行。比如利用多核同时运算。

虚拟

虚拟这个词说的比较玄乎，其实就说给东西重新起名字。比如硬盘上某个硬件区域我们给他起名字是C盘D盘之类的，就是虚拟。

你给一个东西起两个名字，比如一个信道起两个名字，看起来就是有两个信道，所以这就是虚拟信道。

异步

异步指的是多个程序的步调不一致，也就是说，有的程序执行的快有的程序执行的慢，只有一个CPU，那么整体执行起来看上去是“走走停停”的样子，所以叫做异步。

操作系统的主要功能

操作系统的主要功能有：处理机管理、存储器管理、设备管理、文件管理、操作系统与用户之间的接口。

微内核操作系统

微内核实际上是一个压缩版本的操作系统，只具有一些基本的功能。

1. 足够小的内核
2. 基于客户/服务器模式
3. 应用“机制与策略分离”原理
4. 采用面向对象技术

微核的目标是将系统服务的实现和系统的基本操作规则分离开来。例如，进程的输入/输出锁定服务可以由运行在微核之外的一个服务组件来提供。这些非常模块化的用户态服务器用于完成操作系统中比较高级的操作，这样的设计使内核中最内核的部分的设计更简单。一个服务组件的失效并不会导致整个系统的崩溃，内核需要做的，仅仅是重新启动这个组件，而不必影响其它的部分。

总之，就是可以提高安全性（这个很明显，把一般的操作放在操作系统外面，即使崩了也不会有大影响），操作系统也比较轻量。

第二章 进程的描述与控制

进程、程序、线程

进程

进程是程序的一次执行。

进程的结构：程序块、数据块、PCB。

PCB：系统中存放进程的管理和控制信息的数据结构，是操作系统中最重要的记录性数据结构。是进程存在的唯一标志。

进程的三种状态转换：

程序

程序是指令的有序集合。

具有静态性。

线程

程序执行流的最小单元。

线程是进程的组成部分。

引入线程以后，线程是调度和分配的基本单位，但不是拥有资源的基本单位（除了在运行过程中必不可少的资源，本身基本不拥有系统资源），进程才是拥有资源的基本单位。

如未引入线程，则进程是调度和分配的基本单位。

不管怎样，进程都是拥有资源的基本单位。

进程和程序的区别

1. 程序是静态的，进程是动态的。
2. 进程更能真实地描述并发，而程序不能。
3. 进程是由程序和数据、进程控制块PCB三部分组成的。
4. 进程具有创建其他进程的功能，而程序没有。
5. 同一程序同时运行于若干个数据集合上，它将属于若干个不同的进程。也就是说同一程序可以对应多个进程。

进程同步

两种制约关系

1. 间接相互制约关系：系统资源竞争，进程间彼此无关。
2. 直接相互制约关系：进程间合作，彼此相关。

临界资源

一次仅允许一个进程访问的程序。

临界区

每个程序中，访问临界资源的那段程序，注意是程序。

同步机制应遵循的规则

1. 空闲让进。
2. 忙则等待。
3. 有限等待。
4. 让权等待。

这16个字要背下来。

信号量机制

信号量原语

//P(s)
while s<=0:
    do no-op;
s=s-1;

//V(s)
s+=1;

1. 处理互斥
2. 处理同步

对于处理互斥，建立一个信号量mutex，初值为1，在互斥操作前后执行PV操作。mutex为1表示允许1个进程执行，小于等于0则等待，因此可以满足互斥请求。

对于处理同步，建立同步信号量n，表示允许执行的信号个数。

具体的还是看例子比较好理解：https://www.cnblogs.com/aoru45/p/11773325.html

进程通信

共享存储系统

进程间通过共享某些数据结构或共享存储区进行通信。

管道通信系统

在读写进程之间建立一个共享的文件，读的时候不能写，写的时候不能读。

消息传递系统

不必借助共享区域数据结构，以格式化的消息为单位，将通信的数据封装在消息中，并利用操作系统提供的一组通信命令，在进程间进行消息传递。

核心态、用户态

核心态：（内核态、管态）cpu可以访问内存的所有数据，包括外围设备，例如硬盘，网卡，cpu也可以将自己从一个程序切换到另一个程序。

用户态：只能受限的访问内存，且不允许访问外围设备，占用cpu的能力被剥夺，cpu资源可以被其他程序获取。

用户态到核心态的转换是通过系统调用。

第三章-处理机调度与死锁

处理机调度的层次

分为三个层次：高级调度（作业调度）、中级调度（在内存和外存之间调度）、低级调度（进程调度）。

周转时间

从作业被提交个系统开始到作业运行完的时间。

平均周转时间就是周转时间求和除以作业数。

进程调度的两种方式

1. 非抢占式：不允许某进程抢占已经分配出去的处理机。
2. 抢占方式：给定优先级，优先级高的可以抢占优先级低的已经在执行的进程。

作业调度算法

先来先服务（FCFS）

顾名思义，按照来的先后顺序分配和淘汰队列中的进程。

短作业优先（SJF）

执行时间短的作业先执行。

优先级调度算法（PSA）

优先级高的先执行。

最高相应比优先（HRRN）

相应比：周转时间/运行时间。

因此，按照相应比高的先执行。

例子

上面说的简单，来个例子就很容易理解了。

设有三个作业同时到达，运行时间分别为3、4、5 优先级为2,1,3，在单处理系统中按单道运行，则各种SJF和PSA的平均周转时间是多少？
\[SJF：\frac{3 + (3 +4) + (3+4+5)}{3} = \frac{22}{3}\PSA: \frac{4 + (4 + 3) + (4+3+5)}{3} = \frac{23}{3}\\]
设三个作业到达时间分别为0,1,2，实行时间分别是3,4,5，那么HRRN的平均周转时间是多少。

0时刻A先执行，3时刻执行完，则此时B、C的相应比分别为：
\[P(B) = (3-1 + 4) / 4 = 1.5\P(C) = (3-2 + 5)/5 = 1.2\]
所以先执行作业B。最后执行作业C。

平均周转时间为：
\[\frac{(3 + 3+4-1 + 3+4+5-2)}{3} = 6.33\]

进程调度

分时系统

转轮调度：即在分时系统中，给定一个时间片，每个进程获得1/n的时间片的处理机时间，比较好理解。

优先级调度、多队列调度、多级反馈队列调度、基于公平原则的调度、

实时系统

实时调度。

死锁

概念（背）：一组进程中，每个进程都无限等待被该组进程中另一进程占有的资源，因而永远无法得到该资源，这种现象称为死锁。

原因：资源竞争、进程推进顺序不当。

死锁的必要条件：互斥、不可抢占、请求和保持、环路等待。

死锁处理

预防死锁：破坏必要条件。

避免死锁：银行家算法。

检测死锁、解除死锁。

银行家算法

比较简单。以书上例题为例：

第四章-存储器管理

程序的装入和链接

程序要在系统中运行，要经过下面步骤：

1. 编译：由编译程序将用户源代码编译成若干个目标模块
2. 链接：由链接程序将目标模块和所需要的库函数链接
3. 装入：由装入程序将模块装入内存。

链接

分为：

1. 静态链接
2. 装入时动态链接
3. 运行时动态链接

装入

1. 绝对装入方式
2. 可重定位装入方式
3. 动态运行时装入方式

连续分配存储管理方式

是将用户程序装入内存的分配方式。

1. 单一连续分配
2. 固定分区分配
3. 动态分区分配

动态分区分配-基于顺序搜索的动态分区分配算法

首次适应算法（FF）

把第一个长度适应的未分配分区分配给程序。每次都从上往下找。

循环首次适应算法（NF）

与FF的区别就是NF从上一次分配的地方开始往下找，找一个轮回。

最佳适应算法（BF）

每次找一个最小的最适合的空间分配给程序。

最坏适应算法（WF）

每次找一个最大的最适合的空间分配给程序。

例题

分页管理方式

页

分页存储管理将进程的逻辑地址空间分成若干个页，并对各页加以编号，从0开始，如第0页，第1页等。

地址结构

分页地址中的地址结构如下：

它包含两部分内容：第一部分为页号P，后一部分为偏移量d，即页内地址。对某特定机器，其地址结构是一定的。

p = 地址/页面大小的向下取整 d = 地址/页面大小的 余数。

页表

在知道如何计算页号和偏移量后，要计算实际的物理地址，还需要知道页号在内存中的起始地址，如何知道每个页面在内存中存放的位置——操作系统要为每个进程建立一张页表。

页表地址寄存器

保存当前执行进程页表的起始地址和页表的长度

地址变换机构

基本地址变换

借助页表、页表寄存器完成作业逻辑地址（虚地址）到内存物理地址的变换

问题：从虚地址转换为物理地址，然后再完成地址访问，共访问几次主存，效率是多少？　　答：共访问两次主存，效率为50%

具有快表的地址变换

增设若干具有并行查询能力的特殊高速缓冲寄存器（联想寄存器\快表），保存当前执行进程的部分\全部页表表目，

具体流程为：查快表，找到则访问内存直接得物理地址，没找到则先访问内存查页表再访问内存查到物理地址

例题

\[某简单分页系统中，有2^{24}字节的物理内存，\\256页的逻辑地址空间，且页的大小为2^{10}字节，\\问逻辑地址需要多少位？\]

逻辑地址格式是页号加上页内偏移，页号256 即8位，页大小10位，所以是18位。

已知某分页系统，主存容量为4K，页面大小为1K，对一个4页大的作业，其0、1、2、3页分别被分配到主存的2、4、6、7块中，将十进制的逻辑地址1023、2500、3500、 4500转换为物理地址。
\[1023/1024 = 0 查到主存的第2块\\1023 \; mod \; 1024 = 1023\\物理地址 = 2 \times 1024 + 1023 = 3071\]

\[2500/1024 = 2查到主存的第6块\\2500\; mod \; 1024 = 452\\物理地址 = 6 \times 1024 + 452 = 6596\]

\[3500/1024 = 3查到主存的第7块\\3500\; mod \; 1024 = 428\\物理地址 = 7 \times 1024 + 428 = 7296\]

\[4500/1024 = 4查不到页号，缺页中断。\]