操作系统笔记1
操作系统：进程管理、存储管理、外部设备管理、文件管理操作系统是计算机系统中的一个系统软件，管理和控制计算机系统中的硬件和软件资源，合理组织计算机工作流程以便有效利用这些资源为用户提供一个功能强大、使用方便的工作环境从而在计算机与用户之间起到接口的作用
什么推动着操作系统的发展
计算机硬件升级和新硬件的出现
提供新的服务，方便使用
提高计算机资源利用率
更正软件错误
计算机体系结构发展：单处理机系统、多处理机系统、分布式系统、计算机网络
概念：
批处理
多道程序设计
作业
任务
进程与线程
接口
虚拟存储
文件
单道批处理系统：
解决了作业间的自动转接问题，减少了机器时间的浪费
不管作业大小，只要他一旦占用处理机就开始执行，则它必须一直占据处理机直到运行完毕
资源利用率低，任意时刻只允许一道作业在内存中运行
对短作业不公平，因为他们等待执行的时间可能远远超过他们实际执行时间
交互性差，作业有批处理程序控制运行
多道批处理系统：
允许多个程序同时存在于主存中，按照某种原则分派处理机，逐个执行这些程序
批处理：
用户提交的作业首先存放在外村兵排成一个队列，然后由作业调度程序按照一定算法从该队列中一次选取一个或若干个作业装入内存执行。
当某个程序占用处理及执行过程中遇到了输入输出语句，可以启动专门负责输入输出的系统服务程序完成输入输出操作而处理器切换到另一个程序执行。(IO速度慢，继续运行时恢复中断状态)
多道程序设计技术：
为了提高系统吞吐量和资源利用率，允许多个程序同时驻留内存，使处理机在这些程序之间切换，在一段时间内执行完多个程序的处理技术称为多道程序设计技术
多道程序设计技术引发的问题：
处理机的分配和回收
内存的分配与回收
I/O设备的共享和效率
文件的有效管理
作业的组织
多道批处理系统提高了资源利用率和吞吐量，但是交互性很差
分时系统在多道程序技术的基础之上，为多个用户配置了一个联机终端 中断：接受输入和输出的设备
内存：前台区存放按时间片调入和调出的作业流，后台去存放批处理作业。仅当前台作业调入调出或前台无作业可运行时，方才运行后台区作业，提供交互式快速服务，同时在处理机空闲时运行后台较大的批作业。前台和后台按优先级区分
多道分时系统：允许在内存中存放多道作业并把具备运行条件的所有作业排成一个队列，让他们依次轮流获得时间片(分时)运行。
操作系统的功能：
管理处理机
进程控制：创建和撤销进程以及控制进程的状态转换
进程同步：协调互斥访问临界资源，协调执行速度(同步<=>协调)
进程通信：进程间的信息交换
进程调度：按一定算法从进程就绪队列中选出一个进程把处理及分配各塔使之运行
时间片用完的进程会继续进入就绪队列，等待处理机
管理存储器
任务
为多道程序并发执行提供良好环境
便于用户使用存储器
提高存储器的利用率
用尽量多的用户提供足够大的存储空间
功能
内存分配：静态分配、动态分配、连续分配、非连续分配
内存保护：系统内存空间、用户内存空间
地址映射：逻辑地址->物理地址(用地址转换复杂性换取内存利用率)
内存扩充：虚拟存储技术
管理输入输出设备·
任务
为用程序分配I/O设备
完成用户程序请求的I/O操作
提高处理机和I/O设备的利用率
改善人机界面
功能
缓冲管理
设备分配
设备处理：启动设备、中断处理
虚拟设备功能
RAID技术、磁盘调度
管理数据文件
任务
管理用户文件和系统文件
管理文件的存储空间
保证文件数据的安全
方便用户使用文件
功能
文件目录管理
文件的逻辑组织与访问方式
存储空间的管理：文件的物理组织、空闲磁盘空间的管理
文件共享与安全
提供接口服务
现代操作系统特征
任务共行性 宏观上同时运行，微观上交替运行
资源共享性 宏观上共享资源，微观上互斥使用
虚拟性 将一个物理上的实体变为若干个逻辑上的对应物
不确定性 ①程序执行结果不确定 ②进程以异步方式执行
操作系统笔记5
存储分配：
分配基本的内存空间
增加新的内存空间
回收内存空间
存储分配步骤：
首先根据系统内存分配算法在空闲的内存分区中寻找到一块满足进程需要的内存空间，将其分配给进程
然后更新进程的资源分配清单、内存分配情况清单等数据结构
内存的回收：
更新相应的数据结构，将回收的内存空间标识为“空闲可用”
高级语言或汇编语言使用符号地址：变量或标号，源程序经过编译链接以后，其中的符号地址就会变成数字式的逻辑地址，编译链接程序会自动计算每一个变量或标号所对应的逻辑地址是多少
静态重定位：
地址映射：程序装入内存易后由操作系统将逻辑地址改为逻辑地址加上起始地址得到物理地址。
重定位：对目标程序中的指令和数据地址进行修改的过程
静态映射实现简单。地址变换只在程序装入时一次完成，程序运行时不再改变，但不适合多道程序系统，不允许系统执行内存碎片整理，无法实现虚拟存储
动态重定位：
操作系统将程序装入内存以后，并不立即把目标程序中的逻辑地址转换为物理地址，而是在处理机执行每一条指令时进行地址转换，复杂且费时。
存储保护：
防治地址越界，防止越权操作。
地址越界：进程访问不属于自己的地址空间，或者说进程在运行时所产生的物理地址超越其自身地址空间范围
操作越权：进程对共享存储区的操作违反了系统规定的权限
存储保护只能在进程执行过程中动态执行，不可能在运行前一次性静态完成
若采用动态映射计算物理地址，可能计算出错误地址，若采用静态映射，进程执行过程中也可能出错，从而导致地址越界或操作越权
为了提高系统效率，存储保护的主要工作必须由高速的专用硬件完成：在地址管理部件中
存储共享：
为了进程通信和节约内存空间，两个或多个进程共用内存中相同的分区，及他们的物理空间有相交的部分
可以共享进程的代码，也可以共享进程数据
一般地进程之间的共享代码目的主要是节约存储空间，共享数据的目的主要是实现进程中的相互通信
存储管理作用：
回收内存
存储共享
重定位
存储保护
共享代码
程序可重入：设计程序时，逻辑上将程序代码区和数据区分开
代码区不包含运行程序是需要改变的数据，被处理的数据都放在独立的数据区，这样进程执行过程中就不会改变代码部分的任何内容。
数据区是单独的一个段、堆栈式动态申请的分区或通过参数传递
创建新进程时，不需要为该进程的代码部分另外申请内存空间，只需将该进程PCB中的进程代码空间地址指向已有的代码空间地址
进程的数据区要么等到操作系统为其分配相应存储空间以后将数据区地址填写在PCB中，要么由进程运行时向操作系统动态申请
内存划分：静态划分、动态划分
分页：特殊的静态分区，需要事先将内存空间划分为若干个大小相同的分区，称为页框或帧，当进程申请申请存储空间时，系统可以为之分配多个空闲页框
等长固定分区：
分配简单只要进程大小不超过分区大小就可以装到任何一个分区中运行
浪费存储空间：若进程申请的存储空间很小却需要占用整个分区，分区内存在不可用的浪费空间称为内零头
无法运行超过分区大小的程序
无法精确确定分区的大小
不等长分区：
减少了空间浪费，但是限制装入进程数量，很难确定每个分区大小，存在内零头问题
动态划分：
根据进程实际需要，动态划分内存空间并分配给进程，彻底解决了内零头(内存碎片)问题
首次适应算法：总是从内存某一端(低地址)开始查找，选择一个超过进程申请大小的空闲分区
优点：尽量使用低地址空间因而高低指出可能保留较大空闲分区，所以大进程申请的存储空间大都能在搞地质端得到满足
缺点：由于每次仅简单地使用找到的第一个分区，结果可能导致将较大的空闲分区不断分割为较小的空闲分区
动态划分算法可能产生很多较小的分区：外零头
下次适应算法：记住上次分配的分区位置，下次实施分配时从上一次分配为止之后开始查找选择一个大小足够的空闲分区
该算法常常导致内存中缺乏大分区，导致大进程无法运行，出现大量外零头，需要较频繁地实施紧凑操作
最佳适应算法：总是选择满足申请要求且长度最小的空闲分区
优点：尽量不分割大的空闲分区
缺点：可能会形成大量较小的、难以再分配的分区--外零头
可执行程序的装入：
绝对装入
重定位装入
运行时动态装入
连续存储管理：
基址寄存器 存放当前执行进程所在分区的物理存储单元的起始地址
界限寄存器 存放当前执行进程所在分区最后一个物理存储单元的地址，限定进程的执行范围，保护其他进程不被非法访问
基址寄存器和界限寄存器被多个进程共享，只有当前执行进程才是用他们
连续存储：分区(静态划分、动态划分)
需要内存中一块连续的、足够大的分区。容易出现外零头，解决方法：拒绝分配、紧凑技术拼接外零头、内存交换
分区为连续存储，分页为离散存储
非连续存储：分页 分段
允许进程的程序和数据分别装在内存不同分区中。必须登记一个进程分到所有分区的位置、大小、使用情况等信息
分页存储技术：静态固定分区方法划分
系统事先将物理内存划分为许多尺寸相同的页框，并将进程分隔成许多大小相同的页面，页面与页框大小相同
分段存储技术：程序的每个子程序每一段占一个分区
分段分页技术：程序分段、内存分区
分区：进程的逻辑地址空间连续，一维线性地址，进程的每一条指令和数据的地址相对于第一条语句地址而定
分页：进程被分隔成许多页面，每个页面内的指令和数据是连续的，他们的地址相对于其所属页的第一条语句的地址，称为页内偏移量
页表：系统为每个进程建立一张页面映射表，用于记载进程各页面到物理内存中页框的映射信息，进程的每个页面依次对应页表中的一个表项，其中包含相应页在内存中对应的物理页框和页面存取控制权限等字段
地址变换：
硬件机制：实现逻辑地址到物理地址的转换
1.根据逻辑地址，计算出页号和页内偏移量
2.用页号检索页表，查找指定页面对应的页框号
3.根据页框号和页内偏移量计算出物理地址
页表寄存器：实现快速地址映射，存储执行进程的页表起始地址，设置在处理机硬件中，当进程创建时，也表起始地址记载于进程PCB中，进程被调度执行时页表的起始地址将从该进程的PCB中取出并填入页表寄存器中。进行地址变换时处理机从页表寄存器中查找页表的地址。
逻辑地址分为2部分：页号+页内偏移量
当一个进程被装入物理内存时，系统将为该进程每个页面分配一个独立的页框，同一个进程的多个页面不必存放在连续的多个页框
大页表解决方法：
多级页表：将大页表分割离散存储在内存的多个页框中，为之建立二级页表，记录被分割的各个页面存储在哪些页框中称为外层页表。缺点是占内存
虚拟存储技术：只装入需要的部分页表项，其余页表驻留在磁盘上需要时再装入内存
反置页表：从内存的角度建立页表，整个系统只有一张页表，页表的表项基于内存中的每一个物理页框设置，页表项按页框号顺序排序，其中还必须包含页框对应的页号及其隶属进程的标识符等信息
一般情况下，系统从进程角度为每个进程建立一张页表，页表的表项按页号排序，这种方法会导致占用大量内存空间
操作系统笔记6
块表
分页系统：处理及每次存取指令或数据至少需要访问2次内存，第一次访问页表第二次存取指令或数据
第一次访问页表，第二次存取指令或数据
局部性原理：在一个很短的时间段内，程序的执行总是局部于某一个范围，进程最近访问过的页面在不久的将来还可能被访问
为了提高地址变换速度，为进程页表设置一个专用的高速缓冲存储器，称为块表、TLB(Translation Lookaside Buffer)
快表的工作原理类似于系统中的数据高速缓存(cache)，其中专门保存当前进程最近访问过的一组页表项
分页系统地址转换
通过根据逻辑地址中的页号，查找快表中是否存在对应的页表项，若块表中存在该表项称为命中，去除其中的页框号，加上页偏移量计算出物理地址。若块表不存在该页表项，称为命中失败，则再查找页表，找到逻辑地址中指定页号对应的页框号，同时更新块表，将该页表项插入块表中，并计算物理地址
页面与页框大小的主要因素：页内零头、地址转换速度和页面交换速率
较小的页面有利于减少内零头，从而有利于提高内存的利用率，然而较小的页面也将导致页表过大，从而降低了处理机访问页表时的命中率
块越大，内外内存之间数据交换效率越高，因此对于支持交换技术的系统，较大页面有利于提高页面换入换出内存的效率
分页存储管理的评价：
彻底消除外零头，极少内零头，提高内存利用率，分页操作由系统自动进程，一个页面不能实现某种逻辑功能，用户看到的逻辑地址是一维的，无法调试执行其中某个子程序或子函数，采用分业技术不易于实现存储共享，也不便于程序的动态链接
程序的逻辑地址由段号和段内偏移量决定
系统采用动态划分技术，将物理内存动态的划分成许多尺寸不相等的分区，系统将为进程每一段独立分配一个分区，多个段不必连续
分段系统基本数据结构：段表、空闲分区表。
地址变换和存储保护：
根据逻辑地址中的段号检索进程段表，获得指定段对应的段表项
判断是否地址越界
把逻辑地址段内偏移量与段表表项段基址相加，从而得到物理地址
分段系统评价：
有效消除了内零头，提高了存储利用率
允许子程序独立编译和修改，而不需要重新编译或连接其他相关子程序
容易实现存储共享(每段有逻辑意义)
具有较高的安全保证
很容易满足程序段的动态增长需要
分段和分页比较：
都采用非连续存储，地址映射实现地址变换
页是信息的物理单位，大小固定，短时信息的逻辑单位，各段的长度不固定，每一段都具有一定的逻辑含义
分页的地址空间是一维的，逻辑地址划分由机器硬件实现，对用户透明，分段的地址空间是二维的或多维的，程序猿知道段名和段内偏移量
分页活动源于系统管理物理内存的需要，在系统内部进行，有系统实施，用户看不见，分段活动源于用户进行模块化程序设计的需要，在系统外部进行，由用户实施。
简单段页式存储管理
采用分段方法组织用户程序，采用分页方法分配和管理内存
首先从段表寄存器从获得进程段表的起始地址，根据该地址查找进程的段表
然后根据逻辑地址指定的段号检索段表，找到对应段的也表起始地址
再根据逻辑地址中指定的页号检索该页表，找到对应页所在的页框号
最后用页框号加上逻辑地址中指定的页内偏移量，形成物理地址
进程运行之前，仅需要将一部分页面或段装入内存，便可启动运行，其余部分暂时保留在磁盘上
进程运行时，如果他所需要访问的页面(段)已经装入内存，则可以继续执行下去；
如果其所需要访问的页面(段)尚未装入内存，则发生缺页中断，进程阻塞，此时，系统将启动请求调页功能，将进程所需的页装入内存
如果当前内存已满，无法装入新的页，则还需要利用页置换功能，将内存中暂时不用的页交换到磁盘上，再将进程所需的页转入内存，环形阻塞进程，使之重新参与调度执行
抖动：系统花费大量时间吧程序和数据频繁装入换出内存而不是执行用户指令。根本原因是选择的页面或段不恰当
操作系统笔记2
进程：程序的一次执行，包括可执行的程序、程序所需的数据和相关状态信息。进程是拥有资源的最小实体，在传统OS中，进程同时也是系统调度的最小单位，(动态的概念，具有创建、执行、等待、结束等状态 进程=程序+数据+状态)
线程：程序的一次相对独立的运行过程，系统调度的最小单位
作业：计算机用户在一次上机过程中要求计算机系统为其所做的工作的集合，作业中每项相对独立的工作称为作业步。通常人们用一组命令来描述作业；其中每个命令定义一个作业步
Interface：在操作系统中具有接口和界面2种含义，借口多用于描述系统硬件之间的连接关系，以及软件和程序模块间的调用关系，如总线接口、打印机接口等。界面多用于描述用户与系统之间的操作环境以及人机之间的交互方式和过程，如字符界面、图形用户界面等
虚拟存储：为了能在有限的内存空间中运行更大、更多的进程，可以将一部分磁盘空间虚拟为逻辑内存，使用户感觉到一个比物理内存空间大得多的逻辑内存空间，即实际物理内存空间与虚拟的那部分逻辑内存空间的总和。有了虚拟存储技术，进程执行时只需要与现在物理内存中装入进程的一部分程序代码和数据，进程即可开始执行。当需要的程序代码和数据不在物理内存时，根据需要临时装入，而整个操作对用户透明。
文件：若干相关数据的集合，有的操作系统将程序、数据以及各种外部设备统统称为文件。对文件的操作包括文件的建立、修改、删除、重命名、设置访问权限等。概括起来文件时命名了的字节流，他是现代操作系统对计算机系统中种类繁多的外部设备进行高度抽象的结果
进程管理
生产者消费者问题
读者写者问题
哲学家进餐问题
基础：进程描述及控制
策略：进程调度
实现：互斥与同步
避免：死锁与饥饿
程序：源代码程序、目标程序、可执行程序
程序执行：编辑、编译、链接、运行
程序的结构：顺序结构、分支结构(if then)、循环结构
进程：可并发执行的程序，在一个数据集合上的运行过程
程序：静态概念，指令和数据的集合，可长期存储
进程组成：程序、数据集合，进程控制块PCB(Process Content Block)
PCB是进程存在的唯一标识。创建进程时创建PCB，进程结束时撤销PCB
PCB内容：
进程标识信息：进程的内部和外部标识符
处理机状态信息：通用寄存器值、指定计数器值、程序状态字PSW值、用户栈指针值
进程调度信息：进程状态、进程优先权、进程调度的其他信息
其他信息：程序及数据地址、进程同步和通讯机制、资源清单、链接指针
PCB组织方式：
单一队列：所有进程的PCB通过链表组织成为一个单一队列。适用于进程数目不多的系统。适用于进程较少的情况windows操作系统。
表格结构：PCB按进程状态不同，组织成不同的表格：就绪进程表、执行进程表(多机系统中)及阻塞进程表，系统分别记载各PCB表的起始地址
多级多列：PCB按进程状态不同用链接指针组成不同队列：就绪进程队列、阻塞进程队列(分成多列缩短长度)，系统分别记载各PCB链表的起始地址
进程状态：分派(进程)程序不按时间片
单处理机任何时刻只有一个进程处于执行状态
并非所有进程只要未执行就处于就绪状态(只等CPU)，有的需要阻塞等待I/O完成。未执行可分为就绪和阻塞，未执行分为就绪和阻塞
进程5状态：
新状态：进程已经创建，但未被OS接纳为可执行进程
就绪状态：准备执行
执行状态：占用处理机(单处理机环境中，某一时刻仅一个进程占用处理机)
阻塞状态：等待某事件发生才能执行，如等待I/O完成等
终止状态 因停止或取消，被OS从执行状态释放
①空->新状态 新创建的进程首先处于新状态
②新状态->就绪状态 当系统允许增加就绪进程时，操作系统接纳新建状态进程，将他变为就绪状态，插入就绪队列
③就绪状态->执行状态 当处理机空闲时，将从就绪队列中选择一个进程执行，该选择过程称为进程调度，或将处理机分派给一个进程，该进程状态从就绪转变为执行
④执行状态->终止状态 执行状态的进程执行完毕或出现诸如访问地址越界、非法指令访问等错误而被异常结束，则进程从执行状态转换为终止状态
⑤执行状态->就绪状态 分时系统中时间片用完或优先级高的进程到来，将中断较低优先级进程执行。进程从执行状态转变为就绪状态，等待下一次调度
⑥执行状态->阻塞状态 执行进程需要等待某事件发生，通常会因为进程需要的系统调用不能立即完成，如读文件、共享虚拟内存、等待I/O操作、等待另一进程与之通信等事件而阻塞
七、阻塞->就绪状态 当阻塞进程等待的事件发生，会进入就绪队列排队等待被调度执行
某些系统允许父进程在任何情况下终止子状态
如果一个父进程被终止妻子进程必须终止
新状态->终止
就绪状态->终止
阻塞状态->终止
问题：
内存资源紧张
无就绪进程，处理器空闲
解决：
采用交换技术，换出一部分进程到外存以腾出内存空间
换出程序和数据，不能换出PCB，之后处于挂起状态
采用虚拟存储技术，每个进程只能装入一部分程序和数据
进程挂起的原因：
进程全部阻塞，处理器空闲(将阻塞进程换出)
系统负荷过重，内存空间紧张
操作系统的需要。操作系统可能需要挂起后台进程或一些服务进程，或者某些可能导致系统故障的进程
终端用户的请求(调试)
父进程需求
进程挂起的特征：
不能立即执行
可能是等待某事件发生，若是则阻塞条件独立于挂起事件，即使阻塞时间发生，该进程也不能执行
使之挂起的进程为：自身、父进程、OS
只有挂起他的进程才能使之由挂起状态转换为其它状态
阻塞与挂起：
原因不同：进程是否等待事件；系统是否被换出内存
4种状态组合：
就绪
阻塞
就绪/挂起
阻塞/挂起
处理机可调度执行的进程：
新创建的进程
换入一个以前挂起的状态
通常为了避免增加系统负载，系统会换入一个以前挂起的进程执行(增加吞吐量)
操作系统笔记3
两种执行模式
系统模式(又称为系统态)、控制模式或内核模式
具有较高的特权
运行系统特定的指令，包括读写控制寄存器的指令、基本I/O指令以及与存储器管理有关的命令，及一些特定内存区
内核模式下的处理机机器指令、寄存器和内存都受到完全控制和保护
用户模式(或用户态)
具有较低的特权
用户程序一般运行在用户模式
往往将一些与硬件紧密相关的(如中断处理程序、设备驱动程序等)、基本的、公共的、运行频率较高的模块(时钟管理、进程调度等)以及关键性的数据结构独立开来使其常驻内存，比鞥对他们进行特殊保护，通常把这一部分称为操作系统内核
操作系统内核功能
资源管理：
进程管理：进城创建和终止、调度、状态转换、同步和通信、管理PCB
存储管理：为进程分配地址空间、对换、段页管理
I/O设备管理：缓存管理、为进程分配I/O设备和通道
支撑功能：
中断处理
统计
监测
时钟管理
原语操作等
进程创建步骤：
1 为进程分配一个唯一标志号ID 主进程表中增加一个新的表项
2 为进程分配空间 用户地址空间、用户栈空间、PCB空间。若共享已有空间则应建立相应的链接
3 初始化PCB 进程标识、处理机状态信息、进程状态
4 建立链接 若调度队列是链表，则将新进程插入到就绪或就绪/挂起链表
5 建立或扩展其他数据结构
进程中止原因：
正常结束
超时终止
内存不足
越界访问
企图使用未允许用的数据或操作方式错
计算错或企图存储硬件允许的最大数
超时等待某事件发生
进程中止步骤：
1 根据被终止进程的标识符ID，找到其PCB读出该进程的状态
2 若该进程为执行状态，则终止其执行，调度新进程执行
3 若该进程有子孙进程，则立即终止其所有子孙进程
4 将该进程的全部资源，或归还给其父进程，或归还给系统
5 将被终止进程(的PCB)从所在队列移除等待其他程序搜集信息
阻塞原因：
请求系统服务
启动某种操作如I/O
新数据尚未到达
暂时无新工作可做
一般进程可以自己阻塞自己，但是需要由操作系统唤醒
进程切换原因：
时钟中断 执行完一个时间片
I/O中断
内存访问出错
虚拟存储中，需要的指令或数据不在内存
陷阱
执行遇到错误
可能使进程转换到终止状态
进程切换
作用于进程之间的一种操作，当分派程序收回当前进程CPU并准备把他分派给某个就绪进程时，该操作将被引用
模式切换
进程内部引用的一种操作，当用户程序转入系统调用或相反时该操作将被引用
进程切换一定引发模式切换(调度程序在内核)，反之则不然
调度：在一个队列中按照某种方法选择一个合适个体的过程。
算法设计标准：公平性、处理及利用率、提高系统吞吐量、尽量减少进程响应时间
调度原则：
用户角度：响应时间、周转时间、截止时间
系统角度：系统吞吐量、处理机利用率、各类资源的平衡使用、公平性及优先级
响应时间：从用户通过键盘提交一个请求开始直到系统首次产生响应为止的时间
=输入的请求发送到处理机的时间+处理机对请求信息进行处理的事件+将响应结果发送到输出中断的时间
周转时间：从作业提交给系统开始到作业完成为止的时间间隔 主要用于评价分时系统性能
=作业在外存排队等待调度的时间+进程在就绪队列中等待的时间+进程被处理机执行的时间+等待I/O操作完成的时间 主要用于评价批处理系统性能
截止时间：某任务必须开始执行的最迟时间或必须完成的最迟时间 主要用于评价实时系统的性能
系统吞吐量：单位时间内系统所完成的作业数 主要用于评价批处理系统的性能
长程调度和中程调度可以决定那些进程进入内存，考虑系统资源均衡实用。进程调度不可
内核提供服务通过原语实现
仅考虑优先权可能出现饥饿，可以将进城排队时间等因素纳入优先权的计算
长程调度：作业从外存调入内存 作业队列
中程调度：进程在外存和内存之间切换 进程队列
短程调度：进程调度 进程队列
I/O调度：阻塞队列(请求IO进程队列)调度
长程调度：又称为高级调度或作业调度，位被调度作业或用户程序创建进程，分配必要的系统资源，并将新创建的进程插入到就绪队列等待短程调度。某些采用交换技术的系统将新创建的进程插入到就绪/挂起队列，等待中程调度。在批处理系统中，作业进入系统后现驻留在磁盘上，组织成批处理队列称为后备队列，长程调度从该队列中选择一个或多个作业为之创建进程
长程调度2个问题：
选择多少个作业进入内存？取决于允许同时在内存中运行的进程数
选择哪些作业？取决于长程调度算法
中程调度：又称为中级调度，是对换功能的一部分。当内存空间非常紧张时或处理机找不到一个可执行的就绪进程时，需要选择一个进程换出到外存，释放出内存空间给别的进程使用，当内存空间较充裕时，从外存选择一个挂起状态的进程调度到内存。
目的：提高内存的利用率和系统吞吐量
短程调度：又称进程调度或低级调度，决定就绪队列中那个进程或的处理机
PCB队列排队
进程调度算法：
先来先服务FCFS
方式：按照进城到达的先后顺序排队，每次调度队首进程。属于非剥夺调度方式，实现简单。对于后进入队列而运行时间较短的进程或I/O进程而言可能需要长时间的等待。
特点：
对短进程不公平
由于长进程可能排在队列前面，必将增加队列后部进程的等待时间，从而将增加平均周转时间。
不利于I/O型进程，未有效利用系统资源
一般滴FCFS与其他调度算法混合使用，例如系统可以按照不同优先级维护多个就绪队列，每个队列内部按照FCFS算法调度
适合长程、中程和短程调度
短进程优先
方式：判断就绪队列中哪一个进程预期执行时间最短或后被作业队列中哪一个或几个作业的预期执行时间最短。属于非剥夺调度算法
特点：
改善了系统性能，降低了系统平均等待时间，提高了系统吞吐量
很难预测进程执行时间
可能导致长进程饥饿
非剥夺调度算法未考虑进程紧迫程度，不适合分时系统和事务处理系统
时间片轮调度法
方式：在一个分时联机系统中同时又n个人通过各自的终端共享一台主机，终端完成输入输出操作，主机负责从终端发来请求，为之建立进程、协调各进程的运行，调度各个进程等，并尽量满足每个终端用户对响应时间的要求
时间片属于剥夺调度算法，进程切换会增加系统额外开销。如果时间片过短进程切换会非常频繁从而降低处理机效率，时间片过长则无法满足交互式用户对响应时间要求。时间片大小确定应综合考虑系统最大用户数、响应时间、系统效率等多种因素。
时间片轮调度法平均周转时间并不比FCFS和短进程优先调度算法小。常用于分时系统及事务处理系统。对于短的、计算型的进程较有利，不适合于批处理系统的进程调度，不利于I/O型的进程。
改进方法：将I/O阻塞事件完成的进程单独组织一个就绪队列，该队列进程的时间片可以设置小一些优先调度。
如何设定进程的优先级：
重要性
急迫性
均衡系统资源的使用
对资源的占用程度(短进程赋予高优先级)
动态优先级
优先级随着进程运行的剩余时间减少而上升，使将要执行结束的进程尽快完成
随着进程排队等待时间增长而上升，使等待时间越长的进程优先得到调度，不至于长时间饥饿
可以在每个时钟中断时或需要进程切换时重新计算就绪队列中个进程的优先级，并优先调度高优先级的进程。
2种调度算法：剩余时间最短优先、响应比高者优先
剩余时间最短者优先：
在时间中断时根据就绪队列中各进程剩余时间动态调整优先级，剥夺型的短进程优先调度算法。
很难准确估计进程剩余执行时间，对长进程不公平，不像FCFS算法偏袒长进程也不想轮转调度算法产生很多中断。
响应比高者优先：
进程优先级与等待时间成正比，与进程预期执行时间成反比
很难准确估计进程预期执行时间，每次调度前需要计算响应比增加系统开销
反馈调度法：
利于短进程，但可能使长进程饥饿
时钟中断：新进程到来、CPU空闲
操作系统笔记4
多线程
引入进程：描述和实现多个程序并发执行，改善资源利用率及提高系统吞吐量
引入线程：减少程序并发执行时系统付出的额外开销是操作系统具有更好的并发性
进程2个基本属性：拥有资源的独立单位、独立调度的基本单位
进程作为资源的拥有者和系统调度对象，需要花费系统较大的额外开销，故系统中同时存在的进程数目不宜过多，切换频率不宜过高，而这也就限制了并发度的进一步提高
目标：既能提高进程并发度又能降低系统额外开销
实现：将进程资源申请和调度属性分开，即进程作为资源的申请和拥有者，但不作为调度的基本单位，产生了线程。线程自身不拥有系统资源只拥有少许运行中必不可少的私有资源，线程可与同属进程的其他线程共享进程的全部资源
进程中的所有线程共享进程状态。线程具有3种基本状态：就绪、执行和阻塞 一般不具有挂起状态(资源共享)
线程操作
派生：系统创建进程时会派生一个进程，同一进程中的线程可以派生其他线程
阻塞：当线程需要等待某事件时，将会被阻塞，释放处理机执行其他线程
解除阻塞：阻塞事件发生，插入到就绪队列等待调度
结束：线程执行完毕释放私有资源
线程阻塞不一定引起整个进程阻塞，否则引入线程并发性不会提高
MSDOS：单用户、单进程、单线程
UNIX：多用户、多进程、单线程
Java虚拟机：单进程、多线程
Windows/Linux：多进程、多线程
同一进程中的线程间切换不会引起进程切换，但当一个进程中的线程切换到另一个进程中的线程时会引起进程切换
系统开销
操作系统管理进程的开销显著地大于管理线程的开销。进程切换的开销也远大于线程切换的开销。由于统一进程中的多个线程具有相同的地址空间，是他们之间的同步和通信也比较容易。有些类型的线程切换、同步和通信都无需系统内核的干预
线程类型
用户级线程创建、撤销及切换等操作全部由支持线程的应用程序完成，内核并不知道线程存在
用户级线程阻塞是否会引起整个进程阻塞？
当进程中的一个线程需要等待另一线程的输出数据而阻塞，整个进程并不会阻塞，即进程保持执行状态，其内的某个线程也是执行状态。
当线程因为I/O阻塞时，内核需要启动系统I/O，控制从用户级转到系统内核级，这时常会引起整个进程阻塞。随即将发生进程切换，进程调度程序重新调度另一个就绪进程执行
用户级线程：
管理和控制仅在用户级进行，线程切换无需内核干预，没有模式切换减少了模式切换的开销
调度更灵活，应用程序可以根据需要选用线程库中不同线程调度算法，不受系统内核进程调度程序约束
线程库独立于系统内核，可以运行在不同操作系统之上，使用户级线程可以得到不同操作系统的支持，无需修改内核
用户级线程存在问题：
由于很多系统调用都会引起阻塞，用户级线程中的系统调用常常会引起线程及整个进程阻塞，削弱线程并发性
由于系统内核不知用户级线程的存在，可能出现进程切换时强行中断某个执行线程
很难实现不同进程的线程并发(内核并不知道线程存在)
内核级线程：
负责内核级线程创建、撤销、切换等操作，应用程序可以设计成多线程程序，多个线程同属于一个进程。系统以线程为调度单位。进行线程切换时需要保存整个进程上下文以及线程上下文，这样当进程中某个线程阻塞时内核可以调度另一个就绪线程执行。线程切换需要进行模式切换
进程互斥与同步
死锁：被阻塞进程永久得不到申请的资源
临界资源：必须互斥使用的资源
临界区：访问临界资源的代码
任何时刻只允许一个进程进入临界区，实现进程对临界资源的互斥访问
临界区使用原则(互斥条件)
忙则等待：每次只允许一个进程处于临界区
有限等待：进程只能在临界区内逗留有限时间，不得使其他进程在临界区外无限期等待
空闲让进：如果临界区空闲则只要有进程申请就立即让其进入
让权等待：进入临界区的进程，不能再临界区内长时间阻塞等待某事件，必须在一定期限内退出临界区
不能限制进程额执行进度及处理机数量
必须保证进程对共享变量修改是正确的，完整性，更强调对数据写操作互斥进行
必须保证数据一致性，一般通过事务处理。只有退出临界区后，才允许别的进程进入临界区进行数据修改
进程通信方式：消息、管道、共享存储区
通过消息传递实现进程传递时，由于没有共享资源故无需互斥，但仍可能出现死锁和饥饿
管道是一种文件，一个进程写，一个进程读
互斥与同步解决策略：
软件方法：由进程自己通过执行相应的程序指令实现与别的进程的同步和互斥。始终不能解决忙等现象
硬件方法：通过屏蔽中断或才用专门的机器指令控制同步与互斥。
进程切换需要依赖中断实现，进程进入临界区前屏蔽中断，退出临界区时打开中断，中断屏蔽后系统时钟中断也被屏蔽，处理机将不会切换到其他进程。
约束条件太强，终端屏蔽以后系统将无法响应任何外部请求，也不响应当前执行进程的任何异常及系统故障，严重地降低了处理机性能。这种方法仅对单处理机系统有效，如果系统有2个或多个内存共享处理机，屏蔽中断仅仅对执行本指令的处理机有效，其他处理机仍将继续运行，并可以访问共享内存空间。存在忙等现象，可能出现饥饿，可能导致死锁
一些专用机器指令也能实现互斥，机器指令在一个指令周期内执行，不会受到其他指令的干扰，也不会被中断。
信号量方法(semaphores)：信号量方法已成为控制进程同步与互斥的通用方法，解决了忙等问题
管程方法：面向对象
消息传递方法
死锁：进程竞争系统中的资源且对资源的总需求量超过系统能提供的最大资源量
可重用资源：某一时刻仅允许一个进程使用、不能被进程消耗、释放以后还可以被其他进程使用的资源。
可消耗资源：可以创造和撤销的资源，其数量不限。如中断、信号、消息、buffer中的数据
死锁产生条件：
1.互斥：竞争的资源一次只能被一个进程使用
2.占有且等待：当一个进程占有一些资源，同时又申请新的资源，如果新资源申请失败进程将占有资源且阻塞等待
3.非剥夺：进程已占有的资源不能被其他进程强行剥夺
4.循环等待：在系统中存在一个由若干进程形成的环形请求链，其中的每一个进程均占有一些资源同时又申请环形请求链的下一个进程所占有的资源。
前3个为必要条件非充分条件，4个条件一起构成充要条件
解决死锁方式：
1.预防死锁 进程申请资源必须遵循某些预先制定的限制条件，以破坏产生思索的四个必要条件中的一个或多个，防死锁发生 该方法严格限制了系统资源分配和使用会降低系统资源利用率
2.避免死锁 进程申请资源时需要预先判断，如果满足这次资源导致死锁则请求将会被拒绝，让请求资源进程阻塞等待直到所需的资源可分配为止 该方法并不严格限制产生死锁的四个必要条件以提高系统资源利用率
3.检测并解除死锁 进程申请资源时不进行任何限制，即允许死锁发生，要求系统定期或不定期检测是否有死锁发生，当检测到死锁时在力求解除死锁 实践证明该方法可进一步提高资源利用率
解除死锁：
1.撤销死锁进程
2.把死锁进程恢复到前一个检查点
3.按照最小代价原则逐个选择死琐进程进行撤销知道解除系统死锁
4.按照最小代价原则逐个剥夺进程资源(可恢复)，解除死锁
最小代价原则：
到目前为止，花费处理机的时间最小的进程
到目前为止，产生输出最少的进程
估计未执行部分最多的进程
到目前为止已获得资源量最少的进程
优先级最低的进程
页:
[1]