精华内容
下载资源
问答
  • 王道操作系统笔记1

    2021-04-04 11:45:55
    王道操作系统笔记整理 1计算机系统1.1 操作系统概述1.2 操作系统的四个特征1.3 操作系统的发展和分类1.4 操作系统的运行机制1.5 中断和异常1.6 系统调用1.7 操作系统的内核 1.1 操作系统概述 1 操作系统概念与定义 ...

    1.1 操作系统概述

    1 操作系统概念与定义
    操作系统指控制和管理整个计算机系统的硬件和软件资源,并合理组织调度计算机工作和资源的分配,以提供给用户和其他软件方便的接口和环境,是计算机系统中最基本的系统软件

    1. 是系统资源的管理者
    2. 向上层提供方便易用的服务
    3. 最接近硬件的一层软件
      在这里插入图片描述
      2 向上层提供方便易用的服务
      封装思想:操作系统把一些丑陋的硬件功能封装成简单易用的服务,使用户能更方便地使用计算机,用户无需关心底层硬件的原理,只需要对操作系统发出命令即可
    • 联机命令接口(交互式命令接口)
      *用户说一句,系统跟着做一句
    • 脱机命令接口(批处理命令接口)
      *用户说一堆,系统跟着做一堆
    • 程序接口:在程序中进行==系统调用(广义指令)==来使用程序接口(普通用户不能直接使用程序接口,只能通过程序代码间接使用)
      在这里插入图片描述

    在这里插入图片描述
    命令接口和程序接口统称为用户接口

    3 最接近硬件的层次
    实现对硬件机器的拓展:在裸机上安装的操作系统可以提供资源管理功能和方便用户的服务功能,将裸机改造成功能更强,使用更方便的机器
    将CPU、内存、磁盘、显示器、键盘等硬件合理的组织起来,让各种硬件能够相互协调配合,实现更多更复杂的功能
    *通常把覆盖了软件的机器称为扩充机器,又称为虚拟机


    1.2 操作系统的四个特征

    在这里插入图片描述
    *没有并发和共享,就谈不上虚拟和异步,故并发和共享是操作系统的两个最基本的特征

    1 并发:两个或多个事件在同一时间间隔内发生(宏观上同时发生,微观上交替发生)
    *并行:两个或多个事件在同一时刻同时发生

    操作系统的并发性指计算机系统中“同时”运行着多个程序,操作系统就是伴随着“多道程序技术”而出现的,故操作系统和程序并发是一起诞生的
    单核CPU同一时刻只能执行一个程序,各个程序只能并发执行
    多核CPU同一时刻可以同时执行多个程序,多个程序可以并行执行

    2 共享(资源共享):指系统中的资源可供内存中多个并发执行的进程共同使用

    • 互斥共享方式:系统中某些资源虽然可以提供给多个进程使用,但一个时间段内只允许一个进程访问该资源
    • 同时共享方式:系统中某些资源允许一个时间段内多个进程“同时”对它们进行访问(宏观上同时访问,微观上交替访问)

    注:并发和共享的关系
    互为存在条件
    *失去并发性则系统中只有一个程序正在运行,则共享性失去存在的意义;失去共享性无法实现同时发送文件,也就无法并发

    3 虚拟:指把一个物理上的实体变为若干个逻辑上的对应物(物理实体是实际存在的,逻辑上对应物是用户感受到的)
    一个程序需要放入内存并给它分配CPU才能执行
    虚拟技术:

    • 空分复用技术(如虚拟存储器技术)---->运行程序的内存远大于电脑内存
    • 时分复用技术(如虚拟处理器)---->单核CPU同时运行多个程序
      *若失去并发性则一个时间段内系统只需运行一道程序,则失去了实现虚拟性的意义

    4 异步:在多道程序环境下允许多个程序并发执行(并发运行的程序会争抢着使用系统资源),但资源有限,进程的执行不是一贯到底的,而是走走停停,以不可预知的速度向前推进
    *若失去并发性则一个时间段内系统只需运行一道程序,则系统只能串行地运行各个程序,那么每个程序的执行会一贯到底


    1.3 操作系统的发展和分类

    1 手工操作阶段
    缺点:用户独占全机、人机速度矛盾导致资源利用率低

    2 批处理阶段
    (1)单道批处理系统
    引入脱机输入、输出技术(用外围机+磁带完成),并由监督程序负责控制作业的输入和输出
    *通过外围机把程序提前存到磁带里
    *监督程序是操作系统的雏形

    优点:缓解了一定程度的人机速度矛盾,资源利用率有所提升
    缺点:内存中仅能有一道程序运行;CPU有大量时间在空闲等待I/O完成

    (2)多道批处理系统
    每次往内存中读入多道程序,在计算机空闲时(计算)读入第二个程序
    *操作系统正式诞生,用户支持多道程序并发运行

    优点:多道程序并发进行,共享计算机资源,资源利用率大幅提升,系统吞吐量增大
    缺点:用户响应时间长,没有人机交互功能(用户提交作业后只能等待计算机处理完成,中间不能控制自己的作业执行)

    3 分时操作系统
    计算机以时间片为单位轮流为各个用户、作业服务,各个用户可通过终端与计算机进行交互

    优点:用户请求可以被即时响应,解决人机交互问题;允许多个用户同时使用一台计算机,并且用户对计算机的操作相互独立
    缺点:不能优先处理一些紧急任务,对各个用户、作业是公平的,循环地为每个用户、作业服务一个时间片

    4 实时操作系统
    在实时操作系统的控制下,计算机系统接收到外部信号后及时进行处理,并且要在严格的时限内处理完事件

    • 硬实时系统:必须在绝对严格的规定时间内完成处理
    • 软实时系统:能接受偶尔违反时间规定
      特点:及时性可靠性
      优点:优先处理一些紧急任务,某些紧急任务不许时间片排队

    5 其他操作系统
    在这里插入图片描述


    1.4 操作系统的运行机制

    预备知识:“指令”指的是处理器CPU能识别的、执行的最基本命令
    1 内核程序和应用程序
    应用程序:跑在操作系统之上,由普通程序员写的程序
    内核程序:编写实现操作系统的程序,很多内核程序组成“操作系统内核”
    内核是操作系统最核心最重要的部分,最接近硬件的部分
    *操作系统的功能未必都在内核中

    2 特权指令和非特权指令
    应用程序只能使用“非特权指令”
    只允许操作系统内核(即管理者)执行“特权指令”
    *在CPU设计和生产的时候就划分了特权指令和非特权指令,因此CPU执行一条指令前就能判断出其类型

    3 内核态(核心态=管态)和用户态(目态)
    处于内核态时说明此时正在运行内核程序,可以执行特权指令
    处于用户态时说明此时正在运行应用程序,只能执行非特权指令
    区分状态:CPU中有一个程序状态寄存器(PSW),以二进制位0/1标识状态
    切换状态:在这里插入图片描述
    内核态---->用户态:执行一条特权指令,修改PSW的标志位为“用户态”,操作系统将主动让出CPU使用权
    内核态---->用户态:由==“中断”==引发,硬件自动完成变态过程,触发中断信号意味着系统将强行夺回CPU使用权
    *需要操作系统介入的地方都会触发中断信号


    1.5 中断和异常

    1 中断作用
    “中断”是让操作系统内核夺回CPU使用权,使COU从用户态变为内核态的唯一途径
    如果没有“中断”机制,一旦应用程序上CPU运行,CPU就会一直运行这个应用程序

    2 终端类型

    • 内中断(异常、例外):与当前执行的指令有关,中断信号来源于CPU内部
      • 试图在用户态下执行特权指令
      • 执行除法指令时发现除数为0
      • 执行陷入指令请求操作系统内核的服务(系统调用是通过陷入指令完成的)
    • 外中断(中断):与当前执行的指令无关,中断信号来源于CPU外部
      *每一条指令执行结束时,CPU都会例行检查是否有外中断信号
      • 时钟中断 (由外部时钟部件发来的中断信号):并发运行
      • I/O中断(由输入/输出设备发来的中断信号)
        在这里插入图片描述

    3 中断机制的基本定理
    不同中断信号需要用不同的中断处理程序来处理
    CPU检测到中断信号后会根据中断信号类型查询中断向量表,找到相应的中断处理程序在内存中的存放位置
    在这里插入图片描述
    中断处理程序是内核程序,需要运行在“内核态”


    1.6 系统调用

    1 系统调用概念与作用
    系统调用:是操作系统提供给应用程序(程序员/编程人员)使用的接口,可理解为一种可供应用程序调用的特殊函数
    应用程序可以通过系统调用来请求获得操作系统内核的服务

    2 系统调用与库函数区别
    在这里插入图片描述
    *库函数可能不涉及系统调用,如“取绝对值”的函数

    2 为什么系统调用是必须的?
    由操作系统内核对共享资源进行统一的管理,并向上“系统调用”,用户进程想使用共享资源,只能通过系统调用向操作系统内核发出请求,内核会对各个请求进行协调处理

    3 什么功能要用到系统调用?
    在这里插入图片描述
    系统中各种共享资源都由操作系统内核统一掌管,凡是与共享资源有关的操作(如存储分配、I/O操作,文件管理等),会直接影响到其他进程的操作,都必须通过系统调用方式向操作系统内核提出服务请求,由操作系统内核代为完成
    —>保证系统的稳定性和安全性,防止用户进行非法操作

    4 系统调用过程
    用户态:传参指令–向寄存器传入参数–>陷入指令(trap指令/访管指令)–内中断信号,转入系统调用的入口程序–>内核态:执行系统调用入口程序–根据寄存器参数判断用户需要的系统调用服务–>执行系统调用处理程序---->用户态:回到原本应用程序执行剩下语句
    在这里插入图片描述
    *陷入指令在用户态执行
    *发出系统调用请求是在用户态,而对系统调用的相应处理在核心态下进行


    1.7 操作系统的内核

    1 内核
    在这里插入图片描述
    *原语:即使收到内中断信号仍然继续执行
    在这里插入图片描述
    2 体系结构

    • 大内核
      在这里插入图片描述
    • 微内核
      在这里插入图片描述
      *变态的过程是有成本的,要消耗不少时间,频繁地变态会降低系统性能

    3 不同体系结构的优缺点
    在这里插入图片描述

    展开全文
  • 王道操作系统笔记2

    2021-04-06 11:24:27
    王道操作系统笔记整理 2进程管理2.1.1进程的概念、组成和特征2.1.2 进程的状态与转换2.1.3 进程控制2.1.4 进程通信2.1.5 线程的概念2.1.6 多线程模型 2.1.1进程的概念、组成和特征 1 进程的概念 区分程序和进程 ...

    2.1.1进程的概念、组成和特征

    1 进程的概念
    区分程序和进程

    • 程序:是静态的,是存放在磁盘里的可执行文件,是一系列的指令集合
    • 进程:是动态,是程序的依次执行过程(同一个程序多次执行会对应多个进程)

    2 进程的组成
    (1)PID
    当进程被创建时,操作系统会为该进程分配一个唯一的、不重复的PID—唯一标志

    *操作系统需要对各个并发运行的进程进行管理,但凡管理时所需要的信息都会被保存在一个数据结构PCB(进程控制块)中
    在这里插入图片描述
    (2)程序段、数据段
    一个进程实体(进程映像)由PCB、程序段、数据段组成
    进程是进程实体的运行过程,是系统进行资源分配和调度的一个独立单位

    1. 程序运行过程
      在这里插入图片描述
      *进程是动态的,进程实体(进程映像)是静态的---->进程实体反映进程在某一时刻的状态

    2. 进程的组成
      在这里插入图片描述

    3 进程的特征
    在这里插入图片描述

    2.1.2 进程的状态与转换

    1 进程的状态
    在这里插入图片描述
    **操作系统根据进程PCB中变量state表示进程当前状态

    2 进程状态转换
    在这里插入图片描述
    *进程不能由阻塞态直接转换为运行态,也不能由就绪态直接转换为阻塞态

    3 进程的组织
    操作系统会将各进程的PCB组织起来以方便对同一个状态下的各个进程进行统一管理

    1. 链接方式
      根据进程状态将PCB分为多个队列,操作系统持有指向各个队列的指针
      在这里插入图片描述
    2. 索引方式
      根据进程状态建立索引表,操作系统持有指向各个索引表的指针
      在这里插入图片描述

    2.1.3 进程控制

    1 进程控制概述
    进程控制是对系统中的所有进程实施有效管理,具有创建新进程,撤销原有进程,实现进程状态转换等功能

    2 实现方法
    用原语实现
    *原语是一种特殊的程序,它的执行具有原子性,程序运行不可中断
    *注:若进程控制过程无法“一气呵成”,可能导致操作系统中的某些关键数据结构信息不统一,影响操作系统进行别的管理工作

    • 如何实现原语的“原子性”?
      利用“关中断指令”和“开中断指令”这两个特权指令实现(不允许普通用户程序使用,只能让内核程序使用)
      在这里插入图片描述

    3 进程控制相关原语

    • 进程的创建
      在这里插入图片描述

    • 进程的终止
      在这里插入图片描述

    • 进程的阻塞和唤醒
      在这里插入图片描述*因何事阻塞,就应由何事唤醒---->阻塞源于和唤醒原语成对使用

    • 进程的切换
      在这里插入图片描述

    无论哪个进程控制原语,都要做的三类事情是

    1. 更新CPB中的信息
    2. 将CPB插入合适的队列
    3. 分配 / 回收资源

    4 环境信息
    *CPU中会设置很多“寄存器”用于存放程序运行过程所需的某些数据
    在这里插入图片描述
    另一个进程在运行过程中会使用各个寄存器,可能覆盖原先进程保留的结果
    解决方法:在进程切换时先在CPB中保存这个进程的运行环境(保存一些必要的寄存器信息)

    2.1.4 进程通信

    1 进程通信概述
    进程通信指进程之间的信息交换
    各进程拥有的内存地址空间相互独立,一个进程不能直接访问另一个进程的地址空间

    2 进程通信方式

    1. 共享存储
      在这里插入图片描述
    • 基于数据结构的共享----低级通信方式
      共享速度慢,限制多(如数据类型,数据大小等)
    • 基于存储区的共享----高级通信方式
      在内存中划出一块共享存储区,数据形式、存放位置都由进程控制而非操作系统,共享速度快
    1. 管道通信
      在这里插入图片描述
      管道:用于连接读写进程的一个共享文件(pipe文件),其实是在内存中开辟大小固定的缓冲区
    • 管道只采用半双工通信(单向传输)
    • 各进程互斥地访问管道
    • 数据以字符流形式写入管道
      管道写满时,写进程的write()系统调用将被阻塞;管道读空时,读进程的read()系统调用将被阻塞
    • 没写满不允许读,没读空不允许写
    • 数据一旦被读出就从管道中被抛弃---->读进程最多只有一个
    1. 消息传递
      进程间数据交换以格式化信息为单位
      进程通过操作系统提供的**“发送消息/接收消息”**两个原语进行数据交换
      在这里插入图片描述
    • 直接通信方式
      消息直接挂到接收进程的消息缓冲队列上
    • 间接通信方式(信箱通信方式)
      消息要先发送到中间实体(信箱)中

    2.1.5 线程的概念

    1 线程的引入
    *有些进程需要同时做很多事,而传统的进程只能串行地执行一系列程序,为此引入线程增加并发度
    在这里插入图片描述
    线程----“轻量级进程”
    线程是一个基本的CPU执行单元,是程序执行流的最小单位,进程只作为除CPU之外的系统资源的分配单元
    *进程之间可以并发,进程内的各线程之间也可以并发

    2 变化
    在这里插入图片描述
    3 线程的属性
    在这里插入图片描述

    2.1.6 多线程模型

    1 线程的实现方式

    1. 用户级线程
      在这里插入图片描述
      *程序员自己写了一个线程库对线程进行管理,在处理机运行时操作系统只看得到进程
    • 用户级线程由应用程序通过线程库实现,所有的线程管理工作都由应用程序负责(包括线程切换)
    • 线程切换由应用程序完成(用户态),无需CPU变态,无需操作系统干预
    • 在用户看来有多个线程,在操作系统内核看来不能意识到用户级线程的存在
      在这里插入图片描述
    1. 内核级线程
      由操作系统支持的线程
      在这里插入图片描述
    • 内核级线程的管理工作由操作系统内核完成
    • 线程调度、切换等工作由内核负责,内核级线程切换必须在核心态下才能完成
    • 操作系统会为每个内核级线程建立相应的TCB对线程进行管理
      在这里插入图片描述

    2 多线程模型(根据用户级线程和内核级线程的映射关系划分)

    1. 一对一:每个用户进程有与用户级线程同数量的内核级线程
      在这里插入图片描述
      在这里插入图片描述
    2. 多对一:多个用户级线程映射到一个内核级线程,一个进程只被分配一个内核级线程
      操作系统只看得见内核级线程,只有内核级线程才是处理机分配的单位
      在这里插入图片描述
      在这里插入图片描述
    3. 多对多:n用户及线程映射到m个内核级线程(n>=m),每个用户进程对应m个内核级线程
      在这里插入图片描述在这里插入图片描述
      内核级线程才是处理机分配的单位
      *内核级线程中可以运行任意一个有映射关系的用户级线程代码,只有两个内核级线程中正在运行的用户级线程都阻塞时,该进程才会阻塞

    2.2.1 调度的概念、层次

    1 基本概念
    调度:当有一堆任务要处理,但由于资源有限无法同时处理,需要确定某种规则来决定处理这些任务的顺序

    2 三个层次

    • 高级调度(作业调度):按一定的原则从外存的作业后备队列中挑选一个作业调入内存,并创建进程
      *每个作业只调入一次(创建PCB)、调出一次(撤销PCB)
    • 低级调度(进程调度/处理机调度):按照某种策略从就绪队列中选取一个进程,将处理机分配给它
      *是操作系统最基本的调度,在一般的操作系统中必须配置
      *进程调度频率很高,一般几十毫秒一次
    • 中级调度:按照某种策略决定将哪个处于挂起状态的进程重新调入内存
      *内存不够时可将某些进程的数据调出外存,等内存空闲时或进程需要运行时再重新调入内存
      *暂时调到外存等待的进程状态为挂起状态,被挂起的进程PCB会被组织成挂起队列
      **一个进程可能被多次调入、调出内存,中级调度发生的频率比高级调度更高

    在这里插入图片描述

    3 七状态模型
    在这里插入图片描述
    挂起和阻塞的区别
    两种状态都暂时不能获得CPU服务,但挂起态将进程映像调到外存去了,而阻塞态下进程映像还在内存中

    2.2.2 进程调度的时机、切换与过程、方式

    1 进程调度的时机

    1. 需要进行进程调度与切换的情况
      • 主动放弃处理机
        进程正常终止
        进程过程中发生异常和终止
        进程主动请求阻塞(如等待I/O)
      • 被动放弃处理机
        分给进程的时间片用完
        有更紧急的事需要处理(如I/O中断)
        有更高优先级的进程进入就绪队列
    2. 不能进行进程调度与切换的情况
      • 在处理中断的过程中(过程复杂,与硬件相关)
      • 进程在操作系统内核程序临界区中
      • 在原子操作过程中(原语)

    进程在操作系统内核程序临界区中不能进行调度与切换 √
    进程处于临界区中不能进行调度与切换 ×

    • 临界资源:一个时间段内只允许一个进程使用的资源,各进程互斥的访问临界资源
    • 临界区:访问临界资源的那段代码
    • 内核程序临界区:一般用于访问某种内核数据结构的

    内核程序临界区
    在这里插入图片描述
    普通临界区在这里插入图片描述
    在这里插入图片描述

    2 进程调度的方式

    • 非剥夺调度方式(非抢占方式)
      只允许进程主动放弃处理机。在运行过程中即便有更紧迫的任务到达,当前进程依然会继续使用处理机,直到该进程终止或主动要求进入阻塞态。
      *实现简单,系统开销小,但无法及时处理紧急任务---->适合于早期的批处理系统
    • 剥夺调度方式(抢占方式)
      当一个进程正在处理机上执行时,如果有一个更重要或更紧迫的进程需要使用处理机,则立即暂停正在执行的进程,将处理机分配给更重要紧迫的那个进程
      *可以优先处理更紧急的进程,也可实现让各进程按时间片轮流执行的功能(通过时钟中断)---->适合于分时操作系统、实时操作系统

    3 进程的切换与过程

    • 狭义的进程调度:从就绪队列中选中一个要运行的进程
      *这个进程可以是刚刚被暂停执行的进程,也可能是另一个进程,后一种情况就需要进程切换
      *进程切换是指一个进程让出处理机,由另一个进程占用处理机的过程
    • 广义的进程调度:选择一个进程和进程切换两个步骤。

    进程切换的过程主要完成了:

    1. 对原来运行进程各种数据的保存
    2. 对新的进程各种数据的恢复
      如程序计数器、程序状态字、各种数据寄存器等处理机现场信息,这些信息一般保存在进程控制块

    *进程切换是有代价的,因此如果过于频繁的进行进程调度、切换,必然会使整个系统的效率降低,使系统大部分时间都花在了进程切换上,而真正用于执行进程的时间减少

    2.2.3 调度算法的评价指标

    • CPU利用率:CPU忙碌的时间占总时间的比例
      利用率 = 忙碌的时间 / 总时间
      *多道程序并发执行的情况,可用“甘特图”辅助计算
    • 系统吞吐量:单位时间内完成的作业的数量
      系统吞吐量 = 总共完成了多少道作业 / 总共花了多少时间
    • 周转时间:从作业被提交给系统开始,到作业完成为止的这段时间间隔
      包括:
      1.作业在外存后备队列上等待作业调度(高级调度)的时间
      2.进程在就绪队列上等待进程调度(低级调度)的时间
      3.进程在CPU上执行的时间
      4.进程等待I/O操作完成的时间
      *后三项在一个作业的整个处理过程中,可能发生多次
      周转时间 = 作业完成时间 - 作业提交时间
      平均周转时间 = 各作业周转时间 / 作业数
      带权周转时间 = 作业周转时间 / 作业实际运行时间(带权周转时间>=1,越小越好)
    • 等待时间:指进程 or 作业处于等待处理机状态时间之和
      • 进程:等待时间指进程建立后等待被服务的时间之和(在等待I/O完成的期间其实进程也是在被服务的,不计入等待时间)
      • 作业:等待时间指建立进程后的等待时间和作业在外存后备队列中等待时间
        *一个作业总共需要被CPU服务多久,被l/O设备服务多久一般是确定不变的,调度算法其实只会影响作业/进程的等待时间
    • 响应时间:从用户提交请求到首次产生相应所用的时间

    2.2.4 FCFS、SJF、HRRN调度算法

    1 先来先服务(FCFS)
    在这里插入图片描述
    例:
    在这里插入图片描述
    *如果进程非纯计算型进程,有计算又有I/O操作的进程,其等待时间就是
    周转时间-运行时间-I/O操作时间

    2 短作业优先
    *用于进程调度应该称为短进程优先调度算法
    在这里插入图片描述

    • 非抢占式
      在这里插入图片描述

    • 抢占式(最短剩余时间优先算法)
      *需要调度的情况:

      • 有新进程加入就绪队列时
        如果新到达的进程剩余时间比当前运行的进程剩余时间更短,则有新进程抢占处理机
      • 进程完成时
        在这里插入图片描述

      注意:

    1. 如果题目中未特别说明,所提到的“短作业/进程优先算法”默认是非抢占式的
    2. 很多书上都会说“SJF 调度算法的平均等待时间、平均周转时间最少”
      严格来说,这个表述是错误的,不严谨的。之前的例子表明,最短剩余时间优先算法得到的平均等待时间、平均周转时间还要更少
      严格说法:
      • 在所有进程同时可运行时,采用SJF调度算法的平均等待时间、平均周转时间最少;
      • 在所有进程都几乎同时到达时,采用SJF调度算法的平均等待时间、平均周转时间最少;
      • 抢占式的短作业/进程优先调度算法(最短剩余时间优先, SRNT算法〉的平均等待时间、平均周转时间最少
    3. 虽然严格来说,SJF的平均等待时间、平均周转时间并不一定最少,但相比于其他算法(如FCFS) ,SJF依然可以获得较少的平均等待时间、平均周转时间
    4. 如果选择题中遇到“SJF算法的平均等待时间、平均周转时间最少”的选项,那最好判断其他选项是否有很明显的错误,如果没有更合适的选项,那就选择该选项

    3 高响应比优先(HRRN)
    在这里插入图片描述
    非抢占式的调度算法,仅当前运行的进程主动放弃CPU时才需进行调度,调度时计算所有就绪进程的响应比,选取最高的进程上处理机
    在这里插入图片描述

    *这几种算法只关心公平性、整体性能指标,不关心“响应时间”,也不区分任务的紧急程度,适合于早期的批处理系统。对用户而言交互性糟糕

    2.2.5 调度算法:时间片轮转、优先级、多级反馈队列

    1 时间片轮转RR
    **常用于分时操作系统,更注重“响应时间”
    在这里插入图片描述
    在这里插入图片描述

    • 时间片太大:使得每个进程都可以在一个时间片内就完成,则时间片轮转调度算法退化为先来先服务调度算法,并且会增大进程响应时间
    • 时间片太小:进程调度、切换是有时间代价的(保存、恢复运行环境),会导致进程切换过于频繁,系统会花大量的时间来处理进程切换,从而导致实际用于进程执行的时间比例减少。

    2 优先级调度算法
    在这里插入图片描述

    • 非抢占式
      在这里插入图片描述
    • 抢占式:每次调度时选择当前已到达且优先级最高的进程
      在这里插入图片描述

    *优先数和优先级的对应关系由题目所交给条件决定

    注意:

    1. 就绪队列未必只有一个,可以按照不同优先级来组织,也可以把优先级高的进程排在更靠近队头的位置
    2. 根据优先级是否可以动态改变,可将优先级分为:
      • 静态优先级:创建进程时确定,之后一直不变
      • 动态优先级:创建进程时有一个初始值,之后会根据情况动态地调整优先级
    3. 如何设置各类进程的优先级
      • 系统进程优先级高于用户进程
      • 前台进程优先级高于后台进程
      • 操作系统更偏好I/O型进程(或称I/O繁忙型进程)
        *与I/O型进程相对的是计算型进程(或称CPu繁忙型进程)
    4. 动态优先级调整时机
      如果某进程在就绪队列中等待了很长时间,则可以适当提升其优先级;如果某进程占用处理机运行了很长时间,则可适当降低其优先级
      如果发现一个进程频繁地进行I/O操作,则可适当提升其优先级

    3 多级反馈队列调度算法---->对其他调度算法的折中权衡
    在这里插入图片描述
    *有源源不断的短进程时,优先级低的进程可能长期得不到服务---->会导致饥饿

    在这里插入图片描述

    *交互式操作系统(包括分时操作系统、实时操作系统等)更注重系统的响应时间、公平性、平衡性等指标,这几种算法能较好地满足交互式系统的需求,适合用于交互式系统


    2.3.1 进程同步和进程互斥

    1 进程同步(直接制约关系)
    进程同步指为完成某种任务而建立的两个或多个进程,这些进程因为需要在某些位置上协调它们的工作次序而产生的制约关系,需要通过进程同步解决异步问题
    *进程间的直接制约关系源于它们之间的相互合作

    2 进程互斥(间接制约关系)
    临界资源:一个时间段内只允许一个进程使用的资源
    对临界资源的访问,必须互斥地进行
    *许多物理设备(比如摄像头、打印机)、许多变量、数据、内存缓冲区等都属于临界资源

    进程互斥指当一个进程访问某临界资源时,另一个想要访问该临界资源的进程必须等待,当前访问临界资源的进程访问结束并释放该资源之后另一个进程才能去访问临界资源

    • 逻辑上分为四部分代码
      在这里插入图片描述

      1. 进入区:负责检查是否可进入临界区
        若可进入,则应设置正在访问临界资源的标志(上锁)以阻止其他进程同时进入临界区
      2. 临界区:访问临界资源的代码
      3. 退出区:负责解除正在访问临界资源的标志(解锁)
      4. 剩余区:做其他处理

      *进入区和退出区是负责实现互斥的代码段

    • 原则(保证系统整体性能)

      1. 空闲让进:临界区空闲时可以允许一个请求进入临界区的进程立即进入临界区
      2. 忙则等待:当已有进程进入临界区时,其他试图进入临界区的进程必须等待
      3. 有限等待:对请求访问的进程,应保证能在有限时间内进入临界区(保证不会饥饿)
      4. 让权等待:当进程不能进入临界区时应立即释放处理机,防止进程忙等待
        *忙等待指进程无法向下推进但却一直占用处理机,处理机一直处于忙碌状态

    2.3.2 进程互斥的软件实现方法

    1 单标志法
    两个进程在访问完临界区后会把使用临界区的权限转交给另一个进程,即每个进程进入临界区的权限只能被另一个进程赋予
    在这里插入图片描述
    主要问题:违背“空闲让进”原则
    必须轮流访问。如果允许进入临界区的进程是P0,但P0一直不访问临界区,即使临界区空闲也不允许P1访问

    2 双标志先检查法
    设置一个布尔型数组flag[],数组中各个元素用来标记各进程想进入临界区的意愿
    每个进程在进入临界区之前先检查当前有没有别的进程想进入临界区,如果没有则把自身对应的标志flag[i]设为true后开始访问临界区

    在这里插入图片描述
    主要问题:违背“忙则等待”原则
    按照1-5-2-6-3-7…顺序执行时P0和P1会同时访问临界区
    原因:进入区的检查和上锁两个处理不是一气呵成的,在“检查”后和“上锁”前这段时间内可能发生进程切换

    3 双标志后检查法
    设置一个布尔型数组flag[],数组中各个元素用来标记各进程想进入临界区的意愿
    每个进程在进入临界区之前先把自身对应的标志flag[i]设为true后,再检查当前有没有别的进程想进入临界区,如果没有则开始访问临界区
    在这里插入图片描述
    主要问题:违背“空闲让进”和“有限等待”原则
    按照1-5-2-6…顺序执行时P0和P1都无法进入临界区,此时会因个进程都长期无法访问临界资源而产生“饥饿”现象

    4 Peterson算法
    若双方抢夺临界资源,让进程尝试“谦让”
    在这里插入图片描述
    遵循空闲让进、忙则等待优先等待三个原则
    主要问题:违背“让权等待”原则
    让权等待:当一个进程无法进入临界区时应该退出而不占用CPU

    2.3.3 进程互斥的硬件实现方法

    1 中断屏蔽方法
    利用“开/关中断指令”实现(在进程开始访问临界区到结束访问为止都不允许被中断,不可发生进程切换)
    在这里插入图片描述

    • 优点:简单、高效
    • 缺点:
      - 不适用于多处理机
      开/关中断指令只对执行该指令的处理机有用
      - 只适用于操作系统内核进程,不适用于用户进程
      开/关中断指令只能运行在内核态

    2 TestAndSet指令(TS指令/TSL(TestAndSetLock)指令)
    该指令由硬件实现,执行过程不允许被中断
    在这里插入图片描述
    !以上为C语言描述的逻辑
    *old变量用于记录以前的临界区加锁状态

    若刚开始lock是false, 则TSL返回的old值为false,while 循环条件不满足,直接跳过循环,进入临界区
    若刚开始lock是true,则执行TLS后old返回的值为true,while 循环条件满足,会一直循环,直到当前访问临界区的进程在退出区进行“解锁”。

    • 优点:
      - 实现简单
      - 把“上锁”和“检查”操作用硬件的方式变成了一气呵成的原子操作
      - 适用于多处理机环境
    • 缺点:不满足“让权等待”原则
      *暂时无法进入临界区的资源会占用CPU并循环执行TSL指令

    3 Swap指令(Exchange指令/XCHG指令)
    该指令由硬件实现,执行过程不允许被中断
    在这里插入图片描述
    *逻辑上与TSL指令相同,先记录下此时临界区是否已经被上锁(记录在old变量上),再将上锁标记lock设置为true,最后检查old,如果old为false则说明之前没有别的进程,此时对临界区上锁后则可跳出循环,进入临界区。

    • 优点:
      - 实现简单
      - 适用于多处理机环境
    • 缺点:不满足“让权等待”原则

    2.3.4 信号量机制

    1 信号量机制:实现进程互斥、同步的方法

    1. 用户进程可以通过使用操作系统提供的一对原语对信号量进行操作
      *wait(S)原语和signal(S)原语(常简称为P、V操作),分别写为P(S)、V(S)
    2. 信号量是一个变量(可以是一个整数,也可以是更复杂的记录型变量),可以用一个信号量来表示系统中某种资源的数量
    3. 原语由关中断/开中断指令实现,时一种特殊的程序段,其执行只能一气呵成,不可被中断
      *软件解决方案的主要问题是由“进入区的各种操作无法一气呵成”,因此如果能把进入区、退出区的操作都用“原语”实现,使这些操作能“一气呵成”就能避免问题

    2 整型信号量
    用一个整数型变量作为信号量,表示系统中某种资源的数量
    *与普通整数变量相比仅有三种操作:初始化、P操作、V操作
    在这里插入图片描述

    • 优点:“检查”和“上锁”一气呵成,避免并发和异步导致的问题
    • 缺点:不满足“让权等待”原则

    3 记录型信号量
    用记录型数据结构表示信号量
    在这里插入图片描述
    S.value的初值表示系统中某种资源的数目

    • 一次P操作意味着进程请求一个单位的该类资源
      *资源数-1后S.value<0表示该类资源分配完毕
    • 一次V操作意味着进程释放一个单位的该类资源
      *资源数+1后S.value<=0表示依然有进程在等待该类资源

    该机制遵循了“让权等待”原则

    2.3.5 用信号量机制实现进程同步、互斥、前驱关系

    1 信号量机制实现进程互斥
    互斥问题,信号量初值为1
    在这里插入图片描述
    在这里插入图片描述
    注意:

    • 对不同临界资源需要设置不同的互斥信号量
    • P、V操作必须成对出现
      *缺少P不能保证临界资源的互斥访问,缺少V会导致资源永不被释放,等待进程永不唤醒

    2 信号量机制实现进程同步
    进程同步:让各并发进程按要求有序地推进
    同步问题,信号量初值为0
    在这里插入图片描述
    在“前操作”之后执行V(S)
    在“后操作”之前执行P(S)

    3 信号量机制实现前驱关系
    每一对前驱关系都是一个进程同步问题,本质上是多级同步问题
    在这里插入图片描述

    2.3.6 生产者-消费者问题

    1. 问题模型:系统中有一组生产者进程和一组消费者进程,生产者进程每次生产一个产品放入缓冲区,消费者进程每次从缓冲区中取出一个产品并使用
      *生产者、消费者共享一个初始为空、大小为n的缓冲区,缓冲区是临界资源,各进程必须互斥地访问
      - 缓冲区没满–>生产者生产
      - 缓冲区没空–>消费者消费

    2. 如何实现
      在这里插入图片描述

    3. 能否改变相邻P、V操作的顺序

      • P(mutex)操作在P(empty)和P(full)操作前
        在这里插入图片描述
        造成生产者等待消费者释放空闲缓冲区,而消费者又等待生产者释放临界区的情况,生产者和消费者循环等待被对方唤醒,出现==“死锁”==
        *若缓冲区中没有产品(full=O, empty=n)时 按③④①的顺序执行就会发生死锁
        !实现互斥的P操作一定要在实现同步的P操作之后
      • V(mutex)操作在V(empty)和P(full)操作后
        V操作不会导致进程阻塞,故两个V操作顺序可交换

    2.3.7 多生产者-多消费者问题

    1. 问题模型:不同类别的生产者+不同类别的消费者
      在这里插入图片描述

    2. 分析在这里插入图片描述

    3. 如何实现
      在这里插入图片描述
      在这里插入图片描述
      如果缓冲区大小为1,有可能不需要设置互斥信号量就可以实现互斥访问缓冲区的功能
      如果缓冲区大小大于1,必须专门设置一个互斥信号量mutex实现互斥访问缓冲区的功能

    4. 注意
      - 解题方法:
      1.关系分析。找出题目中描述的各个进程,分析它们之间的同步、互斥关系。
      2.整理思路。根据各进程的操作流程确定P、V操作的大致顺序。
      3.设置信号量。设置需要的信号量,并根据题目条件确定信号量初值。 (互斥信号量初值一般为1,同步信号量的初始值要看对应资源的初始值是多少)
      - 分析关系的方法
      从==“事件”==的角度来考虑,把“进程行为的前后关系”抽象为对“事件的前后关系”

    2.3.8 多生产者-多消费者问题

    1. 问题模型:可以生产多个产品的单生产者+不同类别的消费者
      在这里插入图片描述
    2. 分析
      在这里插入图片描述
      在这里插入图片描述
    3. 如何实现
      在这里插入图片描述
    4. 注意
      - 轮流与随机
      轮流:用一个整型变量i实现“轮流的在桌上放上组合一、二、三”
      随机:用一个Random变量(随机数)实现
      - 若一个生产者要生产多种产品(或者说会引发多种前驱事件),那么各个V操作应该放在各自对应的“事件”发生之后的位置。

    2.3.9 读者-写者问题

    1. 问题描述
      在这里插入图片描述
      *与消费者进程不同:读者进程读数据后不会将数据清空,不会改变数据(多个读者可同时访问共享数据)
      *写进程和读进程或两个写进程同时共享数据,可能导致读出数据不一致、数据错误覆盖等问题

    2. 分析
      在这里插入图片描述

    3. 如何实现

    • 读进程优先---->写进程可能会饿死
      在这里插入图片描述
    • 写进程优先(读写公平:先来先服务)
      在这里插入图片描述
    1. 注意
      - 计数器count:用于记录当前正在访问共享文件的读进程数,用count值判断当前进入进程是否是第一个(上锁)/最有一个(解锁)读进程(实现读进程不互斥问题)
      - 对count变量的检查和复制实现“一气呵成”:使用互斥信号量
      - 写进程饥饿问题:使用一个信号量w实现

    2.3.10 哲学家进餐问题

    1. 问题描述:需要同时持有多个共享资源,进程间只存在互斥关系
      在这里插入图片描述
    2. 分析
      在这里插入图片描述
    3. 如何实现
      死锁现象:
      在这里插入图片描述
      防止死锁:
      ① 可以对哲学家进程施加一些限制条件
      *如最多允许四个哲学家同时进餐。这样可以保证至少有一个哲学家是可以拿到左右两只筷子的---->设置初始值为4的同步信号量
      ② 要求奇数号哲学家先拿左边的筷子,然后再拿右边的筷子,而偶数号哲学家刚好相反。
      *保证如果相邻的两个奇偶号哲学家都想吃饭,那么只会有其中一个可以拿起第一只筷 子,另一个会直接阻塞---->判断序号后根据序号做不同处理
      ③ 仅当一个哲学家左右两支筷子都可用时才允许他抓起筷子,各哲学家拿筷子这件事必须互斥的执行
      在这里插入图片描述
      *保证即使一个哲学家在拿筷子拿到一半时被阻塞,也不会有别的哲学家会继续尝试拿筷子。当前正在吃饭的哲学家放下筷子后,被阻塞的哲学家就可以获得等待的筷子。

    2.3.11 管程

    1 作用:一种高级同步机制,用于解决信号量机制变成麻烦、易出错的问题

    2 组成和特征
    组成:

    1. 局部于管程的共享数据结构说明
    2. 对该数据结构进行操作的一组过程(用于访问共享数据的“入口”–函数)
    3. 对局部于管程的共享数据设置初始值的语句
    4. 管程有一个名字

    基本特征:

    1. 局部于管程的数据只能被局部于管程的过程所访问
    2. 一个进程只有通过调用管程内的过程才能进入管程访问共享数据(只有通过特定“入口”才能访问共享数据)
    3. 每次仅允许一个进程在管程内执行某个内部过程(每次只开放其中一个“入口”,只能让一个进程或线程进入)

    3 拓展

    • 管程解决生产者-消费者问题
      在这里插入图片描述
      *由编译器负责实现个进程互斥地进入管程中的过程
      *管程中可设置条件变量和等待/唤醒操作以解决同步问题:让一个进程或线程在条件变量上等待,也可以通过唤醒操作将等待在条件变量上的进程或线程唤醒

    • Java中类似于管程的机制
      用关键字Synchronized描述一个函数,该函数在同一时间段内只能被一个线程调用


    2.4.1 死锁的概念

    1 定义
    死锁:在并发环境下,各进程因竞争资源而造成的一种互相等待对方手里的资源,导致各进程都阻塞,都无法向前推进的现象
    *发生死锁后若无外力干涉,这些进程都将无法向前推进

    2 死锁、饥饿、死循环的区别
    共同点:进程无法顺利向前推进的现象

    现象 不同点
    死锁 各进程互相循环等待对方手里的资源,导致各进程都阻塞(至少有两个或两个以上的进程同时发生死锁,且发生死锁的进程一定处于阻塞态
    饥饿 由于长期得不到想要的资源,某进程无法向前推进的现象(可能只有一个进程发生饥饿,发生饥饿的进程可能是阻塞态[长期得不到I/O设备]也可能是就绪态[长期得不到处理机]
    死循环 某进程执行过程中一直跳不出某个循环的现象(死循环进程可以上处理机运行,可处于运行态)
    死锁和饥饿问题是由于操作系统分配资源的策略不合理导致的,而死循环是由代码逻辑的错误导致的。死锁和饥饿是管理者(操作系统)的问题,死循环是被管理者的问题

    3 死锁产生的必要条件

    • 互斥条件:只有对必须互斥使用的资源的争抢才会导致死锁
    • 不剥夺条件:进程所获得的资源在未使用完之前不能由其他进程强行夺走,只能主动释放。
    • 请求和保持条件:进程已经保持了至少一个资源,但又提出了新的资源请求,而该资源又被其他进程占有,此时请求进程被阻塞但又对自己已有的资源保持不放。
    • 循环等待条件:存在一种进程资源的循环等待链,链中的每一个进程已获得的资源同时被下一个进程所请求

    同类资源大于1时即使发生循环等待时未必死锁(循环等待是死锁的必要不充分条件)
    每类资源只有一个时发生循环等待必死锁(循环等待是死锁的充分必要条件)

    4 什么时候会发生死锁
    !分配资源不合理

    1. 对不可剥夺的系统资源的竞争
    2. 进程推进顺序非法,请求和释放资源的顺序不当
    3. 信号量的使用不当

    5 处理策略

    1. 预防死锁:破坏死锁产生的四个必要条件中的一个或几个
    2. 避免死锁:用某种方法防止系统进入不安全状态
    3. 死锁的检测和解除:操作系统负责检测出死锁的发生后采取某种措施解除死锁

    2.4.2 预防死锁

    破坏死锁产生的四个必要条件中的一个或几个

    1. 破坏互斥条件
      将互斥使用的资源改造为允许共享使用:用SPOOLing技术把独占设备在裸机上改造成共享设备
      缺点:不是所有资源都可被改造成可共享使用的资源,很多时候无法破坏互斥条件

    2. 破坏不剥夺条件
      方案一:当某个进程请求新的资源得不到满足时,它必须立即主动释放保持的所有资源,待以后需要时再重新申请
      方案二:当某个进程需要的资源被其他进程所占有的时候,可以由操作系统协助将想要的资源强行剥夺
      缺点:
      - 实现起来比较复杂
      - 释放已获得的资源可能造成前一阶段工作的失效,只适用于易保存和恢复状态的资源(如CPU)
      - 反复地申请和释放资源会增加系统开销,降低系统吞吐量
      - 若采用方案一时只要暂时得不到某个资源,之前获得的那些资源就都需要放弃,以后再重新申请。如果一直发生这样的情况就会导致进程饥饿。

    3. 破坏请求和保持条件
      采用静态分配方法使进程在运行前一次申请完它所需要的全部资源,在它的资源未满足前不让它投入运行,一旦投入运行后这些资源就一直归它所有,该进程就不会再请求别的任何资源
      缺点:
      - 有些资源可能只需要用很短的时间,如果进程的整个运行期间都一直保持着所有资源,会造成严重的资源浪费
      - 可能导致某些进程饥饿

    4. 破坏循环等待条件
      采用顺序资源分配法,首先给系统中的资源编号,规定每个进程必须按编号递增的顺序请求资源,同类资源(即编号相同的资源)一次申请完
      一个进程只有已占有小编号的资源时才有资格申请更大编号的资源,已持有大编号资源的进程不可能逆向地回来申请小编号的资源,从而就不会产生循环等待的现象
      *在任何一个时刻总有一个进程拥有的资源编号是最大的,那这个进程申请之后的资源必然畅通无阻,不可能出现所有进程都阻塞的死锁现象
      缺点:
      - 增加新的设备可能需要重新分配所有的编号
      - 进程实际使用资源的顺序可能和编号递增顺序不一致,导致资源浪费;
      - 必须按规定次序申请资源使用户编程麻烦

    2.4.3 避免死锁

    1 安全序列
    安全序列:指如果系统按照这种序列分配资源,则每个进程都能顺利完成
    *安全序列可能有多个,只要能找出一个安全序列系统就是安全状态
    *如果分配了资源之后系统中找不出任何一个安全序列,系统就进入了不安全状态,意味着之后可能所有进程都无法顺利的执行下去。如果有进程提前归还了一些资源,那系统也有可能重新回到安全状态
    如果系统处于安全状态,就一定不会发生死锁。如果系统进入不安全状态,就可能发生死锁(处于安全状态是不发生死锁的充分非必要条件)

    2 银行家算法
    核心思想:在资源分配前预先判断这次分配是否会导致系统进入不安全状态,若会进入不安全状态则暂时不答应请求,使该进程先阻塞等待

    实现:(假设系统中有n个进程,m种资源)
    nm矩阵Max:表示所有进程对各种资源的最大需求数,Max[i, j]=K表示进程Pi最多需要K个资源Rj
    n
    m的分配矩阵Allocation:表示对所有进程的资源分配情况
    Need=Max - Allocation矩阵:表示各进程最多还需要多少各类资源
    长度为m的一维数组Available:表示当前系统中还有多少可用资源
    长度为m的一维数组Request:表示某进程Pi向系统申请的各种资源量
    在这里插入图片描述
    银行家算法步骤: .
    ①检查此次申请是否超过了之前声明的最大需求数
    ②检查此时系统剩余的可用资源是否还能满足这次请求
    ③试探着分配,更改各数据结构
    ④用安全性算法检查此次分配是否会导致系统进入不安全状态

    安全性算法步骤:
    ①检查当前的剩余可用资源是否能满足某个进程的最大需求,如果可以,就把该进程加入安全序列,并把该进程持有的资源全部回收。
    ②不断重复上述过程,看最终是否能让所有进程都加入安全序列。

    2.4.3 死锁的检测和解除

    1 死锁的检测

    1. 必要条件
      ①用某种数据结构(资源分配图)来保存资源的请求和分配信息
      ②提供一种算法,利用上述信息来检测系统是否已进入死锁状态
    2. 资源分配图
      在这里插入图片描述
    3. 死锁检测
      检测过程:
      如果系统中剩余的可用资源数足够满足进程的需求,那么这个进程暂时是不会阻塞,可以顺利地执行下去。
      如果这个进程执行结束了把资源归还系统,就可能使某些正在等待资源的进程被激活,并顺利地执行下去。这些被激活的进程执行完了之后又会归还一些资源,这样可能又会激活另外一些阻塞的进程。
      按上述过程分析,最终能消除所有边,就称这个图是可完全简化的。此时一定没有发生死锁 (相当于能找到一个安全序列)
      如果最终不能消除所有边,那么此时就是发生了死锁,还连着边的进程是处于死锁状态的进程
      检测死锁的算法:
      1. 在资源分配图中,找出既不阻塞又不是孤点的进程Pi,消去它所有的请求边和分配变,使之称为孤立的结点
      2. 进程Pi所释放的资源可以唤醒某些因等待这些资源而阻塞的进程,原来的阻塞进程可能变为非阻塞进程

    2 死锁的解除
    方法

    1. 资源剥夺法:挂起(暂时放到外存上)某些死锁进程,并抢占它的资源,将这些资源分配给其他的死锁进程
      *应防止被挂起的进程长时间得不到资源而饥饿
    2. 撒销进程法(或称终止进程法):强制撤销部分、甚至全部死锁进程,并剥夺这些进程的资源
      *优点是实现简单,但所付出的代价可能会很大,有些进程可能已经运行了很长时间已经接近结束,一旦被终止后还得从头再来
    3. 进程回退法:让一个或多个死锁进程回退到足以避免死锁的地步
      *要求系统要记录进程的历史信息,设置还原点

    !并不是系统中所有的进程都是死锁状态,用死锁检测算法化简资源分配图后,还连着边的那些进程才是死锁进程

    如何决定对哪些进程动手

    1. 进程优先级
    2. 已执行多长时间
    3. 还要多久能完成
    4. 进程已经使用了多少资源:对使用资源多的先动手
    5. 进程是交互式的还是批处理式的:对批处理(计算型)的先动手
    展开全文
  • 王道操作系统笔记3

    2021-04-18 16:32:09
    王道操作系统笔记整理 内存管理33.1.1 内存的基础知识3.1.2 内存管理的概述3.1.3 覆盖与交换3.1.3 连续分配管理方式 3.1.1 内存的基础知识 1 内存定义与作用 内存:可存放数据,执行前需要先放内存中才能被CPU处理 ...

    3.1.1 内存的基础知识

    1 内存定义与作用
    内存:可存放数据,执行前需要先放内存中才能被CPU处理
    内存地址(存储单元):
    “按字节编址”:每个存储单元大小为1字节(8个二进制位)
    “按字编址”:字长为16位的计算机,每个存储单元大小为1个字(16个二进制位)---->由计算机字长决定

    常用单位:
    210=1K(千),220=1M(兆、百万),230=1G(十亿、千兆)

    2 指令的工作原理
    指令的工作基于地址
    在这里插入图片描述
    代码会翻译成CPU能识别的指令。这些指令会告诉CPU应该去内存的哪个地址读/写数据及这个数据应该做什么样的处理

    3 如何将指令中的逻辑地址转换为物理地址

    • 程序经过编译、链接后生成的指令中指明的是逻辑地址(相对地址:相对于进程的起始地址而言的地址)在这里插入图片描述
    • 装入的三种方式
      1. 绝对装入
        在编译时如果知道程序将放到内存中的哪个位置,编译程序将产生绝对地址的目标代码,在装入程序按照装入模块中的地址,将程序和数据装入内存。
        在这里插入图片描述
        特点:必须知道装入模块的起始地址;只适用于单道程序环境,灵活性差
      2. 静态重定位(可重定位装入)
        根据内存的当前情况,将装入模块装入到内存的适当位置。装入时对地址进行“重定位”,将逻辑地址变换为物理地址(地址变换是在装入时一次完成的)
        在这里插入图片描述
        特点:在一个作业装入内存时必须分配其要求的全部内存空间,没有足够内存就不能装入该作业;作业一旦进入内存后在运行期间不能再移动,也不能申请内存空间;适用于多道批处理操作系统
      3. 动态重定位(动态运行时装入)
        装入程序把装入模块装入内存后,并不会立即把逻辑地址转换为物理地址,而是把地址转换推迟到程序真正要执行时才进行,装入内存后所有的地址依然是逻辑地址。这种方式需要一个重定位寄存器的支持。
        在这里插入图片描述
        特点:允许程序在内存中发生移动;可将程序分配到不连续的存储区中;在程序运行前只需装入它的部分代码即可投入运行,在程序运行期间再根据需要动态申请分配内存;便于程序段的共享,可以向用户提供一个比存储空间大得多的地址空间。

    4 从写程序到程序运行
    在这里插入图片描述
    编译:由编译程序将用户源代码编译成若千个目标模块(把高级语言翻译为机器语言)
    链接:由链接程序将编译后形成的一组目标模块,以及所需库函数链接在一起,形成一个完整的装入模块
    装入(装载) :由装入程序将装入模块装入内存运行

    5 链接的三种方式
    链接的三种方式:

    1. 静态链接:在程序运行之前先将各目标模块及它们所需的库函数连接成一个完整的可执行文件(装入模块) ,之后不再拆开
    2. 装入时动态链接:将各目标模块装入内存时,边装入边链接的链接方式
    3. 运行时动态链接:在程序执行中需要该目标模块时才对它进行链接
      优点:便于修改和更新,便于实现对目标模块的共享

    3.1.2 内存管理的概述

    1 内存管理
    操作系统是系统资源的管理者

    1. 操作系统负责内存空间的分配与回收
    2. 操作系统需要提供某种技术从逻辑上对内存空间进行扩充
    3. 操作系统需要提供地址转换功能,负责程序的逻辑地址与物理地址的转换
    4. 操作系统雷要提供内存保护功能。保证各进程在各自存储空间内运行,互不干扰

    2 内存保护的方法

    1. 在CPU中设置一对上、下限寄存器,存放进程的上、下限地址。
      进程的指令要访问某个地址时,CPU检查是否越界
      内存保护可采取两种方法:
    2. 采用重定位寄存器(又称基址寄存器)和界地址寄存器(又称限长寄存器)进行越界检查
      重定位寄存器中存放的是进程的起始物理地址,界地址寄存器中存放的是进程的最大逻辑地址
      在这里插入图片描述

    3.1.3 覆盖与交换

    内存空间的补充

    1. 覆盖技术(解决程序大小超过物理内存总和的问题)
      思想:将程序分为多个段(多个模块),常用的段常驻内存,不常用的段在需要时调入内存
      内存中分为一个“固定区”和若干个“覆盖区”:
      - 需要常驻内存的段放在“固定区”中,调入后就不再调出(除非运行结束)
      - 不常用的段放在“覆盖区”,需要用到时调入内存,用不到时调出内存
      在这里插入图片描述
      缺点:必须由程序员声明覆盖结构,操作系统完成自动覆盖---->对用户不透明,增加用户变成负担(只用于早期操作系统)

    2. 交换技术
      思想:(进程在内存与磁盘间动态调度) 内存空间紧张时系统将内存中某些进程暂时换出外存,把外存中某些已具备运行条件的进程换入内存
      *暂时换出外存等待的进程状态为挂起状态

      1. 在外存的什么位置保存被换出的进程?
        具有对换功能的操作系统中,通常把磁盘空间分为文件区对换区两部分
        文件区:存放文件(追求存储空间的利用率,文件区空间的管理采用离散分配方式)
        对换区:存放被换出的进程数据(空间只占磁盘空间的小部分,追求换入换出速度,采用连续分配方式)
        对换区的I/0速度比文件区的更快
      2. 什么时候交换?
        在许多进程运行且内存吃紧时进行,而系统负荷降低就暂停时
      3. 应该换出哪些进程?
        优先换出阻塞进程
        优先换出优先级低的进程(防止优先级低的进程在被调入内存后很快又被换出,有的系统会考虑进程在内存的驻留时间)
    3. 虚拟存储技术

    3.1.3 连续分配管理方式

    内部碎片:分配给某进程的内存区域中,如果有些部分没有用上
    外部碎片:是指内存中的某些空闲分区由于太小而难以利用

    1. 单一连续分配
      内存被分为系统区用户区
      系统区:通常位于内存的低地址部分,用于存放操作系统相关数据
      用户区:用于存放用户进程相关数据
      内存中只能有一道用户程序,用户程序独占整个用户区空间
      - 优点:实现简单;无外部碎片;可以采用覆盖技术扩充内存;不一定需要采取内存保护
      - 缺点:只能用于单用户、单任务的操作系统中;有内部碎片;存储器利用率极低。

    2. 固定分区分配
      为了能在内存中装入多道程序且这些程序之间又不会相互干扰,将整个用户空间划分为若干个固定大小的分区,在每个分区中只装入一道作业,形成了最早的、最简单的一种可运行多道程序的内存管理方式
      - 分区大小相等
      *缺乏灵活性,但适合用于用一台计算机控制多个相同对象的场合
      n个炼钢炉控制程序)
      - 分区大小不等
      *增加了灵活性,可以满足不同大小的进程需求(根据常在系统中运行的作业大小情况进行划分)
      操作系统需建立 分区说明表(一个数据结构)实现各个分区的分配与回收,包括分区大小、起始地址、分配状态---->用户程序要装入内存时由操作系统内核程序根据程序大小检索该表,寻找分区并分配
      在这里插入图片描述
      - 优点:实现简单,无外部碎片
      - 缺点:当用户程序太大时可能所有的分区都不能满足需求,此时需采用覆盖技术来解决,降低性能; 会产生内部碎片,内存利用率低

    3. 动态分区分配(可变分区分配)
      不会预先划分内存分区,而是在进程装入内存时根据进程的大小动态地建立分区,并使分区的大小正好适合进程的需要
      *系统分区的大小和数目是可变的

      1. 系统用什么数据结构记录内存使用情况
        在这里插入图片描述
      2. 当很多个空闲分区都能满足需求时应选择哪个分区分配
        依据动态分区分配算法
      3. 如何进行分区的分配和回收操作
        - 分配:修改空闲分区表 / 空闲分区链
        - 回收:相邻的空闲分区合并为一个,修改相应表项;无相邻空闲分区则增加表项(表项顺序由动态分配算法决定)
        特点:动态分区分配没有内部碎片,但是有外部碎片。
        *如果内存中空闲空间的总和本来可以满足某进程的要求,但由于进程需要的是一整块连续的内存空间,因此这些“碎片”不能满足进程的需求---->可以通过紧凑(拼凑)技术解决

    3.1.5 动态分配算法

    1 首次适应算法

    • 思想:每次都从低地址开始查找,找到第一个能满足大小的空闲分区
    • 实现:空闲分区以地址递增的次序排列
      每次分配内存时顺序查找空闲分区链(或空闲分区表),找到大小能满足要求的第一个空闲分区
    • 优点:算法开销小,回收分区后一般不需要对空闲分区队列重新排序

    2 最佳适应算法

    • 思想:尽可能多地留下大片的空闲区,即优先使用更小的空闲区---->保证当“大进程”到来时有连续的大片空间
      *动态分区分配是一种连续分配方式,为各进程分配的空间必须是连续的一整片区域
    • 实现:空闲分区按容量递增次序链接
      每次分配内存时顺序查找空闲分区链(或空闲分区表),找到大小能满足要求的第一个空闲分区
    • 优点:会有更多的大分区被保留下来,更能满足大进程需求
    • 缺点:会留下越来越多很小的、难以利用的内存块,产生很多的外部碎片

    3 最坏(最大)适应算法

    • 思想:在每次分配时优先使用最大的连续空闲区
      *分配后剩余的空闲区不会太小,更方便使用
    • 实现:空闲分区按容量递减次序链接
      每次分配内存时顺序查找空闲分区链(或空闲分区表),找到大小能满足要求的第一个空闲分区
    • 优点:可以减少难以利用的小碎片
    • 缺点:导致较大的连续空闲区被迅速用完,之后有“大进程”到达就没有内存分区可用

    4 邻近适应算法

    • 思想:每次都从上次查找结束的位置开始检索
      *首次适应算法每次都从链头开始查找的,可能会导致低地址部分出现很多小的空闲分区,而每次分配查找时都要经过这些分区,增加了查找的开销
    • 实现:空闲分区以地址递增的顺序排列(可排成一个循环链表)
      每次分配内存时从上次查找结束的位置开始查找空闲分区链(或空闲分区表),找到大小能满足要求的第一个空闲分区。
      -优点:当低地址部分有更小的分区可以满足需求时会更有可能用到低地址部分的小分区,更有可能把高地址部分的大分区保留下来
    • 缺点:低地址、高地址部分的空闲分区都有相同的概率被使用,导致了高地址部分的大分区更可能被使用而划分为小分区,最后导致无大分区可用

    四种算法中,首次适应算法效果反而更好

    3.1.6 基本分页存储管理的概念

    非连续分配管理方式
    1 分页存储

    • 页框:将内存空间分为一个个大小相等的分区,每个分区就是一个“页框”(页框=页帧=内存块=物理块=物理页面)
      每个页框有一个编号,即“页框号”(页框号=页帧号=内存块号=物理块号=物理页号),页框号从0开始。
    • 页 / 页面:将进程的逻辑地址空间也分为与页框大小相等的一个个部分,每个部分称为一个“页”或“页面”
      每个页面也有一个编号,即“页号”,页号也是从 0开始。
      在这里插入图片描述

    操作系统以页框为单位为各个进程分配内存空间,进程的每个页面分别放入一个页框中。
    进程的页面与内存的页框有一一对应的关系
    *各个页面不必连续存放,可以放到不相邻的各个页框中

    2 问题
    1) 每个页表项占多少字节?
    页表:为知道进程的每个页面中存放的位置,操作系统为每个进程建立一张页表
    *页表通常存在PCB中
    1.一个进程对应一张页表
    2.进程的每个页面对应一个页表项
    3.每个页表项由“页号”和“块号”组成(不记录内存块起始地址---->J号内存块内起始地址=J × 内存块大小)
    4.页表记录进程页面和实际存放的内存块之间的映射关系
    在这里插入图片描述
    页表项连续存放,故页号可以是隐含的,不占存储空间
    假设页表中的各页表项从内存地址为x的地方开始连续存放…如何找到页号为i的页表项?
    i号页表项的存放地址=X+3*i

    2)如何实现地址的转换
    虽然进程的各个页面是离散存放的,但页面内部是连续存放的
    在这里插入图片描述

    • 确定一个逻辑地址对应的页号、页内偏移量
      页号=逻辑地址/页面长度(取除法的整数部分)
      页内偏移量=逻辑地址%页面长度(取除法的余数部分)
      页面在内存中的起始地址+页内偏移量=实际的物理地址

    • 页面大小刚好是2的整数幂,则计算机硬件可以很快速的把逻辑地址拆分成(页号,页内偏移量)
      *如果每个页面大小为2B,用二进制数表示逻辑地址,末尾K位即为页内偏移量,其余部分就是页号

    3 逻辑地址结构
    在这里插入图片描述

    • 如果有K位表示“页内偏移量”,则说明该系统中一个页面的大小是2k个内存单元
    • 如果有M位表示“页号”,则说明在该系统中,一个进程最多允许有2M个页面

    3.1.7 基本地址变换机构

    1 基本地址变换机构:借助进程的页表将逻辑地址转换为物理地址
    页表寄存器(PTR):存放页表在内存中的起始地址F和页表长度M
    *进程未执行时页表的始址和页表长度放在进程控制块(PCB)中,当进程被调度时操作系统内核会把它们放到页表寄存器中

    2 逻辑地址到物理地址的变换过程
    在这里插入图片描述

    在这里插入图片描述
    页面大小是2的整数幂

    3 注意

    1. 页面大小L为1K字节----等价于----逻辑地址结构中页内偏移量占10位
    2. 在分页存储管理〈页式管理)的系统中,只要确定了每个页面的大小逻辑地址结构就确定了---->页式管理中地址是一维的
      *只要给出一个逻辑地址,系统就可以自动地算出页号、页内偏移量两个部分
    3. 为了方便页表的查询,常常会让一个页表项占更多的字节,使得每个页面恰好可以装得下整数个页表项

    3.1.8 具有快表的地址变换机构

    1 快表(联想寄存器 TLB)
    是一种访问速度比内存快很多的高速缓存,用来存放最近访问的页表项的副本,加速地址变换的速度
    *与此对应,内存中的页表常称为慢表
    访问速度:在这里插入图片描述

    2 访问执行过程
    在这里插入图片描述
    地址变换过程

    1. CPU给出逻辑地址,由某个硬件算得页号、页内偏移量,将页号与快表中的所有页号进行比较
    2. 如果找到匹配的页号,说明要访问的页表项在快表中有副本,则直接从中取出该页对应的内存块号,再将内存块号与页内偏移量拼接形成物理地址,最后访问该物理地址对应的内存单元。
      *若快表命中,则访问某个逻辑地址仅需一次访存即可
    3. 如果没有找到匹配的页号,则需要访问内存中的页表,找到对应页表项,得到页面存放的内存块号,再将内存块号与页内偏移量拼接形成物理地址,最后访问该物理地址对应的内存单元。
      *若快表未命中,则访问某个逻辑地址需要两次访存

    在找到页表项后应同时将其存入快表,以便后面可能的再次访问
    若快表已满,则按照一定的算法对旧的页表项进行替换

    **注意:有的系统支持快表和慢表同时查找
    在这里插入图片描述

    3 局部性原理

    • 时间局部性:
      如果执行了程序中的某条指令,那么不久后这条指令很有可能再次执行
      如果某个数据被访问过,不久之后该数据很可能再次被访问
      *因为程序中存在大量的循环
    • 空间局部性:
      一旦程序访问了某个存储单元,在不久之后,其附近的存储单元也很有可能被访问
      *很多数据在内存中都是连续存放的

    由于局部性原理,可能连续很多次查到的都是同一个页表项,一般来说快表的命中率可以达到90%以上

    3.1.9 两级页表

    1 单级页表存在问题

    1. 页表项需连续存放才能通过地址公式找到页表项,当页表很大时需要占用多个连续页框
    2. 进程在一段时间内只需访问某几个页面就可以正常运行,无需让整个页表常驻内存

    2 连续存放问题
    思想:将页表进行分组,使每个内存块刚好可以放入一个分组,另外要为离散分配的页表再建立一张页表(称页目录表 / 外层页表 / 顶层页表)
    在这里插入图片描述
    在这里插入图片描述
    两级页表访问内存块方法:

    1. 按照地址结构将逻辑地址拆分成三部分(一级页号+二级页号+页内偏移量)
    2. 从PCB中读出页目录表始址,再根据一级页号查页目录表找到下一级页表在内存中的存放位置
    3. 根据二级页号查表,找到最终想访问的内存块号
    4. 结合页内偏移量得到物理地址

    3 无需常驻内存问题
    思想:在需要访问页面时才把页面调入内存,在页表项中增加一个标志位用于表示该页面是否已经调入内存
    在这里插入图片描述
    实现:虚拟存储技术

    4 注意

    1. 采用多级页表机制,各级页表的大小不能超过一个页面
      在这里插入图片描述
    2. 两级页表的访存次数分析(无快表机构时)
      第一次访存:访问内存中的页目录表
      第二次访存:访问内存中的二级页表
      第三次访存:访问目标内存单元
      N级页表访存次数为N+1次

    3.1.10 基本分段存储管理

    1 分段

    • 进程的地址空间:按照程序自身的逻辑关系划分为若干个段,每个段都有一个段名每段从0开始编址
    • 内存分配规则:以段为单位进行分配,每个段在内存中占据连续空间,但各段之间可以不相邻

    *在低级语言中,程序员使用段名来编程,用户变成更方便,程序可读性更高
    与分页最大区别:离散分配时所分配的地址空间的基本单位不同
    在这里插入图片描述

    • 逻辑地址结构
      段号(段名)+段内地址(段内偏移量)
      在这里插入图片描述

    2 段表
    由于程序分多个段,各段离散地装入内存,为了保证程序能正常运行,就必须能从物理内存中找到各个逻辑段的存放位置---->为每个进程建立一张段映射表(段表)
    在这里插入图片描述

    1. 每个段对应一个段表项,记录该段在内存中的起始位置(又称“基址”)和段的长度。
    2. 各个段表项的长度是相同的
      *段号可以是隐含的,不占存储空间

    3 访问内存单元过程
    在这里插入图片描述
    分段:需检查段内地址是否超过段长(因为每一段的段长各不相同)

    4 分段和分页管理的对比

    • 页是信息的物理单位。分页主要为了实现离散分配,提高内存利用率。分页仅仅是系统管理上的需要,完全是系统行为,对用户不可见
      段是信息的逻辑单位。分段主要为了更好地满足用户需求。一个段通常包含着一组属于一个逻辑模块的信息。分段对用户是可见的,用户编程时需要显式地给出段名。
    • 页的大小固定且由系统决定。段的长度不固定决定于用户编写的程序。
    • 分页的用户进程地址空间是一维的,程序员只需给出一个记忆符即可表示一个地址。
      分段的用户进程地址空间是二维的,程序员在标识一个地址时既要给出段名,也要给出段内地址。
      -分段比分页更容易实现信息的共享和保护。
      • 分段共享实现:
        在这里插入图片描述
        *不能被修改的代码称为纯代码或可重入代码(不属于临界资源),这样的代码是可以共享的。可修改的代码是不能共享的
    • 访存次数(单级页表)
      分页:两次,第一次访存一一查内存中的页表,第二次访存- --访问目标内存单元
      分段:两次,第一次访存–查内存中的段表,第二次访存- – -访问目标内存单元
      *分段系统中也可以引入快表机构,将近期访问过的段表项放到快表中

    3.1.11 段页式管理方式

    1 分页、分段的优缺点分析
    在这里插入图片描述

    2 段页式管理 = 分段 + 分页
    在这里插入图片描述

    3 逻辑地址结构
    段号+页号+页内地址(段内偏移量)
    在这里插入图片描述
    “分段”对用户是可见的,程序员编程时需要显式地给出段号、段内地址
    将各段“分页”对用户是不可见的,系统会根据段内地址自动划分页号和页内偏移量
    *段页式管理的地址结构是一维的

    4 段表、页表
    在这里插入图片描述
    一个进程只会对应一个段表,但可能对应多个页表

    5 访问内存单元过程
    在这里插入图片描述
    需要三次访存
    可引入快表机构,用段号和页号作为查询快表的关键字,若快表命中则仅需一次访存


    3.2.1 虚拟内存的基本概念

    1 传统存储方式的缺点和特征
    在这里插入图片描述
    特征

    • 一次性:作业必须一次性仝部装入内存后才能开始运行
      ①作业很大时,不能全部装入内存,导致大作业无法运行
      ②当大量作业要求运行时,由于内存无法容纳所有作业,因此只有少量作业能运行,导致多道程序并发度下降。
    • 驻留性:一旦作业被装入内存就会一直驻留在内存中,直至作业运行结束
      导致了内存中会驻留大量的、暂时用不到的数据,浪费内存资源

    2 虚拟内存的定义和特征
    虚拟存储技术的提出基于局部性原理
    在程序装入时将程序中很快会用到的部分装入内存,暂时用不到的部分留在外存,就可以让程序开始执行。
    在程序执行过程中,当所访问的信息不在内存时由操作系统负责将所需信息从外存调入内存,然后继续执行程序。
    若内存空间不够,由操作系统负责将内存中暂时用不到的信息换出到外存
    *在操作系统的管理下,在用户看来似乎有一个比实际内存大得多的内存

    • 多次性:无需在作业运行时一次性全部装入内存,允许被分成多次调入内存
    • 对换性:在作业运行时无需一直常驻内存,允许在作业运行过程中将作业换
      入、换出。
    • 虚拟性:逻辑上扩充了内存的容量,使用户看到的内存容量远大于实际的容量

    3 虚拟内存技术的实现
    虚拟内存的实现基于离散分配的内存管理方式
    在这里插入图片描述
    与传统非连续分配存储管理的区别

    • 在程序执行过程中,当所访问的信息不在
      内存时由操作系统负责将所需信息从外
      存调入内存
      *操作系统提供请求调页(或请求调段)功能
    • 若内存空间不够,由操作系统负贵将内存
      中暂时用不到的信息换出到外存
      *操作系统提供页面置换(或段置换)功能

    3.2.2 请求分页管理方式

    1 请求分页存储管理和基本分页存储管理区别
    在程序执行过程中,当所访问的信息不在内存时由操作系统负责将所需信息从外存调入内存,然后继续执行程序;若内存空间不够,由操作系统负责将内存中暂时用不到的信息换出到外存

    新增功能:

    1. 操作系统要提供请求调页功能,将缺失页面从外存调入内存
    2. 操作系统要提供页面置换的功能,将暂时用不到的页面换出外存

    2 页表机制
    请求页表:
    在这里插入图片描述
    3 缺页中断机构
    在请求分页系统中,每当要访问的页面不在内存时便产生一个缺页中断,然后由操作系统的缺页中断处理程序处理中断

    • 缺页的进程阻塞,放入阻塞队列,调页完成后再将其唤醒,放回就绪队列
    • 内存中有空闲块则为进程分配一个空闲块,将所缺页面装入该块并修改页表中相应的页表项
      内存中没有空闲块,则由页面置换算法选择一个页面淘汰,若该页面在内存期间被修改过则要将其写回外存,未修改过的页面不用写回外存

    缺页中断(属内中断):当前执行的指令想要访问的目标页面未调入内存而产生的
    *一条指令在执行期间可能访问多个内存,产生多次缺页中断

    4 地址变换机构
    新增步骤:

    1. 请求调页(查到页表项时进行判断)
    2. 页面置换(需要调入页面,但没有空闲内存块时进行)
    3. 需要修改请求页表中新增的表项

    在这里插入图片描述
    *快表中有的页面一定是在内存中的!若某个页面被换出外存则快表中的相应表项也要删除,否则可能访问错误的页面

    5 注意
    补充细节:

    1. 只有“写指令”才需要修改“修改位”
      *一般只需修改快表中的数据,只有要将快表项删除时才需要写回内存中的慢表---->减少访存次数
    2. 缺页中断处理需要保留CPU现场。
    3. 需要用某种“页面置换算法”来决定一个换出页面
    4. 换入/换出页面都需要启动慢速的I/O操作,如果换入/换出太频繁会有很大的开销
    5. 页面调入内存后需要修改慢表,同时需要将表项复制到快表中

    3.2.3 页面置换算法

    1 最佳置换算法(OPT)
    每次选择淘汰的页面将是以后永不使用或者在最长时间内不再被访问的页面(向后寻找),保证最低的缺页率
    在这里插入图片描述
    条件:必须知道访问页面的顺序
    *实际上只有在进程执行的过程中才能知道接下来会访问到哪个页面,操作系统无法提前预判页面访问序列

    最佳置换算法是无法实现

    2 先进先出置换算法(FIFO)
    每次选择淘汰的页面是最早进入内存的页面
    实现方法:把调入内存的页面根据调入的先后顺序排成一个队列,需要换出页面时选择队头页面即可
    *队列的最大长度取决于系统为进程分配了多少个内存块
    在这里插入图片描述
    Belady异常:当为进程分配的物理块数增大时缺页次数不减反增
    (仅先进先出置换算法会实现)

    优缺点:实现简单,但是该算法与进程实际运行时的规律不适应,先进入的页面也有可能最经常被访问,算法性能差

    3 最近最久未使用置换算法(LRU)
    每次淘汰的页面是最近最久未使用的页面(向前寻找)
    实现方法:赋予每个页面对应的页表项中,用访问字段记录该页面自上次被访问以来所经历的时间t,当需要淘汰一个页面时选择现有页面中t值最大的
    在这里插入图片描述
    优缺点:实现需要专门的硬件支持,虽然算法性能好,但是实现困难,开销大

    4 时钟置换算法(CLOCK)/ 最近未用算法(NRU)
    实现方法:为每个页面设置一个访问位,再将内存中的页面都通过链接指针链接成一个循环队列。
    当某页被访问时其访问位置为1,当需要淘汰一个页面时只需检查页的访问位(如果是0就选择该页换出;如果是1则将它置为O,暂不换出,继续检查下一个页面)
    若第一轮扫描中所有页面都是1,则将这些页面的访问位依次置为0后,再进行第二轮扫描〈第二轮扫描中一定会有访问位为0的页面)
    简单的CLOCK 算法选择一个淘汰页面最多会经过两轮扫描
    在这里插入图片描述
    优缺点:实现简单,算法开销小,但未考虑页面是否被修改过

    5 改进型的时钟置换算法
    操作系统还应考虑页面有没有被修改过,在其他条件都相同时应优先淘汰没有修改过的页面,避免I/O操作。

    用(访问位,修改位)的形式表示各页面状态
    实现方法:将所有可能被置换的页面排成一个循环队列

    • 第一轮:从当前位置开始扫描到第一个(0,0)的帧用于替换----“最近没访问且没修改的页面”
      *本轮扫描不修改任何标志位
    • 第二轮:若第一轮扫描失败则重新扫描,查找第一个(0,1)的帧用于替换----“最近没访问且修改过的页面”
      *本轮将所有扫描过的帧访问位设为0
    • 第三轮:若第二轮扫描失败则重新扫描,查找第一个(0,0)的帧用于替换----“最近访问过且没没修改的页面”
      *本轮扫描不修改任何标志位
    • 第四轮:若第三轮扫描失败则重新扫描,查找第一个(0,1)的帧用于替换----“最近访问过且修改过的页面”
      *第二轮已将所有帧的访问位设为0,因此经过第三轮、第四轮扫描一定会有一个帧被选中

    改进型CLOCK置换算法选择一个淘汰页面最多会进行四轮扫描

    优缺点:算法开销小,性能也不错

    3.2.4 页面分配策略、抖动、工作集

    1 页面分配、置换策略

    1. 驻留集:请求分页存储管理中给进程分配的物理块的集合。
      *在采用了虚拟存储技术的系统中驻留集大小一般小于进程的总大小
      若驻留集太小会导致缺页频繁,系统要花大量的时间来处理缺页,实际用于进程推进的时间很少;
      驻留集太大会导致多道程序并发度下降,资源利用率降低
      • 固定分配:操作系统为每个进程分配一组固定数目的物理块,在进程运行期间不再改变---->驻留集大小不变
      • 可变分配:先为每个进程分配一定数目的物理块,在进程运行期间可根据情况做适当的增加或减少---->驻留集大小可变
      • 局部置换:发生缺页时只能选进程自己的物理块进行置换
      • 全局置换:可以将操作系统保留的空闲物理块分配给缺页进程,也可以将别的进程持有的物理块置换
        到外存再分配给缺页进程
        在这里插入图片描述
        *“固定分配、全局置换”分配置换策略不存在

    2 分配置换策略

    1. 固定分配局部置换:
      系统为每个进程分配一定数量的物理块,在整个运行期间都不改变
      若进程在运行中发生缺页,则只能从该进程在内存中的页面中选出一页换出,然后再调入需要的页面
      *很难在刚开始就确定应为每个进程分配多少个物理块才算合理(根据进程大小、优先级、或程序员给出的参数来确定为一个进程分配的内存块数),灵活性差
    2. 可变分配全局置换:
      刚开始会为每个进程分配一定数量的物理块;
      操作系统会保持一个空闲物理块队列,当某进程发生缺页时从空闲物理块中取出一块分配给该进程,若已无空闲物理块则可选择一个未锁定的页面换出外存,再将该物理块分配给缺页的进程
      *只要某进程发生缺页都将获得新的物理块,仅当空闲物理块用完时系统才选择一一个未锁定的页面调出。被选择调出的页可能是系统中任何一个进程中的页,被选中的进程拥有的物理块会减少,缺页率会增加
    3. 可变分配局部置换:
      刚开始会为每个进程分配定数量的物理块
      当某进程发生缺页时只允许从该进程自己的物理块中选出一个进行换出外存,且会根据发生缺页的频率来动态地增加或减少进程的物理块

    3 何时调入页面

    1. 预调页策略:根据局部性原理(空间局部性),一次调入若千个相邻的页面可能比一次调入一个页面更高效
      *可以预测不久之后可能访问到的页面,将它们预先调入内存,但目前预测成功率只有50%左右
      该策略主要用于进程的首次调入,由程序员指出应该先调入哪些部分(运行前调入)

    2. 请求调页策略:进程在运行期间发现缺页时才将所缺页面调入内存(运行时调入)
      *由这种策略调入的页面一定会被访问到
      *每次只能调入一页,而每次调页都要磁盘I/O操作,I/O开销较大。

    4 从何处调入页面

    1. 对换区空间足够
      在这里插入图片描述
      页面的调入、调出都是在内存与对换区之间进行,保证页面的调入、调出速度很快。
      在进程运行前,需将进程相关的数据从文件区复制到对换区。
    2. 对换区空间不足在这里插入图片描述
      不会被修改的数据都直接从文件区调入,由于这些页面不会被修改,因此换出时不必写回磁盘,下次需要时再从文件区调入即可
      可能被修改的部分,换出时需写回磁盘对换区,下次需要时再从对换区调入
    3. UNIX方式
      在这里插入图片描述
      运行之前进程有关的数据全部放在文件区,未使用过的页面都可从文件区调入
      被使用过的页面需要换出,则写回对换区,下次需要时从对换区调入

    5 抖动(颠簸)现象

    • 频繁的页面调度行为:刚刚换出的页面马上又要换入内存,刚刚换入的页面马上又要换出外存
      产生原因:进程频繁访问的页面数目高于可用的物理块数(分配给进程的物理块不够)
      *为进程分配的物理块太多会降低系统整体的并发度,降低某些资源的利用率

    • 驻留集:请求分页存储管理中给进程分配的内存块的集合
      工作集:指在某段时间间隔里,进程实际访问页面的集合
      在这里插入图片描述
      *工作集大小可能小于窗口尺寸
      操作系统可以统计进程的工作集大小,根据工作集大小给进程分配若干内存块:如窗口尺寸为5,经过一段时间的监测发现某进程的工作集最大为3,说明该进程有很好的局部性,给这个进程分配3个以上的内存块即可满足进程的运行需要

    驻留集大小不能小于工作集大小,否则进程运行过程中将频繁缺页

    展开全文
  • 王道操作系统》学习笔记总目录+思维导图

    万次阅读 多人点赞 2020-02-20 19:02:14
    本篇文章是对《2021操作系统》所有知识点的笔记总结归档,会一直更新下去 之后我也会写组成原理、计算机网络、数据结构与算法、Java、Linux等底层和应用层的技术文章,并总结目录 希望在自己可以复习的同时,也能将...
    • 本篇文章是对《2021王道操作系统》所有知识点的笔记总结归档,虽说是2021年的,但是这些都是最核心的底层基础知识,过多少年都不会有很大的变化,核心都差不多。

    • 我的武功秘籍:note.bithachi.cn,希望可以一起交流学习。

    • 学习视频:王道操作系统

    • 其它学习时总结的目录笔记,有思维导图和案例。见下图

    • 看到很多小伙伴需要课件,这里直接附上网盘链接:

    链接:https://pan.baidu.com/s/17ClnaWO2wkzBX_eX7sB66g
    提取码:8q81
    复制这段内容后打开百度网盘手机App,操作更方便哦

    在这里插入图片描述


    第 1 章 计算机系统概述

    1.1 操作系统的基本概念

             1.1.1 操作系统的概念、功能和目标(系统资源的管理者、提供接口、作为扩充机器、虚拟机)
             1.1.2 操作系统的特征(并发、共享、虚拟、异步)

    1.2 操作系统的发展和分类

             1.2.1 操作系统的发展和分类(手工、单道/多道批处理、分时、实时、网络、分布式、嵌入式、个人计算机)

    1.3 操作系统的运行机制和体系结构

             1.3.1 操作系统的运行机制和体系结构(大内核、小内核)
             1.3.2 中断和异常(内中断和外中断、中断处理过程)
             1.3.3 系统调用(执行过程、访管指令、库函数与系统调用)

    1.0.0 第一章操作系统概述错题整理

    第 2 章 进程管理

    2.1 进程与线程

             2.1.1 进程的定义、特征、组成、组织
             2.1.2 进程的状态(运行、就绪、阻塞、创建、终止)及转换(就绪->运行、运行->就绪、运行->阻塞、阻塞->就绪)
             2.1.3 原语实现对进程的控制
             2.1.4 进程之间的通信(共享通信、消息传递、管道通信)
             2.1.5 线程概念与多线程模型

    2.2 处理机的调度

             2.2.1 处理机调度的概念及层次
             2.2.2 进程调度的时机(主动放弃与被动放弃)、切换与过程(广义与狭义)、方式(非剥夺与剥夺)
             2.2.3 度算法的评价指标(cpu利用率、系统吞吐量、周转时间、等待时间、响应时间)
             2.2.4 作业/进程调度算法(FCFS先来先服务、SJF短作业优先、HRRN高响应比优先)
             2.2.5 作业/进程调度算法(时间片轮转调度算法、优先级调度算法、多级反馈队列调度算法)

    2.3 进程的同步与互斥

             2.3.1 进程的同步与互斥
             2.3.2 实现临界区进程互斥的软件实现方法
             2.3.3 实现临界区进程互斥的硬件实现方法
             2.3.4 信号量机制(整型信号量、记录型信号量P、V)
             2.3.5 信号量机制实现进程的互斥、同步与前驱关系
             2.3.6 进程同步与互斥经典问题(生产者-消费者问题、多生产者-多消费者问题、吸烟者问题、读者-写者问题、哲学家进餐问题)
             2.3.7 管程和java中实现管程的机制

    2.4 死锁

             2.4.1 死锁详解(预防、避免、检测、解除)

    第 3 章 内存管理

    3.1 内存管理的概念

             3.1.1 什么是内存?进程的基本原理,深入指令理解其过程
             3.1.2 内存管理管些什么?
             3.1.3 覆盖技术与交换技术的思想
             3.1.4 内存的分配与回收
             3.1.5 动态分区分配的四种算法(首次适应算法、最佳适应算法、最坏适应算法、临近适应算法)
             3.1.6 分页存储(页号、页偏移量等)
             3.1.7 分页存储管理的基本地址变换结构
             3.1.8 快表的地址变换结构
             3.1.9 二级页表的原理和地址结构
             3.1.10 基本分段存储管理(段表、地址变换、信息共享)
             3.1.11 段页式存储管理(段表、页表、地址转换)

    3.2 虚拟内存管理

             3.2.1 虚拟内存的基本概念(局部性原理、高速缓存、虚拟内存的实现)
             3.2.2 请求分页管理方式(请求页表、缺页中断机构、地址变换机构)
             3.2.3 页面置换算法(最佳置换算法、先进先出置换算法、最近最久未使用置换算法、普通时钟置换算法、改造型时钟置换算法)
             3.2.4 页面分配策略(驻留集、页面分配、置换策略、抖动现象、工作集)

    第 4 章 文件管理

    4.1 文件系统

             4.1.1 初识文件管理概念和功能
             4.1.2 文件逻辑结构(顺序文件、索引文件、索引顺序文件、多级索引顺序文件)关于数据库的索引如聚簇索引可以看一下索引文件例题的解析,感觉还是可以收获到东西的
             4.1.3 文件目录结构(单级-两级-多级-无环图)、索引节点FCB瘦身
             4.1.4 文件的物理结构(连续分配、链接分配[隐式-显式]、索引分配[链接方案-多层索引-混合索引])
             4.1.5 文件管理空闲磁盘块的几种算法(空闲表法、空闲链表法、位示图法、成组链接法)
             4.1.6 文件的基本操作原理(创建、删除、打开、关闭、读-写)
             4.1.7 文件共享(索引节点-硬链接、符号链接-软链接)
             4.1.8 文件保护(口令保护、加密保护、访问控制)
             4.1.9 文件系统的层次结构

    4.2 磁盘组织与管理

             4.2.1 磁盘的结构(磁盘、磁道、扇区、盘面、柱面、磁头)
             4.2.2 磁盘调度算法(FCFS、SSTF、SCAN、LOOK、S-SCAN、C-LOOK)
             4.2.3 减少磁盘延迟时间的方法(交替编号、错位命名)
             4.2.4 磁盘管理(磁盘初始化、引导块、坏块的管理)

    第 5 章 I/O管理

    5.1 I/O管理概述

              5.1.1 什么是I/O设备?有几类I/O设备?
              5.1.2 控制I/O设备的I/O控制器
              5.1.3 控制I/O设备的几种方式?(程序直接控制方式、中断驱动方式、DMA、通道控制)
              5.1.4 I/O软件的层次结构(用户层软件-设备独立性软件-设备驱动程序-中断处理程序)

    5.2 I/O核心子系统

              5.2.1 内核的I/O核心子系统及功能
              5.2.2 I/O设备假脱机技术(SPOOLing)
              5.2.3 I/O设备的分配与回收(DCT-COCT-CHCT-SDT)
              5.2.4 缓冲区管理(单缓冲-双缓冲-循环缓冲-缓冲池)

    展开全文
  • 王道操作系统系列视频学习笔记
  • 所有图片来自于B站王道操作系统视频教程。 第一章:操作系统: 1.定义: 1.负责管理协调硬件、软件等计算机资源的工作。 2.为上层的应用程序、用户提供简单易用的服务。 3.操作系统是系统软件,而不是硬件。 进程的...
  • 操作系统的概念、特征、功能和作用 概念 是系统最基本最核心的软件,属于系统软件 控制和管理整个计算机的硬件和软件资源 合理的组织、调度计算机的工作与资源的分配 为用户和其它软件提供方便的接口和环境 功能及...
  • 操作系统的概念和定义 1.1. 操作系统的层次结构 1.2.操作系统的功能和目标 1.3. 操作系统的四个基本特征 1.4.操作系统的发展和分类 1.5.操作系统的运行机制 体系结构 1.6.中断和异常 总结 ...
  • 王道考研 操作系统学习笔记(复习用): 课程链接:https://www.bilibili.com/video/BV1YE411D7nH 1.1.1: 介绍操作系统的定义,可理解为软硬件中间层,管理处理机、存储器、文件、设备四大资源。 1.1.2: 操作系统...
  • 1.11 操作系统的概念与功能 操作系统(operating system,OS):①是系统资源的管理者——控制和管理计算机系统的硬件和软件资源;②向上层提供方便易用的服务——提供给用户和其他软件方便的接口和环境;3.是最接近...
  • 操作系统笔记( 王道考研)

    千次阅读 2020-06-16 08:47:11
    文章目录(一)1. 操作系统的概念和定义1.1. 操作系统的层次结构1.2.操作系统的功能和目标1.3. 操作系统的四个基本特征1.4.操作系统的发展和分类1.5...
  • 操作系统笔记(b站王道视频)

    万次阅读 多人点赞 2019-08-16 16:41:41
    操作系统的概念和定义1.操作系统的层次结构2.操作系统的功能和目标3.操作系统总结4. 操作系统的四个基本特征5.操作系统四个特征总结6.操作系统的发展和分类7.操作系统的发展和分类的总结8.操作系统的运行机制 体系...
  • 操作系统笔记目录(2019 王道考研) 第一章 概论 1.1 操作系统的概念、功能和目标 1.2 操作系统的特征 1.3 操作系统的发展和分类 1.4操作系统的运行机制和体系结构 1.5中断和异常 1.6系统调用 第二章 第三章 第四章 ...
  • 操作系统王道考研学习笔记 基本地址变换机构 从逻辑地址到物理地址的过程: 学到这的时候应该知道对于计算机来说,知道了逻辑地址A(和页表大小)就等于隐式地知道了页号P和页内偏移量(如果记忆模糊建议翻看上一...
  • 操作系统概念(定义) 操作系统(Operating System, OS)是控制和管理整个计算机系统的硬件和软件资源,并合理地组织调度计算机的工作和资源的分配,以提供给用户和其他软件方便的接口和环境,它是计算机系统中最...
  • 进程通信 什么是进程通信 高级进程通信的三种方法 共享存储 共享一块大家都可以访问的空间,一次只能有一个进程进行读或写操作 管道通信 消息传递 知识回顾 5. 线程概念与线程实现方式 为什么要引入线程 什么是线程 ...
  • 对应课程视频链接 : 王道考研—操作系统 — 分页存储管理 分页存储管理的先导知识: 非连续固定分区分配 导入正式概念: 注意: (1)进程可以被分块,内存也可以被分块 (2)内存块 = 物理块 = 页框 = 页帧,是...
  • 博主观看的 2019 王道考研 操作系统 进行学习的!!强烈推荐!! 考试复习推荐资料:操作系统复习总结 - 百度文库 (baidu.com) 后续章节陆续推出… 一、操作系统概述1.1 操作系统的概念、功能、目标1.1.1 基本概念...
  • 操作系统笔记

    2021-01-20 21:54:48
    王道论坛操作系统笔记> 1.1 操作系统的概念,功能和目标 概念:负责协调计算机上软硬件资源的工作,为上层用户,程序提供简易的服务的一种系统软件. 功能和目标: 系统资源的管理者:管理处理机,管理文件,管理内存,...
  • 1.1.1 操作系统的概念、功能和目标 1.1.2 操作系统的特征 1.1.3 操作系统的发展与分类 手工操作阶段 输入和输出都是一张打了孔的纸袋(有孔是1,无孔是0),速度很慢,而CPU处理速度很快,这就是矛盾的。 ...
  • 操作系统 (Operating System, OS) 是指控制和管理整个计算机系统的硬件与软件资源,合理地组织、调度计算机的工作与资源的分配,进而为用户和其他软件提供方便接口与环境的程序集合。 操作系统是计算机系统中最基本...
  • (3)多级反馈队列调度算法 规则: 2019 王道考研 操作系统 2.3_1进程同步、进程互斥 重点: (1)进程互斥 (2)进程互斥遵循的四个原则:空闲让进、忙则等待、有限等待、让权等待。 2.3_2进程互斥的软件实现方法 ...
  • 3.1.10 基本分段存储管理 进程的地址空间:按照程序自身的逻辑关系划分为若干个段,每个段都有一个段名(在低级语言中,...在下面例子中,若系统是按字节寻址的,则段号占16位,因此在该系统中,每个进程最多有2^16
  • 操作系统概述操作系统的特征:操作系统的运行机制与体系结构:操作系统的运行机制:操作系统内核:操作系统体系结构:中断机制:中断的分类:系统调用功能分类系统调用过程: 操作系统的特征: 1)并发(与并行的...
  • 操作系统系统笔记整理

    千次阅读 多人点赞 2020-09-26 13:37:27
    本篇文章的内容结合了哈工大李治军老师操作系统课程,王道考研操作系统的资料以及学习了B站CodeSheep的一次知识梳理,以及为了便于理解学习,增加了个人的一些解释。总之,对于开发人员来说,操作系统需要下四个方面...
  • 博主观看的 2019 王道考研 操作系统 进行学习的!! 考试复习推荐资料:操作系统复习总结 - 百度文库 (baidu.com) 需要相关电子书的可以关注我的公众号BaretH后台回复操作系统 第一章:操作系统概述 后续章节陆续...
  • 文件保护二、文件系统的实现三、磁盘组织与管理附:王道选择题笔记   本章知识结构图: 一、文件系统的基础 1.文件的概念 2.文件的逻辑结构 3.目录结构 4.文件共享 5.文件保护 二、文件系统的实现 三、磁盘组织与...
  • ③装入 装入的作用:把程序中的逻辑地址转为物理地址进而让计算机得以识别 三种装入方式:(其中只有绝对装入是编译程序实现,其他是操作系统实现) 1.绝对装入(只适用于单道程序环境):在编译时,如果知道程序将...
  • 文章目录一、基本概念二、操作系统的发展与分类三、操作系统的运行环境四、操作系统的体系结构 一、基本概念 二、操作系统的发展与分类 三、操作系统的运行环境 四、操作系统的体系结构 ...
  • 本篇文章是对《2021王道操作系统》所有知识点的笔记总结归档,虽说是2021年的,但是这些都是最核心的底层基础知识,过多少年都不会有很大的变化,核心都差不多。 我看了一下,都总结的很不错,我最近也是在看相关的...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 2,176
精华内容 870
关键字:

王道操作系统笔记