操作系统
2022-05-22 19:24:56 29 举报AI智能生成
登录查看完整内容
计算机操作系统、OS、西安电子系科技大学出版社
作者其他创作
大纲/内容
处理机调度与死锁
高级调度：作业调度。把外存上处于后备队列中的作业调入内存。
低级调度：调度的对象是进程（或内核级的线程）。
中级调度：把暂时不能运行的进程，调至外村等待。
处理机调度的层次
FCFS，先来先服务调度算法
SJF，短作业优先调度算法
PSA，优先级调度算法
HRRN，高响应比优先调度算法（综合考虑运行时间和等待时间）
作业调度算法
RR，轮转调度算法
进程调度
两个或两个以上的进程因争夺资源而造成相互等待的现象。
产生死锁的必要条件：互斥。请求和保持。不可抢占。循环等待。
破坏请求和保持：一次性申请所有资源。
破坏不可抢占：已经获得了某些资源，因提出资源请求而不能满足时，释放已有的资源
破坏循环等待条件：按序申请资源。
预防死锁：破坏产生死锁的一个或多个条件（互斥条件除外）。
避免死锁：资源的动态分配过程，用某种方法防止系统进入不安全状态（银行家算法）。
检测死锁：检测死锁状态（资源图）。
解除死锁：抢占资源（让死锁进程获得需要的资源）。终止进程。
死锁
存储器的层次结构：寄存器（CPU寄存器）。高速缓存、主存储器和磁盘缓存（主存）。固定磁盘、可移动存储介质（辅存）
主存储器：保存进程运行时的程序和数据。处理机都是从主存储器中取得指令和数据的，并将其所取得的指令放入指令寄存器中。
寄存器：（主存储器的访问速度远远低于CPU执行指令的速度）寄存器与处理机有相同的速度，对寄存器的访问速度很快，能与CPU协调工作。
高速缓存：介于寄存器和存储器之间的存储器，用于备份主存中较常用的数据，减少处理机对主存储器的访问次数。
磁盘缓存：缓解磁盘的I/O速度和对主存的访问速度。与高速缓存不同，磁盘缓存实际上并不存在。
主存储器与寄存器
编译、链接、装入
连续分配存储管理方式：单一分配、固定分区分配、动态分区分配
程序的装入和链接
分页存储管理方式：将用户程序的地址空间分为若干个固定大小的“页”，将内存空间分为若干个物理块，页和块大小相同，将用户程序的任一页放入任一物理块中。
分段存储管理方式： 把用户大小分为若干个大小不同的段，每段定义一组完整的信息。存储器分配时，以段为单位，这些段在内存中可以不相邻接。
存储器管理
上面介绍的存储器管理方式都是要求将一个作业全部装入内存后方能运行。
程序在执行时仅局限于某个部分，所访问的存储空间也局限于某个区域。
时间局部性：如果程序中的某条指令/数据被执行/访问过，那么不久以后可能会再次被执行/访问。因为在程序中存在大量的循环操作。
空间局部性：程序在一段时间内访问的地址可能集中在一定的范围之内（程序的顺序执行）。
如果缺页（段），发出缺页(段)请求；如果内存已满，OS利用页的置换功能。
局部性原理
最佳置换算法 Optional：淘汰的页是在最长时间内不再被访问的页面（向后看）。
先进先出置换算法 FIFO：淘汰最先进入内存的页。
最近最久未使用 LRU：淘汰最近最久未使用的页（向前看）。
最少使用置换算法：LFU淘汰最近时期使用最少的页。
页面置换算法
虚拟存储器
I/O系统管理的主要对象是I/O设备和相应的设备控制器。作用：完成用户的I/O请求，提高I/O速率，提高设备的利用率。
用户层IO软件（产生IO请求）
设备独立性软件（实现用户程序与设备驱动器的统一接口、设备命名、设备保护和设备的分配与释放）
设备驱动程序（与硬件直接相关，用户具体实现系统对设备发出的操作指令、驱动I/O设备工作的驱动程序）
中断处理程序（用于保存被中断进程的CPU环境）
硬件（执行I/O操作）
I/O系统的层次结构
IO系统的功能
进程之间的切换是通过中断来完成的。
外中断：CPU对I/O设备发来的中断信号的一种响应。中断是外部设备引起的，称为外中断。
内中断：CPU内部事件所引起的中断。进程在运算中发生了上溢或下溢出
屏蔽（禁止）中断：处理中断时，屏蔽其他中断请求（其他中断等待）
嵌套中断：优先处理优先级较高的中断
对多中断源的处理方式
中断机构与中断处理程序
先来先服务算法
最短寻道时间优先
磁盘调度算法
扫描(SCAN)算法
基于扫描的磁盘调度算法
磁盘存储器
输入输出系统
数据项（描述一个对象的某种属性的字符集）、记录（一组数据项集合）、文件
文件类型：系统文件、用户文件、库文件
文件和文件系统
用户程序调用文件系统接口
对对象操纵和管理的软件集合
对象及其属性
层次结构
文件管理
连续组织方式
链接组织方式
索引组织方式
外存的组织方式
磁盘高速缓存（在内存中为磁盘盘块设置的一个缓冲区）
磁盘请求会先访问磁盘告诉缓冲器；如果不在，启动磁盘将所需要的盘块内容读入。
数据交付方式：数据交付；指针交付。
磁盘块高速缓存置换算法：最近最久未使用算法LRU、最近未使用算法NRU、最少使用算法LFU。
周期性地写回磁盘：修改(update)程序，周期性地调用一个系统调用SYNC，强制将所有在高速缓存中已修改的盘块数据写回磁盘。一般两次调用SYNC的时间间隔定为30s。
其他方法：提前读、延迟写、优化物理块的分布、虚拟盘
提高磁盘I/O速度的途径
事务记录Log
恢复算法（undo、redo）
事务
检查点：对事务记录表中事务记录的清理工作经常化
利用互斥锁实现顺序性
利用互斥锁和共享锁实现顺序性
并发控制
数据一致性控制
磁盘存储器的管理
OS是配置在计算机硬件上的第一层软件，是对硬件系统的首次扩充。主要作用是管理好这些硬件设备，提高它们的利用率和系统的吞吐量。
为用户和计算机硬件系统之间提供接口
管理计算机系统资源，处理机、存储器、I/O设备、文件
子主题
作用
并发：两个或多个事件在同一时间间隔发生。并行：两个或多个事件在同一时刻发生。
进程：在系统种能独立运行并作为资源分配的基本单位。由一组机器指令、数据和堆栈组成。多个进程之间可以并发执行和交换信息。
互斥共享方式（一段时间内只允许一个进程访问的资源称为临界资源，如：打印机）
同时访问方式（允许一段时间内有多个进程同时访问，如：磁盘设备）
共享
通过某种技术将一个物理实体变为若干个逻辑上的对应物的功能称为“虚拟”
时分复用技术：利用某设备为用户服务的空闲实时间，转去为其他用户服务，从而提高资源利用率。
空分复用技术：利用存储器的空闲空间分区域存放和运行其他的多道程序，提高内存的利用率。
虚拟
进程的执行不是“一气呵成”的，而是已“停停走走”的方式运行
异步
特性
进程控制：创建、撤销进程
进程同步：进程互斥方式、进程同步方式
进程通信：一组相互合作的进程共同完成一个任务时，进程之间需要交换信息。
调度：作业调度、进程调度
处理机(CPU、存储器)管理功能
内存分配：静态存储、动态存储
内存保护：用户程序之间的内存互不干扰
地址映射：将地址空间中的逻辑地址转换为内存空间中与之对应的物理地址。
内存扩充：请求调入功能（允许装入部分用户程序便能启动该程序）、置换功能（置换掉一些暂时不用的程序）
存储器管理功能
缓冲管理：在I/O设备和CPU之间引入缓冲，可有效解决CPU和I/O设备速度不匹配问题，提高CPU利用率。
设备分配：根据用户进程的I/O请求、系统现有资源情况为之分配其所需的设备。
设备处理：设备处理程序（设备驱动程序），用于实现CPU和设备控制器之间的通信。
设备管理功能
文件存储空间的管理：对诸多文件及文件的存储空间实施统一的管理。
目录管理：为每个文件建立一个目录项，目录项包括文件名、文件属性、文件在磁盘上的物理位置
文件的读/写管理和保护：文件的读/写管理（读写不会同时进行）；文件保护（防止文件被非法窃取和破坏）
文件管理功能
功能
操作系统
程序并发执行特征：间断性、失去封闭性、不可再现性
程序执行
定义：程序段+数据段+PCB（进程控制块）
动态性。创建产生，调度执行，撤销消亡。
并发性。多个进程实体同时存在于内存，且能在一段时间内同时运行。
独立性。进程实体是一个能独立运行、独立接受调度的基本单位。
异步性。进程是按异步方式运行的，即按各自独立的、不可预知的速度向前推进。
进程的四大特性
就绪：即进程已分配到除CPU以外的所有必要。
执行：进程以获得CPU
阻塞：进程发生某事件（I/O请求，申请缓冲区失败，访问临界资源）暂时无法继续执行的状态，亦称暂停状态。
创建：PCB+程序段+数据段+资源
终止：PCB清零，回收PCB到系统
挂起：用户手动、父进程挂起、负责调节需要、OS需要。
进程的几种状态
内存：内存表。设备：设备表。文件：文件表。进程：进程实体及所用资源列表
独立运行基本单位的标志。
能实现间断性运行方式。
提供进程管理所需要的信息。
提供进程调度所需要的信息。
实现与其他进程的同步和通信。
PCB的作用
进程标识符：唯一标识一个进程。
处理机状态：当进程被切换时，处理机状态信息都必须保存在对应的PCB中，以便在该进程重新执行时能再从断点继续执行。
进程调度信息：OS调度时，需要知道进程的调度信息（进程状态、进程优先级、其他信息）
进程控制信息：程序和数据的地址、进程同步和通信机制、资源清单、链接指针（指向下一个PCB地址）
PCB中的信息
线性方式：将所有的PCB都组织在一张线性表中（放入内存，每次查找遍历线性表）
链接方式：把具有相同状态进程的PCB分别通过PCB中的链接字链接成一个队列（对状态进行分组）。状态指针->PCB1->PCB2...
索引方式：根据进程状态的不同，建立几张索引表（就绪索引表、阻塞索引表）。表指针->表->PCB
PCB的组织方式
进程管理中的数据结构
进程
OS内核：通常将一些与硬件紧密相关的模块（中断处理程序）、各种常用设备的驱动程序以及运行频率较高的模块（时钟管理、进程调度），都安排在紧靠硬件的软件层次中，将它们常驻内存，通常被称为OS内核。
一是便于对这些软件进行保护，防止遭受其他应用程序的破坏；二是可以提高OS的运行效率。
为了防止OS本身及关键数据（PCB）遭受到应用程序有意或无意的破坏，通常将处理机的执行状态分为系统态和用户态。
系统态：管态，内核态。具有较高的特权，能执行一切指令，访问所有寄存器和存储区。
用户态：目态。具有较低特权的执行状态，仅能执行规定的指令，访问指定的寄存器和存储区。
支撑功能。中断处理、时钟管理、原语操作
资源控制功能。进程管理、存储器管理、设备管理
OS内核功能
操作系统内核
进程层次：UNIX的父子进程，子进程可以继承父进程所拥有的资源，子进程被撤销时，从父进程获得的资源返还给父进程。撤销父进程时，必须同时撤销所有的子进程。进程不能拒绝其子进程的继承权。
Windows中不存在任何进程层次结构的概念，所有进程都具有相同地位。
进程创建原语：1. 申请空白PCB；2. 分配资源；3. 初始化PCB；4. 进程队列。
进程创建
正常结束；异常结束（运行/等待超时、算术运算错、I/O故障）；
进程终止
阻塞行为：向系统请求共享资源失败。等待某种操作的完成。新数据尚未到达。等待新任务的到达。
阻塞原语block，阻塞是一种主动行为。
有关进程（提供数据的进程）调用唤醒原语wakeup，将等待该事件的进程唤醒。
block和wakeup原语操作必须成对使用，否则阻塞的进程将永远不会被执行。
进程的阻塞和唤醒
挂起原语suspend：就绪->静止就绪；阻塞->静止阻塞。
激活和挂起相反。
进程的挂起与激活
进程控制
使得并发执行的诸进程之间能按照一定的规则（或时序）共享系统资源，并能很好地相互合作。
间接相互制约关系：多个进程在并发执行下，共享系统资源（I/O设备、CPU等）。
直接相互制约关系：进程A和进程B共享一个缓冲区（类似生产者-消费者）。
进程间的制约关系
临界资源：诸进程间采用互斥方式，实现对临界资源的共享（打印机、磁带机）。
临界区：把每个进程中访问临界资源的那段代码称为临界区。
同步机制规则：空闲让进。忙则等待。有限等待。让权等待。
利用特殊指令解决临界资源问题。
关中断：就是让程序在同一时间内执行多条指令。对应的还有开中断、中断。
利用Test-and-Set指令实现互斥：互斥指令（原语）。
利用Swap指令实现进程互斥：对换指令，XCHG指令（进程中的局部变量true、临界资源设置一个全局变量lock，初始false）。
硬件同步机制
整形信号量：只要信号量S<=0，就会不断地测试。
记录型信号量：不存在”忙等“现象的进程同步机制。
AND型信号量：进程一次申请所有资源，防止死锁发生。
信号量集：对进程所申请的所有资源再一次原语中完成申请或释放。
应用：利用信号量实现进程互斥。
信号量机制
管程：共享资源的数据结构以及由对该共享数据结构实施操作的一组过程所组成的资源管理程序共同构成了一个操纵系统的资源管理模块。
进程同步
生产者-消费者问题：利用信号量解决（S为缓冲池资源）。
哲学家进餐问题：利用信号量解决（S为筷子）。
读者-写者问题：利用信号量保证一个Writer进程必须与其他进程互斥地访问共享对象的同步问题。
经典同步问题
进程之间的信息交换。
进程通信的类型：共享存储器系统、管道通信系统、消息传递系统、客户机-服务器系统。
进程通信
进程在创建、撤销和切换中，必须为之付出较大的时空开销。
调度的基本单位：进程是独立调度和分派的基本单位，线程是独立运行的基本单位。线程切换仅需保存和设置少量寄存器内容。
并发性：进程和线程都可以并发执行
拥有资源：进程可以拥有资源，线程本身不拥有系统资源（保留一些必要的资源，线程控制块TCB、程序计数器、局部变量、少量状态参数）。
独立性：不同进程之间线程要比同一进程中的线程独立性高。
系统开销：创建撤销进程系统要为之分配和回收PCB、分配或回收其他资源，如内存空间和I/O设备。
支持多处理机系统：对于多线程进程，可以分配线程到多个处理机。
线程进程比较
执行、就绪、阻塞
TCB：线程标识符、一组寄存器、运行状态、优先级、线程专有存储区、信号屏蔽、堆栈指针
线程状态
线程
不论是进程还是线程，都必须直接或间接地取得内核的支持。
创建进程，分配一个任务数据区PTDA（Per Task Data Area），包含若干个TCB空间。当PTDA空间用完，只要其所创建的线程数目未超过系统的允许值，系统可再为之分配新的TCB空间。
线程的实现
进程的描述与控制
计算机操作系统（汤小丹）
职业：本科
0 条评论
回复 删除
下一页
