操作系统

概论

操作系统的定义

操作系统(OS )是管理计算机硬件与软件资源的计算机程序。

操作系统的功能

  1. 进程管理——进程线程的状态、控制、同步互斥、通信调度等
  2. 内存管理——分配/回收、地址转换、存储保护等
  3. 设备管理——设备驱动、分配回收、缓冲技术等
  4. 文件管理——文件目录、文件操作、磁盘空间、文件存取控制

操作系统的特征

  1. 并发性
    并发性是两个或多个事件在同一时间间隔内发生的、同时处于活动状态的特性。
  2. 共享性
    主要是指资源共享。内存中并发执行的多个程序可以共享计算机的硬件和软件资源。
  3. 虚拟性
    虚拟性是指将一个物理实体映射为一个或多个逻辑对象。
  4. 随机性
    随机性也叫异步性,指的是每道程序在何时执行、各个程序执行的顺序以及每道程序所需的时间都是不确定的,也是不可预知的。

操作系统的分类

  1. 批处理操作系统
  2. 分时操作系统
  3. 实时操作系统
  4. 嵌入式操作系统
  5. 个人操作系统
  6. 网络操作系统
  7. 分布式操作系统

进程管理

进程就是正在运行的程序及其占用的系统资源,是系统进行资源分配、保护和调度的基本单位。

程序的执行

程序的顺序执行

一个具有独立功能的程序独占处理器直至最终结束的过程称为程序的顺序执行。

顺序执行有如下三个特点:

  • 顺序性
  • 封闭性
  • 可在现性

程序的并发执行与并行执行

并行是指多个事件在同一时刻发生,而并发是指多个事件在同一时期内发生。

并行是并发的特例,程序并行执行的硬件前提是系统中有多个 CPU。

并发的本质是一个 CPU 在多个程序运行过程中的时分复用。

并发执行的特性有以下三点:

  • 间断性
  • 开放/交互性
  • 不可再现性

进程的特征与控制

进程有以下特性:

  • 结构性
  • 动态性
  • 独立性
  • 并发性

进程通常分为两类:系统进程和用户进程

进程上下文:进程的生命周期中,进程实体和支持进程运行的环境

进程状态及转换

进程三态模型

就绪状态——进程在内存中已经具备执行的条件,等待分配 CPU。就绪队列

运行状态——进程占用 CPU 并正在执行。

阻塞状态——也成为等待状态。阻塞队列

进程五态模型

新建状态——进程被创建时所处的状态。

终止状态——进程正常结束或出现严重错误时,会被操作系统终止或被其它有终止权的进程终止。

进程七态模型

挂起就绪——进程具备运行条件,但目前不在内存中,需要被系统调入内存才能运行。

挂起阻塞——进程在等待某一事件或条件并且该进程目前不在内存中。

进程控制块 PCB

描述和控制进程运行的数据结构——进程控制块(进程描述符)

PCB 是进程存在的唯一标志

  1. 进程标识信息——内部标识符和外部标识符
  2. 现场信息——进程运行时 CPU 的即时状态即各寄存器的值
  3. 控制信息——操作系统控制进程需要的信息

进程控制

核心态(内核态)和用户态,也称为管态和目态

进程控制——系统对进程生命周期的各个环节进行控制

进程控制通常由原语完成。原语是由若干条指令所组成,用来实现某个特定功能,在执行过程中不可被中断的程序段。

原语是不可分割的执行单位,原语的执行不可能是并发的。

  1. 创建进程
  2. 撤消与终止进程
  3. 阻塞与唤醒进程
  4. 挂起与激活进程

进程的互斥与同步

并发运行的多个进程之间存在两种基本关系——竞争(互斥)和协作(同步)

竞争,会引起一下两种极端情况:

  • 死锁:一组进程均只占有部分所需资源而无法继续运行,陷入阻塞
  • 饥饿:进程被调度程序长期忽视而分配不到 CPU 执行

临界资源与临界区

临界资源:在某段时间内只能允许一个进程使用的资源
临界区:访问临界资源的代码段

临界区调度原则:

  1. 一次至多一个进程能够进入临界区内执行;
  2. 如果已有进程在临界区,其它试图进入的进程应等待;
  3. 进入临界区内的进程应在有限时间内退出,以便让等待进程中的一个进入;

进程同步机制

  1. 信号量机制

    P(s):将信号量 s 的值减 1,若结果小于 0,则调用 P(s) 的进程被阻塞,并进入信号量 s 的阻塞队列中;若结果不小于 0,则调用 P(s) 的进程继续运行。

    V(s):将信号量 s 的值加 1,若结果不大于 0,则调用 V(s) 的进程从该信号量阻塞队列中释放、唤醒一个处于等待状态的进程,将其转换为就绪状态,调用 V(s) 的进程继续运行;若结果大于0,则调用V(s)的进程继续运行。

    • P 操作意味进程申请一个资源,求而不得则阻塞进程,V 操作意味着释放一个资源,若此时还有进程在等待获取该资源,则被唤醒。
    • 若信号量的值为正数,该正数表示可对信号量可进行的 P 操作的次数,即可用的资源数。信号量的初值一般设为系统中相关资源的总数,对于互斥信号量,初值一般设为 1。
    • 若信号量的值为负,其绝对值表示有多个进程申请该资源而又不能得到,在阻塞队列等待,即在信号量阻塞队列中等待该资源的进程个数。
  2. 管程同步机制

    把临界区集中并封装成抽象数据类型,其中包括与临界资源相关、仅限管程内部访问的公共变量,供管程外的进程调用以访问这些公共变量的接口过程,并提供互斥机制确保进程互斥地使用管程 。

    管程具有以下特点:

    • 模块化
    • 隐蔽性
    • 互斥性

    条件变量(condition variable)同步机制

    • 让进入管程却因资源不足而阻塞的进程暂时放弃管程控制权(开放管程),进入该条件变量的等待队列
    • 条件变量只能在管程中通过两个原语操作——wait 原语和 signal 原语
    • 一个进程已进入管程但无法继续执行,便在相应的条件变量 x 上调用 x.wait( ),将自己阻塞并移入 x 的等待队列中,放弃管程控制权(开放管程),另一进程可以通过对同一个条件变量执行 x.signal( ) 来唤醒之前在 x 上等待的进程

管程与进程的区别:

  • 管程把共享变量上的同步操作集中起来,而临界区却分散在每个进程中;
  • 管程是为管理共享资源而建立的,进程主要是为实现系统并发性而引入的;
  • 管程被进程调用,管程和调用它的进程不能并行工作,而进程之间能并行工作,并发性是其固有特性;
  • 管程是语言或操作系统的组成部分,随操作系统启动而装入内存,不必创建或撤销,而进程有生命周期;

进程同步经典问题

  1. 生产者-消费者问题

    在并发环境下生产者、消费者进程访问缓冲区的速度不协调、不匹配——不同步,或者没有做到互不影响地使用、更新缓冲区——互斥,所以会出现运行错误甚至是死锁。生产者-消费者问题

  2. 读者-写者问题

    • 允许多个读者进程同时读文件
    • 只允许一个写者进程写文件
    • 任何一个写者进程在完成写操作之前不允许其它读者或写者工作
    • 写者执行写操作前,应让已有的写者和读者全部退出
  3. 哲学家就餐问题

    五个哲学家围坐在一圆桌旁,桌中央有一盘通心面,每人面前有一只空盘子,每两人之间放一只筷子。每个哲学家的行为是思考,感到饥饿,然后吃通心面。为了吃面,每个哲学家必须拿到两只筷子,并且每个人只能直接从自己的左手边和右手边去取筷子。哲学家就餐问题

  4. 睡眠理发师

    理发店里有一个理发师,一把理发椅,N 个供等候顾客休息的椅子。若无顾客,理发师躺在理发椅上睡觉。顾客到来时唤醒理发师,若理发师正在理发,新来的顾客坐在空闲的休息椅上等候,如果没有空椅子,顾客离开。

进程通信

  1. 消息传递通信
  2. 共享内存通信
  3. 管道通信

进程调度

两种基本的进程调度方式,抢占方式和非抢占方式,也称剥夺式(preemptive)和非剥夺式(non_preemptive)调度

进程调度模型

  • 高级调度(High-Level Scheduling),又称为作业调度,它决定把后备作业调入内存运行;
  • 中级调度(Intermediate-Level Scheduling),又称为平衡调度,在虚拟存储器中引入,在内、外存对换区进行进程对换;
  • 低级调度 (Low-Level Scheduling):又称为进程调度,它决定就绪队列的某进程获得CPU; 三级调度模型

调度算法选择/评价准则

  • 处理器利用率(CPU utilization)= CPU有效工作时间 / CPU总的运行时间
  • 响应时间(response time):交互环境下用户从键盘提交请求开始,到系统首次产生响应为止的时间
  • 周转时间(turnaround time)Ti = Tf – Ts,即:周转时间 = 完成时刻 - 提交时刻
  • 带权周转时间—— Wi = 作业的周转时间 Ti / 系统为作业提供的服务时间 Tsi,显然带权周转时间总大于 1
  • 平均作业周转时间 T = (ΣTi) / n
  • 平均作业带权周转时间W = (ΣWi) / n

调度算法

非剥夺方式:先来先服务、短作业优先、高响应比优先

剥夺方式:最短剩余时间优先、优先权、时间片轮转

  1. 先来先服务(First-Come First-Served,FCFS)——按进程就绪的先后顺序来调度,到达得越早,就越先执行

    • 获得CPU的进程,未遇到其它情况时,一直运行下去
    • 是一种非抢占式算法
    • 没有考虑执行时间长短、运行特性和资源的要求

    系统中现有 5 个作业 A、B、C、D、E 同时提交(到达顺序也为ABCDE),其预计运行时间分别 10、1、2、1、5 个时间单位,如表所示,计算 FCFS 调度下作业的平均周转时间和平均带权周转时间。

    作业ID 预计需运行时间
    A 10
    B 1
    C 2
    D 1
    E 5

    设作业到达时刻为0,根据定义计算,系统运行情况

    作业ID 运行时间 等待时间 开始时间 完成时间 周转时间 带权周转时间
    A 10 0 0 10 10 1
    B 1 10 10 11 11 11
    C 2 11 11 13 13 6.5
    D 1 13 13 14 14 14
    E 5 14 14 19 19 3.8

    平均周转时间:T =(10+11+13+14+19)/ 5 = 13.4
    平均带权周转时间:W =(1+11+6.5+14+3.8)/ 5 = 7.26

  2. 短作业优先(Shortest-Job-First,SJF)——以进入系统的作业所要求的CPU服务时间为标准,总选取估计所需CPU时间最短的作业优先投入运行

  3. 最短剩余时间优先(Shortest Remaining Time First,SRTF)——若一就绪状态的新作业所需的CPU时间比当前正在执行的作业剩余任务所需CPU时间还短,SRTF将打断正在执行作业,将执行权分配给新作业

  4. 高响应比优先(Highest Response Ratio First,HRRF)——是 FCFS 与 SJF 两种算法的折衷——既考虑作业等待时间,又考虑作业的运行时间,既照顾短作业又不使长作业等待过久,改善了调度性能,仍属于非抢占式算法

    响应比为作业的响应时间与作业所需运行时间之比,简化为:响应比 =1 +(已等待的时间 / 估计运行时间)

  5. 优先权(Highest-Priority-First,HPF)——根据进程的优先权进行进程调度,每次总是选取优先权高的进程调度,也称优先级调度算法,一般是抢占式调度

  6. 时间片轮转(Round-Ribon,RR)——调度程序把CPU分配给进程使用一个规定的时段,称为一个时间片(如100ms),就绪队列中的进程轮流获得CPU的一个时间片。当一个时间片结束时,系统剥夺该进程执行权,等候下一轮调度,属于抢占式调度

死锁

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

  • 并发进程对临界资源的竞争
  • 并发进程推进顺序不当

死锁发生的四个必要条件:

  1. 互斥条件
  2. 请求与保持条件
  3. 不剥夺条件
  4. 环路等待条件

银行家算法的思路:

  1. 在某一时刻,各进程已获得所需的部分资源。有一进程提出新的资源请求,系统将剩余资源试探性地分配给该进程。
  2. 如果此时剩余资源能够满足余下的某些进程的需求,则将剩余资源分配给能充分满足的、资源需求缺口最大的进程,运行结束后释放的资源再并入系统的剩余资源集合。
  3. 反复执行第 2 步,直到所有的进程都能够获得所需而运行结束。说明第1步的进程请求是可行的,系统处于安全状态,相应的进程执行序列称为系统的安全序列。如果所有的进程都试探过而不能将资源分配给进程,即不存在安全序列,则系统是不安全的。

线程与进程

  • 进程是程序在某个数据集合上的一次执行过程,线程是进程内部的一个执行序列
  • 进程是资源分配的最小单位,线程是 CPU 调度的最小单位
  • 一个进程可以包含若干个线程
  • 多个线程共享进程的资源,使用相同的地址空间
  • 进程间切换代价大,线程间切换代价小
  • 进程拥有资源多,线程不拥有自己的资源或只有必要的资源

内存管理

MMU 内存管理单元,也称作分页内存管理单元,把虚拟地址转换成物理地址。TLB 是一块高速缓存,缓存虚拟地址和其映射的物理地址,减少CPU访问物理内存的次数,用于改进虚拟地址到物理地址转换速度。

内存管理概述

计算机的存储系统主要包括内存储器和外存储器

  • 内存储器(Memory)即俗称的内存或主存
  • 外存储器也叫辅助存储器

计算机存储系统的结构

计算机系统的结构与使用关系

地址的表示与地址转换

只有把程序和数据的逻辑地址转换为物理地址,程序才能正确运行,该过程称为地址转换或地址重定位。地址转换有静态重定位和动态重定位两种方式。

  • 静态重定位:这种方式是在用户作业装入内存时由装入程序(装配程序)实现从逻辑地址到物理地址的转换,地址转换在作业执行前一次完成
  • 动态重定位:程序执行过程中,CPU在访问程序和数据之前才实现地址转换。动态重定位必须借助于硬件地址转换机构来实现,硬件系统中设置了一个定位寄存器,当操作系统为某程序分配了一块内存区域后,装入程序把程序装入到所分配的区域中,然后把该内存区域的起始地址置入定位寄存器中。在程序执行过程中需要进行地址转换时,只需将逻辑地址与定位寄存器中的值相加就可得到物理地址。这种地址转换方式是在指令过程中进行的,所以称动态重定位。

内存管理的功能

  1. 内存的分配和回收
  2. 提高内存的利用率
  3. 通过虚拟存储技术“扩充”内存容量
  4. 内存信息保护

覆盖与交换技术

  1. 覆盖技术:按照程序自身的逻辑结构,让不同时执行的程序段先后共享同一块内存区域

    例如:某程序由A、B、C、D、E、F等六个程序段组成,它们之间的调用关系如图3.3左图所示。其中,程序段A只调用B和C,程序段B只调用F,而程序段C只调用D和E。由于B和C之间没有相互调用,所以它们可以共享同一覆盖区。覆盖区的大小以能装入所有共享的程序段为准。本例中,与B、C对应的覆盖区的大小为50K。类似地,D、E、F也可以共享一大小为40K的覆盖区,如下图所示。覆盖技术

  2. 交换技术:由操作系统根据需要,将某些暂时不运行的进程或程序段从内存移到外存的交换区中;当内存空间富余时再给被移出的进程或程序段重新分配内存,让其进入内存

分区内存管理

  1. 单一连续内存管理
  2. 固定分区内存管理
  3. 可变分区内存管理
    • 最先适应分配算法
    • 循环首次适应分配算法
    • 最优适应分配算法
    • 最差适应分配算法
    • 快速适应算法

页式存储管理

页:将用户进程的逻辑地址空间划分为大小相等的区,每一个区称为一页或一个页面,并对各页从 0 开始编号,如第 0 页、第 1 页等。

物理块:将物理内存也划分成与页大小相等的区,每一个区称为一个物理块(block),或称为块、页框,也同样对它们加以编号,如 0 号块、1 号块等。

内存分配的基本单位是页,进程的最后一页经常装不满一块,所以会在最后一块内形成不可利用的碎片,称之为“页内碎片”。

32 位操作系统其逻辑地址是 32 位,采用页式内存管理,如果每页大小 4096 B,那么页内偏移要占用其逻辑地址的低 12 位,从 0 位开始到 11 位结束。逻辑地址剩余的高 20 位用来表示页号,从 12 位开始到 31 位结束,这样最多允许有 220(1M)个页面。页面的编号从 0 开始,分别为 0,1,2,3 …,220−1,如图所示。

页式存储的逻辑地址

快表

为了提高程序的运行速度,可以将最近访问过的页的页表项信息存放在高速缓存中,高速缓存也称为“联想存储器”,其中的页表称为“快表”。

多级页表

为了能够快速查找页表页在内存中的物理块号,为这些页表页再设计一个地址索引表,即页目录表。二级页表的逻辑地址被划分为三部分: 页目录、页表页、页内偏移

二级页表结构

缺页中断指的是在进程运行过程中,发现所访问的页不在内存中时,CPU的内存管理单元发出的中断。与一般中断:CPU 检测中断时间不同,CPU 可多次处理。

缺页中断处理流程是:先查看内存是否有空闲块,若有则按该页在外存中的地址将该页找出并装入内存,在页表中填上它占用的块号且修改标志位。若内存已没有空闲块,则必须先淘汰已在内存中的某一页,再将所需的页装入,对页表和内存分配表作相应的修改。淘汰某页时,要查看该页的修改位来判断该页是否修改过,若该页在执行过程中没有被修改过,那么不必重新写回到存储器中,而已修改过的页调出时必须再将该页写回到外存中。

段式存储管理

分段式存储管理是以段为单位进行内存分配,逻辑地址空间是一个二维空间,分为段号和段内偏移两部分。

段式存储的逻辑地址

分段和分页的比较

  • 段是信息的逻辑单位,由源程序的逻辑结构所决定,用户可见,段长可根据用户需要来规定,段起始地址可以从任何地址开始。在分段方式中,源程序(段号,段内偏移)经连结装配后仍保持二维结构。
  • 页是信息的物理单位,与源程序的逻辑结构无关,用户不可见,页长由系统确定,页面只能以页大小的整倍数地址开始。在分页方式中,源程序(页号,页内偏移)经连结装配后变成了一维结构。
  • 在分段式存储管理的基础上实现分页式存储管理,这就是段页式存储管理,是目前应用最多的一种存储管理方式。

段页式存储的逻辑地址

逻辑地址分 3 个部分:段号、段内页号和页内位移,其形式为:对于用户来说,虚拟地址应该由段号 s 和段内位移 d’ 组成,用户看不到如何分页。而是由操作系统自动把 d’解释成两部分:段内页号 p 和页内位移 d,也就是说,d’ = p × 块长+ d。

虚拟存储技术

将作业不执行的部分暂时存放在外存,待到进程需要时,再将其从外存调入内存。将外存作为内存的补充,从逻辑上扩充内存。

虚拟存储技术的实现基础是内存的分页或分段管理,采用的是进程的分页或分段在内存与外存之间对换。

请求分页虚拟存储管理

硬件支持

  1. 请求分页的页表机制
  2. 缺页中断机构
  3. 地址转换机构

页面分配策略与页面调度算法

1.页面分配策略

通常分为固定分配和可变分配两种不同的方式

  1. 固定分配方式:
    • 进程平均分配法
    • 进程按比例分配法
    • 进程优先权分配法
  2. 可变分配方式

2.页面调入策略

  1. 请求页(demand paging)调入
  2. 预先页(prepaging)调入

3.页面置换策略

  1. 全局置换
  2. 局部置换

页面置换算法

先进先出、最佳页面、最近最久未使用、时钟置换算法

  1. 先进先出(FIFO)页面置换算法

    总是选择最先进入内存的页面或驻留时间最长的页面先淘汰FIFO 页面置换算法

  2. 最佳(OPT)页面置换算法

    在选择页面置换时应该考虑该页面将来使用的情况,将来最长时间不用的页面被淘汰。在进程采用固定页面分配的情况下,最佳页面置换算法具有最低的缺页率OPT 页面置换算法

  3. LRU 页面置换算法

    系统须维护一个页面淘汰队列,该队列中存放当前在内存中的页号,每当访问一页时就调整一次,使队尾总指向最近访问的页,而队列头部就是最近最少用的页,发生缺页中断时总淘汰队列头所指示的页;而执行一次页面访问后,需要从队列中把该页调整到队列尾LRU 页面置换算法

  4. 时钟(clock)置换算法

设备管理

设备管理概述

设备管理目标:

  • 提高使用效率
  • 提供便捷的界面

设备管理功能:

  • 设备的分配与回收
  • 缓冲区管理
  • 设备控制和中断处理
  • 实现虚拟设备

设备控制方法

  1. 程序循环查询方式

  2. 中断驱动方式

  3. 直接内存访问方式(DMA)

    • 数据传输的基本单位是数据块
    • 所传送的数据是从设备直接送入内存,或者直接读出内存的
    • 在传输时CPU参与更少,仅在传送一个或多个数据块的开始和结束时,才需CPU干预,整块数据的传送是在控制器的控制下完成的
  4. 通道方式

    I/O 通道方式是 DMA 方式的发展,它可进一步减少 CPU 的干预,即把对一个数据块的读(或写)为单位的干预,减少为对一组数据块的读(或写)及有关的控制和管理为单位的干预

缓冲技术

缓冲技术主要有以下作用:

  • 改善中央处理器与外围设备之间速度不匹配的矛盾,提高 CPU 和 I/O 设备的并行性
  • 减少 I/O 对 CPU 的中断次数和放宽对 CPU 中断响应时间的要求
  • 协调逻辑记录大小与物理记录大小不一致的问题

输入输出软件

设备独立性,也称为设备无关性,是指在用户程序中不直接使用物理设备名(或设备的物理地址),而只能使用逻辑设备名。

  • 使得设备分配更加灵活,提高了设备的利用率
  • 可以实现 I/O 重定向

设备分配与回收

设备信息描述

  1. 系统设备表 SDT
  2. 设备控制表 DCT
  3. 控制器控制表 COCT
  4. 通道控制表 CHCT

设备分配策略

  1. 独占方式
  2. 共享方式
  3. 虚拟方式

SPOOLing 技术(假脱机)

当系统中引入了多道程序技术后,可以利用其中的一道程序,来模拟脱机输入输出时的外围控制机功能,把低速 I/O 设备上的数据传送到高速磁盘上;或者把数据从磁盘传送到低速输出设备上。这样,便可在主机的直接控制下,实现脱机输入输出功能。

  • 提高了 I/O 的速度,缓和了高速的处理器与低速输入输出设备之间的矛盾
  • 将独占设备改造为共享设备,提高了设备的利用率
  • 实现了虚拟设备功能,将物理的单个设备变换为多个对应的逻辑设备

设备分配算法

  • 先来先服务算法
  • 优先级高者优先算法

文件系统

概述

文件分类方法有很多,下面是常用的几种文件分类方法:

  • 按照文件的逻辑结构的不同,可以把文件分成流式文件和纪录式文件
  • 按照用途将文件分为系统文件、库文件和用户文件
  • 按照性质可以把文件分为普通文件、目录文件和特殊文件按照性质可以把文件分为普通文件、目录文件和特殊文件

文件的组织

逻辑结构组织

1.流式文件

流式文件指文件内的数据不组成记录,只是依次的一串信息集合,如字节流或字符流。流式文件本身可以没有结构。

2.纪录式文件

记录式文件是一种有结构的文件,它是指文件中的数据由若干条定长或不定长的记录构成,每条记录又由若干数据项构成。记录是记录式文件进行存取的基本单位。

按照组织方式的不同,记录式文件可进一步分为:

  • 顺序文件
  • 索引文件
  • 索引顺序文件

物理结构组织

  1. 连续文件

  2. 链接文件

  3. 索引文件3 级索引

  4. 直接文件

文件的存取方法

  1. 顺序存取
  2. 直接存取
  3. 按键存取

文件目录

文件目录的基本概念

文件控制块——用于描述和控制文件的数据结构,称之为文件控制块(File Control Block,FCB)

  • 为了加快文件的查找速度,通常把 FCB 集中起来进行管理,文件控制块的有序集合称为文件目录
  • 文件目录也是以文件的形式保存在外存上的,这就形成了目录文件

目录文件的组织

常用的组织方法主要有三种:

  • FCB 线性表
  • 索引节点
  • 哈希表组织

目录的结构

目录结构都是采用层次结构,主要分为:

  • 单级目录
  • 二级目录
  • 多级层次目录结构(最常用)
  • 图状目录结构
文章作者: gzwang
文章链接: https://gzwangu.github.io/2020/06/05/操作系统/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 Gzwang's Blog