操作系统复习_索引存取和随机存取的区别

---

前言

参考书籍：CDIO之路

---

第二章处理机管理

1.操作系统两个重要特性：程序并发性和资源共享性。（促进多道程序的发展）
2.程序执行分为：顺序执行和并发执行
顺序执行（内部顺序性+外部顺序性）的主要特点： 封闭性 可再现性
并发执行（无须满足外部顺序）：资源共享性 失去封闭性和可再现性
3.进程（动态）是程序（静态）的动态执行
进程实体 = 程序 + 数据 +进程控制块PCB（进程存在的唯一标志）
进程分为 系统进程和用户进程
4.进程的基本状态模型：初始状态，执行状态，阻塞状态，就绪状态，终止状态
执行变为阻塞：进程自己原因（需要使用某种资源）
执行变为就绪：时间片已到或出现优先级更高的进程
引入挂起态：当系统资源不足时…需要挂起某些进程，且不在主存
5.作业：一次计算过程中，从输入开始到输出结束，用户要求计算机所做的关于计算的全部工作。
作业 =程序 + 数据 +作业说明书（在系统中生成作业控制快JCB）
作业表：为了对作业进行管理，将所有作业的JCB构成一张表，存放在外存。
6.PCB作用：
A.标志进程的存亡
B.根据PCB进行并发执行的管理控制

PCB的内容
进程相关的描述信息，进程的控制信息，资源管理信息
7.进程上下文：进程实体和支持进程运行的环境
状态保存+选取新进程+状态恢复
进程上下文切换：从一个进程A切换到另一个进程B，需要保存被切换进程A的状态，并恢复B进程的状态
进程切换的时机：
中断 ，异常，系统调用
进程上下文切换步骤：
1.当前运行进程被中断时保存期CPU现场信息
2.对被中断的当前运行进程进行PCB更新
3.将被中断的当前运行进程的PCB移入适当队列
4.由进程调度程序调度选中另一个就绪进程，为其设置上下文环境并对其PCB进行更新。
5.修改新地址的地址空间，内存管理信息
6.恢复被选中进程CPU现场信息

8进程控制（创建删除+进程通信状态转换…）
主要有 进程管理和原语操作
原语：系统态下执行的某种具有特定功能的程序段（一类在执行期间不允许发生中断的系统调用）
9.进程控制原语：
进程创建.
进程撤销：由被撤销进程的父进程调用，以释放资源。（a.进程完成任务正常撤销b.进程出现故障被迫撤销）
进程阻塞：执行变为阻塞
进程唤醒：阻塞变为就绪
10.多线程（支持一个进程中执行多个线程的能力）
同一进程中的所有线程继承并共享所属进程的一切资源。
进程是资源分配的基本单位，线程是处理机调度的基本单位。
线程控制块TCB
线程分为 用户级线程（线程库管理） 内核级线程（系统内核管理） 组合线程
11.处理机调度：CPU资源在可运行实体之间的分配
实质：资源分配
一个作业提交之后，通常要经过作业调度和进程调度两个过程才能获得处理机。
12.处理机的四级调度
作业调度：又称为长程调度，从输入井选择一个或一批作业，将其调入内存，并分建立进程。（后备状态——运行状态，运行状态——完成状态）
交换调度
进程调度：又称为短程调度，选取活跃就绪的进程占用CPU并进行进程的上下文切换。（活跃就绪——执行状态）
线程调度：内核级线程调度（必须完成模式间的转换），用户级线程调度
13.处理机调度方式（一个线程或进程正在执行，来了个优先级更高的）
非抢先方式：必须等待原处理机上的进程阻塞或完成
抢先方式：依据某些规则，剥夺原进程分配给新进程
（时间片原则，优先级原则，短进程优先原则）
14.中断是系统有用户态转换为系统态的必要条件。
15.调度策略与算法
A.先来先服务
B.最短周期优先，最短剩余剩余时间优先（抢先式调度）
C.最高优先级优先（静态优先级，动态优先级）
D.时间片轮转（固定时间片轮转，可变时间片轮转）
E.多级反馈队列

第一级就绪队列优先级高但是时间片短
下面的高级就绪队列优先级低但是时间片长
新进程进入系统时先加入Q1，如果未完成，则加入下一级队列末尾
进程因输入输出而放弃CPU，返回到同级队列
F.实时调度
G.响应比高者优先算法
响应比=作业周转时间/作业处理时间=（作业处理时间+作业等待时间）/作业处理时间=1+（作业等待时间/作业处理时间）
等待时间=最后一个的提交时间-该作业到达的时间
作业执行规则，响应比高的先执行

第三章进程同步与通信

1.进程通信根据信息量的多少分为 高级通信和 低级通信（包括进程的互斥与同步）
2.多个并发进程之间的的制约关系 直接制约 （一个进程的执行依赖于另一个进程进程同步）和 间接制约 （各并发进程受共有资源的约束 进程互斥）
3.变量集 = 引用变量集（读取） + 改变变量集（改变）
4.临界资源：一次只允许被一个进程使用的一类资源。（互斥资源）
临界区：不允许多个并发进程交叉执行的一段程序，通常在临界区前增加一段用于检查共享变量状态的代码（进入区）。
解决临界区的必要条件：各个进程对于临界资源必须互斥的使用。
5.实现进程互斥：
软件方法：
A.严格轮换法（设置公共整型变量，标识是否允许进入临界区）
B.Peterson算法（保留公共整型变量，并为每个进程设置标识flag）
硬件方法：
A.关中断
B.使用测试和设置指令
C…
6.进程同步. 运用原语sleep 和 wakeup
7.信号量——进程同步与互斥的工具
UP（P）：信号量S的值加一
DOWN(N)：信号量S的值减一
解决互斥问题的时不会出现忙等待，解决同步问题的时候不会丢失信号。
互斥问题初值1 同步问题初值0
当用于解决互斥问题的时候，PV处于同一进程，当解决同步问题时，一般不在同一进程出现
8.高级通信（进程之间大批量的数据交换）
高级通信机制：
消息传递系统：发送和接受原语send(),receive()，若进程之间需要中间实体，则为邮箱机制，投递原语和读取原语，deposit(),remove(),
共享存储器系统，（不需要系统内核的帮助）
共享文件系统（管道通信）：
A.无名管道：只允许单向通信，临时文件，完成通信后不存在
创建函数pipe(int fd[]) fd[0]为读出端 fd[1]为写入端
建立之后无需通过open就可以进行读写，文件系统也看不到无名管道的存在。
通过无名管道通信的进程必须是父子进程
B.有名管道：双向通信，父子关系不是必须的，可以在文件系统上长期存在，
使用时需要先用open系统调用打开
9.死锁：所有死锁进程都在等待资源，又都占有资源，且不释放自己占有的资源。
一个进程不会发生死锁
产生死锁的必要条件：
1.互斥条件（Mutual exclusion）：资源不能被共享，只能由一个进程使用。
2.请求与保持条件（Hold and wait）：已经得到资源的进程可以再次申请新的资源。
3.非剥夺条件（No pre-emption）：已经分配的资源不能从相应的进程中被强制地剥夺。
4.循环等待条件（Circular wait）：系统中若干进程组成环路，该环路中每个进程都在等待相邻进程正占用的资源。

第四章 存储管理

1.存储器= 内存（系统区和用户区） + 外存
存储管理基本功能：地址转换，存储保护，共享，内存分配和回收
进程地址采用逻辑地址（可多维） 内存物理地址空间是一维的
2.地址转换：把进程的逻辑地址转换为内存的物理地址。
地址转换：静态地址重定位（连续的内存空间），动态地址重定位（需要借助硬件，不连续的地址空间）。
3.存储保护：避免其他进程的未经授权的读写操作访问这个进程的存储单元。
存储共享：当多个程序执行同一个程序时，避免每个进程拥有单独的副本，而允许他们访问该程序的同一个副本。
4.内存扩充：把内存中暂时不能运行的进程换出到外存中腾出空间，把外存中具备运行条件的进程换入内存。
方式： 覆盖（应用程序控制）：将一个进程中，不会同时执行的程序段共用一个主存 区。 本质上是以时间延长换取空间节省。

交换：利用外存进程交换区，进程实体进行整体交换
请求调入：程序执行时，如果程序和数据不在内存，则操作系统自动从外存调 入内存。
预调入：预测不远的将来CPU会用到的程序和数据，并在合适的时机调入。
5.内存分配与回收（为每一个并发执行的进程分配空间）
A.连续分配方式（分配连续的空间）：
单一连续分区管理：只能存放单道应用程序。
分区管理方式：（支持多道程序设计）
分为 固定分区 和 动态分区
固定分区：作业装入之前，内存被分配为若干固定大小的连续分区（可大小不同，但分区个数不可变）可采用静态地址重定位或者动态地址重定位。
当进程大小小于分区长度时，分区内部的剩余空间称为内部碎片。
为了对分区进行管理与控制，需要数据结构——分区说明表。
动态分区：根据进程大小对内存进行划分，分区个数可变。（只能采用动态地址重定位）
随着时间推移，内存空间会产生许多外部碎片。
数据结构：分区说明表（已占有），空闲分区表
为了减少外部碎片的浪费，采用分区的紧凑技术，要求进程在运行过程中可以进行在内存中移动，需要硬件的支持（支持动态重定位）。
用户程序1 用户程序1
10KB 用户程序2
用户程序2 30KB
20KB
存储共享，分配算法P159
回收算法P161
覆盖和交换P162
B.离散分配方式（一个程序离散的分配到内存的多个不相连区域）：
分页存储管理：
基本原理：将进程的逻辑地址空间划分成大小相等的块，每一块称为一页，由页号和页内地址组成，内存空间也划分成同样大小的块，每一块称为一页面。进程在每个页面内的地址是连续的，各个页面间的地址并不要求连续。
数据结构：页表（实现从页号到物理页面号的地址映射），作业表（记录每个作业的页表起址和页表长度），存储页面表（记录内存分配情况，位示图法和链表法）。
地址转换： 物理地址=页面号*页表长度+页内地址（访问两次内存）
存储保护：越界保护（如果页号大于页面长度则越界中断）+通过页表控制对内存信息的操作方式以提供保存。
存储共享P167
分段存储管理：
将进程划分为若干具有完整逻辑意义的段，（段的长度可变，段号+段内地址）为每一段分配连续的内存空间，而各个段之间不要求连续
地址转换：P170（访问两次内存）
段页式存储管理：
基本原理：将整个内存划分成大小相等的页面，将进程按逻辑分为若干个段，把每段的线性地址空间划分成与页面大小相等的页。
数据结构：作业表+段表+页表
地址变换：访问三次内存
C.虚拟式存储管理（通过部分装入对换，超内存时也可以使用）：
部分装入：当一个进程执行时，若需要访问的指令和数据在内存中则继续执行，若不在内存，则将这部分信息自动调入内存。
部分对换：若内存中没有足够的空间，则系统将内存中暂时不用的信息从内存中调出。（部分兑换以页或段为单位，交换以整个进程为单位）
请求分页式管理：（增加请求调页和页面置换功能）
根据页面调入时机不同：请求页式管理（发生缺页中断，从外存调入内存）和预调入页式管理（动态预测，预先调入若干页面而非一个页面）
请求页式管理如何处理缺页中断，如何从内存中换出页：扩充页表的内容P176
请求页式管理分配策略：在内存中页面数不低于总页面数的一半。固定分配（保持页面数固定不变，只要发生一个缺页中断，就会有一页被替换掉）可变分配（分配的页面数可变）
页面置换策略：全局置换（从所有页面中选择一个替换页面）和局部置换（从属于进程自己的页面中选择一个替换页面）
置换算法（选择以在内存中的那个页面调出）：随机页面置换算法，先进先出页面置换，最近最久未使用页面置换，
请求分段式管理（增加请求调段和分段置换）：
P180
请求段页式管理：
P180

第五章文件系统

1.文件系统包括 文件（存储用户和系统的程序和数据）和目录（组织系统内的文件）
2.数据项：基本数据单元
记录：（数据项的集合），在逻辑上具有独立意义的最小信息单位
文件：（一组相关记录的集合）
数据库：相关数据的集合
3.文件属性（例如保护属性，管理属性…）所有属性都保存在目录结构（外存上）
4.文件组织
逻辑结构：
A.字符流式的无结构文件（对文件内的信息不在划分单位组成信息，如源程序文件，目标代码文件，可执行程序文件，库函数文件，等对基本信息单位操作不多的文件）
B.记录式的的有结构文件（把文件内的信息按逻辑上独立的，方便用户对记录进行修改查找和删除）
常见的结构：堆，顺序文件，索引顺序文件，索引文件，直接文件
记录成组：把若干的逻辑记录和成一组存放在一块的工作（输出缓冲区）
记录分解：逻辑记录从物理块中分离出来的操作（输入缓冲区）
物理结构：
A.计算法（顺序文件…）
顺序文件：逻辑上连续的信息依次存放在外存上连续的物理块
事先确定文件长度，不利于文件动态增长
B.指针法（索引文件，索引顺序文件，连接文件…）
连接文件：物理块间不连续，设一个指针，指向下一个物理块（只适用于顺序存取）
索引文件：物理块间不连续，为每一个文件建立一张索引表，逻辑块号与物理块号对应。
直接文件：HASH表
5.文件的存取方法
顺序存取：随机存取：索引存取：
6.文件系统必须为每个文件设置用于描述和控制文件的数据结构，包括文件名和存取文件的物理地址。（FCB文件控制块，FCB有序集合为文件目录）
7.文件目录
一级目录：
二级目录：（主文件目录和用户的文件目录）
多级目录：
8.文件共享
系统目录实现（无法实现共享文件的的动态增长），连接实现，符号连接
9.文件保护
存取控制矩阵，存取控制表，口令方式，加密方式
10.外存空间管理
连续分配
非连续分配
A.空闲块表
B.空闲块链表
C.成组空闲块链表
D.位示图（为1时表示该块已占用0时空闲）
11磁盘基本知识
https://www.cnblogs.com/jswang/p/9071847.html

第六章设备管理（对IO设备进行控制和管理）

1.设备分类：输入输出设备，存储设备
2.对IO设备的控制方式
程序直接控制方式（CPU不断读取和测试设备控制器状态寄存器的忙位来判断设备控制器的状态），中断控制方式，DMA方式（直接的数据交换通道），通道方式（专门负责io控制的处理机）
CSDN习题总结
1.操作系统的功能是进行处理机管理、（ 存储）管理、设备管理及信息管理。（进程管理实际上是处理机管理）
2.操作系统提供给程序员的接口是（ 系统调用）
3.在指令系统中只能由操作系统使用的指令成为（ 特权指令）。
4.进程是指令的集合（错）应该是程序
5.进程与程序的重要区别之一是（进程有状态，程序没有）进程程序都要占用资源
6.A. 进程被调度程序选中是从就绪态到运行态；C. 等待某一事件是从运行态到阻塞态；D.等待的事情发生是从等待态到就绪态。B. 时间片到进程从执行状态转变为就绪状态。
7.哪一个进程调度算法会引起进程的饥饿问题（发生死锁或者长时间等待）（优先级算法，多级队列可能）
8.作业周转时间为（ 作业等待时间+作业执行时间）
9.优先权大小：D. 在动态优先权中，随着进程执行时间的增加其优先权将随之下降
A. 计算型是【长作业】低于I/O型作业是【短作业】
B.用户进程的优先权应低于系统进程的优先权
C.要求多的低于要求少的。
10.信号量：记录型，整型为整数， 二进制信号量只能为0.1
对于记录型信号量，采取了让权等待策略，当s<0，即不存在可用资源的时候，因为其存在进程链表等待队列，所以不会盲等，而是会阻塞
对于整型信号量，没有采取让权等待策略，当s<=0的时候，即也是不存在可用资源的时候，因为其没有进程等待队列，所以不会阻塞，而是会陷入盲等状态
p操作代表通过，v操作代表释放

11.N个进程共享M台打印机（其中N>M），假设每台打印机为临界资源，必须独占使用，则打印机的记录信号量的取值范围为（ -(N-M) ~ M）临界资源为在某一时刻只能被一个进程使用的资源。打印机数量最大为M，表示有M个资源可以用。负值表示为最大有几个进程在排队，减去已经有M个在使用了。

PCB 进程控制块：描述进程外部特征，感知控制进程动态变化的数据结构
FCB 文件控制块：存储文件的相关信息的数据结构
DCB 设备控制块：记录硬件设备的特性，连接，使用情况等信息的数据结构
JCB 作业控制块：描述作业状态等相关信息的数据结构
12.（中断机构）是多道操作系统不可缺少的硬件支持。
13.操作系统5大功能：
处理机管理，储存器管理，设备管理，文件管理，以及作为用户与硬件系统之间的接口
14.创建进程的步骤：

1. 申请空白pcb
2. 为进程分配资源
3. 初始化pcb
4. 将进程插入就绪队列
   15.进程通过进程调度程序而获得CPU
   16.只有用户级线程，那进程就是最小单位，因为用户级的无法访问内核资源，如果系统只有用户态线程，则线程对操作系统是不可见的，操作系统只能调度进程，如果系统中由内核态线程，则操作系统可以按照线程进行调度
   17.线程是操作系统进行调度的基本单位，但不是独立运行的必须依存在应用程序中
   18.一个进程可以对应多个程序，一个程序也可以对应多个进程，但一个进程只能对应一个PCB（具有唯一性）
   19.在请求分页系统中，页表中的改变位是供（页面置换）参考的
   修改位（又叫改变位）：标记该页面在调入内存后是否被修改，从而决定是否需要写回外存，没有被修改的话，就没有必要写回外存
   20.页面淘汰算法
   OPT算法（Optimal Replacement）：淘汰的是以后不再使用或者未来长时间不再被访问的页面，无法实现，理想算法
   LRU算法（Least Recently Used）：最久未使用算法，选择最近一段时间内最久没有被使用的页面进行置换
   LFU算法（Least Frequently Used）：最近最少使用算法，选择最近一段时间使用得最少的页面置换
   LRU与LFU区别：
   LRU：最久为使用，和时间有关，和使用次数无关
   LFU：最不经常使用，和使用次数有关，和时间无关
   21.中断分类：
   A.强迫性中断（正在运行的程序没有想到的，来自硬件故障或者外部请求）
5. IO中断（外部IO设备给的，不是程序所预料到的，程序没有想到此刻会有IO中断）
6. 程序性中断（溢出，缺页，缺段，地址越界，除0）
7. 时钟中断
8. 控制台中断
9. 硬件中断
   B.自愿性中断（编程者预期的）
   用户在编程时要求操作系统提供服务，使用访管指令或系统调用使中断发生，叫做访管中断，包括执行OI，创建进程，分配内存，信号量操作，发生接收消息
   21.抖动：置换算法不当，有可能产生刚被调出内存的页又要调回内存
   22.缓冲区(Buffer)就是在内存中预留指定大小的存储空间用来对输入/输出(I/O)的数据作临时存储
   23.响应时间指的是用户从发出请求到接收完响应之间的总耗时
10. 联机操作：输入/输出操作在计算机直接控制下进行的。联机时，操作者“正在”使用计算机资源。
    脱机操作：输入/输出操作在要进行操作的计算机以外的设备上进行，在需要时再送计算机处理。
    假脱机（Spooling）：是指输入/输出不直接送往输入/输出设备或计算机，而是先送到外存储器，典型的例子是打印。
    25.进程调度算法选择不当会导致进程长时间等待，不会发生死锁。死锁是指两个或两个以上进程在执行过程中，因争夺资源而造成的下相互等待的现象
    26.响应时间，周转时间，吞吐量P44
    27.文件的逻辑结构是从用户观点出发看到的文件的组织形式。文件的物理结构是从实现观点出发，又称为文件的存储结构，是指文件在外存上的存储组织形式。文件的逻辑结构与存储介质特性无关，但文件的物理结构与存储介质的特性有很大关系。
    28.进程切换涉及虚拟地址空间的切换而线程不会。因为每个进程都有自己的虚拟地址空间，而线程是共享所在进程的虚拟地址空间的，
    29.SPOOLING特点：
    （1）提高了输入输出速度
    （2）将独占设备改造为共享设备
    （3）实现了虚拟设备功能
    构成：
    输入输出井（磁盘上）
    输入输出缓冲区（主存上）
    管理程序（预输入程序，缓输出程序，井管理程序）
    30.批处理：是指用户将一批作业提交给操作系统后就不再干预，由操作系统控制它们自动运行。这种采用批量处理作业技术的操作系统称为批处理操作系统。批处理操作系统分为单道批处理系统和多道批处理系统。批处理操作系统不具有交互性，它是为了提高CPU的利用率而提出的一种操作系统。
    31.完成中断响应工作的是 中断处理程序