架构-计算机基础3-软件-操作系统

概述

定义

• 有效地组织和管理系统中的各种软件/硬件资源，
• 合理地组织计算机系统工作流程，
• 控制程序的执行，
• 并且向用户提供一个良好的工作环境和友好的接口
  

作用

• 管理计算机中运行的程序和分配各种软硬件资源
• 为用户提供友善的人机界面
• 未应用程序的开发和运行提供一个高效的平台

特征

• 并发性（最基本属性）：宏观上并行，微观上串行。时间上很小。和“并行”区别。
  并行是微观的，并发是宏观的
• 共享性（最基本属性）：文件数据共享，内存、资源等共享
• 虚拟性：设备管理技术，Spooling技术，如打印机共享给多个程序使用
• 不确定性（异步性）：运行的程序中间步骤不确定

功能

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

分类

• 批处理操作系统：
  • 单道批：一次一个作业写入内存，作业由程序、数据、作业说明书组成
  • 多道批：一次多个作业写入内存，特点：多道、宏观上并行微观上串行
• 分时操作系统：
  一个计算机系统与多个终端设备连接。将CPU化为多个时间片轮转为多个用户提供服务，特点：多路性、独立性、交互性、及时性
• 实时操作系统：
  实时是指计算机对于外来信息能够以足够快的速度进行处理，并在被控对象允许的时间范围内做出快速反应。
  实时控制系统和实时信息系统。交互能力不高，可靠性要求高
• 网络操作系统：
  使联网计算机能够方面有效地共享网络资源，为网络用户提供各种服务的软件和协议的集合。Unix、Linux和Windows Server
  三种模式：
  • 集中模式
  • 客户端/服务器模式
  • 对等模式
• 分布式操作系统：
  由多个分散的计算机经连接而成的计算机系统，系统中的计算机无主、次之分，任意两台计算机可以通过通信交换信息
• 微型计算机操作系统：
  • Windows：Microsoft 图形界面、多任务、多线程
  • Linux：类Unix操作系统，多用户、多任务、多线程和多CPU
• 嵌入式操作系统：运行在智能芯片中。特点：
  • 微型化：性能成本考虑，希望占用的资源和代码量少，如内存少、字长短、运行速度有限、能源少（微小型电池）
  • 可定制：成本研发周期考虑，不同微处理器平台上，对硬件变化进行结构和功能上的配置，满足不同的需求
  • 实时性：过程控制、数据采集、传输通信、多媒体信息及关键要害领域需要迅速响应的场合，对实时性要求较高
  • 可靠性：系统构件、模块和体系结构必须达到应用的可靠性，关键要害应用还要提供容错和预故障措施
  • 易移植性（HAL和BSP支持）：采用硬件抽象层和板级支撑包
    嵌入式系统初始化过程：自底向上，从硬件到软件依次：片级初始化->板级初始化->系统初始化

进程管理

概念

进程是程序在一个数据集上运行的过程，它由系统进行资源分配和调度的一个独立单元。
主要组成部分：

• 进程控制块PCB（唯一标志）：包含进程标识符、状态、位置信息、控制信息、队列指针（链接同一状态的进程）、优先级、现场保护区等；
• 程序（描述进行要做什么）
• 数据（存放进程执行时所需数据）

三态图

• 运行：当一个进程在CPU上运行时。（单处理器处于运行态的进程只有一个，多进程CPU上交替运行）
• 就绪：一个进程获得了除CPU外的一切所需资源，一旦得到处理器即可运行
• 阻塞：阻塞也成等待或者睡眠状态，一个进程正在等待某一时间的发生（例如请求I/O、等待I/O完成等）而暂时停止运行，此时即使CPU分配给进程也无法运行
  【能够记住并背下来】
  

前趋图

用来表示哪些任务可以并行执行，哪些任务之间有顺序关系。

• 任务间的并行
• 任务间的先后顺序
  

进程资源图

表示进程和资源之间的分配和请求关系。可判断是否死锁。

进程同步与互斥

临界资源：各进程间需要以互斥方式对其进行访问的资源
临界区：进程中对临界资源实施操作的那段程序。本职是一段程序代码

• 互斥：某资源（临界资源）在同一时间内只能由一个任务单独使用，使用时需要加锁，使用后解锁才能被其他任务使用；如打印机

• 同步：多个任务可以并发执行，只不过有速度上的差异，在一定情况下停下等待，不存在资源是否单独或共享的问题；如自行车和汽车；
  

• 互斥信号量：对临界资源采用互斥访问，使用互斥信号量后其他进程无法访问，初值为1；

• 同步信号量：对共享资源的访问，初值一般是共享资源的数量。
  
  经典问题：生产者和消费者问题
  三个信号量：互斥信号量S0（仓库独立使用权），同步信号量S1（仓库空闲个数）、同步信号量S2（仓库商品个数）

进程调度

方式：指挡有更高优先级的进程到来时如何分配CPU

• 可剥夺：更高来临时，强行将正在运行进程的CPU分配更高的
• 不可剥夺：高优先级进程必须等待当前进程自动释放CPU

一个作业从提交到完成需要经历高、中、低三级调度

• 高级调度。长调度、作业调度或接纳调度。决定输入池中哪个后备作业可以调入主系统做好运行的准备，成为一个或一组继续进程。一个作业只需经过一次高级调用
• 中级调度。中程调度、兑换调度。处于交换区中哪个就绪进程可以调入内存，以便直接参与CPU竞争。
• 低级调度。短程调度、进程调度。处于内存中的哪个就绪进程可以占用CPU。是最活跃、最重要的调度程序，

调度算法

• 先来先服务FCFS：先到达的进程优先分配CPU。用于宏观调度
• 时间片轮转：每个进程CPU时间片，轮流使用CPU，进程时间大小相同、很公平，用于微观调度；
• 优先级调度：每个进程都甬有一个优先级，优先级大的先分配CPU
• 多级反馈调度：时间片轮转和优先级调度结合而成，设置多个就绪队列1.2.3…，每个队列赋予不同的优先级，分配不同的时间片长度；新进程先进入队列1末尾，按FCFS原则，执行队列1的时间片；若未能执行完进程，则转入队列2末尾，如此重复。
  

死锁

当一个进程在等待永远不可能发生的事件时，就会产生死锁，若系统中有多个进程处于死锁状态，就会造成系统死锁
四个必要条件：

• 资源互斥
• 每个进程占有资源并等待其他资源
• 系统不能剥夺进程资源
• 进程资源图是一个环路

解决措施是打破四大条件：

• 死锁预防：采用某种策略限制并发进程对于资源的请求，破坏死锁产生的四个条件之一，使系统任何时刻都不满足死锁的条件。
• 死锁避免：一般采用银行家算法，银行家算法，就是提前计算出一条不会死锁的资源分配方法，才分配资源，否则不分配资源，相当于接待，考虑对方还的起才节前，提前考虑好以后，就可以避免死锁。
• 死锁检测：允许死锁发生，但系统定时运行一个检测死锁的程序，若检测到系统中发生死锁，则设法加以接触。
• 死锁解除：即死锁发生后的接触方法，如强制剥夺资源、撤销进程等。
• 死锁资源计算：系统内有N个进程，每个进程都需要R个资源，发生死锁的最大资源数为n*(R-1)。不发生死锁的最小资源数为n*(R-1)+1。

线程

传统进程属性：

• 可拥有资源的独立单位；
• 可独立调度和分配的基本单位。

引入线程原因：
进程在创建、撤销和切换中，系统必须为之付出较大的时空开销。故在系统中设置的（1）进程数目不宜过多，（2）切换频率不宜过高。

引入线程后，将传统进程的两个基本属性分开：（从2个属性可看出线程不拥有资源）

• 线程作为调度和分配的基本单元
• 进程作为独立分配资源单位。

线程是进程中的一个实体，被系统独立分配和调度的基本单元。
线程基本上不拥有资源，只拥有一点运行中必不可少的资源（如程序计数器、一组寄存器和栈）

• 与可同属一个进程的其他线程共享进程所拥有的全部资源，例如进程的公共数据、全局变量、代码、文件等资源，
• 不能共享线程独有的资源，如线程的栈指针等标识数据
  

存储管理

分区存储管理

分区存储组织：整存，将某进程运行所需的内存整体一起分配给它，然后再执行。
三种分区方式：

• 固定分区：静态分区方法，将主存分为若干个固定嗯分区，将要运行的作业装配进去，由于分区固定，大小和作业需要的大小不同，会产生内部碎片；
• 可变分区：动态分区方法，主存空间的分区是在作业转入时划分，正好划分为作业需要的大小，这样就不存在内存碎片，但容易将正片主存空间切割成许多块，会产生外部碎片。
  已经分配后以后，还需要分配9k，可采用以下算法：
  • 首次适应法：按内存地址顺序从头查找，找到第一个>=9k空间的空闲块，即切割9k空间分配给进程；
  • 最佳适应法：将内存中所有空闲内存块按从小到大的排序，找到第一个>=9k空间的空闲块，切割分配，这个将会找到与9k空间大小最相近的空闲块；
  • 最差适应法：和最佳适应法想法，将内存中空闲块最大的，切割成9k空间分配给进程，这事为了预防系统中产生过多的细小空闲块。
  • 循环首次适应法：按内存地址顺序查找，找到第一个>=9k空间的空闲块，而后若还需分配，则找下一个，不用每次都从头查找，这与首次适应法不同的地方。
• 可重定位分区：可解决碎片问题，移动所有已经分配好的区域，使其成为一个连续的区域，这样其他外部细小的分区碎片可以合并成大的分区，满足作业要求。只有外部作业请求空间得不到满足时进行。

分页存储管理

逻辑页

• 页号
• 页内地址：物理偏移地址

页号和物理块号并非按序对应的，需要查询页表，才能得知页号对应的物理块号，在用物理块号，加上偏移地址，才能得出真正运行时的物理地址。

逻辑地址=页号+页内地址
物理地址=页帧号（物理块号）+页内地址

优点：利用率高，碎片小，分配及管理简单；
缺点：增加了系统开销，可能产生抖动现象
“抖动现象”，指的是当系统为进程分配的物理块数量少于进程所需的最小数量时，进程频繁地进行页面置换，导致系统性能急剧下降的一种现象。简单来说，就是页面在内存和外存之间来回频繁地“抖动”，大量时间被用于页面调度，而进程实际执行的时间却很少，严重影响系统效率，甚至可能导致系统崩溃。

【页号：和容量有关，页内地址，和存储大小有关。
如有4GB内存，以4KB为页面大小，则有2的20次方个。页号有2的20次方，即页号有20位，页内地址，就是4KB大小。】

页面置换算法：

• 最优算法：OPT（Optimal Replacement Algorithm），理论上的算法，无法实现，是在进程执行完后进行的最佳效率计算，用来让其他算法比较差距。
  原理：选择未来最长时间内不被访问的页面置换，这样可以保证未来执行的都是马上要访问的
• 先进先出算法：FIFO（First Input First Output），先调入内存的页先被置换淘汰，会产生抖动现象，即分配的页数越多，缺页率可能越多（即效率越低）
• 最近最少使用：LRU（Least Recently Used），在最近的过去，进程执行过程中，过去最少使用的页面被置换淘汰，根据局部性原理，这种方式效率高，且不会产生抖动现象，使用大量计数器，但没有LFU(Least Frequently Used)多。
  • LFU（最不经常使用页置换算法）是一种根据页面的历史访问频率来决定置换页面的算法
• 淘汰原则：有限淘汰，最近未访问的，后淘汰最近未被修改的页面。

快表&慢表
快表是一块小容量的相联存储器，由快速存储器组成，按内容访问，速度快，并且可以从硬件上保证按内容并行查找，一般用来存放当前访问最频繁的少数活动页面的页号。

• 快表：将页面存在Cache中，访问一次Cache和一次内存，更快；
• 慢表：将页表存于内存上，需要访问两次内容才能取出页；

分段存储管理

将进程空间分为一个个段，每段也有段号和端内地址，与页式存储不同的是，每段物理大小普通，分段是根据逻辑整体分段的，因此段表和页表的内容不同，页表中直接是逻辑页对应的物理块号，段表有段长和基址两个属性，才能确定一个逻辑段在物理段中的位置。分页每段大小是固定的，分段不固定

• 优点：多道程序共享内存，各段程序修改互不影响
• 缺点：内存利用率低，内存碎片浪费大。

段页式存储管理

对进程空间先分段、后分页。

• 优点：空间浪费小、存储共享容易、存储保护容易、能动态链接
• 缺点：由于管理软件的增加，复杂性和开销随之增加，需要的硬件以及占用的内容也有所增加，使得执行速度大大下降
  
  

设备管理

设备是计算机系统与外界交互的工具，具体负责计算机与外部的输入、输出工作，所以常称为外部设备（简称外设）。
在计算机系统中，将负责管理设备和输入/输出的机构成为I/O系统，因此I/O系统由设备、控制器、通道（具体通道的计算机系统）、总线和I/O软件组成

设备的分类

• 按数据组织分类：块设备、字符设备
• 按设备功能分类：输入设备、输出设备、存储设备、网络联网设备、供电设备
• 资源分配角度分类：独占设备、共享设备和虚拟设备
• 数据传输速率分类：低速设备、中速设备、告诉设备

设备管理任务：
在多道程序环境下，当多个进程竞争使用设备时，按一定的策略分配和管理各种设备，控制设备的各种操作，完成I/O设备与主存之间的数据交换
设备管理功能：
动态掌握并记录设备的状态、设备分配和释放、缓存区管理、实现物理I/O设备的操作、提供设备使用的用户接口及访问和控制

I/O软件

I/O设备管理软件的所有层次及每一层功能如下图

实例：用户程序试图访问一个硬盘文件时，需要通过操作系统来实现->设备无关软件检查告诉缓存中有无要读的数据块->若没有，调用设备驱动程序，向I/O硬件发送一个请求->用户进程阻塞并等待磁盘操作完成->磁盘处理完成，产生一个中断，转入中断处理程序->中断处理程序检查终端原因，认为磁盘读取已完成，唤醒用户进程取回信息，结束此次I/O请求。

设备管理技术

一个独占设备，同一时间只能由一个进程使用，其他进程只能等待。
引入SPOOLING（外围设备联机操作）技术：在外设上建立两个数据缓冲区，分别成为输入井和输出井，无论多少进程，都可以共用一个打印机，只需要将命令发出，数据就会排队在缓冲区，打印机会自动按顺序打印，实现了物理外设的共享，使得每个进程都感觉在使用一个打印机，这就是物理设备的虚拟化

文件管理

文件：具有符号名的，在逻辑上具有完整意义的一组相关信息的集合。是一种抽象机制，隐藏了硬件和实现细节，

• 文件体：文件真实的内容
• 文件说明：操作系统为了管理文件所用到的信息，包括文件名、文件内部表示、文件类型、存储地址、文件长度、访问权限、建立时间和访问时间等

文件系统：实现文件统一管理的一组软件和相关数据的集合，专门管理和存储文件信息的软件机构。
功能 有：按名存取、统一的用户接口、并发访问和控制、安全性控制、优化性能、差错恢复。

文件的类型

• 性质和用户：系统文件、库文件、用户文件
• 保存期限：临时文件、档案文件、永久文件
• 保护方式：只读、读/写、可执行、不保护
• UNIX：普通文件、目录文件、设备文件（特殊文件）

文件结构

• 逻辑结构：
  • 有记录的记录式文件：所有的记录通常都描述一个实体集，记录的长度分定长和不定长
  • 无结构的流式文件：文件体为字节流。通常采用顺序访问方式，读写可以任意长度
• 物理结构：文件在屋里设备上的存放方法
  • 连续结构（顺序结构）：将逻辑上连续的文件信息（如记录）一次存放在连续编号的物理块上
  • 链接结构（串联结构）：将逻辑上连续的文件信息（如记录）存放在不连续的物理块上，每个物理块设有一个指针指向下一个物理块
  • 索引结构：将逻辑上连续大大文件信息（如记录）存放在不连续的物理块上，系统为每个文件监力一张索引表。索引表记录了文件信息所在的逻辑块号对应的物理块号，并将索引表的起始地址放在与文件对应的文件目录中。
    
    如图，系统中存在13个索引结点（0-12）。
    0-9为直接索引，即每个索引节点存放得是内容。假设每个物理盘大小为4KB，共可存放4KB * 10=40KB数据
    10号索引节点为一级简介索引，大小为4KB，存放得并非直接数据，而是链接倒直接物理盘块的地址。假设每个地址占4B，共有1024个地址，对应1024个物理盘，可存放1024* 4KB=4096KB数据
    二级索引节点类似，直接盘存放一级地址，一级地址再存放物理块地址，而后连接到存放数据的物理盘块，容量又扩大了一个数量级，为1024* 1024* 4KB数据
  • 多个物理块的索引表（链接文件和多重索引方式）：索引表是在文件创建时由系统自动建立的，并于文件一起存放在同一文件卷上。根据一个文件大小的不统，其索引表占用物理块的个数不等，一般占一个或几个物理块

文件目录

定义：文件控制块的有序稽核成为文件目录

文件控制块包含一下三类信息：

• 基本信息类：例如文件名、文件的物理地址、文件长度何文件块数等
• 存取控制类：文件的存取权限，像UNIX用户分成文件主、同组用户何一般用户三类，这三类用户的读写执行RWX权限
• 使用信息类：文件建立日期、最后一次修改日期、最后一次访问的日期、当前使用的信息（如打开文件的进程数、在文件上的等待队列）等

路径：

• 相对路径：
• 绝对路径：
• 全文件名：绝对路径+文件名。

存储空间管理

读取方式是指读/写文件存储器上的一个物理块的方法。

• 顺序存取：依次进行读写
• 随机存取：按任意的次序随机地读写

空间管理
数据结构通常称为磁盘分配表；（外存往往指硬盘）
管理方法：

• 空闲区表。 连续未分配区域称为空闲区。
  操作系统为磁盘外存上的所有空闲区建立一张空闲表，每个表项对应一个空闲区。
  
• 位示图。 外存上建立一张位示图（Bitmap），记录文件存储器使用情况。
  每一位对应文件存储器上的一个物理块，用0和1表示空闲和占用。
  
• 空闲块链。每个空闲物理块指向下一个空闲物理块的指针，构成一个链表。
• 成组链接法。 UNIX采用该方法。
  实现时系统将空闲块分成若干组，每100个空闲块未一组，每组第1个空闲块等级了下一组的物理块号和空闲块总数。

文件保护
对文件的保护长采用存取控制的方式

• 存取控制矩阵
• 存取控制表（Linux使用，列出一个文件的所有权限用户）
• 用户权限表（列出一个用户能够访问的所有文件）
• 密码

文件共享

• 硬链接： 两个文件目录表目指向同一个索引结点的链接，也称基于索引结点的链接。
  硬连接是指不同文件名与同一个文件实体的链接。不利于删除
• 符号链接：建立新的文件或目录，并与原来文件或目录的路径名进行映射。

作业管理

不考

磁盘管理

存取时间=寻道时间+等待时间。
寻道时间：磁头移动到磁道所需的时间。
等待时间：等待读取的扇区转到磁头下方所用的时间。

读取磁盘数据的时间主要由以下三部分：
1.找磁道的时间
2.找块（扇区）的时间，即旋转延迟时间
3.传输时间


移臂调度算法：

• 先来先服务FCFS
  
• 最短寻道时间优先SSTF
  
• 扫描算法SCAN（电梯算法）
• 循环扫描算法CSCAN
  【补充】操作系统：磁盘的结构和调度 - 乌漆WhiteMoon - 博客园
  【补充】《计算机操作系统(第四版)》，汤小丹 梁红兵 哲凤屏 汤子瀛 编著，西安电子科技大学出版社

其他

微内核(Micro Kernel)是现代操作系统普遍采用的架构形式。
它是一种能够提供必要 服务的操作系统内核，被设计成在很小的内存空间内增加移植性，提供模块设计，这些必要 的服务包括任务、线程、交互进程通信以及内存管理等。
而操作系统其他所有服务(含设备驱动)在用户模式下运行，可以使用户安装不同的服务接口(API)。
微内核的主要优点在于结构清晰、内核代码量少，安全性和可靠性高、可移植性强、可伸缩性、可扩展性高；其缺点是难以进行良好的整体优化、进程间互相通信的开销大、内核功能代码不能被直接调用而带来服务的效率低。