分类 操作系统概论 下的文章

基本分页存储管理方式的逻辑地址结构包括两个部分,即页号和页内地址

假定块表的命中率为98%,快表的访问时间为20ns,内存的一次访问时间为100ns,则系统的有效访存时间是:
(100+100+20)2% + (100+20)98% = 122ns

相对于分页机制,引入分段机制主要目的是:易于实现信息共享

系统允许的最大进程数一定时,系统要求的响应时间越短,时间片取值应该越小(切换的越快执行的越快)
响应时间与进程数和时间片成比例 响应时间越小,时间片取值越小

设系统有一类数量为M的独占性资源,系统中N个进程竞争该类资源,每个进程对资源的最大需求为W,当M、N、W分别取下列哪个值时,系统不会发生死锁?
计算公式:
M = N(W-1)+1

进程死锁的必要条件:
1.互斥条件
2.请求和保持条件
3.不剥夺条件
4.环路等待条件

分时系统具有的四个特征:

  • 多路性
  • 独立性
  • 及时性
  • 交互性

进程是真实存在的实体,应用程序对应的进程由该程序、数据和管理进程所需要的进程控制块(PCB)构成

进程调度中的平均带权周转时间E(服务时间/周转时间)/数量
周转时间 进程从进入系统到完成之后的时间

在基于分页的虚拟存储系统中,常采用两种置换策略: 局部置换 全局置换

在使用分段存储管理的系统中,程序员使用二维的逻辑地址,一个数用来表示段、另一个数用来表示段内偏移

文件系统的用户接口包括:文件的全名、对文件的操作、属性、类型

考虑一个由8个页、每个页1K字节组成的逻辑地址空间,把它映射到由32个物理块组成的存储器,则逻辑地址有: 13 位 物理地址有: 15 位
2^3 = 8 2^10 = 1K = 1024 所以 3+10 = 13
因为物理内存要分的跟逻辑内存一样的大小所以 2^5 = 32
5 + 10 = 15

文件系统的用户接口包括:文件的全名、对文件的操作、类型和属性

在设备管理中,为了提高可适应性和可扩展性,现代操作系统实现了 设备独立性 即应用程序独立于具体使用的物理设备。在应用程序中,使用 逻辑设备名称 来请求使用设备,而在实际执行时,必须使用物理设备名称。

SPOOLING 的优点

  • 提高了IO速度
  • 将独占设备改为共享设备
  • 实现了虚拟设备

I/O系统的结构

  • 微机I/O系统
    CPU可与内存之间直接进行交换 与设备之间的信息交换必须经过设备控制器。
  • 主机I/O系统
    I/O系统可能采用四级结构、一个通道可以控制多个设备控制器,一个设备控制器可以控制多个设备

I/O设备的分类

  • 按传输速率分类
    • 低速设备
    • 中速设备
    • 高速设备
  • 按信息交换的单位分类
    • 块设备
    • 字符设备
  • 按设备的共享属性分类
    • 独占设备
    • 共享设备
    • 虚拟设备

设备控制器

设备控制器是CPU与I/O设备之间的接口,接收I/O的命令并控制设备完成I/O工作

设备控制器的功能:

  • 接收和识别命令
  • 数据交换
    1.将驱动器中的比特流汇集在控制器的缓冲区中以形成字节快

2.实现CPU到控制器、控制器到CPU的双向数据传送
3.将控制器对设备的控制命令传送给设备控制器

  • 设备状态的了解和报告
  • 地址识别
  • 数据缓冲
  • 差错控制

设备控制器的组成

  • 设备控制器与处理机的接口
  • 设备控制器与设备的接口
  • I/O逻辑

I/O通道是一种特殊的处理机,具有执行I/O指令的能力,

I/O控制方式

  • 轮询
    反复检测设备控制器状态寄存器的忙/闲标志位,直到该标志位为空闲 ,主机发送I/O指令。主机发送完I/O指令后,设备控制器把状态寄存器的忙/闲标志设置为忙
  • 中断
    若I/O设备忙则进程阻塞等待,当处于忙状态的设备工作完毕中断控制器发送中断请求信号,CPU响应中断,执行对应设备的中断处理程序。
  • DMA控制方式
    DM控制需要特殊结构的设备控制器,DMA控制器的逻辑组成包括3部分:主机与DMA的接口、DMA与设备的接口,以及I/O控制逻辑。

DMA控制器中设计了4类寄存器:

  • 命令/状态寄存器CR
  • 内存地址寄存器MAR
  • 数据寄存器DR
  • 数据计算器DC
    当读写次数达到阈值DC时会产生中断

缓冲管理

在数据到达速率与数据离去速率不同的地方都可以引入缓冲区
引入缓冲区主要原因可以归纳为两点:

  • 处理数据流的生产者与消费者之间的速度差异
  • 协调传输数据大小不一致的设备
    缓冲有:单缓冲、双缓冲、循环缓冲

缓冲池
至少包含3种类型的缓冲区、3种缓冲队列、4种工作缓冲区

  • 3种缓冲区:空缓冲区、装满载入数据的缓冲区、装满输出数据的缓冲区
  • 3种队列:空缓冲队列、输入队列、输出队列
  • 4种工作缓冲区:收容输入数据的缓冲区,提取输入数据的缓冲区,收容输出数据的缓冲区、提取输出数据的缓冲区。

第四节 设备分配

设备分配中的数据结构
1.设备控制表(Device Control Table)
系统为每个设备建立一张设备控制表,多台设备的设备控制表构成设备控制表集合。每张设备控制表包含以下信息:

  • 设备类型
  • 设备标志符
  • 设备状态
  • 指向控制器表的指针
  • 重复执行的次数或时间
  • 设备队列的队首指针(请求设备而被阻塞的进程的PCB构成的队列)

2.控制器控制表COCT(Controller Control Table)

  • 控制器标志符
  • 控制器状态
  • 与控制器相连接的通道表指针
  • 控制器队列的队首指针
  • 控制器队列的队尾指针

3.通道控制表CHCT(Channel Control Table)

  • 通道标志符
  • 通道状态
  • 与通道连接的控制器表首址
  • 通道队列的队首指针
  • 通道队列的队尾指针

4.系统设备表SDT(System Device Table)
记录系统中全部设备的情况
每个设备占一个表目,其中包括设备类型、设备标志符、设备控制表之间的关系及利用数据结构进行设备分配。

设备分配:

要考虑设备的属性:

  • 独占性
  • 共享性
  • 虚拟性

分配算法:

  • 先来先服务
  • 基于优先权的分配算法

分配方式:
安全分配方式:
发出I/O请求之后就阻塞进程等待执行完毕之后再恢复
优点:分配安全、不会造成死锁
缺点:进程进展缓慢
不安全分配方式:
进程在发出I/O请求后继续运行,仅当进程所请求的设备已被另一个进程占用时,请求进程才进入阻塞状态。
优点:进程进展迅速
缺点:分配不安全、会造成死锁。

设备独立性

应用程序独立于具体使用的物理设备,为了实现设备独立性,引入了逻辑设备和物理设备这两个概念。
优点:

  • 应用程序与物理设备无关,系统增减或变更外围设备时不需要修改应用程序。
  • 易于处理输入/输出设备的故障。
  • 提高了系统的可靠性

设备独立软件:

  • 执行所有设备的公有操作
    独占设备的分配和回收、将逻辑设备名映射为物理设备名(逻辑设备表LUT(Logical Unit Table) 为整个系统设置一张或为一个用户设计一张)、对设备进行保护、缓冲管理、差错控制

向用户层软件提供统一的接口

独占设备的分配程序:

当进程提出I/O请求后,系统的设备分配程序可按下列步骤进行设备分配:

  • 分配设备:
    根据请求设备的物理名、查找系统设备表、找出该设备的设备控制表,检查设备控制表中的设备状态字,若忙则阻塞进程若空闲则根据分配算法分配设备
  • 分配控制器
  • 分配通道

SPOOLING技术

就是用高速I/O做低速I/O的中间操作缓存。
特点:

  • 提高了I/O速度
  • 将独占设备改造为共享设备
  • 实现了虚拟设备功能

I/O软件原理

将软件组织成一种层次结构,低层软件用来屏蔽硬件的具体细节,高层软件则主要为用户提供一个简洁、规范的界面。
分为4个层次:

  • 用户层软件
  • 与设备无关的软件层
  • 设备驱动程序
  • 中断处理程序

设备管理软件的功能:

  • 实现I/O设备的独立性
  • 错误处理
  • 异步传输
  • 缓冲管理
  • 设备的分配和释放
  • 实现I/O控制方式

与硬件无关的I/O软件

  • 设备命名
  • 设备保护
  • 提供独立于设备块的大小
  • 为块设备和字符设备提供必要的缓冲技术
  • 块设备的存储分配
  • 分配和释放独立设备
  • 错误处理

磁盘管理

磁盘结构

  • 数据的组织和格式
    存储面:每个磁盘片分一个或两个存储面

磁道:每个盘面被组织成若干个同心环
扇区:每条磁道被划分的单位
每个扇区包括两个字段:

    • 标识符字段
    • 数据字段 每个分区的起始扇区和大小都记录在磁盘0扇区的主引导记录分区表所包含的分区表中
  • 磁盘类型
  • 固定头磁盘 磁盘转磁头不转
  • 移动头磁盘

磁盘的访问时间

主要有以下时间组成:

  • 寻道时间 把磁头移动到指定磁道上的时间
  • 旋转延迟时间 扇区移动到磁头下经历的时间
  • 传输时间 数据从磁盘读出或磁盘写入数据时经历的时间

其中寻道时间 旋转延迟时间 是访问时间的大头所以有必要把相关的数据集中存放在一起

磁盘调度算法

  • 先来先服务(First Come First Served FCFS)
    根据进程请求的先后顺序进行调度
  • 最短寻道时间优先(Shortest Seek Time First SSTF)
    要求访问的磁道与当前磁头所在的磁道距离最近
  • 扫描算法(电梯调度算法)(SCAN)
    不仅考虑到要访问的磁道与当前磁道的距离,更优先考虑磁头当前移动的方向。
  • 循环扫描(CSCAN)算法
    单向移动到了边界之后再挪回起点重新移动
  • NStepScan和FSCAN调度算法
    SSTF,SCAN,CSCAN这几种算法中有一个或几个进程对某一磁道有较高的访问频率会产生磁道粘着的现象。

NStepScan算法是将磁盘请求队列分成若干个长度为N的子队列磁盘调度将FCFS算法依次处理这些子队列 处理队列时按SCAN算法
NScan算法是NStepScan的简化 只将磁盘请求队列分成两个子队列一个是当前所有请求磁盘I/O的进程行程的队列,由磁盘调度按SCAN算法进行处理,在扫描期间将新出现的所有请求I/O的进程放入另一个等待处理的请求队列。

提高磁盘I/O速度的方法

  • 提前读
  • 根据现在用户请求读的内容 把预计最近不久可能要读的内容与现在请求读的内容一起读入内存
  • 延迟写
    对修改过的换出页在把页标记为换出页时不马上把页的内容写入磁盘而是暂时保留在内存中,直到页所在的页框要被使用导致页的内容被覆盖前的最后时刻才启动磁盘操作,把修改过的一个或若干页写入磁盘。
  • 优化物理块布局
  • 虚拟盘
    利用内存空间去仿真磁盘
  • 磁盘高速缓存
    内存的一块存储空间用来暂存磁盘中读出的一系列盘块中的信息。

文件结构:
1.无结构字节序列
2.固定长度记录序列
3.树形结构

文件类型:
正规文件、目录文件、字符设备文件、块设备文件
正规文件又分为:
1.ASII文件(.txt)
2.二进制文件(.exe)

文件存取:
1.顺序存取
2.随机存取

文件属性
如:创建日期、文件大小、修改时间……

文件操作:
1.CREATE
2.DELETE
3.OPEN
4.CLOSE
5.READ
6.WRITE
7.APPEND
8.SEEK
9.GETATTRIBUTES
10.SETATTRIBUTES
11.RENAME

目录

目录是文件系统中实现按名访问文件的重要数据结构

目录有两种常见的结构
属性放在目录项中和放在i节点中
目录文件包含许多目录项、每个目录项用于描述一个文件。

目录结构:

  • 单层目录
  • 两级目录
  • 树形目录

路径:

  • 绝对路径
  • 相对路径

目录操作:

  • CREATE
  • DELETE
  • OPENDIR
  • CLOSEDIR
  • READDIR
  • RENAME

文件系统的实现:
文件实现:

  • 连续分配:
    把每个文件作为一连串数据存储在磁盘上 按系统规定的簇的大小进行分割。

优点:实现简单、读操作性能好。 缺点:磁盘碎片

  • 磁盘链接表分配
    为每个文件构造簇的链接表 每个簇的开始几个字节用于存放下一个簇的簇号,可以存放在不连续的簇中。

缺点:随机存取相当缓慢

  • 使用内存的链接表分配
    通过内存存放磁盘链接表

缺点:不适合大容量磁盘

  • i结点
    为每个文件赋予一个i结点的数据结构,其中列出了文件属性和文件块的磁盘地址

每个文件对应一个i结点
i结点每一项对应一个文件簇 每个i结点有预留间接地址 有一次间接地址、二次间接地址
二次间接地址会在一次间接地址上每一项都指向间接地址
i结点能表示多大的文件计算公式:
存放簇号的个数×簇大小+(一次间接)簇大小/每个地址大小×簇大小…………

实现目录:
CP/M中的目录(单层目录)
MS-DOS目录项
UNIX目录(只有目录名对应i结点)

磁盘空间管理

  • 簇大小 簇太大容易造成空间的浪费、簇太小则会使访问文件的时间延长。
  • 记录空闲块
    • 空闲链接表
    • 位图(每个簇号对应一个位)

内存管理的目标:

  • 内存管理
  • 提高内存利用率、内存访问速度

存储器的层次结构:

  • 不同容量
  • 不同成本
  • 不同访问时间

从高层到底层(L0~L5) 较低层的存储设备速度更慢、容量更大、价格更便宜。

  • L0:是少量的快速CPU寄存器 CPU可以在一个时钟周期内访问它们。
  • L1:多个小型或中型的基于SRAM的高速缓存存储器 CPU可以在几个CPU时钟周期内访问他们
  • L3:一个大的基于DRAM的主存,可以在几十或几百个时钟周期内访问它们。
  • L4:慢速但容量大的本地磁盘
  • L5:远程磁盘等……

CPU寄存器保存最常用的数据。 靠近CPU的容量小、速度快的高速缓存存储器作为速度相对较慢、容量较大的主存数据和指令子集的缓冲区。

总的来说,局部性原理表现为时间和空间的局部性。

静态链接:

  • 对逻辑地址进行修改
  • 变换外部调用符号
    优点:运行速度快 缺点:占用空间大

动态链接(调用时才进行链接):
优点:节省内存和外存空间
缺点: 速度慢

源程序要变为一个可在内存中执行的程序要经过编译、链接、装入三个阶段。
通常,可执行程序以二进制可执行文件的形式存储在磁盘上,
程序的装入方式分为绝对装入方式、可重定位装入方式和动态运行时装入方式。

  • 绝对装入方式
    事先已知程序在内存中的驻留位置,编译时产生物理地址的目标代码,绝对装入程序按照装入模块的物理地址将程序和数据装入内存。因此装入模块被装入内存后,无需对程序和数据的地址进行修改。
  • 可重定位装入方式

在程序装入时对目标程序中的指令和数据地址的修改过程称为重定位。
可重定位方式的两个特定如下:

  • 编译程序使目标模块的起始地址从0开始
  • 程序装入时根据内存使用情况将模块装入到内存的某个位置 并对模块进行重定位

物理地址=有效逻辑地址+程序在内存中的起始地址

  • 动态运行时装入
    进程在装入内存后,还可能从内存的一个区域移动到另一个区域,这种情况可能发生在支持虚拟存储的系统中。

连续分配存储管理方式:

单一连续区分配方式

  • 固定分区分配方式
    分区方式:分配的用户分区数量是固定的,每个分区的大小也是固定的。但是每个分区的大小可以相等,也可以不相等。

动态分区分配方式

1.动态分区分配原理:当进程请求空间时,由于系统根据进程需要的空间大小划分出一片空闲区分配给进程。
系统初始只有一个大空闲区,

2.动态分区分配数据结构

- 空闲分区表
- 空闲分区链

3.动态分区的分配算法

  • 首次适应算法(First Fit)
    优点:结构简单 缺点:搜索空闲分区链需要的时间开销比较大
  • 循环首次适应算法(Next Fit)
    优点:空闲区分布均匀、查找开销较小 缺点:容易缺乏大空闲分区
  • 最佳适应算法(Best Fit)
    按分区大小递增组成一个空闲链

优点:避免大材小用 提高内存利用 缺点:留下难以利用的小空闲区。

内存分配流程:
1.检索空闲分区链 m.size >= u.size
2.如果m.size(当前结点对应的空闲分区大小) - u.size (用户申请的空间)<= size (系统阈值) 则直接分配 否则从m.size 中划出大小为u.size的空间分配给进程,把剩余的大小为m.size-u.size的空闲空间作为新的空闲分区。
3.将分配给进程的分区起始地址返回给内存分配程序的调用者
4.修改空闲分区链表

内存回收流程

  • 释放一块连续的内存区域
  • 如果被释放区域与其他空闲区间相邻,则合并空闲区
  • 修改空闲分区链

基本分页存储管理方式
把进程离散地存储在内存中物理地址不连续的区域中,这种内存管理方式称为离散内存管理方式。
原理:
页:将一个进程的逻辑地址空间分为若干个大小相等的片
页框:将物理内存空间分成与页大小相同的若干个存储块,称为页框或页帧
分页存储:以页框为单位将进程中的若干页分别装入多个可以不相邻接的页框中。
页内碎片:进程的最后一页一般装不满一个页框。
页表:页表是系统为进程建立的数据结构,作用是实现从页号到页框号的映射。

地址结构:
基本分页的逻辑地址结构分为两部分:页号P和页内偏移W 低n位表示页内偏移量W 用高m-n位表示页号P
以32位为例子:当0~12位表示页偏移时 则可以容纳2的12次方字 大概:4KB 12~31位(20位)可以有2的20次方个页 则有1M个页 则总共可表示4G的逻辑地址空间。
计算公式:A为逻辑地址 L为页大小 W为页内偏移量 计算关系:
P=INT(A/L)
W=MOD(A/L)

分页地址变换过程

  • 进程执行,PCB中页表起始地址和页表长度送CPU的页表寄存器
  • CPU访问逻辑单元A
  • 由分页地址变换硬件自动将A分为页号和页内偏移两部分
  • 由硬件检索页表,得到A所在的页对应的页框号
    页号对应的页表起始地址 = 页表起始地址 + 页表项长度 × 页号
  • 页框号和页内偏移地址送物理地址寄存器,计算物理地址。物理地址 = 页框大小×页框号 + 页内偏移量

页大小的选择:
选择较小 会使进程的页数较多、换出频繁
选择较大 会使进程缺页率高,页表过长占用大量内存空间

影响大小的设计因素:

  • 管理内存的开销
  • 内存的利用率

一般选择2的次幂 4KB一般

快表也称为后援缓冲(Translation Look-aside Buffer):
页表的硬件实现方法之一,用来存放最近被访问过的页表项
相当于是一个键值缓存 通过键(页号)映射到值(页框号)

有效访存时间:
假设CPU访问内存的速度为:120ns,访问TLB的速度为20ns,比较有TLB和无TLB系统的平均访存时间,假定命中率为:90%。
则有TLB:(未命中)(120+120+20)×10% + (命中)(120+20)x90% = 152ns
无TLB:120+120 = 240ns
(240-152)/152 = 57.9%;

反置页表:
现代系统可能存在大量进程,每个进程都允许有很大的逻辑地址空间,因而进程可能拥有一个很大的页表。可以使用反置页表,为每一个页框设一个表项、表项中存放进程号和页号,系统只维护一张反置页表即可。

空闲页框管理:
使用位图管理空闲页框:
用二进制的位数对应物理内存的页框数 0 代表当前位数的页框未占用 1 代表占用

基于分页的虚拟存储系统

虚拟存储技术实现的基本思想:按需载入 如果当前CPU访问的内容不在内存上面则通过抛出异常让外存载入指定内容到内存上。
置换:当内存满的时候把一部分不相关的换出到外存上。

优点:

  • 提高内存利用率
  • 提高多道程序度
  • 把逻辑地址空间和物理地址空间分开

虚拟存储系统具有以下几个主要特征:

  • 离散性
  • 多次性
  • 对换性
  • 虚拟性

请求分页中的硬件支持

  • 页表
    具有以下基本字段:

    • 页框号
    • 状态位p :页是否在内存
    • 访问字段A: 最近访问信息
    • 修改位M :最近修改信息
    • 保护位 :0为只读 1为可读可写
  • 缺页异常机构
    1.通过检查当前页表的状态位p判断是否在内存中不在则产生缺页异常信号

2.找空闲页框然后调用外存读入数据
3.修改页表 存在位、页框号、访问位、保护位等
4.重新开始执行因缺页而被中断的指令

添加请求分页系统的地址变换过程如下:

  • 由分页地址变换机构从逻辑地址中分离出页号和页内偏移地址
  • 以页号为索引查找快表 如快表中没有则转到内存页表中查找
  • 若该页不在内存则产生缺页异常,请求操作系统从外存中把该页调入内存。

页分配策略

1.最少页框数
保证进程正常运行所需要的最少页框数与进程的大小没有关系,它与计算机的硬件结构有关,取决于指令的格式、功能和寻址方式。要计算每个内存单元所涉及的内存地址页数来确认进程运行最少所需分配页框数。
2.页分配和置换策略

  • 固定分配局部置换
  • 可变分配全局置换
  • 可变分配局部置换

3.分配算法

  • 平均分配算法 n个进程 m个内存页框 则为每个进程分配INT[m/n]个页框,其余MOD[m/n]放入空闲框缓冲池中
  • 按比例分配算法
    进程分配的页框数 = 进程页数/所有进程页数的总和×页框数
  • 考虑优先权分配算法
    优先权高页框数多 优先权低页框数少

页调入策略

  • 何时调入页
    1.用到的时候再调入

2.预先调入

  • 何处调入页
    1.从对换区调入 进程运行前从文件区复制到对换区。

2.UNIX方式 没有访问过的页都直接从文件区调入,换出页都存放在对换区。

页置换算法

1.最佳置换算法和先进先出置换算法(难以实现)
选择未来最长时间不会用到的内存页进行置换
2.先进先出页置换
选择进入内存时间最早的页
3.最近最久未使用LRU置换算法
选择最近最久未使用的页换出
实现办法

  • 设置一个寄存器到页中 每隔一段时间寄存向右移一位 并且最高位置一 则最小值的为最久未使用的页
  • 计数器

其他置换算法:
计算机系统要提供足够的硬件来支持LRU算法比较困难 所以实现时都采用LRU的近似算法 如附加位算法、简单Clock算法和改进型Clock算法
改进型Clock步骤:
从当前位置开始扫描循环队列寻找A=0,M=0(未访问页未修改) 如果找到底仍未找到则寻找A=0,M=1 第二轮扫描期间将所有经过的页的访问位A置0
如果第二步也失败则再次寻找A = 0,M = 0的第一类页,如仍失败 再寻找A = 0,M = 1的页

  • 最少使用置换算法
  • 页缓冲算法

P为缺页率 ma为存储器访问时间
有效访问时间 = (1-P)x ma + P x 缺页异常时间
缺页异常时间 = 缺页异常服务时间 + 缺页读入时间 + 进程重新执行时间

例:4-12:要使有效访问时间延长不超过10%,缺页率P为多少?
因为P = 0时,有效访问时间 = 0.1μs
P不为0时,有效访问时间为:(0.1+24999.9P)μs
P不为0时比P为0延长时间:(0.1+24999.9P) - 0.1 = 24999.9P
要使24999.9P / 0.1 < 10% 必须使 P < 0.000.0004

工作集:
引入工作集机制是为了能有效降低缺页率
提前将需要的页面调入内存
工作集就是在某段时间间隔t里,进程实际要访问的页数集合

抖动产生的原因和预防方法
1.抖动 (多道程序下大部分时间都在进行页换入、换出)
2.预防
1.采取局部置换策略,当进程发生缺页后,仅在进程自己的内存空间范围内置换页
2.在CPU调入程序中引入工作集算法,只有当每个进程在内存中都有足够大的驻留集时,才能再从外存中调入新的作业。
3.挂起若干进程,腾出进程占用的空间。

  • 进程调度的功能
    进程调度功能由操作系统内核的进程调度程序完成。
  • 进程调度的时机
    当一个进程运行结束、进程阻塞、中断返回、优先级更高的进程到来、当前运行进程的时间片用完时。

进程调度算法
以下准则为依据:
1.周转时间短(从作业被提交给系统开始,到作业完成为止的这段时间间隔)
平均周转时间、带权平均周转时间
2.响应时间快
3.截止时间的保证
4.系统吞吐量高(单位时间内完成的作业数)
5.处理机利用率好

调度算法:
1.先来先服务调度算法(FirstCome,FirstServed)
性能分析:适合长进程不利于短进程 等待时间相对运行时间太长
平均周转时间=(周转时间之和)/数量
平均带权周转时间 =(周转时间/服务时间 之和)/数量
2.短进程优先调度算法(SPF)
优点:能有效降低进程的平均等待时间,提高系统的吞吐量
缺点:对长进程不利、不能保证紧迫进程及时处理、进程的长短根据用户的估计而定
3.优先权调度算法(Priority-Scheduling Lgorithm)
比起之前加上了优先权特征

  • 非抢占式优先权调度算法
  • 抢占式优先调度算法
  • 优先权类型(静态优先权(运行前确定优先权)、动态优先权(运行时确定优先权))
    缺点:无穷阻塞、饥饿问题

4.时间片轮转调度算法
(应用最广)
时间片切换时间确定:

  • 系统对响应时间的要求
  • 就绪队列中进程的数目
  • 系统的处理能力

5.多级队列调度

  • 多级调度算法
    根据不同属性分成多个就绪队列 不同队列优先权不同

6.多级反馈队列
建立多个优先权不同的就绪队列为每个队列赋予大小不同的时间片
设计要考虑以下:
1.就绪队列数量
2.根据进程优先权确定进程应该进入哪个就绪队列的算法
3.用以确定进程何时转移到较高优先权队列的算法
4.用以确定进程何时转移到较低优先权队列的算法
5.用以确定进程在需要服务时应该进入哪个队列的算法。

实施系统的调度

实现实时调度的基本条件:
1.提供必要的调度信息

  • 就绪时间
  • 开始截止时间和完成截止时间
  • 处理时间
  • 资源要求
  • 优先级
    2.系统处理能力强

3.采用抢占式调度机制
4.具有快速切换机制

常用几种实时调度算法:
1.最早截止时间优先EDF
2.最低松弛度有限LLF 截止时间为T 当前时间为Tc 处理完该任务还需要时间Ts 松弛度L=T-Tc-Ts

进程切换

步骤:
1.保存包括程序计数器和其他寄存器在内的CPU上下文环境
2.更新被替换进程的进程控制块
3.修改进程状态,把执行态改为就绪态或者阻塞态。
4.将被替换进程的进程控制块移动到就绪队列或阻塞队列。
5.执行通过进程调度程序选择的新进程,并更新进程的进程控制块。
6.更新内存管理的数据结构
7.恢复被调度程序选中的进程的硬件上下文。

多处理器调度

类型:
1.紧密耦合的多处理器系统
2.松弛耦合的多处理器系统
3.处理器类型对称与不对称

多处理器系统中的进程分配方式

  • 对称多处理器系统
    1.静态分配 为每个处理器建立一个专门的就绪队列 优点:进程调度开销小,缺点是不能动态的平衡各处理器的负载。

2.动态分配 优点:可以在每次调度时考虑处理器的负载平衡问题,总是把进程分配给当前空闲的处理器。

  • 非对称多处理器系统
    主一从式操作系统 操作系统核心部分驻留在一台主机上 机器上只运行用户程序 主机只执行调度程序

进程(线程)调度方式

1.自调度(公共就绪队列)
优点:易移值、有利于提高CPU的利用率
缺点:瓶颈问题(公共就绪队列互斥问题)、低效性(高速缓存命中率低)、线程频繁切换
2.成组调度
将相互合作的进程或线程同时分配到一组处理器上运行,进程或线程与处理一一对应。
优点:减少线程切换,改善系统性能、减少调度开销
成组调度的时间分配
a.面向所有的应用程序平均分配处理器时间
b.面向所有的线程平均分配处理器时间
3.专用处理器分配
一个应用程序执行期间,专门为该应用程序分配一组处理器,每个线程一个 会导致资源严重浪费。 优点:加速了应用程序的运行速度、避免了进程切换。

###死锁
原因:竞争共享资源且分配资源的顺序不当。
必要条件:
1.互斥条件
2.请求和保持条件
3.不剥夺条件
4.环路等待条件
只有满足上述四个条件才会发生死锁。

处理死锁的基本方法:
预防:保证其中一个条件不成立。
实现:
1.掘弃请求和保持条件
2.掘弃不剥夺条件、
3.掘弃环路等待条件(进程按资源排序的递增顺序申请资源)

死锁的避免:
系统的安全状态

银行家算法:

  • 资源分配
  • 对试分配后系统的状态做安全性检测的过程。

死锁的检测和解除:

  • 何时调用检测算法: 取决于两个因素:死锁可能发生的频率、当死锁发生时受影响的进程数量。

死锁定理:
资源分配状态S为死锁状态的充分条件是仅当S状态的资源分配图是不可完全简化的。

死锁检测:
途径有两个:终止处于死锁状态的进程,抢占死锁进程占有的资源。

进程终止:

  • 终止所有死锁进程
  • 一次只终止一个处于死锁的进程,直到死锁解除。

在采用终止部分进程的方法时,选择终止的进程考虑的因素包括以下几个:

  • 进程优先级
  • 进程执行时间,完成其指定任务前还需要多长时间
  • 进程使用多少资源
  • 进程需要多少资源才能完成
  • 需要终止多少进程才能解除死锁
  • 进程是交互的还是批处理的

资源抢占:

  • 抢占哪个进程和哪些资源 确定抢占的顺序以使代价最小
  • 回滚
  • 饥饿

防止进程死锁的资源数计算:并发进程数p 资源数m r≥p(m-1)+1