计算机操作系统
通常把计算机硬件系统上配置的第一个大型软件称为计算机操作系统。该软件满足:
管理计算机系统的硬件和软件；控制计算机系统的工作流程；为其它软件和用户提供安全方便的运行、操作环境；提高计算机系统的效率。? 现代的计算机操作系统都采取了并发执行的工作流程，多道程序设计技术奠定了操作系 统形成的基础。
例子：假定某计算机系统需要执行两道程序A、B，程序A、B的任务描述如下，求画出顺序执行和并发执行的工作方式。
image-20230626133324259
批量处理，方便操作自动执行，资源利用率高缺少人机交互能力，不便于调试程序平均周转时间长同时性交互性独立性及时性高及时性高可靠性（1）处理器管理
（2）存储器管理
（3）设备管理
（4）文件系统
（5）用户接口及作业管理
（1）命令接口 键盘命令
（2）图形接口 窗口菜单
（3）程序接口 系统调用
（1）一组操作系统设计人员事先编写的子程序，这些子程序作为内核的一部分；
（2）程序员使用这组子程序的方法。
顺序执行是指：处理器在开始执行一道程序后，只有在这道程序运行结束后才能开始执行下一道程序。
并发执行是指：在多道程序设计环境下，处理器在开始执行一道程序的第一条指令后，在这道程序完成之前，处理器可以开始执行下一道程序，同样地，更多其他程序也可以开始运行。
动态性并发性独立性结构性异步性
image-20230623141649123
进程控制块PCB的作用：
(1）是OS对并发执行的进程进行控制和管理的根据；
(2）也是系统用来感知进程存在的根据，即 PCB是进程存在的==唯一标志==
(3）正是由于建立了PCB，进程才成为了资源分配，CPU调度的单位。
控制同步通信调度死锁 进程控制的原语主要有创建、撤销、阻塞、唤醒、切换等。创建的主要操作: （1）建立一个PCB
（2）生成pid
（3）初始化PCB各项内容
（4）加入合适的就绪队列
阻塞将运行状态变为阻塞状态；
唤醒把移出进程的PCB状态改为就绪状态。
信号量是一种变量，一个信号量对应一个整型变量value、一个等待队列bq，同时还可以对应其他的控制信息。
为了简便起见，这里把信号量的数据类型简化定义如下。
s是一个信号量，p操作定义如下：
两个或两个以上的一组并发进程，称他们具有互斥关系。一般PC问题（n=1，m=1，k>1）可描述为：一个生产者和一个消费者通过一个缓冲池共同完成“生产和消费”任务。复杂PC问题（n>1，m>1，k>1）可描述为：N个生产者和M个消费者通过一个缓冲池共同完成“生产和消费”任务。例1：进程A与进程B共享一个文件file，设此文件要求互斥使用，则可将file作为临界资源，有关file的使用程序段分别为临界区CSA和CSB。
例2：桌子上有一只盘子，每次只能向其中放入一个水果。爸爸专向盘子中放苹果，妈妈专向盘子中放橘子，儿子专等着吃盘子中的橘子，女儿专等着吃盘子中的苹果。只有盘子空时，爸爸或妈妈才可向盘子中放一个水果。仅当盘子中有自己需要的水果时，儿子或女儿可以从盘子中取出水果。
含义：两个或多个进程之间交换数据的过程称为进程通信，其中提供数据的一方称为发送进程，得到数据的一方称为接收进程。
为什么需要：
任务协作进程的独立性共享存储区通信消息缓冲通信信箱通信管道通信线程的含义：把进程细化成若千个可以独立运行的实体，每一个实体称为一个线程。
引入线程的目的：
实现进程内部的并发执行，提高并行程度减少处理器切换带来的开销简化进程通信方式线程的两种类型：
（1）用户级线程
（2）系统级线程
（1）作业调度
（2）进程调度
（3）交换调度
（4）设备调度
（1）提交状态
（2）后备状态
（3）执行状态
（4）完成状态
周转时间=完成时间-到达时间
平均周转时间：
作业名所需要CPU时间作业128作业210作业31假设提交顺序为1、2、3，则平均作业周转时间：T=(28+38+39)/3=35
（1）非抢占方式
（2）抢占方式
（1）先来先服务算法（FCFS）
（2）短作业/进程优先调度算法（SJF/SPF）
（3）时间片轮转调度算法（RR）
（4）高响应比优先权调度算法（HRN）
算法比较FCFSRRSJF/SPFHRP调度方式非抢占式抢占式（按时间片）非抢占式非抢占式吞吐量不定时间片太小，可能变低高高响应时间可能很高对于短进程提供良好的响应时间对短作业/进程提供良好响应时间提供良好响应时间系统开销最小低可能高可能高对进程的作用不利于短作业/进程和I/O忙型公平对待不利于长作业/进程良好的均衡饥饿问题无无可能无 例1：假定在一个处理机上执行以下四个作业，在单道程序环境下，处理器工作时间从9:00开始计算，请写出用FCFS、SJF、和HRN算法时各作业的调度顺序，周转时间和平均周转时间。作业号提交时刻（h:m）运行时间（h）j19:002j29:201j39:400.5j49:500.3作业号提交时刻（h:m）运行时间（h）调度顺序开始时间完成时间周转时间（分）j19:00219:0011:00120j29:201211:0012:00160j39:400.5312:0012:30170j49:500.3412:3012:48178平均周转时间=（120+160+170+178）/4=157m=2.62h
作业号提交时刻（h:m）运行时间（h）调度顺序开始时间完成时间周转时间（分）j19:00219:0011:00120j29:201411:4812:48204j39:400.5311:1811:48128j49:500.3211:0011:1888平均周转时间=（120+208+128+88）/4=135m=2.25h
响应比计算=（开始时间–到达时间）/服务时间①9:00时刻，后备队列只有1个作业j1，选择j1运行
②11:00时，后备队列有j2、j3、j4，分别计算响应比
R1=(11:00–9:20)/160=1.67
R2=(11:00–9:40)/130=2.67
R3=(11:00-9:50)/18=3.89 ??选择j4运行
③11:18时刻，后备队列有j2、j3，分别计算响应比
R2=(11:18–9:20)/160=1.97
R3=(11:18–9:40)/130=3.27 ??选择j3运行
④11:48时刻，后备队列只有1给作业j2，选择j2运行
最后调度顺序为1、4、3、2与SJF算法顺序一致，图与SJF图一样所示。
平均周转时间=（120+208+128+88）/4=135m=2.25h
例2：假定某分时系统有两个同时到达的进程AB，它们的任务如下： 进程A：6ms CPU ? 10ms I/O ? 3ms CPU 进程B：12ms CPU ? 5ms I/O ? 6ms CPU 采用RR算法，时间片为4ms，画出RR算法的调度图，并计算进程A和B的周转T及系统的平均周转T？若时间片为3ms呢？
image-20230626151035992
含义：多个进程在运行过程中因争夺资源而造成的一种僵局，若无外力作用，这些进程都将无法向前推进
死锁产生的根本原因是：系统拥有的资源数量小于各进程对资源的需求总数
必要条件：
（1）互斥条件
（2）不剥夺条件
（3）请求与保持条件
（4）环路等待条件
在资源分配上采取一些限制措施，来破坏死锁产生的4个必要条件之一
系统处于安全状态是指，这时对于操作系统的所有进程，可以找出一个处理器执行这些进程的顺序，按照这个顺序依次执行各个进程，每个进程都可以运行完成。
image-20230626151722511
①当前系统是否为安全状态？ （安全）
MaxUsedNeed可用(3 3 5)进程A B CA B CA B CA B C顺序P09 5 33 2 16 3 211 15 155P11 7 81 3 40 4 45 10 113P24 4 20 4 14 0 14 7 72P33 2 61 0 12 2 54 3 61P48 7 53 3 35 4 28 13 144②在图4-15状态下,如果进程P2申请request=(0,1,0),系统能否分配？（能分配）
MaxUsedNeed可用(3 2 5)进程A B CA B CA B CA B C顺序P19 5 33 2 16 3 211 15 155P21 7 81 4 40 3 45 10 113P34 4 20 4 14 0 14 6 72P43 2 61 0 12 2 54 2 61P58 7 53 3 35 4 28 13 144③在图4-15状态下,如果进程P5申请request=(1,0,0),系统能否分配？（不能分配）
MaxUsedNeed可用(2 3 5)进程A B CA B CA B CA B C顺序P19 5 33 2 16 3 2P21 7 81 3 40 4 4P34 4 20 4 14 0 1P43 2 61 0 12 2 53 3 61P58 7 54 3 34 4 2 n*(x-1)+1<=r n—>并发程序 x—>每个进程需要x个 r—>临界资源例1：若系统中有5个并发程序，每个进程都需要临界资源3个，问：至少需要多少个临界资源才不会死锁？
答：5*(3-1)+1<=r r>=11
例2：有6个用户同时运行一个程序，该程序需要临界资源为R，如果拥有资源R的数量为15，且进程在运行过程中一次只能申请1个资源R，那么为保证6个用户都能正常运行，这道程序的申请R最大是多少？
答：6*(x-1) <=15 x=3
（1）存储空间的分配和回收
（2）重定位
（3）存储空间的共享与保护
（4）虚拟存储器
? 重定位，也称地址转换或地址映射，就是把虚拟地址转换为物理地址的过程。因为CPU最终是以物理地址存、取数据和指令，所以程序的运行必然需要重定位
? 重定位分为两种方式：静态重定位和动态重定位
??
? 固定分区存储管理的基本思想：操作系统启动时，根据事先的设置，把用户区分成若干个存储区域，每个区域称为一个分区，各个分区的长度可以不相等；启动成功后，分区的个数和每个分区的长度不再改变；程序装入时，一个分区只能分配一道程序，而一道程序也只能占用一个分区，这种分配方式也称连续分配。
? 可变分区也称动态分区，其思想是：操作系统启动成功后，整个用户区作为一个空闲区。一般地，在程序装入时。系统根据程序的实际需求量查找一个合适的空闲区，如果该空闲区长度等于程序的实际需求量，就可以直接分配；否则，将其分为两个分区，其中一个分区长度等于当前程序的需求量，并分配给程序，另一个分区作为空闲区保留下来。进程完成被撤销后，回收其占用的分区，成为空闲区。
???
定义：在分页存储管理的内存分块、进程分页基础上，如果程序装入时要求把程序的所有页全部一次地装入内存，那么这种分页存储管理称为静态分页存储管理，简称静态分页或基本分页。
分页存储管理的基本思想：
（1）内存分块
（2）进程分页
（3）非连续分配
???
（1）先进先出算法（FIFO）
将内存中的页按装入内存的先后顺序排列，淘汰时，选择最先进入内存的页面予以淘汰。
（2）最近最久未使用算法（LRU）
页表中登记每个页被CPU访问的时间，淘汰时选择最近一段时间，最久没有被访问的页。
????
? 刚刚调入内存的页，很快被淘汰调出到外存，在淘汰后不久处理器又要访问到它，而需要将其从外存调入内存，这样可能出现一段较短的时间范围内，集中在少数的几个页之前，系统频繁地进行调入和调出操作。这种状况称为抖动现象，或者颠簸。
? Belady现象是指：采用FIFO算法时，如果对一个进程未分配它所要求的全部页面，有时就会出现分配的页面数增多但缺页率反而提高的异常现象。
（1）存储空间的分配单位粒度
（2）虚拟地址空间的维度
（3）内存分配
（4）碎片
页式存储管理段式存储管理目的实现非连续分配，消减内存碎片更好地满足用户需要信息单位页（物理单位）段（逻辑单位）大小固定（由系统定）不定（由用户程序定）存储空间的分配单位粒度以页为单位分配内存空间，页由硬件虚拟地址结构决定，页长度是固定的以段为单位分配内存空间，段由程序员的程序设计决定，段之间长度往往不相等虚拟地址空间的维度一维二维内存分配把内存空间看成一组大小相等的块组成采用动态分区碎片每一个进程的最后一页可能不足一个块的长度，按页分配内存块时存在内碎片采用动态分区，随着分配和回收的不断进行，可能存在很小的空闲区，造成外碎片优点有效解决了碎片问题；有效提高内存的利用率；程序不必连续存放。更好地实现数据共享和保护；段长可动态增长，便于动态连接? 每个文件拥有一个标识符，称为文件名。
? 文件名是一组字符串，由用户给定，文件命名后，用户通过文件名来使用文件。
? 有了操作系统的文件管理，用户通过文件名访问文件内容，而无须了解文件内容在存储介质上的存放形式与存取细节，用户也就不必关心存储介质的物理特性，文件的这种使用方式称为文件的按名存取。
文件的逻辑结构分为==流式文件==和==记录式文件==。
文件物理结构的基本类型主要有==连续结构==、==链接结构==和==索引结构==。（1）管理简单。
（2）存取速度快。
（3）存储空间连续分配，存储空间利用率不高。
（4）不便于文件内容的增加或删除。
（1）非连续的存储分配，提高了存储空间的利用率。
（2）方便文件内容的增加或删除。.
（3）只适合顺序存取，存取速度慢。
（4）指针信息造成物理块信息不完整，并导致数据无法控制。
（1）非连续的存储分配，提高了存储空间的利用率。
（2）方便文件内容的增加或删除。
（3）实现随机存取。
（4）索引表占用额外的存储空间。
（5）增加检索的开销。
将文件分配在多个离散的盘块上，并将链接各个物理块的指针显式地登记在一张分配表FAT中。
FAT在整个文件卷中仅设置一张，其每个表项的序号为对应的物理块号，而表项的内容则是分配给文件的下一个物理块的指针。
文件的首个物理块地址被登记在它的目录项中。
由于分配给文件的所有盘块号都放在该表中，故把该表称为文件分配表FAT。
二级目录结构把目录分为两级：用户文件目录（UFD）和系统主目录（MFD）
按照用户名查找系统主目录，得到用户文件目录；接着按照文件名查找用户文件目录，得到文件的FCB，从而得到文件在外存中的存储位置。
1、磁盘驱动调度组成
由于同一个磁盘的每个I/O操作，存取一个物理块的时间大致相等，所以，在磁盘驱动调度时，通常不考虑传输时间Tt，并且，把磁盘驱动调度分为移臂调度和旋转调度组成。
2、移臂调度算法例子（SSTF、SCAN、电梯）