操作系统知识

操作系统概述

操作系统定义

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

操作系统有三个重要的作用

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

操作系统的4个特征

(1)并发性
(2)共享性
(3)虚拟性
(4)不确定性

操作系统的功能

(1)进程管理。
实质上是对处理机的执行“时间”进行管理，采用多道程序等技术将CPU的时间合理地分配给每个任务，主要包括进程控制、进程同步、进程通信和进程调度。

(2)文件管理。
主要包括文件存储空间管理、目录管理、文件的读/写管理和存取控制。

(3)存储管理。
存储管理是对主存储器“空间”进行管理，主要包括存储分配与回收、存储保护、地址映射(变换)和主存扩充。

(4)设备管理。
实质是对硬件设备的管理，包括对输入/输出设备的分配、启动、完成和回收。

(5)作业管理。
包括任务、界面管理、人机交互、图形界面、语音控制和虚拟现实等

操作系统的分类

(1) 批处理操作系统:
单道批处理和多道批处理(主机与外设可并行)。

(2) 分时操作系统:
一个计算机系统与多个终端设备连接。
分时操作系统是将CPU的工作时间划分为许多很短的时间片，轮流为各个终端的用户服务。

(3) 实时操作系统:
实时是指计算机对于外来信息能够以足够快的速度进行处理，并在被控对象允许的时间范围内做出快速反应。
实时系统对交互能力要求不高，但要求可靠性有保障。
为了提高系统的响应时间，对随机发生的外部事件应及时做出响应并对其进行处理。

(4) 网络操作系统:
是使联网计算机能方便而有效地共享网络资源，为网络用户提供各种服务的软件和有关协议的集合。
功能主要包括高效、可靠的网络通信;对网络中共享资源的有效管理;提供电子邮件、文件传输、共享硬盘和打印机等服务;网络安全管理;提供互操作能力。
三种模式:

• 集中模式
• 客户端/服务器模式
• 对等模式。

(5) 分布式操作系统:
分布式计算机系统是由多个分散的计算机经连接而成的计算机系统，系统中的计算机无主、次之分，任意两台计算机可以通过通信交换信息。
通常，为分布式计算机系统配置的操作系统称为分布式操作系统。是网络操作系统的更高级形式。

(6) 微型计算机操作系统:
简称微机操作系统，常用的有Windows、MacOs、Linux。

(7) 嵌入式操作系统:
运行在嵌入式智能芯片环境中，对整个智能芯片以及它所操作、控制的各种部件装置等资源进行统一协调、处理、指挥和控制。其主要特点如下:

1. 微型化。从性能和成本角度考虑，希望占用的资源和系统代码量少，如内存少、字长短、运行速度有限、能源少(用微小型电池)。

2. 可定制。从减少成本和缩短研发周期考虑，要求嵌入式操作系统能运行在不同的微处理器平台上，能针对硬件变化进行结构与功能上的配置，以满足不同应用需要。

3. 实时性。嵌入式操作系统主要应用于过程控制、数据采集、传输通信、多媒体信息及关键要害领域需要迅速响应的场合，所以对实时性要求较高。

4. 可靠性。系统构件、模块和体系结构必须达到应有的可靠性，对关键要害应用还要提供容错和防故障措施。

5. 易移植性。为了提高系统的易移植性，通常采用硬件抽象层(HardwareAbstraction LevelHAL)和板级支撑包(BoardSupportPackage，BSP)的底层设计技术。

• 嵌入式系统初始化过程:
• 按照自底向上、从硬件到软件的次序依次为:
  • 片级初始化→板级初始化→系统初始化
    • 芯片级是微处理器的初始化
    • 板卡级是其他硬件设备初始化
    • 系统级初始化就是软件及操作系统初始化

(8)微内核操作系统:

微内核，顾名思义，就是尽可能的将内核做的很小，只将最为核心必要的东西放入内核中，其他能独立的东西都放入用户进程中，这样，系统就被分为了

• 用户态
• 内核态
  如下图所示:

进程管理

进程的组成和状态

进程的组成:

• 进程控制块PCB(唯一标志)、程序(描述进程要做什么)、数据(存放进程执行时所需数据)
  进程基础的状态是下左图中的三态图。

• 需要熟练掌握左下图中的进程三态之间的转换。
  

• 新建态对应于进程刚刚被创建时没有被提交的状态，并等待系统完成创建进程的所有必要信息终止态等待操作系统进行善后处理，释放主存。

前趋图和进程资源图

• 前趋图

用来表示哪些任务可以并行执行，哪些任务之间有顺序关系，具体如下图:

可知，ABC可以并行执行，但是必须ABC都执行完后，才能执行D，这就确定了两点:任务间的并行、任务间的先后顺序。

• 进程资源图

用来表示进程和资源之间的分配和请求关系，如下图所示:

P代表进程
R代表资源
R方框中有几个圆球就表示有几个这种资源
在上图中，R1指向P1表示 R1有一个资源已经分配给了P1，P1指向 R2，表示P1还需要请求一个 R2资源才能执行

阻塞节点
某进程所请求的资源已经全部分配完毕，无法获取所需资源，该进程被阻塞了无法继续。如上图中 P2。

死锁
当一个进程资源图中所有进程都是阻塞节点时，即陷入死锁状态;

进程资源图的化简方法:
(1) 先看系统还剩下多少资源没分配
(2) 再看有哪些进程是不阻塞的
(3) 接着把不阻塞的进程的所有边都去掉,形成一个孤立的点,
(4)再把系统分配给这个进程的资源回收回来,这样,系统剩余的空闲资源便多了起来
(5)接着又去看看剩下的进程有哪些是不阻塞的,然后又把它们逐个变成孤立的点。
(6)最后，所有的资源和进程都变成孤立的点。

进程间的同步与互斥

互斥和同步并非反义词，
互斥
互斥表示一个资源在同一时间内只能由一个任务单独使用，需要加锁,使用完后解锁才能被其他任务使用;

同步
同步表示两个任务可以同时执行，只不过有速度上的差异，需要速度上匹配，不存在资源是否单独或共享的问题。

信号量操作

• 基本概念

临界资源:
各个进程间需要互斥方式对其进行共享的资源，即在某一时刻只能被一个进程使用，该进程释放后又可以被其他进程使用。

临界区:
每个进程中访问临界资源的那段代码。

信号量:
是一种特殊的变量。

• 两类信号量

互斥信号量
对临界资源采用互斥访问，使用互斥信号量后其他进程无法访问，初值为1。
同步信号量
对共享资源的访问控制，初值是共享资料的个数。

P 操作和V操作
都是原子操作，用来解释进程间的同步和互斥原理，PV操作原理如下图所示:

例如在生产者和消费者的问题中，生产者生产一个商品S，而后要申请互斥的使用该仓库，即首先需要执行互斥信号量 P(S0)，申请到仓库独立使用权后，再判断仓库是否有空闲(信号量 S1)，执行P(S1)，若结果大于等于0，表示仓库有空闲，再将S放入仓库中，此时仓库商品数量(信号量 S2)增加 1，即执行 V(S2)操作，使用完毕后，释放互斥信号量 V(S0)。

对于消费者，首先也需要执行互斥信号量P(S0)，申请到仓库独立使用权后，再判断仓库中是否有商品，执行 P(S2)，若结果大于等于0，表示有商品，可以取出，此时造成了一个结果，即仓库空闲了一个，执行 V(S1)操作，使用完毕后，释放互斥信号量 V(S0)。因此，执行P操作是主动的带有判断性质的-1，执行V操作是被动的因为某操作产生的+1。

进程调度

• 进程调度方式是指当有更高优先级的进程到来时如何分配CPU。
• 分为可剥夺和不可剥夺两种，可剥夺指当有更高优先级进程到来时，强行将正在运行进程的CPU分配给高优先级进程;
• 不可剥夺是指高优先级进程必须等待当前进程自动释放CPU。

在某些操作系统中，一个作业从提交到完成需要经历高、中、低三级调度。

(1)高级调度
高级调度又称“长调度”“作业调度”或“接纳调度”，它决定处于输入池中的哪个后备作业可以调入主系统做好运行的准备，成为一个或一组就绪进程。
在系统中一个作业只需经过一次高级调度。

(2)中级调度
中级调度又称“中程调度”或“对换调度”，它决定处于交换区中的哪个就绪进程可以调入内存，以便直接参与对CPU的竞争。

(3)低级调度
低级调度又称“短程调度”或“进程调度”，它决定处于内存中的哪个就绪进程可以占用CPU。
低级调度是操作系统中最活跃、最重要的调度程序，对系统的影响很大。

调度算法
先来先服务 FCFS:先到达的进程优先分配CPU。用于宏观调度。

时间片轮转
分配给每个进程CPU时间片，轮流使用CPU，每个进程时间片大小相同，很公平用于微观调度。
优先级调度
每个进程都拥有一个优先级，优先级大的先分配CPU。

多级反馈调度
时间片轮转和优先级调度结合而成，设置多个就绪队列1,2,3.n，每个队列分别赋予不同的优先级，分配不同的时间片长度;新进程先进入队列1的末尾，按FCFS原则，执行队列1的时间片:若未能执行完进程，则转入队列2的末尾，如此重复。

死锁问题

• 当一个进程在等待永远不可能发生的事件时,就会产生死锁;
• 若系统中有多个进程处于死锁状态就会造成系统死锁。

死锁产生的四个必要条件

(1)资源互斥
(2)每个进程占有资源并等待其他资源
(3)系统不能剥夺进程资源
(4)进程资源图是一个环路。

死锁产生后，解决措施是打破四大条件，有下列方法:

(1)死锁预防:
采用某种策略限制并发进程对于资源的请求，破坏死锁产生的四个条件之一，使系统任何时刻都不满足死锁的条件。

(2)死锁避免:
一般采用银行家算法来避免，银行家算法，就是提前计算出一条不会死锁的资源分配方法，才分配资源，否则不分配资源，相当于借贷，考虑对方还得起才借钱，提前考虑好以后，就可以避免死锁。

(3)死锁检测
允许死锁产生，但系统定时运行一个检测死锁的程序，若检测到系统中发生死锁，则设法加以解除。

(4)死锁解除
即死锁发生后的解除方法，如强制剥夺资源，撤销进程等。

死锁资源计算
系统内有n个进程，每个进程都需要R个资源
那么其发生死锁的最大资源数为n*(R-1)。
其不发生死锁的最小资源数为 n*(R-1)+1。

线程和进程

进程
传统的进程有两个属性:

• 可拥有资源的独立单位;
• 可独立调度和分配的基本单位。
• 一个进程可以拥有多个线程

线程

• 计算机能识别的最小任务单元
• 线程是进程中的一个实体，是被系统独立分配和调度的基本单位。
• 线程基本上不拥有资源，只拥有一点运行中必不可少的资源(如程序计数器、一组寄存器和栈)

引入线程的原因是进程在创建、撤销和切换中，系统必须为之付出较大的时空开销，故在系统中设置的进程数目不宜过多，进程切换的频率不宜太高，这就限制了并发程度的提高。
引入线程后，将传统进程的两个基本属性分开，线程作为调度和分配的基本单位，进程作为独立分配资源的单位。用户可以通过创建线程来完成任务，以减少程序并发执行时付出的时空开销。

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

存储管理

• 存储器的结构

寄存器--高速缓存Cache--主存--外存

• 地址重定位

将逻辑地址转换为实际主存物理地址的过程
分为静态重定位(在程序装入主存时就完成了转换)、动态重定位(边运行边转换)

分区存储管理

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

固定分区
静态分区方法，将主存分为若干个固定的分区，将要运行的作业装配进去，由于分区
固定，大小和作业需要的大小不同，会产生内部碎片。

可变分区
动态分区方法，主存空间的分区是在作业转入时划分，正好划分为作业需要的大小，这样就不存在内部碎片，但容易将整片主存空间切割成许多块，会产生外部碎片。

可重定位分区
可以解决碎片问题，移动所有已经分配好的区域，使其成为一个连续的区域，这样其他外部细小的分区碎片可以合并为大的分区，满足作业要求。只在外部作业请求空间得不到满足时进行。

分页存储管理

• 如果采用分区存储，都是整存，会出现一个问题，即当进程运行所需的内存大于系统内存时，就无法将整个进程一起调入内存，因此无法运行，若要解决此问题，就要采用段页式存储组织，页式存储是基于可变分区而提出的。

• 如下图所示，逻辑页分为页号和页内地址，页内地址就是物理偏移地址，而页号与物理块号并非按序对应的，需要查询页表，才能得知页号对应的物理块号，再用物理块号加上偏移地址才得出了真正运行时的物理地址。
  

• 优点:利用率高，碎片小，分配及管理简单。

• 缺点:增加了系统开销，可能产生抖动现象。

地址表示和转换

• 地址组成:页地址+页内偏移地址;(页地址在高位，页内偏移地址在低位)
• 物理地址:物理块号+页内偏移地址;
• 逻辑地址:页号+页内偏移地址;
• 物理地址和逻辑地址的页内偏移地址是一样的，只需要求出页号和物理块号之间的对应关系，首先需要求出页号的位数，得出页号，再去页表里查询其对应的物理块号，使用此物理块号和页内偏移地址组合，就能得到物理地址。

页面置换算法

有时候，进程空间分为100个页面，而系统内存只有10个物理块，无法全部满足分配，就需要将马上要执行的页面先分配进去，而后根据算法进行淘汰，使 100个页面能够按执行顺序调入物理块中执行完。

缺页表示需要执行的页不在内存物理块中，需要从外部调入内存，会增加执行时间，因此，缺页数越多，系统效率越低。页面置换算法如下:

(1)最优算法
OPT，理论上的算法，无法实现，是在进程执行完后进行的最佳效率计算，用来让其他算法比较差距。原理是选择未来最长时间内不被访问的页面置换，这样可以保证未来执行的都是马上要访问的。

(2)先进先出算法
FIFO，先调入内存的页先被置换淘汰，会产生抖动现象，即分配的页数越多，缺页率可能越多(即效率越低).

(3)最近最少使用
LRU，在最近的过去，进程执行过程中，过去最少使用的页面被置换淘汰，根据局部性原理，这种方式效率高，且不会产生抖动现象，使用大量计数器，但是没有LFU多。淘汰原则:优先淘汰最近未访问的，而后淘汰最近未被修改的页面。

段氏存储管理

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

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

分页存储和分段存储的总结
分页是根据物理空间划分，每页大小相同;
分段是根据逻辑空间划分，每段是一个完整的功能，便于共享，但是大小不同。

地址表示
(段号，段内偏移):其中段内偏移不能超过该段号对应的段长，否则越界错误，而此地址对应的真正内存地址应该是:段号对应的基地址+段内偏移。

段页式存储管理

对进程空间先分段，后分页，具体原理图和优缺点如下

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

设备管理

概述

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

设备的分类
按数据组织分类:块设备、字符设备。

按照设备功能分类
输入设备、输出设备、存储设备、网络联网设备、供电设备等等。

资源分配角度分类
独占设备、共享设备和虚拟设备

数据传输速率分类
低速设备、中速设备、高速设备。

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

I/O软件

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

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

文件管理

概述

文件的物理结构是指文件的内部组织形式，即文件在物理存储设备上的存放方法，包括:

(1)连续结构
连续结构也称顺序结构，它将逻辑上连续的文件信息(如记录)依次存放在连续编号的物理块上。只要知道文件的起始物理块号和文件的长度，就可以很方便地进行文件的存取。

(2)链接结构
链接结构也称串联结构，它是将逻辑上连续的文件信息(如记录)存放在不连续的物理块上,每个物理块设有一个指针指向下一个物理块。因此,只要知道文件的第一个物理块号,就可以按链指针查找整个文件。

(3)索引结构
在采用索引结构时，将逻辑上连续的文件信息(如记录)存放在不连续的物理块中，系统为每个文件建立一张索引表。索引表记录了文件信息所在的逻辑块号对应的物理块号，并将索引表的起始地址放在与文件对应的文件目录项中。

(4)多个物理块的索引表
索引表是在文件创建时由系统自动建立的，并与文件一起存放在同文件卷上。根据一个文件大小的不同,其索引表占用物理块的个数不等,一般占一个或几个物理块。

索引文件结构

• 如下图所示，系统中有13个索引节点，0-9为直接索引，即每个索引节点存放的是内容，假设每个物理盘大小为 4KB，共可存 4KB*10=10KB 数据;

• 10号索引节点为一级间接索引节点，大小为4KB,存放的并非直接数据，而是链接到直接物理盘块的地址，假设每个地址占4B，则共有1024个地址，对应1024个物理盘，可存1024*4KB=4098KB数据。

• 二级索引节点类似，直接盘存放一级地址，一级地址再存放物理盘快地址，而后链接到存放数据的物理盘块，容量又扩大了一个数量级，为1024*1024*4KB数据。

文件目录

文件控制块中包含以下三类信息

(1)基本信息类
(2)存取控制信息类
(3)使用信息类

文件控制块的有序集合称为文件目录。
相对路径
是从当前路径开始的路径。
绝对路径
是从根目录开始的路径。

文件存储空间管理

• 文件的存取方法是指读/写文件存储器上的一个物理块的方法。
• 通常有顺序存取和随机存取两种方法。
• 顺序存取方法是指对文件中的信息按顺序依次进行读/写;
• 随机存取方法是指对文件中的信息可以按任意的次序随机地读/写。

文件存储空间的管理:

(1)空闲区表
将外存空间上的一个连续的未分配区域称为“空闲区”。
操作系统为磁盘外存上的所有空闲区建立一张空闲表，每个表项对应一个空闲区，适用于连续文件结构。

(2)位示图
这种方法是在外存上建立一张位示图(Bitmap)，记录文件存储器的使用情况。
每一位对应文件存储器上的一个物理块，取值0和1分别表示空闲和占用。

(3)空闲块链
每个空闲物理块中有指向下一个空闲物理块的指针，所有空闲物理块构成一个链表，链表的头指针放在文件存储器的特定位置上(如管理块中)，不需要磁盘分配表，节省空间。
每次申请空闲物理块只需根据链表的头指针取出第一个空闲物理块,根据第一个空闲物理块的指针可找到第二个空闲物理块，依此类推。

(4)成组链接法
例如，在实现时系统将空闲块分成若干组，每100个空闲块为一组，每组的第一个空闲块登记了下一组空闲块的物理盘块号和空闲块总数。假如某个组的第一个空闲块号等于0，意味着该组是最后一组，无下一组空闲块。