【星海随笔】操作系统02326知识点总结

Android操作系统的体系结构分为四层

从高层到低层分别是

• 应用程序层、应用框架、系统运行库层、Linux内核层。

windows

windows的体系结构层次中
始终运行在核心态的是 内核
隐藏了与硬件相关的细节、为操作系统的硬件平台提供低级接口的是 硬件抽象层。

常见的操作系统结构

• 常见的操作系统结构有
• 整体式结构
• 层次式结构
• 客户/服务器结构

操作系统体系结构包括四个主要部分

• Linux内核
• LinuxShell
• 文件系统
• 用户应用程序

操作系统的设计过程一般分为

• 功能设计
• 算法设计
• 结构设计

分时操作系统的特点包括

• 独立性 、及时性、交互性、多路性。
• • 多路性：允许一台主机上同时链接多台联机终端。
• • 独立性：各终端用户彼此独立操作，互不干扰。
• • 及时性：是指用户请求在很短的时间内获得响应。
• • 交互性：用户通过终端与系统进行广泛的人机对话。

保护技术

界地址寄存器：用于存储保护。
缓冲技术 、DMA 、通道技术：用于解决 I/O 设备与CPU速度不匹配的问题。

系统使用 基地址寄存器 和 限长寄存器 来实现存储保护。

操作系统的基本类型

按照用户界面的使用环境和功能特征的不同，把操作系统分为三种基本类型：

• 批处理操作系统、分时操作系统 和 实时操作系统。

Unix系统

把 I/O 设备看成是 特殊文件。

I/O软件结构可以分为四层

中断处理程序
设备驱动程序
设备独立的操作系统软件
用户级软件

• 程序控制方式：是指用户进程直接控制处理器和外围设备之间信息传送的方式。
• 中断控制方式：是一种发生在一个异常事件时，调用相应处理程序进行服务的过程。
• DMA控制方式：一种完全由硬件执行 I/O 数据交换的工作方式。
• 通道控制方式：实现对外围设备的统一管理和外围设备与内存之间的数据传送。

I/O设备划分为字符设备和块设备。
按设备的使用性质可分为：输入设备、输出设备、交互式设备、存储设备。
按设备使用可共享性可分为：独占设备、共享设备、虚拟设备。

最小单位

内存空间的最小分配单位是 块。

主存储器的编制单位是 字节。

I/O设备可以划分为 字符设备 和 块设备。

多线程优势

创建线程无需另外分配资源，而创建进程需要分配资源。
因为创建线程无需分配资源，因此创建线程速度比创建进程速度块。
线程间的通信在同一地址空间中进行，不需要额外的通信机制，所以通信简单，信息传递速度也更快。
线程能独立运行，充分利用和发挥处理器与外围设备并行工作的能力。

存储管理

存储管理的主要任务包括 内存的分配与回收、内存扩充、存储共享和存储保护。

重定位：程序和数据装入内存时，需对目标程序中的地址进行修改。这种把逻辑地址转变为内存物理地址的过程称作重定位。

动态地址重定位 是指在程序装入时不进行地址转换，而是直接将程序装入到分配的内存区域中。程序运行过程中，再将指令中的逻辑地址转换为物理地址。

静态重定位：即在程序装入内存的过程中完成，是指在程序开始运行前，程序中的各个地址有关的项均已完成重定位，地址变换通常是在装入时一次完成的，以后不再改变，故称为静态重定位。

存储器的最小编址单位是字节。

分区存储管理方案

紧缩技术

• 在可变分区存储管理方案中，解决碎片问题的一个有效办法是采用紧缩技术，通过移动内存中的程序，把空闲的碎片合并成一个连续的大空闲区置于内存的一端，把所有程序占用区放在内存的另一端。

操作系统采用三种算法查找和分配空闲区。

• 最先适应算法、最优适应算法 和 最坏适应算法
• first fit,FF：算法优先使用 低地址 部分空闲区，在低址空间造成许多小的空闲区，在高地址空间保留大的空闲区。
• best fit，BF：在分配内存空间时取满足申请要求且长度最小的空闲区域。空闲区域按照长度“由小到大”的次序以此记录于空闲区域表中。
• worst fit WF:在分配空间时选取满足申请要求且长度“最大”的空闲区域。空闲区域按照长度“由大到小”的次序以此记录于空闲区域表中。

磁盘驱动调度策略

在磁盘读写请求来到时，应采用调度策略降低访问者的总访问事件。
磁盘驱动调度由 移臂调度 和 旋转调度 两部分组成。
磁盘空间管理策略中，能够迅速找到大量空闲盘块地址的是成组链接法。

磁盘属于辅助存储器。

交换技术

在分时系统中，用户的进程比内存容纳的数量更多，系统将那些不再运行的进程或某一部分调出内存，暂时放在外存上的一个后背存储区，通常称为交换区，当需要运行这些进程时，再将它们装入内存。
覆盖技术：把程序划分为若干个功能上相对独立的程序段，按照其自身的逻辑结构使那些不会同时运行的程序段共享同一块内存区域。

程序段先保存在磁盘上，当有关程序的前一部分执行结束后，把后续程序段调入内存，覆盖前面的程序段。

在计算机系统中，对资源的共享方式分为 同时共享 和 互斥共享。

• 同时共享：硬盘、内存、用重入码编写的文件
• 互斥共享：磁带机
• • 磁带作为文件存储介质时，文件只能组织成 顺序文件。

磁带的利用率为：逻辑记录 / ( 逻辑记录 + 块间隙 )

采用缓冲技术最根本的原因

• 缓冲技术解决的是两个互相协作的设备之间速度差异的协调问题。
  如果没有缓冲，则高速的设备需要暂停来等待速度较低的设备。
  有了缓冲，这种等待就可以降低或消除。

CPU分为管态和目态

• 管态又称为特权态，系统态或核心态。

• • CPU 在管态下可以执行指令系统的全集。

• 目态又称为常态或用户态。

通常操作系统在管态下运行，如果用户程序在目态下执行特权指令，硬件将发生中断，由操作系统获得控制，特权指令执行被禁止，这样可以防止用户程序有意或无意的破坏操作系统，
从目态转换为管态的唯一途径是中断；从管态到目态可以通过修改程序状态字来实现，这将伴随着由操作系统程序到用户程序的转换。
I/O 指令是特权指令

采用中断控制方式

处理器具备的功能包括

• 识别中断请求的能力、响应中断的能力、按优先级响应中断请求的能力。

中断的两种方式

硬件中断装置和软件中断处理程序
典型的中断有：I/O中断、时钟中断、硬件故障中断、程序性中断、系统服务请求(或自愿性中断)。

程序性中断

程序性中断是指程序指令出错、指令越权或者指令越界而引发的系统保护。
程序性中断可以由操作系统和程序自己完成。
如系统调试中断、算法错误等。

系统调用

系统调用的目的是：请求系统服务

系统调用，就是用户在程序中调用操作系统提供的一些子功能。是一种特殊的调用。

操作系统屏蔽了用户对操作系统的具体动作，而只提供了有关的功能。 编程人员可以通过系统调用去请求和释放系统资源。也可以调用对计算机硬件部分的相关工作。

用户程序向系统提出外设的请求方式是系统调用

为了从操作系统中获得服务，用户程序必须使用系统调用，系统调用陷入内核并调用操作系统。

操作系统组织PCB

• 为了便于管理，操作系统把所有的PCB用适当的方式组织起来。
• 一般的组织方式有：线性方式、索引方式和链接方式。

原语

原语是操作系统核心的一个组成部分，由若干条指令组成，用来实现某个特定的操作功能，执行时具有不可中断性。

创建进程

申请空白的PCB，为新进程分配资源（内存）；初始化进程控制块；将进程插入就绪队列。

进程和程序的本质区别为进程是动态的，程序是静态的。

进程的状态

等待状态 （等待某个事件的发生）<- 运行状态（被调度选中） <-> (时间片用完) 就绪状态 <- 等待i状态（某个事件已发生）

二状态进程模型

• 运行态
• 未运行态

注 五状态进程模型：

• 创建状态
• 就绪状态
• 运行状态
• 阻塞状态
• 结束状态

七状态进程模型

• 创建状态
• 就绪状态
• 运行状态
• 阻塞状态
• 结束状态

就绪态：进程被加载到主存里，在运行队列（就绪队列）中，随时准备被执行
阻塞态：进程被加载到主存里，在等待队列（阻塞队列里）中，等待着其他必备事件的发生。
就绪/挂起态：进程在外存（辅存）里面，在挂起队列中，等待着其他必备事件的发生。
阻塞/挂起态：进程在外存（辅存）里面，在挂起队列中，随时准备加载到主存里执行

进程间的通信

进程间的大量信息通信通常有 共享内存、消息机制 和 共享文件进行通信（或管道通信）。
高级通信原语：共享内存、消息机制以及通过共享文件进行通信。

进程的调度

进程调度：即处理器调度，是根据一定的调度算法，系统从就绪队列中选择一个进程，把处理器分配给它。
吞吐量：系统每小时完成的进程数量。
周转时间：指从一个批处理进程提交时刻开始直到该进程完成时刻为止的统计平均时间。

处理器的寄存器：用于记录处理器的运行模式信息的是 程序状态字。
指令寄存器：包含最近取出的指令。
程序计数器：记录将要取出的指令的地址。
地址寄存器：用于存储数据及指令的物理地址、线性地址或有效地址，用于某种特定方式的寻址。
数据寄存器：主要用于存放操作数。

设备控制器是一种电子部件
每个设备控制器都有若干个寄存器用来与处理器进行通信，包括控制寄存器、数据寄存器和状态寄存器。
数据寄存器又称缓冲寄存器，是计算机控制单元中的寄存器，寄存了将要写入计算机主存储器(例如：RAM)的数据，或由计算机主存储器读取后的数据。它就像缓冲器，持有从内存复制的数据，以准备给处理器使用。
主存储器的编址单位是字节。

线程

线程的两种实现方式

• 用户级线程、内核级线程

在线程的两种实现方式中

• 不依赖于内核的是用户级线程
• 而所有线程的创建、撤销和切换都由内核实现的。

引入线程的操作系统中，线程作为调度和分派的基本单位，而进程作为资源拥有的基本单位。

使用文件

把文件控制块FCB送到内存，即打开文件。

文件保密的方式：
1）隐藏文件目录
2）设置口令
3）使用密码

FCB

操作系统给每个文件都设置了一个描述性数据结构，即文件控制块(FCB)，它是文件存在的标志。把所有的文件的描述性数据结构组织起来就构成了目录。

保护文件

文件系统经常采用两种方法保护文件

• 建立副本、定时转储。

文件系统

按文件的用途进行分类，可以把文件分成系统文件、库文件和用户文件。

虚拟存储技术

虚拟存储技术的基本思想和目的
思想：

• 在硬件支持下对内存和外存实施统一管理，利用大容量的外存来扩充内存。
• 产生一个比有限的实际内存空间大的多的，逻辑的虚拟内存空间。利用虚拟存储技术的目的是有效地支持多道程序系统的实现和大型程序运行的需要，从而增强系统的处理能力。

多道程序设计的优势之一是（缩短作业 执行时间）

缓存命中率

Nc表示cache完成存取总次数，Nm表示主存完成存取总次数，h表示 cache 命中率
h = Nc / ( Nc + Nm )

tc表示命中时的cache访问时间，tm表示未命中时的贮存访问时间，ta表示 cache/主存系统的平均访问时间
ta = h×tc + (1-h)×tm

r表示主存慢于cache的倍率，r = tm/tc；e表示访问效率。
e = tc / ta = tc / [ h×tc + (1-h)×tm ] = 1 / [ h + (1-h)×r ] = 1 / [ r + (1-r)×h ]

索引

每个索引文件都有一个索引表，索引表的条目包含文件的

• 逻辑块号 及所对应的 物理块号。

临界区

每次只允许一个进程进入临界区。
保证进程互斥地进入自己的临界区，便可实现诸进程对临界资源的互斥访问。
对临界区的调度使用原则，忙则等待。
所谓临界区是指访问临界资源的程序段。

管程

管程中的 共享变量 在管程外部是看不见的，外部只能通过调用管程中所说明的 外部过程 来间接的对其进行访问。

管程由四部分组成

分别为管程名称
共享数据的说明
对数据进行操作的一组过程
共享数据的赋初值语句。

管程能保障共享资源的互斥执行，即一个管程中活动的进程数最大为 1 个。

P、V操作

使用进程同步和互斥-信号量P、V操作时，大量数据交换时，PV操作效率太低，会使用消息通道或管道的方式完成信息交换。

• value >0 时：信号量可用的资源个数；
• value=0 时：无空闲资源，无空闲进程，正在执行一个进程；
• value< 0时：value的绝对值代表使用该资源的阻塞进程的个数（或等待队列中进程的个数）；

P（S）、V（S）
P占用资源
V释放资源

死锁

产生死锁的主要原因有两个

• 竞争资源
• 进程间推进顺序非法

死锁的四个必要条件：

• 互斥条件
• 不可剥夺条件
• 请求和保持条件
• 循环条件

死锁的预防方法中

• 掘弃请求和保持条件、掘弃环路等待条件、掘弃不剥夺条件。

能实现死锁避免的

银行家算法，是1965年提出的一种避免死锁的资源分配算法，即基本思想是一个进程提出请求资源后，系统先进行资源的试分配。

• 资源有序分配是在解决死锁问题中用于预防死锁

死锁的检测

死锁检测的实质是通过检测是否存在 循环等待 条件，以此来确定死锁的存在与否，并识别出与死锁有关的进程和资源。

页

页：将一个进程逻辑地址空间分成若干个大小相等的片；
页框（页帧）：将物理内存空间分成与页大小相同的若干个存储块；
页表：系统为进程建立的数据结构，实现从页号到页框的映射。

在没有快表的情况下，页式存储管理系统按照给定的虚拟地址进行读写时，不许访问内存的次数是两次

• 第一次按页号读出页表中对应的块号。
• 第二次按计算出来的绝对地址进行读写。

页式存储提供编程使用的虚拟地址由两部分组成，即虚拟页号和页内地址。

• 虚拟页存储主要优点：
  由于其不要求进程的程序段和数据在内存中连续存放，从而有效地解决了碎片问题。
  即提高了内存的利用率，又有利于组织多道程序执行。
• 主要缺点
  由于不同代码的长度不同，但页面大小固定，导致每个程序最后一页内总有一部分空间得不到利用，从而存在页面浪费问题。

页内存储管理计算

例如：系统结构长度为16位，其中高6位用于页号，低10位用于页内地址，则该系统的页大小位 2^10 次 = 1024 ，虚拟地址2058的位置的页内地址是 （10）

SPOLLing技术 - 应用于 I/O 设备

Spolling系统是由

输入程序模块、输出程序模块、作业调度程序

提高了处理器的利用率
是用于将 IO 设备进行虚拟化的技术，主要解决的是速度不匹配的问题。
作业执行时，从磁盘上的输入井中读取数据，并把作业的执行结果暂时存放在磁盘上的输出井中。

SPOOLing提高了设备利用率，缩短了用户程序执行时间，但不提高处理器利用率。
斯普林技术

设备独立性

应用程序独立于具体使用的物理设备
好处：提高设备管理软件的设计效率，当 I/O 设备更新时，不需要重新编写全部的软件。

搜索一个磁盘的位置，需要访问磁盘次数

首先访问 i 结点的盘块
访问一次一重间接地址盘块
访问一次二重间接地址盘块
。。。
访问一次某地址的盘块

字节偏移量 / 磁盘块大小 = 位于的磁盘块数 #如果等于615.234，则是在615个盘块中。
每个直接地址占一个盘块
每个簇中可以存放的盘块号(一般为256) = 盘块大小 （2048）/ 每个地址项占的字节（8字节）

对磁盘的空闲管理通常有四种方案

分别为位示图、空闲块表、空闲块链表以及以此基础上的改进方案：空闲块成组链接法。

缺页算法

FIFO缺页算法和LRU缺页算法
FIFO缺页算法：

• 页中有则页内内容不变，为不缺页状态

LRU缺页算法：

• 页中有则将其置换为时间最短页（即为最后淘汰页）。

缺页率 = （总的 - 访问成功的次数 ） / 总的
缺页次数 = 总数 - 访问成功的次数

进程调度算法

FCFS（先到先运行）
SJF（最短先运行）