操作系统
进程三种状态级变化
在操作系统中,进程是程序在操作系统中的一次执行过程。进程状态指的是进程当前在操作系统中的状态。在操作系统中,进程状态主要分为三种:就绪状态、运行状态和阻塞状态。
- 就绪状态:指进程已经准备好运行,并等待系统分配资源来运行。就绪状态的进程通常处于等待处理器分配资源的状态。当处理器空闲时,操作系统会选择一个就绪状态的进程来运行。
- 运行状态:指进程正在执行,处于正在占用处理器的状态。在进程处于运行状态时,它将占用处理器并执行相应的操作。当进程的时间片用完时,它将被从运行状态转换为就绪状态。
- 阻塞状态:指进程因为某些原因(例如等待输入/输出、等待资源等)而暂时停止运行,并等待操作系统的唤醒。在阻塞状态下,进程不会占用处理器。
进程状态在操作系统中是动态变化的。当一个进程从一个状态转换到另一个状态时,它被称为状态变化。在进程状态之间进行转换的因素包括处理器分配、等待资源、等待输入/输出等。状态变化如下:
- 就绪状态变为运行状态:调度
- 运行状态变为就绪状态:时间片用完
- 运行状态变为阻塞状态:I/O请求
- 阻塞状态变为就绪状态:I/O完成
进程的组成
程序段、数据段、进程控制块(PCB)。
程序段是进程要执行的指令集
数据段则用于存储进程需要的数据。
进程控制块(PCB)则包含了进程的各种状态信息,如当前状态、进程ID、优先级等。此外,PCB还包含了进程的上下文信息,如处理器寄存器的值、虚拟地址空间的映射等。PCB可以被看作是操作系统对进程的管理单元,操作系统通过管理PCB来控制进程的运行和调度。
信号量的变化范围
P操作(wait)
P(semaphore s) {
s.value--;
if (s.value < 0) {
add this process to s.wait_queue;
block();
}
}
V操作(signal)
V(semaphore s) {
s.value++;
if (s.value <= 0) {
remove a process from s.wait_queue;
wakeup(process);
}
}
银行家算法
Work,Allocation(已分配的,Need(Max-Allocation),Work+Allocation,Finish
- Request≤Need
- Request≤Available,满足这两条就说该进程能够请求到资源
- 改表(Allocation+Request,Need-Request,剩余资源减少后Available重新推)
假定系统中有五个进程 (P0. P1, P2 P3, P4) 和三类资源 [A, B, C] , 各种资源的
数量分别为10, 5, 7, 在T0时刻的资源分配情況如图所示
Max(ABC) | Allocation(ABC) | Need(ABC) | |
---|---|---|---|
P0 | 7 5 3 | 0 1 0 | 7 4 3 |
P1 | 3 2 2 | 2 0 0 | 1 2 2 |
P2 | 9 0 2 | 3 0 2 | 6 0 0 |
P3 | 2 2 2 | 2 1 1 | 0 1 1 |
P4 | 4 3 3 | 0 0 2 | 4 3 1 |
- T0时刻的安全性
- P1请求资源: P1发出请求向量Request, (1, 0, 2), 系统按银行家算法进行检
查: - P4请求Request, (3, 3, 0)。。。。。。
Work(ABC) | Allocation(ABC) | Need(ABC) | Work+Allocation | Finish | |
---|---|---|---|---|---|
P1 | 3,3,2 | 2,0,0 | 1,2,2 | 5,3,2 | T |
P3 | 5,3,2 | 2,1,1 | 0,1,1 | 7,4,3 | T |
P4 | 7,4,3 | 0,0,2 | 0,1,1 | 7,4,5 | T |
P0 | 7,4,5 | 0,1,0 | 7,4,3 | 7,5,5 | T |
P2 | 7,5,5 | 3,0,2 | 6,0,0 | 10,5,7 | T |
-
剩余资源Available为332(10,5,7-Allocation=3,3,2),
能找到一个安全序列:P1→P3→P4→P0→P2,安全
-
1,0,2≤1,2,2
1,0,2≤3,3,2
该进程能够请求到资源
此时表为:
Max(ABC) Allocation(ABC) Need(ABC) P0 7 5 3 0 1 0 7 4 3 P1 3 2 2 3 0 2 0 2 0 P2 9 0 2 3 0 2 6 0 0 P3 2 2 2 2 1 1 0 1 1 P4 4 3 3 0 0 2 4 3 1 此时剩余资源总数Available为 2 3 0
Work(ABC) | Allocation(ABC) | Need(ABC) | Work+Allocation | Finish | |
---|---|---|---|---|---|
P1 | 2,3,0 | 3,0,2 | 0,2,0 | 5,3,2 | True |
P3 | 5,3,2 | 2,1,1 | 0,1,1 | 7,4,3 | True |
P4 | 7,4,3 | 0,0,2 | 4,3,1 | 7,4,5 | True |
P0 | 7,4,5 | 0,1,0 | 7,4,3 | 7,5,5 | True |
P2 | 7,5,5 | 3,0,2 | 6,0,0 | 10,5,7 | True |
P1→P3→P4→P0→P2发现是安全的
-
3,3,0≤4,3,1
3,3,0>2,3,0 则P4不能分配成功
CPU、内存、外存结构
存储层次(高到低):CPU寄存器,主存,辅存
相关临界区
临界资源指的是同时只能由一个进程访问的资源,例如打印机、磁盘等。由于多个进程可能同时需要访问这些资源,因此需要通过临界区来保证资源的正确性和一致性。
临界区是指一个访问临界资源的代码段,同时只能由一个进程访问,其他进程需要等待当前进程执行完临界区代码后才能进入临界区。
为了保证临界区的正确性和稳定性,操作系统提供了多种同步机制,例如信号量、互斥量等。
静态地址重定位
程序装入内存有三种装入方式:
绝对装入方式: 在计算机只能运行单道程序时,将程序的绝对地址直接装入内存2
可重定位装入方式:在多道程序环境下,每个程序的起始地址都为0,将这些地址加上实际要装入的物理地址的起始位置后才装入内存(静态)这个相加的过程就叫重定位
动态运行时的装入方式:装入实际内存的时候并不修改地址,而是等程序进行运行时配合上重定位寄存器将其地址转换为真正的物理地址,使用重定位寄存器的与原因是为了不影响指令的执行速度
存储管理功能
四大功能: 分配 保护 扩充 回收 (分配和回收最重要)
连续地址分配方式:
单一连续分配: 单道程序系统
固定分区分配: 将用户空间划分成多个固定的大小空间,每个分区只能装入一个作业(大小可不等,但固定) 是最早出现的用于多道程序系统中的存储管理方式
动态分区分配时涉及到三个问题: 动态分区分配的数据结构,动态分区分配算法
数据结构:
空闲分区表(分区号,分区大小,分区起始地址,状态)
空闲链结构
分区分配算法:
首次适应算法:从内存首地址开始,只要大小够就分配
低地址不断的被划分,会留下许多难以重新利用的极小空间(也就是碎片)
优点是会有很多大的空闲分区
解决碎片的办法是使用紧凑技术或分页技术,就是把多个分散的小分区拼接成一个大分区
循环首次适应算法:和首次适应算法不同的是:从上一次分完的地址开始找
能使空闲分区分布更均匀,缺点是会缺乏大的空闲分区
最佳适应算法:以内存的分区从小到大排序后找到第一个能够放下的
最坏适应算法:以内存的分区从大到小排序后找到第一个能够放下的
产生碎片的几率最小,有利于中、小作业,查找效率高
离散地址分配方式:
分页存储管理方式:将程序的地址划分为多个固定大小的页(1~8KB),将内存划为和页一样大的块(一维)
进程的最后一页往往不能装满一整个块,就会形成页内碎片
页面越小越好,因为这样就能减少碎片提高内存利用率,但是会导致页表过长,占据内存,降低效率
地址结构:页号P、偏移量W(页内地址)
逻辑地址位数=页号位数+偏移量位数
偏移量为12位则每页2^12 =4KB,页号为20位,则地址空间最多允许有道2^20=1M页
逻辑地址为A,页面大小为L,求页号(A//L)和偏移量(A%L)
物理地址=物理块号*页面大小+偏移量
页表结构:页号,块号 根据程序中得页号找到页表中得块号,再根据块号取内存
分段存储管理方式:(二维)将程序的地址分为多个大小不定的段,每段存储一组相对完整的信息
段页式存储管理:结合了以上两种的方式,是使用最广的存储管理方式
页表的作用
页表是用来实现逻辑地址到物理地址的映射的数据结构。它的主要作用是记录每个逻辑页面(页号)与其对应的物理块(物理页面)之间的映射关系并进行相互转换。页表还能通过在页表中设置相应的权限位来保护系统的安全性和稳定性。
磁带的存储
顺序存储
可变分区中空闲区的合并
在可变式分区方案中, 某一作业完成后,系统回收期主存空间, 并与相邻空闲区合并,为此需要修改空闲区表, 造成空闲区数减1的情况是:D
A 无上邻空闲区, 也无下临空闲区 +1
B 有上邻空闲区, 但无下临空闲区 不变
C 有下邻空闲区, 但无上临空闲区 不变
D 有下邻空闲区, 也有上临空闲区 -1
在将一个新空闲可用区插入可用表时,该空闲区和上下相邻区的关系是下述4种关系之一:
a)该空闲区的上下两相邻分区都是空闲区:将三个空闲区合并为一个空闲区。新空闲区的起始地址为上空闲区的起始地址,大小为三个空闲区之和。空闲区合并后,取消可用表中下空闲区的表目项,修改上空闲区的对应项。
b)该空闲区的上相邻区是空闲区:将释放区与上空闲区合并为一个空闲区,其起始地址为上空闲区的起始地址,大小为上空闲区与释放区之和。合并后,修改上空闲区对应的可用表的表目项。
c)该空闲区的下相邻区是空闲区:将释放区与下空闲区合并,并将释放区的起始地址作为合并区的起始地址。合并区的长度为释放区与下空闲区之和。同理,合并后修改可用表中相应的表目项。
d)两相邻区都不是空闲区:释放区作为一个新空闲可用区插入可用表
多道程序设计的目的
多道程序设计的目的是提高资源利用率,增加用户的吞吐量,减少用户的等待时间,提高系统的吞吐量和效率。
设计原理:在计算机内存中同时存放几道相互独立的程序,它们在管理程序的控制下相互穿插地运行,共享CPU和外设等资源。采用多道程序设计技术的批处理系统称为多道批处理系统
逻辑地址的定义
逻辑地址指的是程序中使用的地址,也称虚拟地址。在程序中,使用的地址通常是相对于程序起始位置的偏移量。在程序执行时,需要将逻辑地址转换为物理地址才能访问内存中的数据。逻辑地址的转换通常由操作系统中的内存管理单元来完成。
逻辑地址一般在程序中使用,在逻辑空间中每条指令的地址和指令中要访问的操作数地址统称为逻辑地址
分页存储中逻辑地址,物理地址的构成
逻辑地址由页号和页内偏移量构成
物理地址=页号*页面大小+偏移量
逻辑地址转化为物理地址
例:在一分页存储管理系统中, 逻辑地址长度为16位,页
面大小为4096字节, 现有一逻辑地址为2F6A,且第0,1,2页依
次存放在物理块5,10,11中, 问相应的物理地址为多少?
逻辑地址长度16意味着16=页码位数+偏移量位数
已知页面大小为4096字节,页面位数就为12位,也就是偏移量位数
则页码位数为16-12=4,十六进制位数为1
上面的页码位数也能用A//L来求
这里的逻辑地址为2F6A,已知页码为第一位2,则对应的物理块是11
物理地址=物理块号*页面大小+偏移量
物理地址=11*4096+F6A=BF6A
例:考虑一个由8个页面, 每页有1024个字节组成的逻辑空间,
把它裝入到有32个物理块的存储器中,问:
(1) 逻辑地址需要多少二进制位表示?
8=2^3 1024=2^10 3+10=13位
(2) 物理地址需要多少二进制位表示?
共有32个物理块,每块能放1024B,则共=32*1024=25*210=2^15
所以需要15位
例:在采用页式存储管理的系统中, 某作业J的逻辑地址空间为4页 (每页2048字节) , 且第0,1,2,3页依次存放在物理块2,4,6,8中,现有一逻辑地址为4865, 问相应的物理地址为多少?
页码位数=4865//2048=2
偏移量=4865%2048=769
2对应的物理块为6,6*2048+769=13057
例: 一台计算机为每个进程提供65536B的地址空间, 划分为4KB的页.
个特定的程序有32768B的正文,16386B的数据和15870B的堆栈. 这个程
序能装入地址空间吗? 如果页面长度是512B, 能放下吗?
65536/4000=16.384=16个页面
32768/4000=8
16386/4000=5
15870/4000=4
8+5+4=17>16,所以放不下
虚拟存储技术的定义、最多存储空间
虚拟存储技术的定义:是指建立在离散分配存储管理方式上的、具有请求调入功能和置换功能,能从逻辑上对内存容量加以扩充的一种存储器系统。
它能将内存和外存结合起来,使得用户程序认为它具有比实际内存空间更大的地址空间,从而可以在地址空间中存储比实际内存空间更大的程序。
虚拟存储技术的工作情况:根据程序的局部性原则,程序的执行没必要把所有的页装入内存,可以只把需要执行的页或段装入内存,其余的留在外存中。程序在执行的过程中如果接下来要执行的页在内存中,则直接执行,如果不在,则发出缺页中断请求,OS将页调入内存中。如果当前内存已满,则OS会将暂时不用的页置换到外存中,腾出空间给新的页使用。
虚拟存储技术的特征:多次性 、对换性、虚拟性、离散性
虚拟存储管理技术的基础:程序的局部性原理(程序在执行时会有许多局部性的规律,包含时间局限性和空间局限性)
页面置换算法:
OPT(Optimal)最佳置换算法:
淘汰的页面是最长未来时间内不会访问的页面
可以获得最低的缺页率
FIFO 先进先出:
淘汰的是先进入的页面
LRU(Least Recently Used)最近最久未使用算法:
淘汰的是最近最久未使用(是之前时间中)
LFU (Least Frequently Used)最少使用:
淘汰的是最少使用的(是之前时间中)
(必考)请求分页中缺页率(小数表示)
在一个请求分页系统中, 有一个长度为 5 页的进程, 假如系统为它
分配 3 个物理块 , 并目此进程的页面走向为2, 3, 2, 1,5, 2,4
5, 3,2, 5, 2. 分别用 FIFO , LRU, OPT 算法分别计算出程序访
问过程中所发生的缺页次数.
FIFO(First in first out)
FIFO | 2 | 3 | 2 | 1 | 5 | 2 | 4 | 5 | 3 | 2 | 5 | 2 |
---|---|---|---|---|---|---|---|---|---|---|---|---|
1 | 2 | 2 | 2 | 5 | 5 | 5 | 3 | 3 | 3 | |||
2 | 3 | 3 | 3 | 2 | 2 | 2 | 5 | 5 | ||||
3 | 1 | 1 | 1 | 4 | 4 | 4 | 2 | |||||
缺 | 缺 | 缺 | 缺 | 缺 | 缺 | 缺 | 缺 | 缺 | 缺 |
这里的数据列2,3因为是首次进来,程序需要调用的页面2,3都不在内存中,所以都是缺页,之后的都是根据已有的内存列表中
LRU(Least Recently Used)
LRU | 2 | 3 | 2 | 1 | 5 | 2 | 4 | 5 | 3 | 2 | 5 | 2 |
---|---|---|---|---|---|---|---|---|---|---|---|---|
1 | 2 | 2 | 2 | 2 | 2 | 3 | 3 | |||||
2 | 3 | 3 | 5 | 5 | 5 | 5 | ||||||
3 | 1 | 1 | 4 | 4 | 2 | |||||||
缺 | 缺 | 缺 | 缺 | 缺 | 缺 | 缺 | 缺 |
OPT
OPT | 2 | 3 | 2 | 1 | 5 | 2 | 4 | 5 | 3 | 2 | 5 | 2 |
---|---|---|---|---|---|---|---|---|---|---|---|---|
1 | 2 | 2 | 2 | 2 | 4 | 2 | ||||||
2 | 3 | 3 | 3 | 3 | 3 | |||||||
3 | 1 | 5 | 5 | 5 | ||||||||
缺 | 缺 | 缺 | 缺 | 缺 | 缺 | 缺 |
抖动
页面置换算法中的抖动(thrashing)指的是操作系统在执行进程时,频繁地将页面从内存中换出到外存,然后再将其换入内存的现象。
为了避免抖动的出现,可以采用一些策略,最根本的方法是控制多道程序的道数或增加内存容量、优化页面置换算法等。其中,增加内存容量可以有效地减轻抖动现象,而优化页面置换算法则是减轻抖动的重要手段。
抖动的出现是由于系统中同时存在的进程过多,导致内存不足,无法同时容纳所有的进程所需的页面,因此操作系统不得不频繁地进行页面置换,导致系统性能急剧下降。这种情况下,系统的大部分时间都用于进行页面置换,而不是执行进程所需的任务,从而导致响应时间变长,吞吐量下降等问题。
作业的四种状态
提交状态:作业被创建并提交给操作系统,但还未开始执行,作业正在等待分配资源、分配内存和初始化等操作
后备状态(收容~):将用户提交的作业输入到硬盘中,再创建该作业的JCB,将其放入后备队列中
执行状态:作业被调度后便为其分发所需的资源和建立进程,并放入就绪队列,一个作业从进入就绪队列到运行结束前都是执行状态
完成状态:当作业完成或异常结束时就会进入完成状态,系统会回收JCB和所用资源
作业进程调度
短作业优先(SJF)
先来先服务(FCFS)
优先级调度(PSA)
高响应比优先(HRRN)
响应比R=作业周转时间/作业处理时间
=(作业处理时间+作业等待时间)/作业处理时间
= 1+(作业等待时间/作业处理时间)
饿死现象
在短作业优先调度算法中,存在一些长作业和短作业时,SJF算法会倾向于优先调度短作业,以实现最短的平均等待时间。这可能导致长作业一直被短作业抢占,无法得到执行的机会。
死锁的四个必要条件
互斥条件
请求和保持条件
非剥夺/不可抢占条件
循环等待条件
死锁是指两个或多个的进程在执行过程中,因争夺资源而造成的一种互
相都将无法执行下去的情况.
平均周转时间的计算
- 完成时间-提交时间
- 等待时间+运行时间
平均带权周转时间就是在分子的每一项除以一个运行时间
21、虚地址空间
文件的分类逻辑结构
按文件的逻辑结构分类
流式文件:
构成文件的基本单位是字符,是有序字符的集合。
记录式文件:
构成文件的基本单位是记录,是一组有序记录的集合。
按文件的物理结构分类:
顺序(连续)文件,链接文件,索引文件。
操作系统虚拟机的概念
使用户和程序员在不必涉及和了解硬件工作细节的情况下能方便的使用计算机,而为用户所提供的一个等价的扩展计算机,称为虚拟计算机。或者换句话说虚拟机就是装了操作系统的裸机。
管态和目态
管态:又称核心态,指操作系统占用CPU的状态
目态:又称用户态,指应用程序占用CPU的状态
34、资源分配图
系统不安全的最坏情况
不安全状态指无法找到一个序列使进程顺利执行完成
★只要系统处于安全状态,系统就不会发生死锁
★在系统处于不安全状态下未必一定发生死锁,但安全状态下系统是一定不会发生死锁的
现有同类资源12个供3个进程共享,假定进程所需资源和已占资源的情况如下表所示。3个进程在执行中又都提出申请一个资源的要求,回答:
a.如果先满足进程A的要求,系统将会出现什么现象?解释之。
b.你认为应按怎样的次序分配资源才合适?为什么?
进程 | 已占用资源 | 最大需求数 |
---|---|---|
A | 1 | 4 |
B | 4 | 6 |
C | 5 | 8 |
a.在当前状态下,尚余2个资源可供分配,如果先满足进程A的要求,把其中1个资源分配给A进程,此时A、B、C进程仍未拥有足够资源完成任务。系统进入不安全状态,随着进程的继续执行,剩余的1个资源无论分给哪个进程,均导至所有进程进入等告待而出现死锁。
b.根据目前的资源占用情况,应该先满足B的要求,把剩下的2个资源分配给他,这样,B进程可执行完毕归还系统6个资源。这6个资源可以满足A和C进程的资源需求,从而使系统处于安全状态
操作系统提供给程序员的接口
(1)程序员接口:用户在程序中请求操作系统的服务(称为系统调用或操作系统应用程序接口(API))
(2)操作员接口:用户通过操作系统提供的操作控制命令输入、调试和执行程序
IO杂项
执行I/O操作的机械部分的一般是IO设备,执行控制I/O的电子部件是设备控制器或适配器(IO设备一般是和控制器进行通信的,再有控制器与CPU通信)
IO设备与控制器有三个信号线:数据信号线、控制信号线、状态信号线
控制器的主要功能是:控制一个或多个IO设备、以实现IO设备和计算机之间的数据交换
spooling提高IO设备的使用效率
在传统的IO操作中,CPU需要等待IO设备完成数据的输入或输出操作,这期间CPU处于空闲状态,造成了CPU的闲置时间。而使用Spooling技术,IO操作被缓冲到虚拟输出队列中,使得CPU可以继续执行其他任务,而无需等待IO设备完成,可以在IO操作进行的同时执行其他任务也就是并行工作,从而提高了IO设备的使用效率,充分利用了CPU的处理能力,提高系统的整体效率。
多道程序技术可以将一个CPU虚拟成多个逻辑CPU,spooling技术能将一个IO设备虚拟为多个逻辑IO设备,能使多个用户共享一个IO设备
缓冲技术的目的
为了缓和CPU和IO设备间速度不匹配的问题
减少CPU的中断频率,放宽对CPU中断响应时间的限制
解决数据粒度不匹配的问题
提高CPU和IO设备之间的并行性
缓冲技术有: 单缓冲,双缓冲,环形缓冲,缓冲池
(必考)IO控制方法
程序直接控制方式
程序直接对IO/CPU/内存进行通信,会有大量的CPU时间浪费在循环测试IO是否完成
CPU和IO串行工作
中断控制方式
由CPU内部引起的中断叫做陷入(内中断)
由IO设备引起的中断叫外中断
以字节为单位传输
由于CPU使用中断来和IO设备通信,CPU只需要花费极少的时间去响应中断即可处理相应的IO数据传输
CPU和IO并行工作,但设备多时对CPU打扰多
直接存储器访问(DMA)方式
IO通过DMA控制器与内存直接数据传输,只在数据块传输的开始和结束时需要CPU干预,减少了CPU的负担,提高了数据传输的速度
传输基本单位是数据块
通道控制方式
是升级版的DMA,能进一步减少CPU的干预
使用一组数据块进行传输,进一步减小来CPU的干预
描述IO控制法中的:程序直接控制方式、中断控制方式、DMA方式、通道控制方式
磁盘逻辑记录的存放
假定有一个磁盘组共100个柱面,每个柱面上有8个磁道,每个盘面被划分成8个扇区。现有一个含有6400个逻辑记录的文件,逻辑记录的大小与扇 区大小一致,该文件以顺序结构的形式被存放到磁盘上。柱面、磁道、扇区的编号均从“0”开始,逻辑记录的编号也从“0”开始。文件信息从0柱面、0磁道、0扇区开始存放。
试问: a.该文件的第 3680个逻辑记录应存放在哪个柱面的第几磁道的第几个扇区? b.第78柱面的第6磁道的第6扇区应存放在了该文件的第几个逻辑记录?
解:
a.因为在磁盘中,文件是按柱面-磁道-扇区为序存放的。计算如下:
柱面号=3680//(8*8) =57
磁道号=(3680%88*)//8=4
扇区号=(3680%64)%8=0
b.反过来也可计算:
逻辑记录号=7888 +68* +6 =5046
磁盘的优化分布
磁盘的访问时间
索引表
索引表(Index Table)是在文件管理中用于加快文件检索和访问的数据结构。它的作用是记录文件中数据块的位置和其他相关信息,以便快速定位和访问文件的内容。
位示图作用、计算
0表示空闲
行和列都是从1开始,i为行,j为列
盘块号=n(i-1)+j
44、地址空间、存储空间
分时系统
分时系统:
多路性:能够让多个用户使用同一个主机,提高了资源利用率
独立性:多路性的同时带来的就是好的独立性,每个用户使用的都是独立的环境
及时性:响应速度快
交互性:用户使用主机的交互性好
批处理系统:
资源利用率高:多道程序交替运行,CPU一直处于忙碌状态,所以资源利用率高
吞吐量大:
CPU和其他资源持续保持忙碌状态;
仅当作业完成时或运行不下去时才切换作业,开销小
平均周转时间长:因为作业需要排队进行处理
无交互能力
标签:状态,复习,地址,期末,IO,进程,CPU,空闲,操作系统 From: https://www.cnblogs.com/cghk002/p/17456171.html