《第三章》 操作系统知识

操作系统概述

定义

操作系统能有效的组织和管理系统中的各种软硬件资源，合理的组织计算机系统工作流程，控制程序的执行，
并向用户提供良好的工作环境和用户接口。
操作系统的作用：
    * 通过资源管理提高计算机系统的效率
    * 改善人机界面向用户提供友好的工作环境
4个特性： 并发性、共享性、虚拟性和不确定性。

功能

* 进程管理
    对处理机的“时间”进行管理，采用多道程序等技术将CPU时间合理分配
    包括 进程控制、进程同步、进程通信和进程调度。
* 文件管理
    包括 文件存储空间管理、目录管理、文件读写管理和存取控制。
* 存储管理
    对主存储空间进行管理，包括 存储的分配与回收、存储保护、地址映像(变换)和主存扩充。
* 设备管理
    对硬件设备管理，包括 输入/输出设备的分配、启动、完成和回收。
* 作业管理
    包括 任务、界面管理、人机交互、图形界面、语音控制和虚拟现实。

操作系统的分类

* 批处理操作系统   分 单道批处理系统 和 多道批处理系统
* 分时操作系统    将CPU的工作时间划分多个时间片，轮流用各个用户终端工作。
* 实时操作系统    对外来信息能够以足够快的速度处理，并在被控对象允许时间范围内做出反应
        对交互能力要求不高，但要求可靠
* 网络操作系统    使联网计算机能够方便高效的共享网络资源，为网络用户提供各种软件服务和协议。
        三种模式： 集中模式、服务器/客户机模式和对等模式
* 分布式操作系统   多个无主次的分散计算机连接而成
* 微型计算机系统   WIN，MacOS, Linux
* 嵌入式操作系统   运行在嵌入芯片中，对智能芯片和操作控制的部件进行统一协调、处理、指挥和控制。
    特点：
        - 微型化   占用资源和系统代码量小
        - 可定制   可运行在不同处理器平台，能针对硬件变化进行调整
        - 实时性   用于过程控制、数据采集、传输通信等实时性较高的领域
        - 可靠性   高可靠性，要害应用有冗余防错和防故障要求
        - 易移植性  采用底层抽象HAL 和 板级支撑包BSP 的底层技术 提高可移植性

    嵌入式初始化采用自底向上的初始化方式 
        芯片级初始化(微处理器初始化)-》板卡级初始化(其他硬件设备初始化)-》系统初始化(软件及操作系统初始化)。
* 微内核操作系统   尽可能内核做的小，只将核心东西放入内核，其他放到用户进程中。
        系统分为 用户态和内核态

单体内核 图形、设备驱动、文件系统都在内核实现 减少了进程间通信和状态切换，提高了运行效率， 占用资源多，稳定性和安全性不好。
微内核 只有基本功能，图形、驱动、文件系统在内核之外 便于移植，系统服务在用户空间，稳定性和可靠性，安全性高，可用于分布式， 
    用户态和内核态切换频繁效率低

分布式操作系统与网络操作系统有什么不同之处?
(1)分布性:分布式操作系统是驻留在系统的各个结点上,
    而网络操作系统的控制功能大部分是集中在服务器上。
(2)并行性:分布式操作系统可将一个用户的多个任务分配到多个计算机上并行执行;而网络环境下,
    每个用户的一个或多个任务只能在自己的计算机上处理。
(3)透明性:分布式系统能隐藏自己内部的物理位置、并发控制、系统故障等实现细节来使用系统;
    而网络操作系统计算机之间的通信需要IP地址。
(4)共享性:分布式系统中,所有分布在各个站点的软、硬件资源均可供系统中所有用户共享,并能以透明的方式使用它们;
    而网络操作系统共享的资源大多数是设置在服务器中,它机的资源一般由本机用户使用。
(5)健壮性:分布式系统任何结点的故障都不会对系统造成太大的影响,某些部件的故障可以通过容错技术实现系统的重构;
    而网络操作系统的控制功能大部分集中在服务器中,这使得服务器会成为单点故障,它一出故障,就会影响整个系统的可靠性。

进程管理

进程的组成

进程有 程序控制块PCB，程序，数据组成
进程三态 就绪态、运行态、阻塞态

PCB进程块的存储方式： 线性表，链式表，索引表

前趋图和进程资源图

前趋图 用来表示那些任务可以并行执行， 那些任务之间有顺序关系，有向无环图。 
    前驱图中增加信号量的时候， 从左向右，从前向后，从小到大， s1,s2,s3....
进程资源图 用来表示进程和资源之间的分配和请求关系。

进程的同步和互斥

互斥 表示同一个资源在同一个时间只能有一个进程使用
同步 表示两个任务和同时执行，不存在资源的单独占用和共享问题

P操作：申请资源，S=S-1,若S>=0,则执行P操作的进程继续执行；
    若S<0,则置该进程为阻塞状态（因为无可用资源），并将其插入阻塞队列。

V操作：释放资源，S=S+1,若S>0,则执行V操作的进程继续执行；
    若S<=0,则从阻塞状态唤醒一个进程，并将其插入就绪队列（此时因为缺少资源被P操作阻塞的进程可以继续执行），
    然后执行v操作的进程继续。

信号量

- 临界资源 各个进程间需要互斥方式使用的资源
- 临界区 每个进程中访问临界资源的代码
- 信号量 
    * 互斥信号量： 对临界资源采用互斥访问， 使用互斥信号量后其他进程无法使用 初始化=1
    * 同步信号量： 对共享资源的访问控制， 初始化=资源数量

进程调度

进程调度是指当有更高优先级的进程到来时，如何分配CPU。 
    - 可剥夺 指当有更高优先级的进程到来时，强制将CPU分配给高优先级的进程
    - 不可剥夺 指高优先级的进程必须等待当前进程释放CPU
一个作业要经历高中低三级调度
    * 高级调度 又叫长调度、作业调度。 决定输入池中那个作业可以进入主系统成为就绪进程， 仅一次
    * 中级调度 又叫中程调度、对换调度。 决定交换区中的哪个就绪进程可以进入内存参与争夺CPU。
    * 低级调度 又叫短程调度、进程调度。 决定内存中的哪个进程可以占用CPU

在单处理机系统中，采用先来先服务调度算法。系统中有4个进程P1、P2、P3、P4(假设进程按此顺序到达），
其中P1为运行状态，P2为就绪状态，P3和P4为等待状态，且P3等待打印机，P4等待扫描仪。
若P1（）,则P1、P2、P3和P4的状态应分别为（）
--------------------------------------
A.时间片到 B.释放了扫描仪 C.释放了打印机 D.已完成

A.等待、就绪、等待和等待
B.运行、就绪、运行和等待
C.就绪、运行、等待和等待
D.就绪、就绪、等待和运行

第一个空不能选D，已完成则第二空就不能等待/运行/就绪。
第二个空P3,P4不管那个资源有了，都是从等待到就绪， 所以只能选C， 还是等待中，
    则第一个空只能选A，时间片到了P1转为就绪，P2运行，P3、P4继续等待。

调度算法

* 先来先服务 FCFS， 先到达的进程先占用CPU
* 时间片轮转  分配给每个进程大小相等的时间片，轮流使用CPU，
* 优先级调度  每个进度有独自的优先级，优先级高的优先使用CPU
* 多级反馈调度 设置从高到低不同优先级队列，进程分配不同优先级和时间片。
        首先进入最高级队列， 执行完成后进入次一次的队列。 直到执行完成退出

死锁问题

当一个进程等待永远不会发生的事情时， 就会死锁。
死锁的必要条件： 资源互斥、进程占用并等待其他资源、系统不能剥夺进程资源、进程资源图是一个环路。
打破死锁：
- 死锁预防： 采用某种策略限制并发进程对资源的请求
- 死锁避免： 采用银行家算法，提前分配资源，如果死锁则不分配资源
- 死锁检测： 定时检测死锁并加以清除
- 死锁解除： 强制剥夺资源，清除死锁进程
死锁资源计算： 
    系统有n个进程， 每个进程请求r个资源
    发生死锁的最大资源数为： n*(r-1)
    不发生死锁的最小资源数为： n*(r-1)+1

线程

进程有两个属性： 可拥有资源的独立单位、可独立调度和分配的基本单位
进程在创建、撤销和切换中，要付出较大的时空开销。
引入线程作为调度和分配的基本单位， 进程作为独立分配资源的单位        

存储管理

分区存储管理

就是整存， 将进程运行所需的内存整体全部分配给它再执行
- 固定分区 静态分区法，主存分为若干固定区
- 可变分区 动态分区法， 主存空间在作业转入时正好划分所需的空间
    * 首次适应法     按地址顺序从头查找大于等于需要的空间分配
    * 最佳适应法     所有空闲分区排序，找到最接近需要大小的空间
    * 最差适应法     找到空闲分区中最大的分配
    * 循环首次适应法   按顺序继续查找，不再从头开始找，区别首次适应法
- 可重定位分区 移动所有已分配好的分区，使其连续

分页存储管理

根据可变分区演化
逻辑页包括 页号+页内地址。 页内地址就是物理偏移地址， 页号与物理块号通过页表查询对照，找到物理块号+偏移地址
优点： 利用率高，碎片小，分配和管理建单
缺点： 增加了系统开销，可能产生抖动

1) 根据页面大小可计算出页内地址的位数
2) 页内地址位数结合逻辑地址计算出页内地址（即，块内地址）和页号
3) 页号结合页表，即可得出块号
4) 块号&块内地址即可得出物理地址

有多少个页，决定了我的页号是多少位，
    4GB=（4*1024*1024）KB进程，分的每页是4KB，
    这个时候就是有（4*1024*1024）KB/4KB= 2^20个页数，对应的两进制是20位，也就是页号有20位，
    所以说有多少个页，就决定了我的页号是多少位！
页号有多少位跟页数多少有关
页内地址跟什么相关？页内地址是根据页的大小来的，比如页大小是4KB=（4*1024）B=2^12，所以页地址就是12位！

某计算机系统页面大小为4K,若进程的页面变换表如下所示，逻辑地址为十六进制1D16H.该地址经过变换后，其物理地址应为十六进制（）。
系统页面大小4K，决定页内地址位数 4K=4*1024b=2^12b 即页内地址 12位
逻辑地址1D16H,低三位正好是12位二进制页内地址，则最高位的1 是页号

地址表示和转换

地址组成： 页地址+页内偏移地址， 页地址在高位
物理地址： 物理块号+页内偏移地址
逻辑地址： 页号+页内偏移地址
首先求出页号的位数， 得到页号， 去页表对照得到物理块号， 加上页内偏移地址得到实际地址

页面置换算法

例如： 进程需要100个页面， 系统只有10个物理块，则需要加载马上要执行的页面
* 最优算法  理论算法
* 先进先出算法    先调入内存的页面先调出
* 最近最少使用算法  进程执行过程中，过去最少使用的页面先调出
* 淘汰原则  优先淘汰最近未访问的页面，而后淘汰最近未修改的页面

快表

快表是一个小容量相连存储器，由快速存储器组成，按内容访问，速度快
快表是将页表放入Cache，慢表是页表放入内存上，慢表访问两次内存，快表访问Cache+内存，速度更快

段式存储管理

将内存为每个段分配一个连续的分区，段的长度由相应的逻辑信息组的长度决定，因而各段长度不等， 每段由段号和段内地址。每段物理大小不同
优点： 多道程序共享内存，各段程序修改不互影响
缺点： 内存利用率低，内存碎片大

分页是根据物理空间划分，每页大小相同
分段是根据逻辑空间划分，每段大小不同

地址表示

地址组成： 段号+段内偏移

段页式存储管理

对进程空间先分段，再分页。
优点： 空间浪费小，存储共享容易，存储保护容易、能动态链接。
缺点： 复杂性和开销增加，执行速度下降

设备管理

设备分类

设备是计算机系统与外界交互的工具，具体负责计算机与外部的输入／输出工作，所以常称为外部设备（简称外设）
设备的分类：
    按数据组织分类：块设备、字符设备。
    按照设备功能分类：输入设备、输出设备、存储设备、网络联网设备、供电设备。
    资源分配角度分类：独占设备、共享设备和虚拟设备。
    数据传输速率分类：低速设备、中速设备、高速设备。
将负责管理设备和输入／输出的机构称为I/O系统 I/O系统由设备、控器、通道（具有通道的计算机系统）、总线和／0软件组成。
设备管理的任务是保证在多道程序环境下，当多个进程竞争使用设备时，按一定的策略分配和管理各种设备，控制设备的各种操作，完成I/0设备与主存之间的数据交换。
设备管理的主要功能是动态地掌握并记录设备的状态、设备分配和释放、缓冲区管理、实现物理I/O设备的操作、提供设备使用的用户接口及设备的访问和控制。
    缓冲管理、设备分配与回收、设备处理和虚拟设备

I/O软件

当用户程序试图读一个硬盘文件时，需要通过操作系统实现这一操作。
与设备无关软件检查高速缓存中有无要读的数据块，若没有，则调用设备驱动程序，向I/O硬件发出一个请求。
然后，用户进程阻塞并等待磁盘操作的完成。
当磁盘操作完成时，硬件产生一个中断，转入中断处理程序。
中断处理程序检查中断的原因，认识到这时磁盘读取操作已经完成，于是唤醒用户进程取回从磁盘读取的信息，从而结束此次I/O请求。
用户进程在得到了所需的硬盘文件内容之，后继续运行。

文件管理

概述

文件是具有符号名的、在逻辑上具有完整意义的一组相关信息项的集合。
信息项是构成文件内容的基本单位，可以是一个字符，也可以是一个记录，记录可以等长，也可以不等长。
一个文件包括文件体和文件说明。
    文件体是文件真实的内容。
    文件说明是操作系统为了管理文件所用到的信息，包括文件名、文件内部标识、文件的类型、文件存储地址、文件的长度、访问权限、建立时间和访问时间等。
文件管理系统，就是操作系统中实现文件统一管理的一组软件和相关数据的集合，专门负责管理和存取文件信息的软件机构，简称文件系统

文件的类型
    按文件性质和用途可将文件：   系统文件、库文件和用户文件。
    按信息保存期限分类可将文件：  临时文件、档案文件和永久文件。
    按文件的保护方式分类可将文件： 只读文件、读／写文件、可执行文件和不保护文件。
    UNIX系统将文件：  普通文件、目录文件和设备文件（特殊文件）。

文件结构

文件结构分为逻辑结构和物理结构
文件的逻辑结构可分为两大类：有结构的记录式文件；无结构的流式文件。
文件的物理结构是指文件在物理存储设备上的存放方法
    连续结构：连续结构也称顺序结构，它将逻辑上连续的文件信息（如记录）依次存放在连续编号的物理块上。
    链接结构：链接结构也称串联结构，它是将逻辑上连续的文件信息（如记录）存放在不连续的物理块上，
        每个物理块设有一个指针指向下一个物理块。
    索引结构：将逻辑上连续的文件信息（如记录）存放在不连续的物理块中，系统为每个文件建立一张索引表。
        索引表记录了文件信息所在的逻辑块号对应的物理块号，并将索引表的起始地址放在与文件对应的文件目录项中。
    多个物理块的索引表：索引表是在文件创建时由系统自动建立的，并与文件一起存放在同一文件卷上。
        根据一个文件大小的不同，其索引表占用物理块的个数不等，一般占一个或几个物理块。

索引文件结构

索引结构分了直接索引跟间接索引。
    直接索引，每个索引节点直接指向一个物理盘块。
    间接索引，每一个索引节点，存放的是又一个索引节点，终结点还是指向物理盘块！（分为一级间接索引，二级间接索引，三级间接索引.......

设文件索引节点中有8个地址项，每个地址项大小为4字节，其中5个地址项为直接地址索引，2个地址项是一级间接地址索引，1个地址项是二级间接地址索引，
磁盘索引块和磁盘数据块大小均为1KB,
若要访问文件的逻辑块号分别为5和518,则系统应分别采用（）,而且可表示的单个文件最大长度是（）KB.

5个地址项为直接地址索引 可以访问0~4号逻辑块
2个地址项是一级间接地址索引 每个索引块1KB=2^10B 每地址项4字节=2^2B， 每个一级地址索引可拥有：2^10/2^2=2^8=256个逻辑块
    即：2个地址项是一级间接地址索引共有512个逻辑块编号可访问5~511号逻辑块
1个地址项是二级间接地址索引 每个索引块包含256个一级间接地址索引 总计 256*256=65536个物理块
总计可索引： 65536+512+4 = 66052个物理块

> 依题意，5个直接地址索引可以表示5×1KB=5KB，其逻辑块号是0-4；
> 一级间接地址索引可以产生的索引项为1024/4=256，
> 一级间接索引可以表示256×1KB=256KB， 其逻辑块号是5～511；
> 2个一级间接地是索引表示256×2=512KB，
> 二级间接索引产生的二级间接索引项也为256，因此二级索引表示256×256KB=65536KB，其逻辑块号是512-65535。 
> 由于5＞4，因此要访问逻辑块号为5的文件，系统应采用一级间接地址索引。
> 而518＞511，要访问逻辑块号为518的文件，则系统应采用二级间接地址索引。

文件目录

文件控制块中包含以下三类信息：基本信息类、存取控制信息类和使用信息类。
    基本信息类。例如文件名、文件的物理地址、文件长度和文件块数等。
    存取控制信息类。文件的存取权限，像UNIX用户分成文件主、同组用户和一般用户三类，这三类用户的读／写执行。
    使用信息类。文件建立日期、最后一次修改日期、最后一次访问的日期、当前使用的信息（如打开文件的进程数、在文件上的等待队列）等。
文件控制块的有序集合称为文件目录。

相对路径：是从当前路径开始的路径。
绝对路径：是从根目录开始的路径。
全文件名＝绝对路径＋文件名。
要注意，绝对路径和相对路径是不加最后的文件名的，只是单纯的路径序列。

文件存储空间管理

文件的存取方法是指读／写文件存储器上的一个物理块的方法
通常有顺序存取和随机存取两种方法。
    顺序存取方法是指对文件中的信息按顺序依次进行读／写；
    随机存取方法是指对文件中的信息可以按任意的次序随机地读／写。
文件存储空间的管理：
    - 空闲区表。将外存空间上的一个连续的未分配区域称为“空闲区”。
        操作系统为磁盘外存上的所有空闲区建立一张空闲表，每个表项对应一个空闲区，适用于连续文件结构。
    - 位示图这种方法是在外存上建立一张位示图（Bitmap),记录文件存储器的使用情况。
        每一位对应文件存储器上的一个物理块，取值0和1分别表示空闲和占用。（注意位示图是考点）
    - 空闲块链。每个空闲物理块中有指向下一个空闲物理块的指针，所有空闲物理块构成一个链表，
        链表的头指针放在文件存储器的特定位置上（如管理块中），不需要磁盘分配表，节省空间。
    - 成组链接法。例如，在实现时系统将空闲块分成若干组，每100个空闲块为一组，
        每组的第一个空闲块登记了下一组空闲块的物理盘块号和空闲块总数。假如某个组的第一个空闲块号等于0,意味着该组是最后一组，无下一组空闲块。

某文件管理系统采用位示图（bitmap)记录磁盘的使用情况。
如果系统的字长为32位，磁盘物理块的大小为4MB,物理块依次编号为：0、1、2、．．．，位示图字依次编号为：0、1、2、．．
那么16385号物理块的使用情况在位示图中的第（ )个字中描述：如果磁盘的容量为1000GB,那么位示图需要（ )个字来表示。

16385 转为十六进制=4001H, 4001H/32bit = 4*16^3+1/2^5 =2^2*2^12+1/2^5=2^9+1 = 512 + 1即在512字上
总计物理块 = 1000GB/4MB = 1000*1024MB / 4MB=1000*256块， 即需要2^8*1000个bit的位示图，
系统字长32bit， 2^8*1000/2^5=2^3*1000=8000 字