德龙的博客
0%

操作系统复习

Posted on Edited on In

第一章 引论

操作系统定义。现代操作系统通常向用户提供三种接口。

操作系统定义：

操作系统是控制和管理计算机系统内各种硬件和软件资源，有效组织多道程序运行的系统软件（或程序集合），是用户与计算机之间的接口。

OS为用户提供三种接口：

  • 图形用户接口（GUI）——图形界面
    • 鼠标、窗口、菜单、图标、工具条。
  • 命令行接口——命令界面
    • 键盘输入命令，由命令解释程序（比如unix中的shell）接收并解释，传递给OS内部程序执行。
  • 程序接口——系统调用接口
    • 系统调用是OS内核与用户程序、应用程序之间的接口，位于OS系统的最外层（Linux以C函数形式出现）。所有内核之外的程序都必须经由系统调用才能获得OS的服务。
    • Unix/Linux中：fork()、sleep()、wakeup()、exit()

系统执行原语操作禁止中断。

一般来说，操作系统有4种结构。

1 整体结构 2 虚拟机结构 3 层次结构 4 客户-服务器结构

操作系统也叫做虚拟机。

分时系统、实时系统概念。

分时系统：一台计算机连接多个终端的计算机系统。

实时系统是指计算机能及时响应外部事件的请求，在规定时间内完成对该事件的处理，并控制所有设备和任务协调一致工作的操作系统。

特征
同时性：若干用户可以同时上机使用计算机系统
交互性：人机对话方便
独立性：各终端彼此独立工作，互不干扰
及时性：用户在很短时间内得到系统响应

实时系统特征：实时性（先实时、后效率）、高可靠性、容错能力强

多道批处理系统两大特征是， 并发和共享（多道和成批）。

操作系统的四大功能是：存储器管理，设备管理，文件管理和处理器管理。

处理机的核心态和用户态概念、做课后习题。（13．只在核心态下执行的指令有：①屏蔽所有中断。③设置时钟日期。⑤启动打印机。⑥清内存。）

核心态（系统态、管理态）
执行os程序时所处的状态。此时有较高特权，可执行一切指令。

用户态
执行用户程序时所处的状态。权限较低，只能执行指令集中的非特权指令。

第二章 进程和线程

若一个信号量的初值经过多次P、V操作，正值和负值的含义。

创建进程要完成的操作。

进程创建的过程
（1）申请一个空闲的PCB
（2）为新进程分配资源
（3）将新进程的PCB初始化
（4）将新进程加到就绪队列中

理解进程状态转换图。

1

进程的状态：

  • 运行状态
    • 进程正在被执行，占用处理资源；处于此状态的进程数目小于等于CPU数目。
  • 就绪状态
    • 进程已获得除处理机外的所需资源，等待分配处理机资源；只要分配CPU就可执行。
  • 阻塞状态
    • 进程等待某个事件的发生（如I/O操作或进程同步），在该事件发生前，即使把处理机分配给进程，他也无法运行。
  • 创建状态
    • 进程刚创建还不能运行，OS还没有把它加入到可执行进程组中，通常是还没有加载到主存中的新进程。
  • 结束状态
    • OS从可执行进程组释放出的进程。
    • 进程结束，回收除PCB之外的其他资源，并让其他进程从PCB中收集有关信息。

进程的状态转换：

  • 新建——》就绪（提交admit）
    • 接纳一个新进程，进入就绪状态。
  • 就绪——》运行（分派dispath）
    • 从就绪进程表中选择一个进程，进入运行状态。
  • 运行——》阻塞（事件等待event wait）
    • 进程要求的事件未出现而进入阻塞。
  • 阻塞——》就绪（事件出现event occurs）
    • 进程等待的事件出现。
  • 运行——》就绪（超时timeout）
    • 由于用完时间片或高级进程就绪等导致进程暂停运行。
  • 运行——》退出（释放release）
    • 由于进程完成或失败而终止进程运行。
    • 分为正常和异常退出。

有三个进程PA、PB、PC协作，见书后习题。经典进程同步问题之理发师。

有三个进程A，B，C协作解决文件打印问题。
A将文件记录从磁盘读入内存的缓冲区1，每执行一次读一个记录；
B将缓冲区1的内容复制到缓冲区2，每执行一次复制一个记录；
C将缓冲区2的内容打印，每执行一次打印一个记录。
缓冲区的大小和一个记录大小一样。
使用P、V操作来保证文件的正确打印。

答案↓

2

Pa与pb共用一个缓冲区1；
Pb与pc共用一个缓冲区2；
当缓冲区1为空时，PA可将一个记录读入其中；
若缓冲区1有数据，缓冲区2为空时，PB可将记录从缓冲区1复制到缓冲区2；
若缓冲区2有数据，PC可以打印记录；
其他条件下，相应进程必须等待。

设置如下信号量

Empty1,empty2为同步信号量，初值为1，分别表示缓冲区1，2空闲，可以存放记录。
Full1,full2为同步信号量，初值为0，分别表示缓冲区1，2还没有被取用的记录。

3

问题描述：
理发店有一名理发师、一把理发椅、几把等待座椅。
如果没有顾客，理发师就打盹。顾客到来，唤醒理发师。如果顾客到来时理发师正在理发，则顾客坐在椅子上等待；如果座满了，直接离开。
用P、V操作协调理发师和顾客的同步行为。

第一种思路

  • 设三个信号量，一个计数器：
    customers：用来记录等候理发的顾客数，初值为0。
    barbers：用来记录等候顾客的理发师数，初值为0。
    waiting：整型计数器，表示等候理发的顾客数，初值为0。waiting是customers的副本，但不是信号量，可以在程序中对它做增减操作。
    mutex：用于控制对waiting的互斥操作，初值为1。

  • #define CHAIRS 5
    typedef struct{

         int value;
     struct PCB *list;

    } semaphore;

    semaphore customers=0;
    semaphore barbers=0;
    semaphore mutex=1;
    int waiting=0;

    void barber(void)
    {
    while(TRUE){

    P(customers);  
P(mutex);       
waiting--; 
V(barbers);
V(mutex); 
cut_hair();
}

    }

    void customer(void)
    {
    P(mutex);
    if(waiting﹤CHAIRS){

      waiting++;
  V(customers);       
  V(mutex);
  P(barbers);         
  get_haircut();

    }else

      V(mutex);

    }

第二种思路

  • 将理发椅（1个bchair）与等待椅（n个wchair）分开看作两种不同的资源，顾客分别申请使用。

  • 考虑等待的顾客数（坐在凳子上的顾客数），设置一个整型变量waiting，初值为0。当一个顾客到达时waiting加1，当一个顾客开始理发时waiting减1。

  • 考虑对waiting的互斥操作，设互斥信号量mutex，初值为1。

  • 考虑空凳子数量，设信号量wchair，初值为5。

  • 考虑理发椅的数量，设信号量bchair，初值是1。

  • 考虑顾客和理发师的同步操作，设ready和finish两个信号量，前者表示顾客是否准备好，后者表示理发师是否完成理发，初值均为0。

  • typedef struct{
         int value;
         struct PCB *list;
} semaphore;

int waiting=0;
semaphore mutex=1;
semaphore bchair=1;
semaphore wchair=5;
semaphore ready=finish=0;

barber( )
{
   while(true){
    P(ready); cut_hair();  
    V(finish);
    }
}

customer( )
{
   P(mutex);      
   if(waiting﹤=5) {
      waiting++;
      V(mutex); 
   } else
   { V(mutex); 离开; }
   P(wchair);
   P(bchair);
   V(wchair);
   V(ready);       
   P(finish); 
   V(bchair); 
   P(mutex);
   waiting--;
   V(mutex);
}

现代操作系统处理机调度和分配的对象是线程。

线程（Thread）是进程中实施调度和分派CPU的基本单位。

操作系统在撤销进程时，必须完成的操作。

终止进程的过程
（1）找到指定进程的PCB
（2）终止该进程的运行
（3）回收该进程所占用的全部资源
（4）终止其所有子孙进程，回收它们所占用的全部资源
（5）将被终止进程的PCB从原来队列中摘走

UNIX/Linux系统中的终止原语exit()

第三章 死锁

安全状态计算。

死锁的四个必要条件，破坏死锁必要条件的几个预防死锁的方法。

当计算机系统同时具备下面4个必要条件时，会发生死锁。
1.互斥条件
2.占有且等待条件（请求并保持）
3.不可抢占条件（不可剥夺）
4.循环等待条件（环路等待）

方法：

  • 破坏互斥条件
    有些资源本身要求必须互斥访问，这是资源的固有属性，所以，用否定互斥条件的办法不能预防死锁。
  • 破坏占有且等待条件
    一种办法是“空手”申请资源策略：
     不占有资源的时候，才能申请。
    一种办法是预分资源策略：
         静态分配：执行之前申请到全部资源
  • 破坏不可抢占条件
    • 隐式抢占方式（被抢）
      如果一个进程占有某些资源，它还要申请被别的进程占有的资源，该进程就一定处于等待状态，则进程当前所占有的全部资源可被抢占。
      抢占等待者的资源（去抢）
      进程申请资源，如果没有可用，可以从等待进程那里抢占资源。这些办法常用于资源状态易于保留和恢复的环境中，如CPU寄存器、内存，但不能用于打印机、磁带机等。
  • 破坏循环等待条件
    • 一种方法是实行资源有序分配策略。
    • 另一种方法：先弃大，再取小。

什么是死锁？死锁的预防和避免的概念。

所谓死锁，是指在一个进程集合中的每个进程都在等待仅由该集合中的另一个进程才能引发的事件而无限期地僵持下去的局面。（系统中多个进程无限地等待永远不会发生的状态）

  1. 死锁的预防——静态策略
    破坏死锁的四个必要条件之一。
  2. 死锁的避免——动态策略
    利用某些协议避免死锁，保证系统不会进入死锁状态。

静态策略：死锁预防——破坏产生死锁的必要条件；静态策略的缺点是降低资源利用率和减少系统吞吐量。

动态策略：不限制进程有关申请资源的命令，而是对进程所发出的每个申请资源命令加以检查，根据检查结果决定是否进行资源分配。

第四章 调度

时间片轮转、先来先服务、短进程优先、优先级法（抢占和非抢占）、高响应比优先。几种调度算法概念、特点。最短剩余时间优先法的计算平均周转时间。课后习题8题，9题。

先来先服务法

  • 实现思想：排队买票
    每次从就绪队列中选择一个最先进入该队列的进程，把CPU分给它，令其运行。该进程一直运行下去，直至完成或由于某些原因而阻塞，才放弃CPU。
  • 特点

    • 非抢占式
      简单，易于理解，容易实现。效率低。
      有利于长作业（进程）,不利于短作业（进程），
      有利于CPU繁忙型作业（进程），不利于I/O繁忙型作业（进程）。

      适用于作业调度、进程调度。通常不单独使用，与其他算法结合起来使用。

短作业优先法

  • 所谓长短
    是指作业（进程）要求运行时间的多少。

  • 实现思想
    当分配CPU时，选择所需处理时间最短的进程。短进程将越过长进程，跳到队列头。一个进程一旦分得处理机，便执行下去，直到该进程完成或阻塞时，才释放处理机。

  • 特点

    • 非抢占式
      优点：对于一组给定的作业，SJF算法能给出较小的平均等待时间，提高了系统的吞吐量。
      缺点：
      实现上有困难，需要知道或至少需要估计每个作业/进程所需要的处理时间。
      对长作业（进程）不利。不能保证及时处理紧迫作业（进程）。

      适用于作业调度和进程调度。作业调度用的多，进程调度用的少。

最短剩余时间优先法

  • 实现思想
    当新进程进入就绪队列时，如果它需要的运行时间比当前运行的进程所需的剩余时间还短，则执行切换，当前运行进程被剥夺CPU的控制权，调度新进程运行。
  • 特点
    • 抢占式
      优点：
      保证新的短作业一进入系统就能很快得到服务，平均等待时间短。
      缺点：
      为保存进程断点现场，统计进程剩余时间增加了系统开销。
      不利于长作业。
      适用于作业调度和进程调度。作业调度用的少，进程调度用的多。

高响应比优先法

  • 调度思想：在调度作业时，挑选响应比最高的作业运行。
  • 4
  • 特点
    • 非抢占式
      优点
      是对FCFS和SJF调度算法的综合平衡，同时考虑每个作业的等待时间和估计需要的运行时间。
      缺点
      调度前需要计算作业的响应比，增加系统开销。
      适用于作业调度和进程调度。作业调度用的多。

优先级法

  • 实现思想：
    优先级调度算法是从就绪队列中选出优先级最高的进程，让它在CPU上运行。

轮转法

  • 实现思想：
    将系统中所有的就绪进程按照FCFS原则，排成一个队列。每次调度时将CPU分派给队首进程，让其执行一个时间片。
    在一个时间片结束时，发生时钟中断。调度程序据此暂停当前进程的执行，将其送到就绪队列的末尾，并通过上下文切换执行当前的队首进程。
  • 5

多级队列法

多级反馈队列法

进程调度程序执行的时机。

调度时机（引起进程调度的原因）：
（1）当前进程运行结束。
（2）当前运行进程因某种原因（I/O请求、P操作、阻塞原语等），从运行状态进入阻塞状态。
（3）执行完系统调用等系统程序后返回用户进程，这时可以看做系统进程执行完毕，从而可以调度一个新的用户进程。
（4）在采用抢占调度方式的系统中，一个更高优先级的进程要求使用cpu，则使当前运行进程进入就绪队列。
（5）分时系统中，分配给该进程的时间片用完。

三级调度指的是什么？

一个作业从提交开始直到完成，一般要经历三级调度：

  • 高级调度（作业调度）
    中级调度（内存调度、进程挂起与对换）
    低级调度（进程调度）

第五章 存储管理

分页系统，逻辑地址的有效位、物理地址有效位的计算。

分页技术：允许一个进程的存储空间不必连续，可以分散地放在各个空闲的内存区域中。解决了外部碎片，并提高了内存的利用率。

各种存储方法中，内碎片和外碎片的情况。

单道连续分配只有内部碎片。多道固定连续分配既有内部碎片，又有外部碎片。

不会产生内部碎片的存储管理是：分段式存储管理。

按需分配没有内碎片，例如：动态分区分配、分段存储管理
固定分配没有外碎片，例如：固定分区分配、分页存储管理

内部碎片与外部碎片
在一个分区内部出现的碎片（即被浪费的空间）称做内部碎片，固定分区法会产生内部碎片。
在所有分区之外新增的碎片称做外部碎片，动态分区法会产生外部碎片。

动态分区分配的三种算法：最先适配法、最佳适配法、循环适配法。

最先适应法——首次适应法

空闲表按空闲块地址递增排序。
分配内存时，顺序查找满足大小要求的第一个可用块。

循环首次适应法——邻近适应法

由首次适应法演变而成，不同之处是，分配内存时从上次查找结束的位置开始继续查找。
该算法的分配和释放的时间性能较好，使空闲分区分布得更均匀，但较大的空闲分区不易保留。

最佳适应算法

空闲表以空闲块大小为序，按增量形式排列。
接到内存申请时，顺序查找第一个满足大小要求的空闲块。
特点：用最小空间满足要求。
选择分区时总是寻找其大小最接近所要求的存储区域。

课后练习题第10题，分页系统中逻辑地址转变成物理地址。

10

最佳页面置换算法（OPT）、 先进先出页面置换算法（FIFO）和最近最久未使用（LRU）页面置换算法，计算缺页次数。

最佳置换法（OPT）

思想：为调入新页面而必须预先淘汰某个老页面时，所选择的老页面应在将来不被使用，或者是在最远的将来才被访问。以此保证获得最低的缺页率。

6

先进先出法（FIFO）

思想：为调入新页面而必须预先淘汰某个老页面时，总是淘汰在内存中停留时间最长的一页，即先进入内存的页，先被换出。

7

最近最少使用置换法(LRU)

思想：当需要置换一页时，选择在最近一段时间里最久没有使用过的页面予以淘汰。
理由：认为过去一段时间内未被访问过的页面，在最近的将来可能也不会被访问。

8

第六章 文件系统

在UNIX系统中，通常把输入/输出设备当做什么。

字符特别文件.

位示图概念理解。

利用一串二进制位值反映磁盘空间的分配情况，也称位向量（Bit Vector）法。
每个盘块对应一个二进制位，1表示盘块空闲，0表示已分配。
设下列盘块是空闲的：2, 3, 4, 5, 8, 9, 10, 11, 12, 13, 17, 18, 25, 26, 27,…，则位示图向量是：
0011110011111100011000000111…

文件课后练习题13题。平均需要访问多少次磁盘。

多重索引文件分配表中，计算文件最大为多少字节（各级）、访问某逻辑地址40KB需要访问磁盘几次？每个索引盘块最多存储多少个索引项？文件的字节偏移量转换为物理块号分别需要用到什么索引？假设一个块1024B，一个文件索引项4B。

第七章 设备管理

假脱机技术（SPOOLing）把独占设备变为共享设备，成为虚拟设备的。

以下I/O控制方式中，中断控制方式、DMA控制方式、通道控制方式的特点。

中断控制方式

利用中断技术解决了CPU忙等的问题。
基本工作过程：
① CPU执行设备驱动程序，发出启动I/O设备的指令，使外设处于准备工作状态。然后，CPU继续运行程序，进行其他信息的处理。
② I/O控制器按照I/O指令的要求，启动并控制I/O设备的工作。

③ 当输入就绪、输出完成或发生错误时，I/O控制器便向CPU发送一个中断信号。
④ CPU接收到中断信号后，保存少量的状态信息。
然后将控制传送给中断处理程序。
⑤ 中断处理程序确定中断原因，执行相应的处理工作，最后退出中断，返回中断前的执行状态。
⑥ CPU恢复对被中断任务的处理工作。

中断控制方式一般用于随机出现的I/O请求。每传送一个字节，控制器就向CPU发一次中断，使CPU执行一次中断服务。中断次数过多，耗时多，只适用于中慢速外设。

DMA控制方式

具有4个特点：
1.数据是在内存和设备之间直接传送的，不需要CPU干预。
2.仅在一个数据块传送结束后，DMA才向CPU发中断请求。
3.数据的传送控制完全由DMA控制器完成，速度快。
4.在传送过程中，CPU与外设并行工作，提高系统效率。

通道控制方式

（1）通道的引入
为使CPU摆脱繁忙的I/O事务，现代大、中型计算机都设置了专门处理I/O操作的机构，这就是通道。
通道相当于一台小型处理机，它接受主机的委托，独立执行通道程序，对外部设备的I/O操作进行控制，实现内存与外设之间的成批数据传输。
当主机委托的I/O任务完成后，通道发出中断信号，请求CPU处理。

（2）通道类型
① 字节多路通道。以字节作为信息输送单位，服务于多台低速I/O设备。
② 选择通道。在同一时间里只能为一台设备服务，主要用于连接高速外部设备。
③ 成组多路通道。结合了字节多路通道分时操作和选择通道高速传送的优点，广泛用于连接高速和中速设备。

操作系统的I/O子系统分四层，各层功能。

用户级I/O软件、设备无关软件、设备驱动程序、中断处理程序

用户级I/O软件

  • 多数I/O软件都在操作系统中，用户空间中也有一小部分。通常，它们以库函数形式出现。
    用户空间中另一个重要的I/O软件是SPOOLing系统。

设备无关软件

  • 设备驱动程序的统一接口
  • 缓冲技术
  • 缓冲区的设置
  • 出错报告
  • 分配和释放独占设备
  • 提供与设备无关的块大小

设备驱动程序主要功能

  • 接受来自上层、与设备无关软件的抽象读写请求，并且将该I/O请求排在请求队列的队尾，同时还要检查I/O请求的合法性。
    取出请求队列中队首请求，且将相应设备分配给它。
    向该设备控制器发送命令，启动该设备工作，完成指定的I/O操作。
    处理来自设备的中断。
  • 每个连接到计算机的I/O设备都需要某些设备特定的代码来对其进行控制，这样的代码就是设备驱动程序。

中断处理程序

  • 在I/O软件系统的底层
    当输入就绪、输出完成或发生错误时，I/O控制器便向CPU发送一个中断信号。
    CPU接收到中断信号后，将控制传送给中断处理程序。
    中断处理程序确定中断原因，执行相应的处理工作。如，磁盘I/O中断调用磁盘驱动程序处理。

磁盘寻道算法FCFS算法、最短寻道时间优先法SSTF算法、扫描法SCAN算法、巡回（循环）扫描法C-SCAN算法。

FCFS是最简单的磁盘调度算法。

基本思想：按进程请求访问磁盘的先后次序进行调度。

最短寻道时间优先法SSTF

基本思想：选择与当前磁头所在磁道距离最近的请求作为下一次服务的对象。

扫描法（SCAN）

基本思想：磁头从磁盘的一端出发，向另一端移动，遇到所需的磁道时就进行服务，直至到达磁盘的另一端。在另一端上，磁头移动方向反过来，继续下面的服务。

巡回（循环）扫描法（C-SCAN）

基本思想：规定磁头移动时，服务方向是单向的。例如，自里向外移动，边移动边服务，当磁头移到最外磁道时立即返回到最里磁道，如此循环进行扫描。

答题规范：
② SSTF
磁头移动顺序：143→147→150→130→102→94→91→86→175→177
磁头移动总量：4+3+20+28+8+3+5+89+2=162
③ 扫描法SCAN
磁头移动顺序：143→147→150→175→177→199→130→102→94→91→86
磁头移动总量：4+3+25+2+22+69+28+8+3+5=169

与设备无关的操作系统I/O软件包括什么功能。

9

引入缓冲的主要目的三点？（见PPT）

（1）引入缓冲技术的主要目的
① 缓解CPU与I/O设备间速度不匹配的矛盾。
② 提高它们之间的并行性。
③ 减少对CPU的中断次数，放宽CPU对中断响应时间的要求。