【操作系统】复习

操作系统复习

按章节顺序,由题目引出复习内容

lthero.整理

第一章 概论

从资源管理观点看,操作系统具有的功能

四种资源:处理机、存储器、I/O设备、文件管理

章节分布 系统资源 OS对应的功能
2~3 处理机(cpu) 分配处理机、对其进行有效管理
4~5 存储器 提高存储器利用率,扩充其逻辑上容量
6 I/O设备 提高I/O设备利用率,为用户分配I/O设备并完成I/O请示
7~8 文件管理 对用户文件和系统文件进行管理

操作系统目的:

操作系统作为用户与计算机硬件的接口,让用户方便的操作自己的计算机硬件

处理机管理

下面是2、3两章细节内容

进程控制

为每个作业,创建这个作业的一个或多个进程,分配资源,撤消进程,回收资源

进程同步

为了让多个进程或线程合作完成某个作业,需要让进程们进行协调

对资源访问要互斥,如加锁

对合作任务需要调整执行顺序,如信号量

进程通信

如果很多进程需要合作完成作业时,需要相互通信;

可以由源程序发送命令,将消息发送到目标进程的消息队列,再由目标进程从消息队列中提取信息

调度

作业调度与进程调度与中级调度

作业调度:将作业从作业队列中调入内存

中级调度:将内存中不要的进程换出,把外存中的进程换入

进程调度:把处理器在不同进程中切换


存储器管理功能

内存分配

目标是

  • 给每个程序分配空间

  • 提高存储器利用率

方法是

  • 静态分配:作业在装入内存时,就确实被分配的内存大小

  • 动态分配:同上,但允许作业运行时申请新的空间

内存保护

目标是

  • 不同程序间不能相互访问对方程序的数据

  • 不能让用户程序访问操作系统的程序和数据

方法是

  • 设置内存保护机制,增加两个界限寄存器,对每条指令要访问的地址进行检测,判断地址是否超出本程序被分配的地址空间

地址映射

目标是

  • 逻辑地址与物理地址相转换,由硬件完成

内存扩充

目标是

  • 将逻辑内存地址进行扩充,提高系统性能

方法是

  • 增加置换功能:即中程调度,不要的进程换出,能用的进程换入

  • 动态调入数据:允许进程装入最基本的数据便开始运行,运行中途再将其它需要的数据动态调入内存


设备管理功能

  • 完成用户进程提出的I/O请示,为用户分配I/O设备

  • 提高I/O设备的利用率,提高I/O速度

缓冲管理

在I/O设备与cpu之间加入缓存,解决cpu与I/O设备速度不匹配的问题,提高cpu利用率,也提高系统的呑吐量

设备分配

给用户进程分配I/O设备

设备处理

实现cpu与I/O设备的通信,如:cpu向I/O设备发送指令需要被执行;I/O设备发送的中断也需要被cpu处理


文件管理系统

对用户文件和系统文件进行管理,保证文件的安全性

文件存储空间的管理

在多用户环境下,不同用户需要有对应的存储空间,因此,文件管理系统需要对文件存储空间实施统一的管理

目标是:

  • 为每个文件分配必要的外在空间,提高外存利用率

  • 实现存储空间的分配和回收功能

方法是:

  • 设置对应的数据结构,用来记录外在的使用情况

目录管理

为每个文件建立一个目录项,包含:文件名,文件属性,在磁盘上的物理位置等

文件的读写管理和保护

  • 根据用户请示,从外存中读取数据,或将数据写入外存

  • 防止系统文件被非法窃取和破坏


操作系统具有的基本特征

*并发性

两个或多个事儿在同一段时间内交替发生

*共享性

系统中的资源可以提供多个并发执行的进程使用

并发性与共享性是最最最最基本的特征

虚拟性

通过某种技术,将单个物理实体变成多个逻辑实体

异步性

由于并发性的存在以及资源的限制,并发执行的进程不能一次性彻底执行完成,需要“走走停停”地完成


分时系统与实时系统

为了让人机进行交互,引入了分时系统

分时系统

目标

  • 程序员需要对程序进行调试

  • 多个用户需要共享一台主机,每个用户有自己的终端

方法

  • 为了能多个用户共享,系统需要提供多个终端

  • 系统需要即时接收并处理用户的命令,即使多个用户发送命令,也要即时接收并处理

特征

  • 多路性:多个用户接入同一个主机

  • 独立性:不同用户有自己独立的环境

  • 及时性:系统可以即时接收并处理用户的命令

  • 交互性:用户可以通过终端与主机进行交互

实时系统

实时,表示“及时处理,要快快快”,要求系统即时响应外部事件,并在规定时间内完成处理

如:

  • 信息查询系统,像:订票系统,要快

  • 武器控制系统,快

  • 多媒体系统,

特征

  • 多路性:多个用户接入同一主机

  • 独立性:不同用户使用之间不存在干扰

  • 及时性:像信息查询系统需要根据用户所能接受的时间而动态确定;像实时控制系统的及时性,需要在截止时间内完成

  • 交互性:交互性仅限于用户发送的某些特定命令,如开始播放,停止播放,快进等

  • 可靠性:需要高度可靠,而分时系统只需要可靠即可


单道批与多道批

单道批

概念

每次内存中只有一个进程,所有进程的运行是串行的

Snipaste_2021-12-05_14-01-39

多道批

概念 内存中存放多道程序,一个程序不执行时,处理器转换到另一个可以被执行的程序,提高了处理器的利用率

如:

某道程序因某种原因如执行I/O操作,此时不能继续运行放弃CPU时,操作系统便调度另一程序运行,这样CPU就尽量忙碌,达到提高系统效率的目的。

Snipaste_2021-12-05_14-03-03

  1. 当A进程申请I/O时,操作系统启动I/O(蓝线)。

  2. 随后,A进入I/O操作(磁盘操作);cpu处理B进程

  3. 当B进程也申请I/O操作时(磁带操作),操作系统启动I/O(蓝线)。

  4. 此时A的I/O还没结束,此时cpu处于空闲状态

  5. 当A的I/O完成后,操作系统调度A进程(蓝线),cpu处理A进程

  6. A进程处理完成,此时恰好,B的I/O操作完成,操作系统调度B进程(蓝线),cpu处理B进程


时分复用技术与空分复用技术

时分复用

本质

单个的物理实体,变成多个逻辑实体

利用某设备为一个进程服务的空闲时间,转去为其它用户服务,提高设备的利用率

举例

虚拟处理机技术:多个进程并发执行时,虽然系统只有一个处理器,但让每个用户感到自己被分配到一个独立的处理器

虚拟设备技术:如,一台物理实体的打印机,被虚拟成多台逻辑实体的打印机

空分复用

目标

利用存储器的空闲空间分区域存放和运行其它多道程序,提高内存的利用率

本质

需要引入虚拟存储技术,还是用到内存的分时复用,让进程的一部分调入内存运行,运行完成后再调出内存


微内核简介

概念

具有最基本核心功能的小型内核,它不是一个完整的操作系统

基本功能

  • 进程管理

  • 低级存储器管理

  • 中断陷入处理

第二章 进程的描述

程序的执行

一个作业包含多个程序,程序的执行有“顺序”与“并发”两种状态

顺序执行

程序按照指令顺序执行,如果进程不使用cpu,此时cpu就会休息

特点

  • 顺序性:每个操作结束后都有下一个操作

  • 封闭性:程序运行时,独占主机的全部资源,执行结果不受外界影响

  • 可再现性:只要程序执行的环境和初始条件相同,程序重复执行的结果是一样的

并发执行

顺序执行对程序员友好,但系统利用率太低;利用多道批机制,提高系统利用率

特点

  • 间断性:由于资源共享使用,这些并发的进程执行中,可能会需要其它进程运算的结果。就使这些程序形成了相互制约的关系

  • 失去封闭性:由于资源共享,程序在运行时,这些资源的状态由这些程序一起修改;某个程序运行时会受到其它程序的影响

  • 不可再生性:由于失去了封闭性,即使在相同的初始条件下,执行结果可能不同

进程

为了更好的控制并发执行的程序解决并发程序不可再生性的问题,引入进程概念

进程组成

程序段、数据段、PCB

特征

  • 动态性:进程最基本的特征,“由创建而产生,由调度而执行,由撤消而消亡”。

  • 并发性:多个进程实体在同一个内存中,并发执行

  • 独立性:进程是能独立运行独立占用资源独立接受调度的基本单位

  • 异步性:进程按未知的速度、顺序执行(所以需要引入同步进制)

进程与程序区别

  • 动态性:程序是一堆代码的集合,是静态的;进程“由创建而产生,由调度而运行,由撤消而消亡”

  • 并发性:程序没有PCB,不能参与并发执行;因为被中断切换的进程要把当前运行状态保存到PCB中,没有PCB就不能参与并发。

  • 独立性:程序没有PCB,不能参与执行,因为系统通过PCB通知进程的存在,没有PCB不能被分配资源

进程控制块(PCB)

作用

  • 作为独立运行的标志系统通过PCB感知进程的存在拥有PCB的单位才能被分配资源与其它进程通信

  • 能帮助系统实现间断性运行:系统在切换进程时,需要把当前进程运行状态信息保存在PCB中;以便该再次被调度时恢复现场

  • 提供进程管理需要的信息:根据PCB上的信息,查看进程已经使用的资源帮助进程取得需要的数据或I/O设备

  • 提供进程被调度时的信息:提供进程的状态(就绪、阻塞……),以及进程等待cpu时间、已经被运行的时间等信息

  • 与其它进程同步通信:通信队列指针,

进程同步

为了解决进程异步性的问题,让并发执行的进程按一定规则共享系统资源,并相互合作

临界区&临界资源

临界区

每个进程中“访问临界资源的那段程序”叫临界区,“那段程序”叫临界区。

每个进程进入临界区前,先对想访问的临界资源进行检查,如果该资源未被访问,则进程可以进入自己的临界区,并将此资源设置为被访问标志。如果资源正在被访问进程则必须等待

临界资源

每次只能被一个进程访问的资源,如打印机、输入机

进程进入临界区的调度规则

  1. 如果有很多进程要求进入空闲临界区,一次只能进入一个进程

  2. 任何时候,处于临界区的进程不得超过一个

  3. 进入临界区的进程要在有限时间内退出

  4. 如果进程不能进入自己的临界区,应该让出cpu

信号量

整形&记录型信号量

整形信号量:

 wait(S){
     S=S-1;
     while (S<0);
 }
 signal(S){
     S=S+1;
 }

wait(申请资源操作),如果S<=0,就会一直申请(一直while),直到得到了资源;但这不遵守“让权等待”

记录型信号量:

记录型信号量,由于采用记录型的数据结构而得此名字,数据结构如下:

 typedef struct{
     int value;
     struct process *L;//把需要等待的进程入到这个链表
 } semaphore;

wait操作如下:

 void wait (semaphore S) { //相当于申请资源
     S.value--;//先减1!!!再判断,如果传入的S=0了,这个进程就要等待了
     if(S.value<0) {
         add this process to S.L;
         block(S.L);
     }
 }

当信号量S<=0时,会将当前申请的进程添加到“申请链表”,进行自我阻塞放弃处理机,遵循了“让权等待

signal操作如下:

 void signal(semaphone S){
     S.va
 }

读写锁问题

读程序与写程序之间需要一把write_mux,再设置一个reader_count来记录当前读程序的数量,如果旦凡有一个读程序,写程序就不能执行;直到最后一个读程序结束

 semaphone write_mux=1;  //写锁
 semaphone mutex;        //保护写锁的锁
 int reader_count=0;
 void reader(){
     do{
         wait(mutex);//确保在这个过程中不能被打断
         reader_count++;
         if(reader_count==1){
             wait(write_mux);//给写上锁
         }
         signal(mutex);
         
         ……………………//这里是写操作
             
         wait(mutex);//确保在这个过程中不能被打断
         reader_count--;
         if(reader_count==0){
             signal(write_mux);//解开写的锁
         }
         signal(mutex);
     }while(true);
 }
 void writer(){
     do{
         wait(write_mux);//上写锁其它 写进程不能再写
         ………………//写操作
         signal(write_mux);
     }
 }

生产者消息者问题

爸爸进程负责去空盘子里面放水果,每次只能放一个水果,并且水果只能是苹果或者香蕉,如果是苹果,通知女儿进程取走吃掉;如果是香蕉通知儿子进程取走吃掉

结构体如下

 struct semaphone{
     int value;
     struct porcess *L;
 }

代码如下

 semaphone mutex_apple=0,mutex_banana=0,mutex=1,need=1;//need默认盘子为空,就是需要放一个水果,mutex为了保护放水果不被打断
 void father(){
     do{
         wait(need);//need如果小于等于0,说明现在不需要放水果,否则就要放水果
         wait(mutex);
         if(判断是放苹果){
             signal(mutex_apple);//现在apple增加1,可以拿
         }else{
             signal(mutex_banana);
         }
         wait(mutex);
     }while(true);
 }
 void son(){
     do{
         wait(mutex_banana);//如果香蕉不为空,则可以拿
         wait(mutex);//把盘子锁住,别人不能放或者拿
         ……//拿水果
         signal(need);//告诉父亲,需要一个水果
         signal(mutex); 
         
     }while(true);
 }
 void daughter(){
     do{
         wait(mutex_apple);
         wait(mutex);
         ……//拿水果
         signal(need);//告诉父亲,需要一个水果
         signal(mutex); 
         
     }while(true);
 }

线程

为了进一步提高进程并发能力减少并发执行时付出的时空开销,引入了比进程更小的基本单位---线程

由于进程在创建、切换、撤消时,系统需要付出巨大的开销,因而限制了进程的数目;

引入线程,让线程作为调度的基本单位;在线程发生切换时,仅需保存少量内容,线程切换代价远低于进程切换

特征

  • 并发性:同一个进程的不同线程可以并发;不同进程的不同线程可以并发

  • 拥有资源:进程拥有资源的一个基本单位线程仅拥有必不可少的资源

  • 独立性:进程之间独立性较高;线程因为需要合作,独立性较低,它们共享同一进程的全部资源

TCB

线程控制块

与进程控制块类似,也有以下内容

  • 线程唯一标识

  • 线程运行状态

  • 一组寄存器,包括程序计数器PC

  • 线程存储区,用来记录线程被切换时的现场状态

  • 线程优先级

线程实现

内核实现

线程的创建、阻塞、撤消、切换都是在内核空间实现的

优点:

  • 内核可以让同一个进程的不同线程并发执行

  • 某个线程被阻塞时,这个进程的其它线程可以正常运行

用户级实现

在用户空间实现,用户级线程与内核无关。内核不知道用户级线程的存在

缺点:(对应内核实现的优点)

  • 某个线程被阻塞时,这个进程的所有线程都被阻塞

  • 一个进程只有一个cpu,这个进程下的所有线程使用同一个cpu

第三章 cpu调度

三种调度方式

低级调度

又称为进程调度、短程调度,它决定就绪队列中的哪个进程将获得处理机 ,然后由分派程序执行把处理机分配给该进程的操作。 在批处理,分时,实时三类系统中,必须有低级调度,因而是一种最基本的调度

中级调度

又称为中程调度,引入中级调度的主要目的是为了提高内存的利用率和系统的吞吐量。 内存中不能有太多的进程,把进程从内存移到外存,当内存有足够空间时,再将合适的进程换入内存,等待进程调度 。 中级调度实际上就是存储器管理 中的对调功能

高级调度

又称为作业调度,高级调度的主要功能是根据某种算法,把外存上处于后被作业队列中的那些作业调入内存,也就是说它们的调度对象是作业

作业与进程

作业:

作业是用户向计算机提交任务的任务实体。用户提交作业后,系统将它放入外存作业等待队列

进程:

进程是完成用户任务的执行实体。是向系统申请分配资源的基本单位

一个作业可以由多个进程组成,而且必须至少由一个进程组成;

作业与进程的区别

作业主要用在批处理系统

进程用在多道程序系统,是进行资源分配的单位

作业调度算法:

  1. 先来先服务算法(FCFS)

  2. 短作业优先算法(SJF)

  3. 优先级调度算法(PSA)

  4. 高响应比优先调度算法(HRRN)

优先级=(等待时间/要求服务时间)+1

进程调度

三个步骤

  • 保存被切换进程的处理机状态

  • 根据进程调度算法,从就绪队列中取得一个进程

  • 将处理机分配给这进程

进程调度算法

  1. 轮转调度算法

  2. 优先级调度算法

  3. 多队列调度算法

  4. 多级反馈队列调度算法

  5. 基于公平原则的调度算法

优先级调度

也分为抢占与非抢占式

非抢占

将处理机分配给进程后,即使有其它高优先级进程,也不得抢占,必须当前进程执行完成后;或当前进程主动放弃处理机

抢占式

只要有高优先级进程,就可以抢占当前低优先级进程(适合实时性系统

多级反馈队列

调度机制:

1、设置多个就绪队列每个队列赋予不同的优先级,第一个队列的优先级最高,越往下越低。但第一个队列的时间片最少,越往下越多

2、每个队列都用FCFS算法

如:某个进程先放入第一队列末尾,如果时间片用完,进程尚未结束,调度程序到第二队列的末尾,以此类推

3、按队列优先级调度

如:如果优先级高的队列不为空,就必须先执行高队列,否则再执行低优先级队列进程。

如果当前某个低优先级队列中进程获得了处理机,但有个高优先级进程加入,也要把当前进程放回到原队列中,并执行高优先级队列进程。

调试性能:

对于不同类型用户都有不错的效果

1、终端型,由于终端型用户提交的多数为交互型作业,运行时间少,在第一队列即可完成

2、短批处理,在第一队列或第二队列即可完成,周转时间也较短

3、长批处理用户,对于长作业,在第1、2、N队列后依然可以轮转运行,不会长期饥饿

时间片轮转算法

分配的是处理机资源,在不考虑线程的系统中,进程获取资源并被独立调度的最小单位

时间片轮转是针对进程的算法

举例:

Snipaste_2021-12-05_15-26-36

忽略I/O以及其它开销时间,若分别按先来先服务(FCFS)、非抢占的短进程优先(SPF)调度算法进行CPU调度。请给出各进程的完成时间、周转时间、带权周转时间、平均周转时间和平均带权周转时间。

(1)先来先服务

周转时间=完成时间-到达时间

带权周转时间=周转时间/服务时间

进程 到达时间 服务时间 开始时间 完成时间 周转时间 带权周转
A 0 4 0 4 4 1
B 1 3 4 7 6 2
C 2 5 7 12 10 2
D 3 2 12 14 11 5.5
E 4 4 14 18 14 3.5

平时周转时间:(4+6+10+11+14)/5

平时带权周转时间:(1+2+2+5.5+3.5)/5

(2)短进程优先

A最先到达,此时的最短进程只有A;A服务完成时,已经有多个进程都到达,此时需要找到一个最短服务时间的进程

进程 到达时间 服务时间 开始时间 完成时间 周转时间 带权周转
A 0 4 0 4 4 1
D 3 2 4 6 3 1.5
B 1 3 6 9 8 2.67
E 4 4 9 13 9 2.25
C 2 5 13 18 16 3.2

平时周转时间:(4+3+8+9+13)/5

平时带权周转时间:(1+1.5+2.67+2.25+3.2)/5

死锁产生的四个必要条件

不可抢占、循环等待、请示与保持、互斥条件

互斥条件

资源一次只能被一个进程调用

请示与保持

进程至少已经占用了一个资源,并提出新的请示

不可抢占

除非进程主动释放资源,否则其它进程不可抢占

循环等待

发生死锁时,需要有“资源-等待”环型链

解除死锁

必须打破三个必要条件中的一个,(互斥条件是资源共享的特性,不能打破)

如:

  • 进程要请示新资源时,需要将已经保持资源释放

  • 进程必须在运行前,一次性申请完所有需要的资源,否则不能运行

  • 对所有资源进行排序并赋予不同序号

避免死锁

将系统分为安全、不安全状态;当系统处于安全状态时,可以避免死锁发生。

使用银行家算法可以避免死锁

举例:

Snipaste_2021-12-05_15-11-26

(1)该状态是否安全?

存在一个安全序列A=>C=>E=>D=>B

其中available+allocation是当前系统剩余的

进程 available allocation need available+allocation
A 1 2 0 3 1 1 1 0 0 4 3 1
C 4 3 1 1 1 0 3 0 0 5 4 1
E 5 4 1 0 0 0 2 1 0 5 4 1
D 5 4 1 1 0 1 0 1 0 6 4 2
B 6 4 2 0 0 0 0 1 2 6 4 2

第四章 存储器管理

多层结构存储器系统

为了使读取速度、存储容量、价格三个条件相互平衡

程序的装入

程序从外存中装入内存,需要修改程序的地址

绝对装入

程序的相对地址实际物理地址相同

仅能用于单道程序”,要求程序员熟悉内存使用情况

可重定位装入

这个也叫“静态重定位”,静态表现在:装入到内存的地址已经全部被修改过

  • 程序装入到内存后,立即把所有的逻辑地址转换成实际地址

  • 实际物理地址由程序的相对地址加偏移量构成,而偏移量是根据内存使用情况动态变化

适合于“多道程序”,程序员不用考虑实际内存情况

运行时动态装入

也称为“动态重定位”,动态表现在:只有执行程序时才转换地址

把程序装入到内存后,不立即修改对应的逻辑地址,而是在程序真正执行时才转换成实际地址

程序的链接

静态链接

静态链接,指在程序运行前,将各种目标模块需要的库函数链接成一个完整的装配模块

要解决的两个问题:

修改相对地址:

不同模块的相对首地址都是0,链接到一个完整的模块后,需要指定唯一首地址

如:有三个模块A、B、C,长度分别为L、M和N;链接成一个完整模块后,B、C的首地址就不是0

  • A首地址为0,A末尾地址为L-1;

  • B首地址为L,B末尾地址为L+M-1

  • C首地址为L+M,C末尾地址为L+M+N-1

更换外部调用符号:

如:A模块内部调用了B模块,语句为“call B;”,但链接到一个完整模块后,需要修改成B所在的相对地址

  • A调用B,从call B变为jsr L (L为B首地址)

  • B调用C,从call C变为jsr L+M (L+M为C首地址)

装入时动态链接

把一个模块装入内存时,如果该模块调用了其它模块,再把被调用模块装入内存并链接

优点:

方便修改和更新模块

各种模块分开存放,方便修改模块内容。不像静态链接,需要对一个完整的模块重新打开再修改

方便对目标模块共享

  • 静态链接,每个应用模块调用其它目标模块时,装入的是其它目标模块的拷贝不能实现共享

  • 动态装入,一个目标模块可以被链接到几个不同应用模块

运行时动态链接

程序运行时,部分目标模块可能不会被用上,但也被装入了应用模块,这样很低效

当程序运行时,如果某个被调用模块未被装入,才将其装入内存链接

*连续分配存储管理方式

动态分区分配

使用的数据结构:

  • 空闲分区表

  • 空闲分区链

每个分区的起始位置设置一些控制分区分配的信息,以及在分区首设置一个前向指针,在分区末尾设置一个后向指针,用来将不同空闲分区链接成一个双向链表。

分配算法

  • 基于顺序式搜索算法

  • 索引式算法

分配操作

  • 分配内存

按某种分配算法,从空闲分区链或分区表中,找到一个合适的分区

如果分区内一部分满足要求,则切割分区;否则整个分区都给出

  • 回收内存

回收时,要考虑当前分区与前后分区的状态,是否需要合并:一共有四种情况,与前分区接壤;与后分区接壤;同时与前后接壤;与前后都不接壤

基于顺序搜索

空闲分区构成一个链,按照顺序搜索空闲分区,找到一个大小能满足要求的分区。

适合不大的系统,当系统大时,内存分区很多,使用顺序搜索查找会变慢

1、首次适应

链首开始查找,直到找到一个能满足要求的空闲分区,现在此分区划分一片空间给进程

2、循环首次适应

上次找到的空闲分区的下一个分区开始查找,直到找到一个满足要求的分区

3、最佳适应

找一个能满足要求,而且是最小的空闲分区

4、最坏适应

当前最大的分区,分割一部分给进程

缺点:导致系统缺少大分区

基于索引搜索

1、分类搜索

将空闲分区按容量大小进行分类,每类有相同容量的构建一个分区链表。

按照进程长度,从索引表中找到能满足条件的最小的分区链表,再从链接中找到一个分区


以上的顺序搜索、索引搜索都是连续分配方式;缺点是很多小分区不能被利用

动态重定位分区分配

紧凑

将原来分散的多个小分区,合并成一个连续的大分区

让系统对内存更方便的进行紧凑,减少无法被利用的小分区。

但每次紧凑后,原来的程序会找不到这些数据的位置,系统需要对全部的数据地址进行修改,更加麻烦!!!

动态分区分配

与装入时的“动态重定位”相似,在程序被装入时,不修改逻辑地址,但引入一个重定位寄存器,寄存器里面存入真正在内存中的地址

程序在执行时,真正的访问的内存地址是逻辑地址加上重定位寄存器地址,随后再更新重定位寄存器

动态重定位分区分配

在动态分区分配基础上,添加紧凑功能

原来的紧凑,需要修改代码的所有数据地址,非常麻烦!!!

但使用动态分区分配时,代码的数据地址还是原来的逻辑地址,只要修改重定位寄存器的地址就行

这样使紧凑相对更方便

对换

对换的引入

某些因缺少资源而阻塞的进程占用了大量内存空间,而有些进程因为缺少内存空间一直停留在外存。此时需要提高系统吞吐量,设置了对换。

对换的类型

整体对换

cpu的中级调度实际就是对换功能,将整个程序从内存中换出,把外存中程序换入

部分对换

不把整个进程的代码和数据全部换出,只对换一部分

如果按进程的一个“页面”或“分段”为单位,则称为“页面对换”或“分段对换”。

磁盘中两种空间的管理

对换空间的管理

对换空间是在磁盘中小部分,用来临时存入从内存中换出的进程

特点

  • 对换的停留在磁盘的时间短

  • 访问的频率高

  • 使用连续分配内存方式(上面提到的几种动态分配方式)

主要需要提高对换空间的换入、换出速度

文件区管理

文件区是磁盘大部分内容,存放各种文件。

特点

  • 长期停留在磁盘中

  • 访问频率低

  • 使用离散分配内存方式(下面要提到的分页、分段方式)

主要需要提高文件区的利用率,其实是提高访问速度

*离散存储管理方式

连续分配内存,是将整个进程完整的装在一片连续空间,但这样还是不能充分利用空间

进程分散地装在不同的不相邻的分区,可以极大提高利用率

三种方式概念

  • 分页存储管理

程序的地址空间分成若干个固定大小“页”,如1KB

将内存空间分成对应的“物理块”

程序的任何一页,可以放到任何一块中

  • 分段存储管理

程序地址空间分成若干大小不同的段

程序的每段在内存中也分散分配

  • 段页式管理

将两种分类方式结合

分页存储

进程逻辑地址空间分成若干个固定大小页面,页面强调是进程的逻辑地址合集

内存物理地址空间分成若干个同大小,块强调是内存的物理地址合集

程序的任何一页,可以放到任何一块中

页面大小

若页面容量过小,可以减少页内碎片同时,每个进程需要的页面数目就增多了,就需要更多的页表来记录,也会占用大量内存

若页面容量过大,每个进程需要的页面数目减少,增加了换进换出速率增加了页内碎片

合适的页面大小为2的幂,1KB~8KB

页表

为了能在内存找到每个页面对应的,系统为每个进程建立一张页面映像表,简称页表

页表记录的是每个页面对应的物理块号

分段存储

引入分段,主要是方便程序员使用;如一个程序有主代码段、子程序A段、子程序B段……

特点

  • 方便编程:每个子程序一个段

  • 信息共享:可以把被共享的信息独立成一个段,比分页存储实现信息共享方便

  • 信息保护:每个段可以设定只读、只写等保护属性

  • 动态增长:段长度不固定,存放数据非常方便

  • 方便动态链接:在不同模块链接时,让每个段作为一个基本单位,非常适合动态链接

段页式存储

将程序先分成几个段,每个段又分成几个页;

段号、段内页号、页内地址

地址变化过程

img

需要一个段表寄存器,记录段表开始地址段表总长度

段号如果小于总长度,说明有效

段地址=段号(逻辑地址上的)*段表大小+段表开始地址

通过段地址,得到页表的开始地址页表大小

页号=页表号(逻辑地址上的)*页表大小+页表开始地址

再通过页号,按页号查找页表,找到物理块地址

真实物理地址=物理块地址+页内地址


第五章 虚拟存储器

100G的游戏可以在内存16G电脑运行,利用的就是虚拟存储技术

引入虚拟存储器前,先了解常规存储器的不足

1、一次性:

  • 作业必须一次性全部装入内存后才能开始运行。导致大作业无法在小内存运行

2、驻留性:

  • 作业被装入内存后,整个作业都一起驻留在内存中,其中任何部分都不会被换出,直到作业运行结束。

3、影响:

  • 一次性与驻留性,让许多程序运行中不用或暂时不用的数据占据了大量空间

虚拟存储器定义

具有“请求调入功能和置换功能”,从逻辑上内存容量进行扩充的存储器系统

特征

  • 多次性

将当前进程必不可少的数据和代码装入内存即可运行。其它需要的部分可以动态请求装入

  • 对换性

不用的数据和代码调到外存,将需要的数据和代码从外存中调入

  • 虚拟性

虚拟性只是表现,是建立在多次与对换基础上。

虚拟存储器实现方法

分页请求系统

在分页存储系统上,添加请求调页和页面置换功能,体现了虚拟存储器的多次性

需要以下硬件

  • 分页的页表机制

  • 缺页中断机构,当进程某页不在内存时,发出缺页中断请求

  • 地址变换机构,在分页地址变换机构发展

分段请求系统

在分段存储系统上,添加请求调段和分段置换功能,体现了虚拟存储器的多次性

需要以下硬件

  • 分段段表机制

  • 缺页中断机构,当进程某页不在内存时,发出缺页中断请求

  • 地址变换机构,在分段地址变换机构发展

分页请求存储管理

三种硬件机制

两种实现都需要三种硬件,下面为三种硬件的实现

分页的页表机制

页表包含以下选项,页表存储在外存/内存中

页号 物理块号 状态位 访问字段A 修改位 外存地址
  • 状态位,若为1,则表示当前页在内存中;否则,当前页在外存

  • 访问字段:本页面被访问的次数,给页面置换算法进行参考

  • 修改位:如果当前页被调入内存,没有被修改,就不需要写回到外存;否则当前页被修改,需要写回到外存

缺页中断机构

进程的某页不在内存,需要发出缺页中断

  • 立即产生中断信号,cpu立即处理中断

地址变换机构

查看源图像

页面置换算法

最佳置换算法

一种理想化的算法,实际上无法实现

选择未来或很长时间内不会被用上的页面,进行换出

最近最久未使用

LRU

将最久没被使用的淘汰

需要有寄存器记录每个页面被使用的次数

使用栈

进程访问某个页面时,将这个页面从栈中移出,压入栈顶

4,7,0,7,1,0,1,2,1,2,6

4 7 0 7 1 0 1 2 1 2 6
2 1 2 6
1 0 1 1 2 1 2
0 7 7 1 0 0 0 0 1
7 7 0 0 7 7 7 7 7 0
4 4 4 4 4 4 4 4 4 4 7

最后,6进入时,把最久未被使用的4剔除;越是栈底的,就是越久没被使用

最少使用

LFU

分段请求存储管理

请求段表机构

段名 段长 段基址 存取方式 访问字段A 修改位M 存在位P 增补位 外存地址
  • 存取方式:只执行、只读、允许读写

  • 访问字段A:被访问的次数

  • 修改位M:如果没被修改无需写回到外存

  • 存在位P:如果P=1,说明已经在内存中

  • 增补位:分段特有,是否动态增长过

中断处理机构

查看源图像

地址变换机构

查看源图像

页面缓冲算法

特点

  • 降低了页面换进、换出的频率

  • 因为降低了页面换进、换出的频率,才可以使用简单的置换算法,如先进先出算法

方法

下面两个链接都是系统掌握的空闲物理块

  • 空闲页面链表

当有一个未被修改的页面换出时,系统不立即写回到外存,而是加载到空闲链表后面

  • 修改页面链表

当有一个被修改的页面换出时,也不立即写回外存加载到修改页面链表


第六章 输入输出系统

I/O系统基本功能

  1. 方便用户使用I/O设备

  2. 提高I/O设备的利用率

  3. 保证用户在使用设备时提供方便,保证系统能够有条不紊的运行

I/O软件层次结构

  1. 用户层软件:提供与用户交互接口,用户可以直接调用接口以对设备进行操作

  2. 设备独立性软件:设备命名保护分配释放,提供数据存储空间

  3. 设备驱动软件:将上层发来的“抽象的”I/O请求,转成“具体的”请求,再发给设备控制器

  4. 中断处理程序:保护中断进程的cpu环境,并转入相应的中断处理程序,再恢复被中断进程的cpu环境,并从中断点继续运行。

以下为I/O系统中各种模块之间的层次视图

查看源图像

根据图,从上到下,为I/O系统接口,独立性软件,驱动、中断处理

I/O系统接口

这里的接口,是I/O系统对高层的接口

块设备接口

块设备,指数据的存取传输都是以数据块为单位的设备。如:磁盘

通常采用,DMA方式

流设备接口

字符设备接口,用于控制字符设备的输入或输出。

如:键盘,打印机这种低速

通常采用,中断方式

I/O设备

I/O设备由“执行操作的机械部分”与“执行控制I/O电子部件”组成

机械部分叫作:一般的I/O设备

电子部件叫作:设备控制器适配器

I/O设备类型

存储设备如:外存

I/O设备如:键盘、鼠标、扫描仪

I/O设备与设备控制器之间的接口

设备不是直接与cpu进行通信,设备是与设备控制器通信

接口使用了三个信号线

  • 数据信号线:设备与设备控制器传送数据

  • 控制信号线:设备控制器向I/O设备发送控制信号

  • 状态信号线:用来传送当前设备的状态信号

对I/O设备的控制方式

  • 轮询

cpu循环等待I/O设备完成,需要不断测试设备状态,非常浪费cpu时间

  • 中断方式

cpu向设备控制器发送命令,然后cpu继续做其它进程,控制器完成命令后,向cpu发出中断

DMA方式

特点

  • 传输单位是数据块

  • 直接将I/O设备数据存入内存,或从内存读取数据到I/O设备

  • 只有开始或结束传送数据块时,才会有cpu介入

组成

  • 主机与DMA接口

  • DMA与设备接口

  • I/O控制逻辑

演示

  • cpu将需要本次目标存入地址送到MAR

  • cpu将需要读入的数据长度送到计数器

  • cpu将源地址送到DMA控制器

  • cpu忙其它的,DMA开始工作


I/O设备控制器

作用:控制一个或多个I/O设备,实现I/O设备与cpu之间的数据交换。

基本功能:

  • 接收&识别命令:接收并识别处理器(cpu)发送的命令,并将命令存入控制寄存器

  • 数据交换:控制器实现的是设备与cpu之间的数据交换,将数据存入数据寄存器

  • 标识&报告设备的状态:控制器将设备的状态发送给cpu

  • 地址识别:控制器需要识别控制的每个设备的地址

  • 数据缓冲:cpu速度快,将高速的cpu发送的数据缓存到数据寄存器,以匹配与I/O设备不同速率

组成

  • 控制器与cpu的接口:实现控制器与cpu的通信(需要有数据线、地址线、控制线,以及对应的数据寄存器状态/控制寄存器

  • 控制器与设备的接口:一个控制器有一个或多个与设备连接的接口,每个接口有对应的数据线、地址线、控制线;控制器根据cpu逻辑,找到对应的设备接口传输信息。

I/O通道

现在,cpu与设备之间的通信,有了设备控制器作为中介;

但为了进一步减少cpu的负担,在cpu与设备控制器中间,再加一个“I/O通道”,让cpu从繁杂的I/O任务中解脱,提高cpu处理数据的利用率

cpu
I/O通道
设备控制器
设备

特点:

I/O通道是一个特殊的处理机,它与cpu共享内存

原因:

I/O通道只接受cpu的I/O指令,然后从内存中取出本次要执行的通道程序,再执行该通道程序;执行完成后,I/O通道向cpu发出中断

I/O通道控制方式

I/O通道控制是DMA的升级版本,从一个数据块的读写,改成以一组数据块读写

举例:

cpu需要完成一组读写操作时,向I/O通道发送I/O指令,给出要访问的I/O设备通道程序首地址

通道程序

通道指令包含以下内容

  • 操作码:规定了指令执行的操作:读、写

  • 内存地址:字符送往内存的地址和从内存中读出的地址

  • 计数:要读或要写的数量


中断机构

中断机构是I/O系统的最低的一层,是I/O系统的基础,之前的设备控制器不属性I/O系统

中断

中断是cpu对I/O设备发来的中断信号一种响应

cpu停止当前执行的进程,并保存当前处理机信息到寄存器中,随后去执行中断请求。执行完成后,再恢复原来进程的现场,再执行原断点处理继续执行

由于这种中断来自cpu外部,也叫外中断

陷入

由cpu内部运算时,发生溢出或其它错误。叫内中断或陷入

中断向量表

每个设备对应一个中断处理程序,把这个信息填写到一个中断向量表中,这个设备对应一个中断号,和一个中断处理程序的入口地址

中断号 中断程序入口地址 某个设备
111 1100011 键盘K键

多个中断源的处理方式

屏蔽中断源

cpu处理一个中断时将屏蔽其它的所有中断,这些中断会自动添加到一个等待链表

嵌套中断

cpu会处理优先级高的中断,高优先级中断可以抢占低优先级中断

设备驱动程序

设备驱动程序是I/O系统高层设备控制器之间的通信程序

功能

  • 将高层发来的抽象的命令转换成具体的要求后,发送给设备控制器,再由控制器让设备执行

  • 控制器发来的信息传送给高层

I/O系统高层
设备驱动程序
I/O设备控制器
I/O设备

处理过程

  • 将抽象过程置换成具体要求

  • 对服务请求进行校验,拒绝非法的请求:如从打印机计入数据

  • 检查设备的状态

  • 传送必要的参数

  • 启动I/O设备:驱动程序控制器发送命令

设备无关I/O软件

I/O系统最上层的

  • 应用程序使用的设备不局限某个具体设备

  • 在设备驱动程序上层再设置一个“设备无关性软件”层

THE END
分享
二维码
< <上一篇
下一篇>>
文章目录
关闭
目 录