操作系统提纲

我宣布，心软的丁丁老师应该是所有计科同学的男神

调度算法PV操作作业调度 大题：①进程调度（顺序、等待时间）、②PV操作（伪代码）、③作业调度（各种时间）、④分页式存储（查找物理地址）、⑤分段式存储（查找物理地址）⑥缺页中断（三种算法原理、优缺点、手工图解方法）、⑦磁盘调度、⑧....

第一章：引论

操作系统定义：操作系统是计算机系统中的一个系统软件，他统一管理计算机的软、硬件资源和控制程序的执行

1. 操作系统阶段：

   1. 手工操作、早期批处理、执行系统（通道和中断技术的出现）、

   2. 多道批处理系统（标志着操作系统进入日趋成熟的阶段）、

   3. 分时（多个用户或任务可以同时共享计算机的资源，和多道标志着操作系统的初步形成）、【dd举例】

   4. 实时（在规定的时间内完成对该事件的处理，并控制所有实时任务协调一 致地运行）、

   5. 通用操作系统、微机操作系统、网络操作系统、

   6. 分布式操作系统（基础是计算机网络）、嵌入式操作系统

2. 操作系统分类：批处理OS、分时OS、实时OS、微机OS、网络OS、分布式OS、嵌入式OS

3. 操作系统特征：【可能简答题】

   1. 并发(concurrence，基本特征)：&#x5E76发性是指宏观上在一段时间内多道程序同时执行，单处理器系统中，微观上这些程序是交替执行的。（注意：并发是多个事件同一时间发生；并行是多个事件同一时刻发生，要有多核）

   2. 共享(sharing，基本特征)：所谓共享是指系统中的资源可供主存中多个并发执行的进程同时使用。&#x61.互斥共享方式：某些资源（比如打印机），尽管可以提供给多个进程使用，但是不能同时占用。这些我们一般称为临界资源，要求被互斥共享（和第二章的处理器管理联系）。b.同时访问方式：宏观上“同时”，微观上是交替访问的，比如磁盘。

   3. 虚拟(virtual)：&#x5728多道分时系统中，虽然只有一个CPU，但是因为多道技术和分时技术，会让每个终端用户都认为有一个CPU在专门服务，这就是将一个物理上的CPU虚拟成多个虚处理器，只在逻辑上存在。

   4. 异步性(asynchronism，重点)：&#x7531于需要的资源不一样，通常进程的执行，并非“一气呵成”，而是以“走走停停”的方式运行。即使先进入主存的作业也有可能后完成，而后进入主存的作业先完成。（例子：假设采用时间片轮转调度算法，先进入主存的作业时间长，后进入主存的作业时间短，就有可能因为时间片的平均分配，让后者先完成。注意区分和第三章的作业调度算法，第三章的习题进入主存的进程都是不可以被打断的，所以会看到每个作业都是按时间执行的）

\

第二章：处理器管理

1. 进程的概念

   1. 程序的一次执行过程，系统进行资源分配的基本单位

   2. 扩展：进程特点：

      1. 动态性：&#x7531创建而产生，由调度而执行；有一定的生命周期。

      2. 并发性：&#x591A个进程实体同存于主存中，并能在一段时间内同时运行。

      3. 独立性：&#x8FDB程实体是一个能独立运行的、系统中独立获得资源和独立调度的基本单位。

      4. 异步性：&#x6309照独立的、不可预知的速度向前推进。

      5. 结构性：&#x4E00个进程由程序段、数据段、进程控制块三大部分组成。这三大部分被统称为“进程上下文”

      PCB：存放os用于记录和描述进程状态的数据结构，进程控制块，是进程存在的唯一标志进程队列：处于相同状态的进程（就绪队列、等待队列

   3. 状态切换【期末可能考选填，期中考了大题】

      1. 
   4. 进程通信：进程之间的信息交换

      1. 共享存储器系统：共享数据结构 & 共享存储区

      2. 消息传递系统：原语

      3. 管道通信系统：连接一个读进程和写进程以实现通信的共享文件（pipe文件

   5. 进程同步

      1. 类型：直接同步、间接同步

      2. 分类：互斥同步、条件同步、信号同步

2. 线程

   1. 定义：轻量级的进程

   2. 分类：用户级线程和内核级线程

   3. 状态（6种）：New、Runnable、Blocked、Waiting、Timed_Waiting、Terminated

3. 进程和线程的区别

   1. 【职能】进程就是来加载指令，管理内存，管理io的；线程是一个指令流，将指令按顺序交给cpu运行

   2. 【特点】进程是资源分配的最小单元；线程是调度的基本单位。进程是线程的容器，线程存在于进程中

   3. 【通信】进程通信较为复杂，拥有共享的资源，进程给线程提供虚拟内存、全局变量等资源

      • 线程更轻量，线程上下文切换成本一般上要比进程上下文切换低【因为它们共享进程内的内存，比如说多个线程可以访问同一个共享变量】

4. 进程调度的算法（掌握，一般结合作业调度去考应用题，即列出进程调度时间和作业调度时间的表，而通常又是先来先服务或者优先数调度。时间片轮转调度会考选填等小计算，了解多级反馈队列的特点）

   1. 先来先服务算法。&#x6613于理解。

   2. 优先数调度算法。&#x5148比较优先数，优先数相同再按先来先服务。确定优先数的方法又分为两类：a.静态法。在执行之前就写死，根据进程的类型给予不同的优先数；b.动态法。根据占用CPU的时间长短和就绪队列的进程等待CPU的长短来决定的，不是一成不变的。

   3. 时间片轮转调度算法。q = R/N（q即时间片长度，R是系统要求对响应时间的要求，N是就绪队列中所允许的最大进程数。）

   4. 多级反馈队列调度算法。注意：在被抢占的情况下，是回到本队列的队尾。

5. pv操作【大题】，看看课后习题27、28、29、30、31、32

   1. 注意先P操作同步信号量再P操作互斥信号量

   2. 定义信号量并初始化

6. 死锁【简答题】

   1. 原因：竞争资源 ＋ 进程推进顺序非法。

   2. 条件：

      1. 互斥条件：&#x8FDB程应互斥使用资源，另一个进程请求一个已被占用的资源时，会被置成等待状态，直到占用者释放资源。

      2. 占有且等待条件：&#x4E00个进程请求资源得不到满足时，不会释放已占有的资源。

      3. 不剥夺条件：&#x5DF2被占用的资源不能被剥夺式地抢占，只能由进程自己来释放。（CPU就是可剥夺抢占的，打印机一般是不能剥夺的）

      4. 循环等待条件：&#x5B58在一个循环等待链。其中，每一个进程分别等待另一个进程所持有的资源，造成永远等待。

   3. 解决：

      1. 预防死锁：破坏四个必要条件中的一个或几个

         1. 1. 破坏请求条件：资源一次性分配

            2. 破坏保持条件：不能全部满足就一个也不分配

            3. 破坏不可剥夺：不能获得全部资源就自动释放

            4. 破坏环路：资源有序分配

      2. 避免死锁：防止系统进入不安全状态（银行家算法【可能考填空题，这个注意一下】：在资源分配之前预先判断这次分配是否会导致系统进入不安全状态，以此决定是否答应资源分配请求)

      3. 死锁的检测和解除：允许死锁发生，但OS会检测出死锁的发生，然后采取某种措施解除死锁。用进程-资源分配有向图来检测环路。

7. 调度

   1. 高级（作业，进入系统）

   2. 中级（交换，内存到外存）

   3. 短期（任务，获取CPU）

   4. IO调度（IO操作）

\

第三章：作业管理

1. 作业调度的性能指标（应用题必考周转时间、平均周转时间、平均带权周转时间）

   1. CPU利用率：指的是有效运行时间和总运行时间之比。

   2. 吞吐能力：指单位时间内能完成作业的数量。

   3. 周转时间：①在输入井后备队列中等待作业调度的时间；②进入主存后等待进程调度的时间；③作业占据CPU执行的时间；④（容易漏掉）进程等待I/O操作完成的时间。

   4. 平均周转时间：所有作业的周转时间的平均值。

   5. 平均带权周转时间：周转时间/运行时间 =（运行时间+周转时间）/运行时间

2. 高级调度和低级调度

   1. 高级调度（又称作业调度）：把后备作业队列中的部分满足资源要求的作业调入主存。有机会占用处理器，即就绪队列（上文第二章第2点）。

   2. 低级调度（又称进程调度）：即按照某种原则（进程调度算法）决定谁能占用CPU。

   3. 中级调度（平衡负载调度）：有些暂时不能运行的进程调出主存，使其处于挂起状态，即负载过重，平衡负载。

   4. 
3. 作业调度算法（联系进程调度算法考应用题，作业调度指调入到就绪队列）

   1. 先来先服务算法：&#x65E0技术含量。

   2. 短作业优先算法：&#x65E0技术含量。

   3. 响应比最高优先算法：响应比实际上就是带权周转时间，即周转时间/运行时间。

   4. 优先数调度算法：&#x65E0技术含量。

   5. 分类调度算法：&#x5373分成CPU密集型作业队列，IO密集型作业队列，均衡型作业队列。作业调度程序调度时，各取一些装入主存。

   6. 时间片轮转调度算法（重点，本次必考，没有课后习题，只能结合P91（4）例子看）：（为简单起见，假设采用基本时间片，书中的时间片长为2个时间单位。用完一个时间片后未结束，则插入到当前队列的末尾，除了运行结束，不会有作业只占据半个时间片。解题的时候画出一个等待队列一步一步完成。）

必考题型：作业调度+进程调度

1. 先给所有作业放在作业井排队

2. 找出所有满足需求的作业 → 作业调度算法给这些作业排序将其调度入就绪队列并更新系统的资源。重复②，直到没有满足需求的作业。

3. 所有按照②的排序的作业在就绪队列 → 根据进程调度算法被调度（不一定是先到先服务）

\

1. 操作系统与用户的接口【这个要考吗】

\

第四章：存储管理【现在没怎么看，头晕】

1. 了解内存管理方式

   1. 连续空间的内存管理

   2. 离散的——分页分段 这三种要有逻辑

2. 缺页中断【重要指标】 处理

3. 缺段？避免缺段的方法

4. 页式段式存储管理

5. 内存地址的转换 —— 虚拟意义 —— 物理和内存的转换【p156 T13,14做一下，p157 T15 123做一个子题 】

物理地址和逻辑地址（关注定义、区别、联系，考选填，一般不会直接问定义、区别、联系，而是结合段式存储管理和页式存储管理结合出）

1. 物理地址（绝对地址）：主存中实际上存在的物理存储空间。

2. 逻辑地址（相对地址和虚地址）：物理上不存在，操作系统为了方便用户程序编制，为其提供映射，存储到相应的物理地址，而用户是不知道存储在哪个物理地址的，也可以说是对用户屏蔽了。

\

第五章：设备管理

1. IO控制方式【选填】

   1. 直接程序控制方式：简单来说就是CPU监督I/O设备，但是I/O又比较慢，CPU又要监督，不断访问它的忙碌字段。

   2. 中断驱动控制方式：CPU不再不断询问，而是当I/O出问题时，请求中断才会报告给CPU。

   3. 直接存储器访问控制方式：不再以字为单位，而是以块为单位，并把监督权交给DMA控制机构，如无意外，无需报告给CPU，出现中断，则报告给CPU。

   4. 通道控制方式：进一步减少干预程度，以一组块为单位传输数据，进一步下放监督权给通道，由通道完成对I/O设备的操作。

2. 【磁盘xx定位】读写操作的具体阶段 对应 评价磁盘三个指标【驱动调度的三个时间】

   1. 寻找时间：磁头在移动臂带动下移动到指定柱面的时间；

   2. 延迟时间：指定扇区旋转到磁头下方位置所需的时间；

   3. 传送时间：由磁头读写，完成信息传送的时间。

3. 磁盘调度，电梯算法，单向双向方向扫描，最短距离调度

   1. 先来先服务FCFS：无技术含量；

   2. 最短寻找时间优先调度算法SSTF：无技术含量；

   3. 单向扫描调度算法：也无太大技术含量，注意该算法一定会运行到尽头再返回另一端重新扫描，其规则是只向一边扫描；

   4. 双向扫描算法：和单向的算法类似，只是在回程时也扫描，而不是像单向一样回到另一端再开始扫描；

   5. 电梯调度算法：只考虑磁头当前方向，且不用直至尽头。

   6. 举例：假设磁头当前在磁道50，有以下请求顺序：[45, 10, 95, 60, 30, 70]电梯算法（SCAN）

      1. 从50开始，先处理比50大的请求：[60, 70, 95]

      2. 到达磁盘边界后，反向处理：[45, 30, 10]

      单向扫描（LOOK）

      1. 从50开始，先处理比50大的请求：[60, 70, 95]

      2. 立即反向处理比50小的请求：[45, 30, 10]

      双向扫描（C-SCAN）

      1. 从50开始，处理比50大的请求：[60, 70, 95]

      2. 到达磁盘边界后，直接返回起始端，处理比50小的请求：[10, 30, 45]

      最短寻道时间优先（SSTF）

      1. 从50开始，选择距离最近的请求：[45]

      2. 从45继续，选择最近的请求：[30]

      3. 重复以上步骤，处理顺序为：[45, 30, 10, 60, 70, 95]

\

1. I/O系统结构

四级结构：主机->通道->设备控制器->I/O设备

1. 缓冲技术（熟记+理解，考选填、简答）

为了缓解CPU与外围设备之间速度不匹配和负载不均衡的问题，为了提高CPU和外围设备的工作效率和系统中各部件的并行工作程度，在现代操作系统中普遍采用了缓冲技术。减少中断频率：设置多位的缓冲区，减少相应的时间。缓冲机制：a.单缓冲；b.双缓冲；c.多缓冲：循环缓冲机制；d.缓冲池：3个缓冲区队列，空缓冲区队列，输入缓冲区队列，输出缓冲区队列；缓冲区有四种缓冲区，收容输出，提取输出，收容调入，提取调入。\

1. 设备的逻辑号和物理号（理解，考选填）

逻辑设备名是用户命名的，可以更改；物理设备名是系统规定的，是不可更改的。设备管理的功能之一就是将逻辑设备名映射为物理设备名。用户以设备类、逻辑号向系统提出使用设备的要求。

\

第六章 文件管理

p233 T34、35

1. 磁盘定位，由位图知道怎么把它转化到具体的这个磁盘物理单位？每一个柱面，磁头，扇区？ =》 涉及到逻辑地址转为物理地址【大题】

1. 文件控制块

一个文件控制块唯一标识一个文件。

1. 文件基本信息

2. 文件结构信息

3. 文件管理信息

4. 文件存取控制信息

\

1. 文件的逻辑结构（看懂）

（1）无结构文件（流式文件）：无结构的一串字符的集合，例子：源程序、可执行文件、库函数、文本文件。我们平时写文本文件时就是使用了输入输出流。（2）有结构文件：若干个逻辑记录组成的，类似二维表，数据库的关系。又可分为：a.顺序文件（列表）；b.索引文件（字典）；c.顺序索引文件（DataFrame）。\

1. 文件的物理结构（了解）

（1）顺序结构（2）链接结构（3）索引结构（4）直接文件（哈希）\

1. 文件目录结构（看懂）

（1）一级目录结构（2）二级目录结构（3）多级目录结构（是建立在二级目录结构基础之上的，是多个用户可以建立自己的多级目录）（4）无环图目录结构\

1. 辅存空间的管理

空闲区链表（重点）将空闲区以链表的形式组装，分配时通常按照最先适应算法，顺序分配满足文件要求的若干物理块给用户。每次都是分配第一个空闲区，若分配完闭则调整首指针继续分配；回收时要和邻接的空闲区合并。优点：链表长度短，不用频繁访问辅存，效率高。缺点：分配和回收过程复杂。