【SCU期末】scu操作系统期末简答题整理

操作系统

题型与范围

1.选择题

注：选择题基本上选自平时学习通作业原题

2.简答题

写满不空，非标作答，灵活改卷

3.计算题

写明步骤，按步骤给分

简答题重点

第二章重点（简答题）

（无计算题）

1.操作系统的概念与其他软件的区别

概念：操作系统是控制应用程序执行的程序，是系统软件，是应用程序和计算机硬件之间的接口。对上提供服务，对下管理资源的系统软件。

（操作系统*（英语：Operating System，缩写：OS）*是一种内置的程序，用来协作计算机的各种硬件，以与用户进行交互。常见有Windows，[macOS ](https://baike.baidu.com/item/macOS /8654551?fromModule=lemma_inlink)和开源的 Linux。 根据运行的环境，操作系统可以分为桌面操作系统，手机操作系统，服务器操作系统，嵌入式操作系统等。 操作系统是人与计算机之间的接口。）

**区别：**操作系统和各种应用软件都属于”软件“，本质区别在于对”硬件“管控方式不同，操作系统在硬件管理中处于支配地位，应用软件则没有这个地位；操作系统可独立运行，应用软件不能直接安装在无操作系统的电脑中。

操作系统是系统软件（计算机的主要软件），直接访问系统的硬件。它负责监控计算机的所有其他功能。应用软件是计算机中用于执行特定功能的附加软件。用户可以直接访问这个应用软件，但这个软件在系统中并不是必需的。我们可以使用没有这个应用软件的系统。

操作系统是覆盖在硬件上的第一层软件，他管理计算机的硬件和软件资源，并向用户提供良好的界面。操作系统与硬件密切相关，它直接管理着硬件资源，为用户完成所有与硬件相关的操作，从而极大地方便了用户对硬件资源的使用并提高了硬件资源的利用率。操作系统是一种特殊的系统软件，其他系统软件运行在操作系统的基础之上，可获得操作系统提供的大量服务，也就是说操作系统是其他系统软件与硬件之间的接口。而一般用户使用计算机除了需要操作系统支持以外，还需要用到大量的其他系统软件和应用软件，以使其工作更高效和方便。

2.操作系统的目标与功能（2.1章的三个小标题）

**目标：**方便、有效、扩展能力

**功能：**对上提供服务，对下管理资源的系统软件（作为用户/计算机接口的操作系统、作为资源管理器的操作系统、操作系统的易扩展性）（进程管理、I/O管理、文件系统管理、存储管理、程序开发、系统访问）

3.操作系统的构成模块

进程控制、内存管理、虚拟内存、处理器调度、I/O管理与磁盘调度、文件管理

①4个模块：进程+MM+IO+文件系统；②3个模块：进程+MM+IO/文件系统

4.操作系统发展的脉络

1. 串行处理：必须顺序访问计算机，所有的程序设计都是直接操控硬件，不算操作系统
2. 简单批处理系统：计算机操作员把作业按顺序组织成批，并把整个批作业放在输入设备上，供**监控程序**使用。
   • 监控程序每次读取一个作业到用户程序区域，并把控制权交给这个作业，每个程序完成处理后(控制权)返回到监控程序，同时监控程序自动加载下一个程序。
   • 控制权在监控程序==处理器从监控程序中取指执行
   • 控制器交由作业==处理器遇到了监控程序中的分支指令，到了用户程序中取指执行
3. 多道批处理系统：在内存中保存多个用户程序，在不冲突的条件下切换执行；
   • 吞吐量=n个作业/小时
4. 分时系统：多个用户通过终端同时访问系统，操作系统控制每个用户程序在很短时间内***交替***执行；
   • 人机**交互**：系统能及时响应用户程序中的问题
   • interactive multiprogramming systems, where terminals were connected to systems that allowed access by multiple concurrent users

5.批处理系统和分时处理系统的异同（表2.3）

	批处理多道程序设计	分时系统
主要目标	充分利用处理器	减小响应时间
操作系统指令源	作业控制语言命令 作业提供的命令	终端输入的命令
进程调度	作业A因I/O请求暂停运行时，B才能运行（非抢占）	根据时间片轮转，抢占式
相同点	都是微观上串行，宏观上并行

6.结合操作系统的一般概念和构成，概述linux的综述（结合作业）

1. 开源和自由软件

Linux作为类Unix操作系统，是一种多用户、多任务的操作系统，是一个开源软件，根据GNU通用公共许可证（GPL）发布。这意味着用户可以自由地使用、修改和分发Linux内核及其相关软件。开源社区的贡献使得Linux不断发展，功能不断完善。

*2.多用户和多任务

Linux支持多用户登录和多任务处理。这意味着多个用户可以同时在同一系统上工作，而操作系统能够有效地管理多个任务和进程，确保系统资源的合理分配和使用。

3.移植性

Linux具有高度的移植性，可以运行在从嵌入式设备到超级计算机的各种硬件平台上。其内核的模块化设计使得适配不同硬件变得更加容易。

*4.Linux操作系统的构成可以分为以下几个主要部分：

内核（Kernel）、系统库（System Libraries）、系统工具（System Tools）、Shell（命令行解释器）、应用程序（Applications）

5.Linux发行版

• Ubuntu：基于Debian，用户友好，适合桌面和服务器使用。
• Fedora：由Red Hat支持，包含最新的软件和技术，适合开发者和桌面用户。
• Debian：以稳定性著称，适合服务器和开发环境。
• CentOS：基于Red Hat Enterprise Linux (RHEL)，适合企业级服务器使用。
• Arch Linux：滚动更新，极简设计，适合高级用户和定制化需求。

第三章重点（简答题）

1.进程的概念，进程和应用程序的关系和异同

概念：（资源分配的基本单位）一个正在执行的程序；一个正在计算机上执行的程序实例；能分配给处理器并由处理器执行的实体；由一组执行的指令、一个当前状态和一组相关的系统资源表征的活动单元。进程就是程序的执行过程

关系与异同：

• 关系

  • 进程与程序有关，进程包含程序。程序是进程的核心内容，没有程序就没有进程。进程不仅仅是程序，还包含程序在执行过程中使用的全部资源。没有资源，程序就无法执行，因此进程是程序执行的载体。

• 区别

  • 进程是程序的一次执行过程，它是动态地创建和消亡的，具有一定的生命周期，是暂时存在的；而程序则是一组代码的集合，他是永久存在的，可长期保存。

  • 进程具有并发性，而程序没有；

• 相同

  • 都需要计算机资源来运行（CPU、内存）
  • 都是指令和数据的集合
  • 一个程序可对应多个进程； 一个进程可以执行一个程序或多个程序。

2.进程控制块的概念与功能，以及基本构成（图3.1选几个字段写）

概念：进程控制块(Processing Control Block)，是操作系统核心中一种数据结构，由操作系统创建和管理，主要表示进程状态。

• 操作系统利用PCB描述进程的*基本特征*

• 一个PCB对应一个进程

• PCB可用于描述进程的一些变化，如其状态的变化

功能：是操作系统为支持多线程并提供多重处理技术的关键工具。可以在中断后恢复进程的执行。

基本构成：标识符、状态、优先级、程序计数器、内存指针、上下文数据、I/O状态信息

？3.进程的操作与控制函数（创建、销毁和切换）

• 创建、销毁、切换、同步、互斥

• fork、*exit、*exec

4.进程的五状态图（画图或者给图来描述，不考七状态图）

• 创建态：PCB已创建但还未加载到内存中的新进程
• 就绪态：进入就绪队列，等待CPU的调度
• 运行态：进程正在处理器上执行
• 阻塞/等待态：进程因正在等待某些事件而暂停执行，如等待IO操作完成；
• 退出态：操作系统释放进程

5.进程的切换与态的切换

• 进程的切换时机

  • 产生中断与异常
    进程切换可能发生在：时钟中断、系统调用、缺页故障

• 进程的切换流程

  • 保存处理器上下文
  • 更新当前处于运行态的进程的进程控制块
  • 将其移动到相应队列
  • 选择另外一个进程执行
  • 更新其PCB
  • 更新内存管理数据结构
  • 载入PC和其他寄存器先前的值，恢复上下文

• 进程的切换与态的切换

  • 用户模式到内核模式由中断/异常(如缺页故障)/系统调用 中断用户进程执行而触发

  • 内核模式到用户模式由OS执行中断返回指令将控制权交还用户进程而触发

  • 进程切换必须在操作系统内核模式下完成，这就需要模式切换。即有进程切换，一定有处理器态的切换。

  • 两者区别

    • 模式切换可在不改变运行态进程的状态情况下出现（此时保存上下文”并在以后恢复上下文仅需很少的开销）。
    • 当前正运行进程换为另一状态(就绪、阻塞等)，则操作系统必须使环境产生实质性的变化。

6.学习通的任务-多角度看：多个进程的举例

1）OS的角度：2分 物理控制流：有交替执行

2）进程的角度：3分 逻辑控制流：无交替执行/没有被打断

3）CPU的角度：3分 指令周期：取指令+执行指令

• CPU：CPU根据PC的值来获取并执行内存中的指令，遇到分支指令会在用户程序执行，当超时等中断产生时会到操作系统中取址执行
• OS：通过将CPU的控制权分配给不同程序来实现多个程序之间的交替执行，负责管理程序的执行顺序及进程状态转化
• 某一程序：程序本身不会意识到其他程序存在，以为自己一直占有CPU

7.进程创建的流程（基于linux的fork函数–一次调用两次返回的特点（可以结合图））

Linux中的fork()系统调用是创建新进程的主要方式之一。该调用在父进程中被调用，会复制父进程的所有内存和资源，并创建一个新的子进程。这个过程具有“一次调用和两次返回”的特点。“一次调用”指的是在父进程中调用一次fork()，然后操作系统会创建一个几乎完全相同的子进程，包括父进程的所有内存、文件描述符等。这个过程非常快速，因为实际上只是将父进程的内存映射到子进程的地址空间中。而“两次返回”意思是在一次fork()调用之后，会有两个不同的返回值。这两个返回值为父进程中fork()返回的子进程的进程ID（PID），这个PID用于区分父子进程。而另外一个就是子进程中的fork()返回的0值，这样子进程可以知道自己是新创建的。fork()系统调用的“一次调用和两次返回”特性使得父子进程能够根据返回值的不同来执行不同的逻辑。

以Fork为例

• Fork创建一个继承的子进程：
  • 分配标识符、PCB
  • 复制父进程的变量和内存
  • 将进程设为就绪态，放入就绪队列
• 调用一次，返回两次：子进程返回0，父进程返回子进程标识符，如果出现错误，fork返回一个负值

第四章重点（简答题）

1.线程的概念、线程和线程的关系和异同

**概念：**线程是进程的一条执行流程。资源调度与执行的基本单位（任务的调度与执行）

关系与异同：

• 关系

  • 一个进程有一个或多个线程；

• 不同

  • 进程是资源分配的单位，线程是调度的单位；
  • 线程是轻量级进程：线程创建，终止时间比较短
  • 一个进程的崩溃通常不会影响其他进程。而线程是共享进程的资源，一个线程的崩溃可能导致整个进程的崩溃。

• 相同

  • 同样具有状态之间的转换。
  • 同样具有**就绪，阻塞和执行**三种基本状态

2.线程的实现方法（ULT、KLT、二者综合）（书本P95-图4.5）

3.ULT、KLT两个实践方法的优缺点（两者互补）

实现方式	描述	优点	缺点
用户线程实现 ULT	完全建立在用户空间的线程库上，系统内核不能感知线程存在的实现。 用户线程的建立、同步、销毁和调度完全在用户态中完成	1.不需要切换内核态，效率非常高且低消耗； 2.调度可以因应用程序的不同而不同，可以为应用程序量身定制调度算法； 3.ULT可以在任何操作系统中运行； 4.可以支持规模更大的线程数量	1.ULT在执行一个系统调用时，不仅会阻塞这个线程，还会阻塞进程中的所有线程（由于没有系统内核的支援，阻塞处理等问题的解决十分困难） 2.一个进程只有一个线程可执行
内核线程实现 KLT	直接由操作系统内核支持的线程，由内核来完成线程切换。（内核通过操纵调度器（Scheduler）对线程进行调度，并负责将线程的任务映射到各个处理器上。）	内核线程保证了每个轻量级进程都成为一个独立的调度单元，即使有一个轻量级进程在系统调用中阻塞了，也不会影响整个进程的继续工作。	1.系统调用代价高，需要在用户态和内核态来回切换； 2.轻量级进程要消耗一定的内核资源，一个系统支持轻量级进程的数量是有限的
混合	用户线程与轻量级进程的数量比是不定的，线程创建完全在用户空间完成，线程的调度和同步也在应用程序中进行；一个程序中的多个用户级线程会被映射到内核级线程	应用程序可以使用内核提供的线程调度功能及处理器映射； 同一个用户程序中的多个线程可以在多个处理器上并行，某一线程阻塞不会阻塞整个进程

第五章重点（简答题）

主要考察计算题（信号量）

1.并发要解决的四个问题并把这四个问题简单的名词解释下

同步、互斥、饥饿、死锁

问题	描述	解决
互斥	在并发执行的过程中，确保同一时刻只有一个进程能够访问某个资源，其他进程需要等待	1.软件方法（Dekker，Peterson） 2.硬件方法（关中断，专用指令）
同步	多个并发执行的进程之间相互协调和合作，以保证它们按照一定的顺序和时间间隔执行	信号量
饥饿	由于竞争条件不平等，与其他进程或线程竞争访问共享资源运行期间，被调度器无限忽视，无法访问共享资源的情况，称为饥饿。	哲学家就餐问题
死锁	两个或两个以上的进程（LWP）都在等待互相释放自己的资源，导致进程都不能继续执行的情形	1.死锁预防； 2.死锁避免； 3.死锁检测与解除

2.什么是条件竞争并给予实例（可写伪代码）

**概念：**发生在多个进程或线程读写数据时，其最终结果取决于多个线程的指令执行顺序

3.进程之间的关系

4.解决同步与互斥的方法（三类）

（软件算法不考算法知道有就好，硬件方法考选择题，系统级很重要-信号量与管程）

• 软件方法

  • Dekker算法-2个进程
  • Peterson算法-N个进程

• 硬件方法（不用了解的太详细）

  • 关中断/中断禁用：（单处理器机器）处理器只能交替执行并发进程，不能重叠；让硬件将中断处理延迟到中断启用后。在临界区内，没有中断，没有上下文切换，因此没有并发。

  • 特殊指令：（多处理配置）保证原子性，将两个动作结合到一个指令周期。

    • testset：进入临界区之前，首先用TS指令测试lock，如果为false，则表示空闲，将lock赋为true，关闭临界资源；如果TestAndSet返回true，则一直循环测试，直到返回false，跳出循环，进入临界区。基于这个指令，我们可以实现获取资源和释放资源的操作。

    • exchange/swap

      void exchange_swap(int register, int memory) { 
          int temp; 
          temp = memory; 
          memory = register; 
          register = temp; 
      }

• OS/开发语言提供的机制（系统级的方法）

  • 信号量：互斥+条件同步，容易造成死锁

  • 管程=共享资源数据结构+对数据结构的操作。
    利用少量的共享数据结构抽象的表示系统中共享资源，并且将对该共享数据结构的特定操作定义为一组过程。对于共享资源的访问必须通过这组过程，每次只有一个进程进入管程。

5.信号量与管程的条件变量的概念与异同

• 概念
  • 信号量是用于进程间传递信号的一个整数值；
  • 管程定义了一组局部数据和内部操作，访问管程的进程通过内部操作访问或修改内容数据。
• 相同
  • 都用于解决同步与互斥问题
• 不同
  • 管程所有同步机制都被限定在了管程内部，易于验证同步的正确性并检测错误。
  • 相对于信号量，若一个管程被正确编写，则所有进程对于受保护资源的访问都是正确的
  • 信号量可以并发，而管程则是在任意时刻都是只能有一个

第六章重点（简答题）

银行家算法考计算题（给出安全序列）

1.什么是死锁，死锁的概念并举例描述（可以使用伪代码描述，结合独木桥、十字路口问题）

• 概念：当一组进程中的每个进程都在等待某个事件（如等待释放所请求的资源），而仅有这组进程中被阻塞的其他进程才可触发该事件时，就称这组进程发生了死锁。
• 举例：
  • 独木桥。A，B都要过独木桥，但是互不退让，僵死。
  • 十字路口。A，B，C，D四辆车各占据一个资源，且由于所需要的第二个资源被另一辆汽车占有，因此他们都不能通行。

2.死锁的条件

注意前三个是必要条件；前四个是充要条件

• 互斥。一次只有一个进程可以使用一个资源。其他进程不能访问已分配给其他进程的资源。
• 占有且等待。当一个进程等待其他进程时，继续占有已分配的资源。
• 不可抢占。不能强行抢占进程已占有的资源。
• 循环等待。存在一个闭合的进程链，每个进程至少占有此链中下一个进程所需的一个资源。

3.死锁的解决方法（四大类）

**不允许死锁**的两类：死锁预防、死锁避免

• 死锁预防：破坏死锁的四个条件，但是都会导致低效的资源使用和低效的进程执行。
  （间接死锁预防：防止三个必要条件的发生；直接死锁预防：防止循环等待的发生）

  • 互斥：使资源同时访问而非互斥使用，就没有进程会阻塞在资源上，从而不发生死锁。比如可以同时多个读访问，但是写访问必须互斥，因此很多操作不能破坏该条件。

    • 一般来说，第一个条件不可能禁止。

  • 占有且等待：要求进程一次性地请求所有需要的资源，并阻塞这个进程直到所有请求都同时满足。

    • 低效：
      • 1.可能被阻塞很久；
      • 2.请求满足后占有该资源但是可能在很长时间内不使用，此时其他进程也不能使用
    • 该进程可能事先并不知道它所需要的所有资源

  • 不可抢占：

    • 若请求资源被拒绝，则释放之前占有的资源（必要时可再次请求）
    • 请求被其他进程占用的资源时，操作系统可以根据优先级进行抢占。（俩进程优先级必须不同）
    • 适用情况：资源状态可以很容易地保存和恢复的情况下。

  • 循环等待：定义资源类型的线性顺序。

    • 低效：

      • 1.使进程执行速度变慢；
      • 2.可能在没有必要的情况下拒绝资源访问。
      

• 死锁避免：允许前三个条件，通过选择确保不会到达死锁点。需要知道未来进程资源请求的情况。

  • 进程启动拒绝：若一个进程的请求会导致死锁，则不启动该进程；

  • 资源分配拒绝（银行家算法）：若一个进程增加的资源请求会导致死锁，则不允许这一资源分配。

    

**允许死锁**的两类：死锁检测、鸵鸟算法

• 死锁检测和恢复

  • 检测——进程资源分配图

    • 无环路：无死锁
    • 有环路
      • 每种资源类中仅有一个资源，则系统发生了死锁。
      • 每种资源类中有多个资源，则环路的存在只是产生死锁的必要不充分条件，系统未必会发生死锁。

  • 检测——死锁检测算法

    • 操作系统周期性的执⾏算法检测“循环等待”条件，检测到死锁再以某种策略进⾏恢复

  • 恢复

    

• 不处理

• 综合方法（前三个方法的综合）

第七章重点（简答题）

1.对七个内存管理方法的归纳总结，找出七个方法的联系和区别（表7.2）

item	描述	优点	缺点
固定分区	把内存划分为若干个固定大小的连续分区。分区大小可等可不等。	易于实现，开销小。	内部碎片造成浪费； 分区总数固定，限制了并发执行的程序数目。
动态分区	进程装入内存时，系统会给它分配一块与其所需容量完全相等的内存空间	没有内部碎片	有外部碎片； 只能是连续分配
简单分页	将内存和进程都划分为大小固定且相等的块。程序加载时，可将任意一页放入内存中任意一个页框，这些页框不必连续，从而实现了离散分配。	进程最后一页的一部分可能形成内部碎片； 不必连续存放	要求程序全部装入内存，没有足够的内存，程序就不能执行。
简单分段	将程序的地址空间划分为若干个段；进程中的各个段可以不连续地存放在内存的不同分区中	没有内碎片，外碎片可以通过内存紧缩来消除；便于实现内存共享。	与页式存储管理的缺点相同，进程必须全部装入内存
虚存分页	将虚拟内存和物理内存划分为固定大小的页；虚拟地址与物理地址之间通过页表来映射	消除外部碎片； 在加载程序的时候，不再需要一次性都把程序加载到物理内存中，提高了并发的进程数	内部碎片； 页表占内存； 对程序员不可见
虚存分段	段的大小不等且是动态的；通过段表实现地址转换	对程序员可见； 能够处理不断增长的数据结构； 支持共享和保护	外部碎片； 内存交换的效率低
段页式	用户的地址空间被程序员划分为许多段，每段划分为固定大小的页。只有一个段表，但有多个页表。	增加了硬件成本和系统开销	提高了内存的利用率

• 全部加载且连续

  • 固定分区：分区大小预先设定，产生内部碎片

  • 动态分区：分区大小在进程装入内存时按需分配，产生外部碎片

• 全部加载不连续

  • 简单分页：内存分成固定大小页框，进程分成等大的页，运行前全部载入页框，会产生较小的内部碎片；

  • 简单分段：程序分成多个大小不同的段载入内存，载入内存时可以不连续，会产生较小的外部碎片

• 部分加载且不连续

  • 虚存分页：将虚拟内存和物理内存划分为固定大小的页，地址之间通过页表来映射；产生内部碎片
  • 虚存分段：段的大小不等且为动态的，通过段表实现地址转换；支持共享和保护；产生外部碎片
  • 虚拟段页式：用户的地址空间被程序员划分为许多段，每段划分为固定大小的页；只有一个段表，但有多个页表。

2.内存管理的需求（重定位、保护、共享、逻辑组织、物理组织）见教材

3.固定分区与分页、动态分页与分段的异同（内外部碎片、加载方式）

• 固定分区与分页

  • 简单分页是将内存划分为页，而固定分区是将内存划分为分区。

  • 简单分页的页大小是固定的，而固定分区的分区大小可以不同。

  • 简单分页的地址转换是通过页表进行的，而固定分区的地址转换是通过分区表进行的。

• 分段没有内部碎片但有外部碎片

• 固定分区是全部加载，其他是化整为零

第八章重点（简答题）

有计算题（与去年类似）

1.虚拟存储器的概念（为什么要用虚拟内存）

**概念：虚拟内存别称虚拟存储器。电脑中所运行的程序均需经由内存执行，若执行的程序占用内存很大或很多，则会导致内存消耗殆尽。为解决该问题，操作系统运用了虚拟内存技术，即匀出一部分硬盘空间**来充当内存使用。应用程序执行时，会有部分暂时存储在外部磁盘存储器上，在需要时进行数据交换。

意义：

• 在有限的内存中运行足够大的程序
• 支持更有效的系统并发度
• 解除用户与内存之间没有必要的紧密约束

2.虚拟存储器的实现方法（三个：段、页、段页（先段再页））

部分加载且不连续

• 虚存分页：将虚拟内存和物理内存划分为固定大小的页，地址之间通过页表来映射；产生内部碎片
• 虚存分段：段的大小不等且为动态的，通过段表实现地址转换；支持共享和保护；产生外部碎片
• 虚拟段页式：用户的地址空间被程序员划分为许多段，每段划分为固定大小的页

3.什么是页故障（page fault）、页故障的处理流程是什么

**概念：**发生在查询页表时，页号没有对应的页框号，即对应数据还未加载到内存

处理流程：

4.书上的曲线图8.10，理解缺页率与页大小的关系以及页框数和缺页率的关系

图一（缺页率与页大小的关系）：

• 若页尺寸非常小，则每个进程在内存中就有较多数量的页。一段时间后，内存中的页都包含有最近访问的部分，因此缺页率较低。

• 当页尺寸增加时，每页包含的单元和任何一个最近访问过的单元越来越远。因此局部性原理的影响被削弱，缺页率开始增长。

• 但是，当页尺寸接近整个进程的大小时（图中的P点），缺页率开始下降。当一页包含整个进程时，不会发生缺页中断。

图二（缺页率和页框数的关系）：

• 对固定的页尺寸，当内存中页数量增加时，缺页率会下降，直到页框数增加到极值点N时，缺页率为0。

（p表示整个进程的大小、w表示工作集的大小、n表示进程中的总页数）

第九章重点（简答题）

1.长中短调度的概念、功能、特点

（注意图9.1、9.2、9.3）

概念：

• 长程调度：从外存中选择一个任务（作业）送到内存中，为之创建线程，并将这个线程加入准备队列。

• 中程调度：从将外存中挂起的线程中选择线程送到内存

• 短程调度：从准备队列中选择线程送到CPU执行（一般说的进程调度就是）

  •哪些任务可以被准入？

  长程调度 (Long-term scheduling)

  –也被称为任务调度、作业调度（job scheduling）或者准入调度（admission scheduling）

  •哪些进程可以被执行？

  中程调度 (Medium-term scheduling)

  –将因为I/O或者锁被挂起或阻塞的进程换出到磁盘或者从将外存中挂起的线程中选择线程送到内存

  短程调度 (Short-term scheduling)

  –也被称为分发器（dispatcher）

  •长程调度类似赛季阵容

  –只有注册的运动员可以上场比赛

  •中程调度类似比赛大名单

  –只有列出的运动员可以上场比赛

  –受伤或者禁赛的运动员不能在名单中，一切正常的运动员可以进入大名单

  •短程调度类似场上球员名单

  –决定哪些运动员目前可以在场上比赛

2.处理器调度需要考虑的因素

P251 表9.2

3.调度算法

（选2-3个考）

• 周转时间tr：进程从提交到完成（包括执行+等待）
• 响应时间：对于交互式进程而言，从提交请求到开始接收响应
• 归一化周转时间=周转时间/服务时间：表示一个进程的相对延迟情况
• Gantt chart甘特图，表示进程运行情况

关注一下：是否会饥饿死锁

item	描述	抢占？	优点	缺点
FCFS	先来先服务	×	简单	对短进程不利
RR	轮转。周期性地产生时钟中断。	√	公平对待	时间片过短会使进程切换过于频繁，增加系统开销；时间片过长会使进程响应时间增加。
SPN	最短进程优先	×	对短进程友好	对长进程不利
SRT	最短剩余时间	√
HRRN	最高响应比	×	提供较好的响应时间
反馈法	优先队列，优先级下移，在第RQi队列可使用2^i个时间片	√	对I/O密集型的进程可能有利

反馈法：

• 维护多个优先级

• 每个优先级一个队列

• 初始放入优先级最高的队列

• 对于调度执行结束的进程，调整优先级

  • 分片结束前主动释放CPU，保持当前优先级

  • 使用整个时间片且被抢占，移入下一级优先级队列
    （只要有其他进程，就会按照周期性的时间间隔执行抢断）

第十章重点（简答题）

1.关于实时调度算法的特点及其过程分析

• 最早时限优先（EDF)

  • 基本思路：选择开始时限最早的进程进行调度执行
    （是否有先验知识会导致不同的调度：缺少先验知识情况下可能导致无法保证某些任务的deadline，例如Process B；有先验知识条件下EDF可以进一步优化（例如在周期性任务情况下可以预测任务下一次到达的时间）

    详见PPT动画

    

• 速率单调调度（RM）

  • 速率单调针对周期性硬时限任务进行调度

  • 基本思路：执行越频繁的任务优先级越高

  • 每轮调度选择优先级最高的进程执行

  • 一个周期为T的任务的所有实例的优先级：
    $$
    p = \frac{1}{T}
    $$

  • 优先级是周期时间的倒数，优先级随着调用速率的增大单调提高

• 二者对比
  • 两种方法扩展后都可以处理周期、非周期和混合情况下的调度
    • EDF不能保证**周期性**任务在时限内完成
    • RM不能保证**非周期性**任务在时限内完成

第十一章重点（简答题）

计算题（磁盘调度算法和调度过程分析（平均寻道时间））

1.I/O缓冲的作用和组织形式

作用：

• 缓和CPU和I/O设备之间的速度差异
• 减少对CPU的中断频率
• 放宽对中断响应时间的限制，提高CPU和I/O设备之间的并行性

组织形式：（图11.5）

• 单缓冲区
• 双缓冲区
• 循环缓冲区

第十二章重点（简答题）

1.关于文件组织的五个形式与特点

• 堆
  • 最简单的文件组织形式，数据按照到达顺序被收集。
  • 由于没有结构，对记录的访问只能通过穷举查找方式进行
• 顺序文件
  • 最常用的。每条记录都使用一种固定的格式
  • 关键域：每条记录的第一个域，唯一标识这条记录。记录按关键域进行存储
• 索引顺序文件
  • 记录仍按照关键域的顺序组织
  • 增加了用于支持随机访问的文件索引和溢出文件
    • 索引：能够快速接近目标记录
    • 溢出文件：类似顺序文件中的日志文件；新记录放入溢出文件
      • 溢出文件中的记录采用批处理方式合并到主文件
• 索引文件
  • 为多个关键域建立索引
    • 完全索引（Exhausive index）：所有记录都有的关键域的索引
    • 部分索引（Partial index）：部分记录才有的关键域的索引
  • 采用多索引结构
• 直接文件/散列文件
  • 能够直接访问磁盘中任何一个地址已知的块的能力
  • 要求快速访问时，记录长度固定，通常一次只访问一条记录

适用场景

item	适用	不适用
堆	1.数据在处理前采集并存储； 2.数据难以组织； 3.保存的数据大小和结构不同；	除前面限制外的其他
顺序文件	批处理应用（尤其是涉及到对所有记录的处理）	查询或更新记录的交互式应用
索引顺序文件	既适合于随机存取也适合于顺序存取
索引文件	对信息的及时性要求比较严格且很少会对所有数据进行处理的应用程序中
散列文件	要求快速访问时

？2.文件定位和访问权限管理

3.文件分配方式的特点和分配过程

• 连续分配
  • 给每个文件分配一段连续的变长分区
  • 每个文件只需要一个FAT表项
    • FAT信息：起始盘块及分区长度
  • 局部性好，但是利用率和分配灵活度低
  • 可能存在外部碎片（类似段式内存管理）
    • 采用**压缩（compaction）**减少外部碎片
• 链式分配
  • 给每个文件分配的盘块可以来自任意位置
  • 每个盘块中存储了下一个盘块的位置
  • 每个文件只需要一个FAT表项
    • FAT信息：起始盘块（链表表头）
  • 局部性差，但是利用率和分配灵活度高
    • 采用合并提高局部性
• 索引分配
  • 每个文件使用一个块用于存放索引信息，称为**索引块**
  • 索引包含了对应文件的所有分区信息
  • 分区可以是
    • 变长分区
    • 盘块
  • 每个文件需要一个FAT表项
    • FAT信息：索引块的块号
  • 使用最广泛的分配方法

4.空闲空间的管理方式与特点

• 位表

  • 对每一个盘块使用一位表示使用情况
    • 0 - 该盘块还未分配，可以使用
    • 1 - 该盘块已经分配

• 链式空闲区

  • 对空闲分区采用链式管理（空闲链表）
  • 每个空闲分区的开头盘块存储当前分区的长度和下一个空闲分区的开头
  • 不需要磁盘分配表：记录首个空闲分区的位置即可
  • 对于基于分区的文件组织方式可能造成碎片
  • 分配及回收时间长

• 索引法

  • 将所有空闲空间看作一个文件，采用索引文件分配中的索引方法（空闲表）
  • 通常为了提高效率选择变长分区进行索引

• 空闲块列表

  • 磁盘中保存了所有可用分块的编号
    • 占用硬盘空间较小
  • 将一部分块号放入内存进行管理提高速度
    • 排序后找到连续可用盘块
    • 内存中的块号组织为栈或者队列

易错题

chapter2

17. (单选题, 5分)计算机操作系统的功能是

• A. 完成计算机硬件与软件之间的转换
• B. 实现计算机用户之间的相互交流
• C. 控制、管理计算机系统的资源和程序的执行
• D. 把源程序代码转换为目标代码

我的答案: C:控制、管理计算机系统的资源和程序的执行;正确答案: C:控制、管理计算机系统的资源和程序的执行;

18. (单选题, 5分)操作系统的系统调用，是基于CPU的哪种异常实现的

• A. 终止/Abort
• B. 陷入/Trap
• C. 中断/Interrupt
• D. 故障/Fault

我的答案: B:陷入/Trap;正确答案: B:陷入/Trap;

19. (单选题, 5分)Linux操作系统是一种（ ）操作系统。

• A. 多用户、多任务
• B. 多用户、单任务
• C. 单用户、多任务
• D. 单用户、单任务

我的答案: A:多用户、多任务;正确答案: A:多用户、多任务;

20. (单选题, 5分)在中断发生后，进入的中断处理程序属于

• A. 可能是应用程序，也可能是操作系统程序
• B. 操作系统程序
• C. 用户程序
• D. 既不是应用程序，也不是操作系统程序

我的答案: B:操作系统程序;正确答案: B:操作系统程序;

chapter3

17. (单选题, 5分)下面对进程的描述中,错误的是（ ）

• A. 进程是动态的概念
• B. 进程执行需要处理机
• C. 进程是有生命期的
• D. 进程是指令的集合

我的答案: D:进程是指令的集合;正确答案: D:进程是指令的集合;

chapter4

5. (单选题, 5分)下列关于线程的叙述中,正确的是():

• A. 线程包含CPU现场,可以独立执行程序
• B. 每个线程有自己独立的地址空间
• C. 进程只能包含一个线程
• D. 线程之间的通信必须使用系统调用函数

我的答案: A:线程包含CPU现场,可以独立执行程序;正确答案: A:线程包含CPU现场,可以独立执行程序;

8. (单选题, 5分)当一个线程需要等待一个事件时,与线程状态变化相关的基本线程操作称为():

• A. 阻塞操作
• B. 解除阻塞操作
• C. 生成操作
• D. 以上都不是

我的答案: A:阻塞操作;正确答案: A:阻塞操作;

11. (单选题, 5分)若系统中只有用户级线程，则处理器的调度单位是( )。

• A. 线程
• B. 进程
• C. 程序
• D. 作业

我的答案: B:进程;正确答案: B:进程;

13. (单选题, 5分)在以下描述中，（ ）并不是多线程系统的特长

• A. 利用线程并行的执行矩阵乘法运算
• B. Web服务器利用线程响应HTTP请求
• C. 键盘驱动程序为每个正在运行的应用配备一个线程，用以响应该应用的键盘输入
• D. 基于GUI的调试程序用不同的线程分别处理用户输入、计算和跟踪等操作

我的答案: C:键盘驱动程序为每个正在运行的应用配备一个线程，用以响应该应用的键盘输入 ;正确答案: C:键盘驱动程序为每个正在运行的应用配备一个线程，用以响应该应用的键盘输入 ;

14. (单选题, 5分)Windows操作系统中动态DLL库里的系统线程，被不同的进程所调用，它们是（ ）的线程

• A. 不同
• B. 相同
• C. 可能不同，也可能相同
• D. 不能被调用

我的答案: B:相同;正确答案: B:相同;

15. (单选题, 5分)关于线程，在下面的叙述中正确的是( )。

• A. 线程是比进程更小的能独立运行的基本单位
• B. 引入线程可提高程序并发执行的程度，可进一步提高系统效率
• C. 线程的引入增加了程序执行时时空开销
• D. 一个进程一定包含多个线程

我的答案: B:引入线程可提高程序并发执行的程度，可进一步提高系统效率;正确答案: B:引入线程可提高程序并发执行的程度，可进一步提高系统效率;

17. (单选题, 5分)使用Linux的pthread库创建的线程属于

• A. 用户级线程/ULT
• B. 内核级线程/KLT
• C. 都有可能
• D. 都不是

我的答案: A:用户级线程/ULT;正确答案: A:用户级线程/ULT;

19. (单选题, 5分)下列关于线程的描述中，错误的是___。

• A. 内核级线程的调度由操作系统完成
• B. 操作系统为每个用户级线程建立一个线程控制块
• C. 用户级线程间的切换比内核级线程间的切换效率高
• D. 用户级线程可以在不支持内核级线程的操作系统上实现

我的答案: B:操作系统为每个用户级线程建立一个线程控制块;正确答案: B:操作系统为每个用户级线程建立一个线程控制块;

chapter5

6. (单选题, 5分)实现互斥需要满足下列哪些要求:( )

• A. 一次只允许一个进程进入临界区
• B. 一个进程驻留在临界区中的时间必须是有限的
• C. 对相关进程的执行速度没有任何要求和限制
• D. 以上都是

我的答案: D:以上都是;正确答案: D:以上都是;

8. (单选题, 5分)没有指定进程从队列中移除的顺序的信号量称为:( )

• A. 弱信号量
• B. 强信号量
• C. 二元信号量
• D. 以上都不是

我的答案: A:弱信号量;正确答案: A:弱信号量;

13. (单选题, 5分)一个正在访问临界资源的进程由于申请等待I/O操作而被中断时，它（ ）

• A. 允许其他进程进入与该进程相关的临界区
• B. 不允许其他进程进入任何临界区
• C. 允许其他进程抢占处理器，但不得进入该进程的临界区
• D. 不允许任何进程抢占处理器

我的答案: C:允许其他进程抢占处理器，但不得进入该进程的临界区;正确答案: C:允许其他进程抢占处理器，但不得进入该进程的临界区;

14. (单选题, 5分)以下关于管程的叙述中，错误的是（ ）

• A. 管程是进程同步工具，解决信号量机制大量同步操作分散的问题。
• B. 管程每次只允许一个进程进入管程
• C. 管程中signal操作的作用和信号量机制中的semSignal操作相同
• D. 管程是被进程调用的，管程是语法范围，无法创建和撤销

我的答案: C:管程中signal操作的作用和信号量机制中的semSignal操作相同;正确答案: C:管程中signal操作的作用和信号量机制中的semSignal操作相同;

chapter6

19. (单选题)对资源采用按序分配策略能达到下列哪一个目的？

• A. 死锁预防
• B. 死锁避免
• C. 死锁检测
• D. 死锁解除

我的答案: A:死锁预防;正确答案: A

chapter7

4. (单选题)将程序和数据组织起来,使不同的模块分配到同一内存区域的做法称为:( )

• A. 共享/Sharing
• B. 重定位/Location
• C. 覆盖/Overlay
• D. 以上都不是

我的答案: C:覆盖/Overlay;正确答案: C:覆盖/Overlay;

7. (单选题)进程的页表内所维护的地址是:( )

• A. 进程中每一页/page的页框/frame地址
• B. 进程中每个页框/frame的页/page地址
• C. 每个进程的虚拟内存地址
• D. 以上都不是

我的答案: A:进程中每一页/page的页框/frame地址;正确答案: A:进程中每一页/page的页框/frame地址;

11. (单选题)在页式管理中，页表的始址存放在（ ）

• A. 内存中
• B. 存储页面表中
• C. 联想存储器中
• D. 寄存器中

我的答案: D:寄存器中;正确答案: D:寄存器中;

12. (单选题)操作系统采用分页式存储管理(Paging)方法，要求( )

• A. 每个进程拥有一张页表，且所有进程的页表必须驻留在内存中
• B. 每个进程拥有一张页表，但只有执行进程的页表驻留在内存中，其他进程的页表不必驻留在内存中
• C. 所有进程共享一张页表，以节约有限的内存空间，但页表必须驻留在内存中
• D. 所有进程共享一张页表，只有页表中当前使用的页面必须驻留在内存中，以最大限度地节约有限的内存空间

正确答案: B:每个进程拥有一张页表，但只有执行进程的页表驻留在内存中，其他进程的页表不必驻留在内存中;

chapter8

4. (单选题)与决定驻留在主存中的进程数相关的概念被称为:( )

• A. 页面错误频率
• B. 加载控制
• C. 清除策略
• D. 以上都不是

我的答案: B:加载控制;正确答案: B:加载控制;

5. (单选题)以下和虚拟存储相关的中断/异常类型是:( )

• A. 系统调用/System call
• B. 陷阱/Trap
• C. 故障/Falt
• D. 以上都不是

我的答案: C:故障/Falt;正确答案:

7. (单选题)在分段系统中,共享通过什么实现的:( )

• A. 一个所有进程共享的公共数据存储区
• B. 每个进程的段表都有一个对主存区域调度程序的引用
• C. 在两个及两个以上的进程中引用段表中的同一个段
• D. 以上都是

我的答案: C:在两个及两个以上的进程中引用段表中的同一个段;正确答案: C

9. (单选题)有一种替换算法,这种算法在页面错误时仅在进程驻留的页面中选择页去替换,这种算法被称为:( )

• A. 局部替换策略
• B. 可变替换策略
• C. 全局替换策略
• D. 以上都不是

我的答案: A:局部替换策略;正确答案: A:局部替换策略;

14. (单选题)对于虚拟存储器的分页系统，对于驻留集（Resident Set）管理，有两个维度：其一是固定或者可变分配；其二是局部或者全局分配。综合（即组合）起来，理论上，有2*2=四种可能性，但实际上，有一种实际上是不存在的，它是：

• A. 固定分配 & 局部分配
• B. 固定分配 & 全局分配
• C. 可变分配 & 局部分配
• D. 可变分配 & 全局分配

我的答案: B:固定分配 & 全局分配;正确答案: B:固定分配 & 全局分配;

chapter9

8. (单选题)在轮转法中,最主要的设计问题是( ):

• A. 确定在一组给定的进程中轮转的方式
• B. 确定时间片对单个进程的公平分配
• C. 决定时间片的长度
• D. 以上都不是

我的答案: C:决定时间片的长度;正确答案: C:决定时间片的长度;

9. (单选题)最短进程优先调度技术的一个难点是( ):

• A. 需要了解或估计每个进程所需的处理时间
• B. 缺乏抢占
• C. 长进程会发生饥饿
• D. 以上都是

我的答案: A:需要了解或估计每个进程所需的处理时间;正确答案: A:需要了解或估计每个进程所需的处理时间;

18. (单选题)下列不是处理器调度算法的目标的是（ ）

• A. 提高系统资源利用率
• B. 处理器时间分配的公平性
• C. 系统资源分配的平衡性
• D. 保证平均周转时间短

我的答案: D:保证平均周转时间短;正确答案: D:保证平均周转时间短;