跳到主要内容

os期末复习

[toc]

根据大纲及命题计划表，出题分配大概如下

问答题出题：进程管理出一道计算题，处理机调度与死锁出一道银行家算法题和一道简答题，存储器管理出一道计算题，文件管理一道题。

编程题：pv操作一题，lO编程一题

名词解释：os概述一题，进程管理一题，处理机调度与死锁一题，存储器管理一题，文件管理一题

选择题和判断题：os概述一题，进程管理2个选择2个判断，处理机调度与死锁2个选择2个判断，存储器管理1个选择1个判断，设备管理1个选择1个判断，os接口1个选择，实验内容3个选择2个判断

  1. 操作系统概论

    1. OS选择题
    2. OS概述名词解释题
    3. 有一题选择或者判断

  2. 进程管理

    1. 两个选择两个判断
    2. 一道计算题
    3. 一道名词解释

  3. 处理机调度和死锁

    1. PV操作编程题
    2. 一道银行家算法和一道简答题
    3. 一道名词解释
    4. 两个选择和两个判断

  4. 内存/存储器管理

    1. 存储器管理一道计算题、一道解释
    2. 一个选择一个判断

  5. 文件管理

    1. 一道问答（？

    2. 一道名词解释设备管理

    3. 一个选择一个判断

  6. 操作系统接口

    1. IO操作编程题
    2. 一个选择
    3. 实验内容3个选择2个判断

编程题​

#include<stdio.h>
#include<string.h>

#define SEARCH_EDU "计算机与网络安全学院" //待查学院
#define SIZE 10 //学生人数
#define FILE_NAME "./student.txt" //打开文件名
#define FILE_OUT "./csStudent.txt" //输出文件名
#define MAXSIZE 1024

typedef struct STUDENT
{
    char name[20];//姓名
    char sno[20];//学号
    char edu[50];//学院
    char age[4];//年龄
    char sex[4];//性别
}Student;

int main()
{
    Student students[SIZE];
    FILE* stuFile = fopen(FILE_NAME,"r");
    FILE* outFILE = fopen(FILE_OUT,"w");
    char buf[MAXSIZE];
    //读取文件学生信息到内存
    for(int i = 0; i < SIZE; i++{
        fgets(buf,MAXSIZE,stuFile);
        sscanf(buf, "%[^:]:%[^:]:%[^:]:%[^:]:%[^\n]\n", students[i].name,
               students[i].sno,students[i].edu,students[i].age,students[i].sex);
    }
    //打印内存中所有学生数据到屏幕，检验错误
    for(int i = 0; i < SIZE; i++)
    {
        printf("%s %s %s %s %s\n", students[i].name,
               students[i].sno,students[i].edu,students[i].age,students[i].sex);
    }
    //输出指定学院的学生到文件
    for(int i = 0; i < SIZE; i++)
    {
        if(strcmp(students[i].edu,SEARCH_EDU) == 0)
        {
            fprintf(outFILE,"%s:%s:%s:%s:%s\n", students[i].sno,
                    students[i].name,students[i].age,students[i].sex,students[i].edu);
        }
    }
    return 0;
}

操作系统概述​

Concepts​

程序级接口​

程序级接口是为程序访问系统资源提供的，由一组System calls组成

批处理​

对其对象进行批量处理

进程​

并发执行的程序在一个数据集合上的执行过程

临界区​

PCB​

信号量​

一个变量，用来表示系统某种资源的数量

作业​

从输入开始到输出结束用户需要计算机完成的一系列动作的总和

JCB​

作业说明书负责作业的资源调配和程序调用

工作集​

在某个时间间隔内，进程要访问的页面集合。基于程序局部性原理，可以通过最近访问过的页面来确定工作集

死锁​

多个进程循环等待其他进程抢占的资源，因而无限期僵持下去的情况

资源分配图​

系统对资源的分配情况可以用有向图加以描述，该图由顶点和有向边组成G=(V,E)。 其中，V是顶点的集合；

死锁定理​

如果资源分配图中不存在环路，则系统不存在死锁；

紧凑​

动态重定位​

动态重定位即在程序运行过程中要访问数据时再进行逻辑地址与物理地址的变换（即在逐条指令执行时完成地址映射)

页表​

一种特殊的数据结构，用于存放逻辑页和物理逻辑的对应关系。

系统又为每个进程建立一张页面映像表，标明每个逻辑页号所装入的物理块号，简称页表。

页表在内存,是连续的

在页表中，一个页号与其对应的物理块号称之为一个页表项。

快表​

一种高速缓存器，用于缓存页表部分或者全部内容

Belady现象​

分配页面数增多，但缺页率反而提高的异常现象

抖动​

多在FIFO页面置换算法上出现的，频率非常高的页面置换现象

文件系统​

文件分配表FAT​

描述文件系统内存储单元的分配状态及文件内容的前后链接关系的表格

位示图​

用二进制的一位来表示磁盘盘快有无使用 ，1代表已经分配

通道​

数组选择通道​

以数组为单位传输数据，速率较高，通常连接高速设备

DMA​

直接内存访问，传输数据

中断​

在计算机运行中， 出现什么情况需要处理机干预，让机器停止转去执行处理情况的程序，然后处理完毕后返回原来程序

设备无关性​

当应用程序使用某类设备使，不直接指定具体哪个设备，而只指定使用哪类设备，由操作系统来为进程分配哪一类的具体设备

SPOOLing系统​

在联机情况下实现的同时外围操作的技术称为SPOOLing 技术，或称为假脱机 技术

真联机假脱机，在联机的情况下同时访问外围操作，实现了输入井输出井，提高了IO速度、把独占设备变成共享设备

简答题

1-1：什么是操作系统？它有哪些基本功能和基本特征？

1-2：操作系统发展的动力是什么？

1-5：为什么要引入多道程序并发执行技术？

1-11：操作系统的结构有哪些类型？请分别阐述。

  1. 操作系统定义：一个软件系统，它控制和管理计算机系统内各种硬件和软件资源，提供用户和计算机系统之间的接口

  1. 动力

    1. 不断提高计算机资源的利用率的需要
    2. 方便用户
    3. 硬件的不断更新换代
    4. 计算机体系结构的不断发展

  2. 操作系统类型

    1. 批处理
      1. 单道批处理（自动性、顺序性、单道性
      2. 多道批处理（多道性、调度性、异步性、宏观上并行，微观上并行
      3. 多道批处理系统优缺点
        1. 资源利用率高
        2. 系统吞吐量大
        3. 无交互功能
        4. 平均周转时间长

  3. 体系结构

    1. 模块式结构
    2. 层次结构（按照操作系统各模块的功能和相互依存关系，把系统中的模块分为若干层次）
    3. 微内核结构

进程管理​

2-2：试着比较进程和程序之间的区别（7分

2-6：试着说明PCB的作用,为什么说PCB是进程存在的唯一标志（7分）

2-8：什么叫临界区,为什么进程在进入临界区之前要执行申请操作,在离开临界区要执行释放操作（7分）

2-9：试说明进程的基本状态及转换的原因（7分）

2-10：创建一个进程需要做哪些工作（7分）

2-19：在读写者问题中,如果修改问题中的同步算法,要求对写进程优化,即一旦写进程到达,后续的读者进程就必须等待看,而不管是否有读者进程在读文件,试写出相应的程序段（12分）

2-20：试利用记录型信号写出一个不会出现死锁的哲学家进餐问题算法（12分）

2-21：设公共汽车上有一位司机和一位售票员,他们的活动如下图,请分析司机与售票员之间的同步关系,并用P,V操作实现（12分）

2-17：什么是线程,试说明它与进程的主要区别（7分）

2-23： 从调度性，并发性，拥有资源，独立性，和系统开销，以及对多处理机的支持等方面对进程和线程进行比较（10分）

2-24：什么是内核支持线程和用户级线程（7分）

2-25：什么是管程（5分）

Concepts​

管程：一个管程定义了一个数据结构和能为并发进程执行的一组操作，这个操作能同步进程和改变进程的数据

进程控制块的作用​

使一个在多道程序环境下的程序成为一个能够独立运行的单位，能和其他进程并发的单位

线程​

线程是比进程更小的能够独立运行的基本单位，使进程中执行运算的最小单位

进程控制块中的信息​

  1. 进程标识符
  2. 处理机状态
  3. 进程调度信息
  4. 进程控制信息

线程与进程的比较​

线程是操作系统能够进行运算调度的最小单位。

  1. 调度
  2. 并发性
  3. 拥有资源
  4. 系统开销

2-2：试着比较进程和程序之间的区别（7分​

提示

动态性、并发性、独立性、异步性

  1. 程序是静态的概念，而进程是一次执行过程，它是动态的概念
  2. 进程是一个能独立运行的单位，能与其他进程并发执行；而程序是不能作为一个独立运行的单位而并发执行的。
  3. 程序和进程无一一对应的关系
  4. 各进程在并发执行的过程中会产生相互制约关系，而程序本身是静态的，不存在这种异步特征

2-6：试着说明PCB的作用,为什么说PCB是进程存在的唯一标志（7分）​

使一个在多道程序环境下不能独立运行的程序（含数据）成为一个能够独立运行的基本单位，一个能够与其他进程并发执行的进程。

PCB是操作系统中用于描述和管理进程的数据结构，其中存储了进程的各种信息，包括进程的标识、优先级、状态、调度信息、控制信息等等。每个进程都有唯一一个PCB，是操作系统用来系统跟踪和控制的主要数据结构。

2-8：什么叫临界区,为什么进程在进入临界区之前要执行申请操作,在离开临界区要执行释放操作（7分）​

临界资源：一次仅允许一个进程使用的资源

临界区：每个进程中访问临界资源的那段代码叫临界区，两个或以上进程不能同时使用的资源叫临界资源

为了保证多个进程或者线程能够安全地访问临界资源，在进入临界区之前要进行申请操作，以保证只有一个进程或者线程能够获取锁或者信号量，而释放是为了让其他进程或者线程获取该锁进入临界区访问

2-9：试说明进程的基本状态及转换的原因（7分）​

  1. 就绪状态
  2. 执行状态
  3. 阻塞状态

2-10：创建一个进程需要做哪些工作（7分）​

  1. 申请空白PCB
  2. 为新进程分配资源
  3. 初始化进程控制块
  4. 将新建进程插入就绪队列

2-19：在读写者问题中,如果修改问题中的同步算法,要求对写进程优化,即一旦写进程到达,后续的读者进程就必须等待看,而不管是否有读者进程在读文件,试写出相应的程序段（12分）​

semaphore mutex = 1
semaphore wsem = 1
int readcount = 0

# 读者进程
Process reader()
{
    while (1) {
        # 进入读入区域
        wait(mutex)
        readcount++
        if (readcount == 1) {
            wait(wsem) # 阻塞写进程
        }
        signal(mutex)

        # 读取文件
        read_file()

        # 离开读入区域
        wait(mutex)
        readcount--
        if (readcount == 0) {
            signal(wsem) # 唤醒写进程
        }
        signal(mutex)

        # 休息一段时间
        sleep()
    }
}

# 写者进程
Process writer()
{
    while (1) {
        # 进入写入区域
        wait(wsem)

        # 写入文件
        write_file()

        # 离开写入区域
        signal(wsem)

        # 休息一段时间
        sleep()
    }
}

2-20：试利用记录型信号写出一个不会出现死锁的哲学家进餐问题算法（12分）​

image-20230625155922723

2-21：设公共汽车上有一位司机和一位售票员,他们的活动如下图,请分析司机与售票员之间的同步关系,并用P,V操作实现（12分）​

void conductor()
{
    while(true)
    {
        //关门
        signal(door);//售票员给司机关门的信号
        //此阶段为售票时间
        wait(stop);//等待停车信号，一旦停车，则开门
        //开门
    }
}
void driver()
{
    while(true)
    {
        wait(door);//司机等待关门信号，一旦获取信号，则启动车辆
        //此阶段为正常行车时间
        signal(stop);//司机给售票员停车的信号
    }
}

编程题汇总​

06752205ed55c25c95fbd92249a41df

af5a1e304c5127ca52a58165dab4526

600fff9355b86da361b20883f529f09

处理机调度与死锁​

  1. 处理机调度层次

    1. 低级调度：进程调度/短程调度，按照算法决定就绪队列哪个进程获得处理机
    2. 中级调度：内存调度，把外存的就绪队列重新调入内存，将状态改为就绪
    3. 高级调度：作业调度/长程调度，

  2. 进程调度的时机

    1. 完成任务
    2. 等待资源
    3. 运行时间到
    4. 进入睡眠状态
    5. 发现标志
    6. 优先级变化

  3. 处理机调度性能评价指标

    1. 资源利用率
    2. 公平性
    3. 平衡性
    4. 策略强制执行

  4. 处理机调度算法

    eeeaa640be77149dd8222250d14c58c

  1. 适合批处理系统

    1. FCFS先来先服务

    2. 短作业优先

    3. HRF响应比最高者优先：响应比 R=1+已等待时间要求服务时间1+\frac{已等待时间}{要求服务时间}在后背队列选一个R值高的执行

      s

      平均周转时间=从提交到完成的时间

      带权就除以需要运行的时间

  2. 适合分时系统的

    1. 非抢占调度方式

      一旦把处理机分配给进程后，就一直运行下去，不会因为任何原因抢占当前正在运行进程的处理机，直到进程完成或发生某事件被阻塞

    2. 抢占调度方式

    3. 时间轮流片RR：系统根据先来先服务策略将所有的就绪进程排成就绪队列，就绪队列上的每个进程每次仅允许一个时间片

    4. 优先权调度算法HPF

      1. 非抢占式优先级调度算法
      2. 抢占式优先级调度算法：把处理机分配给优先级最高的进程执行，但执行期间若出现 另一个优先级更高的进程，调度程序就将处理机分配给新的优先级最高的进程。

    5. 多级反馈队列调度算法 MFQ

      1. 设置多个就绪队列：第一队列优先级最高，第二队列次之...

        优先级越高的队列分配的时间片越小，第二队列时间片是第一队列的长一倍，以此类推。

      2. 每个队列采用先来先服务算法，当新进程进入内存后，先放到第一队列末尾，轮到该进程执行时，如果能够在该时间片内完成则撤离系统，不能完成就转入第二队列末尾等待调度，以此类推。

      3. 按队列优先级调度，调度程序首先调度最高优先级的队列中的所有进程运行，才会调度下一队列中的进程运行。

  3. 实时调度

    1. 优先级倒置（反转吧？

      高优先级的被低优先级的堵塞了

    2. 解决方案：优先级继承，优先级低的进程继承优先级高的，直到退出临界区

  4. 死锁

    1. 概念：多个进程循环等待其他进程抢占的资源，因而无限期僵持下去的情况。

    2. 死锁的必要条件

      1. 互斥条件
      2. 请求和保持条件
      3. 不可抢占条件
      4. 循环等待条件

    3. 处理方法

      1. 预防死锁

        采取某种策略，限制并发进程对其资源的请求，让条件不满足

      2. 避免死锁

        通过某种方法防止系统进入不安全状态、

      3. 检测死锁

        运行过程中通过检测机构检测出死锁发生，然后及时地去解放进程

      4. 解除死锁

  5. image-20230627164714932

    1. N进程*(单个进程所需要的资源数)>=系统仅有的资源数

银行家算法​

跳转一下

存储器管理​

存储器三层结构​

CPU寄存器、主存、辅存

目标程序装入内存的方法​

  1. 绝对装入方式
  2. 可重定位装入（在程序执行前，由操作系统重定位完成）
  3. 动态运行时装入方式（访问的时候，由重定位寄存器完成）

目标程序链接​

  1. 静态链接
  2. 装入时动态链接（在装入一个目标模块时，若发生一个外部模块调用时，装入程序去找相应的外部目标模块，并将它装入内存）
  3. 运行时动态链接

分区存储管理方式​

  1. 单一分区（分为系统区和任务区）
  2. 固定分区（将用户空间划分为若干个固定大小的区域，将它们分配给程序装入）
    • 内碎片：分配区，程序用完之后浪费的
    • 外碎片：中分区的长度小于作业程序长度，
  3. 可变分区
  4. 可重定位分区

可变分区/动态分区分配算法​

  1. 首次适应法first fit ：自由块按始地址从低到高排序。按照顺序，谁先能放进去谁进去

    （好处：较大的空闲分区可以被保留在内存高端。（最后面没塞满） 不足：但随着低端分区不断划分而产生较多小分区，每次分配时查找时间开销会增大。）

  2. 循环首次适应算法（next fit）：设置了个指针，循环查找

  3. 最佳适应法best fit：排序

    要求按自由块的大小按从小到大的顺序排序。 找到的自由块能满足要求的最小块。 排序:按分区大小，从小到大。

  4. 最差匹配法(worst-fit)：总是挑选最大的空闲区分割给作业使用，以至于空间中缺乏较大的空闲区，故称为最坏适应算法。该算法要求按照容量从大到小排序形成空闲分区链

image-20230626120458494

分区回收​

回收分区的主要工作是： 1）首先检查是否有临接的空闲区，如有则合并，使之成为一个连续的空闲区； 2）之后，修改有关的分区描述信息。 一个回收分区邻接空闲区的情况有四种：

  1. 回收区与插入点的前一个空闲分区 F1 相邻接：修改 F1 大小
  2. 回收分区与插入点的后一空闲分区 F2 相邻接：可合并 F2，但用回收区的首地址作为新空闲区的首地址，大小为两者之和
  3. 回收区同时与插入点的前、后两个分区邻接：将三个分区合并，使用第一个分区的首地址和表项
  4. 回收站不与 F1、F2 邻接：单独新建一个新表项

页表​

系统又为每个进程建立一张页面映像表，标明每个逻辑页号所装入的物理块号，简称页表。

地址变换机构​

将用户地址空间中的逻辑地址变换为内存中的物理地址

例题​

已知某分页系统，主存容量为64K，页面大小为2KB，对一个4页大的作业，其0、1、2、3页分别被分配到主存的2、4、6、7号物理块中，将逻辑地址1023、1023H、2500、0x2500、3500、4500转换成物理地址

  1. 1023物理地址：
    1. 页号P=1023/2048=0 页号0=>2号物理块 2号起始地址=2048*2=4096
    2. 页内偏移：Offset=1023%2048=1023
    3. 物理地址=4096+1023=5119

3.某分页式系统的用户空间共有32个页面，每页1KB，主存16KB。试问： （1）逻辑地址的有效位是多少？ （2）物理地址需要多少位？ （3）假定某时刻系统用户的第0，1，2，3页分别分配的物理块号为5，10，4，7，试将虚地址0x0A5C和0x093C变换为物理地址。（8分）

image-20230626164338353

名词解释：

  1. 静态重定位：在编译阶段产生相对地址，装入程序时确定要装入模块的地址，在装入时进行重定位
  2. 动态重定位：在编译阶段产生相对地址，到程序执行时才将模块的相对地址转为绝对地址
  3. 最近最久未使用算法：在置换一页时，会寻找最近一段时间很久没用的一页置换掉
危险

谨慎使用chatgpt

image-20230627171006213image-20230627171019656

虚拟存储器​

请求分页地址变换过程​

页表机制、缺页中断机构和地址变换机构

  1. 页表机制
    1. image-20230627174247060
  2. 缺页中断机构
    1. image-20230627174311017
  3. 地址变换机构
    1. image-20230627174329528

内存分配策略​

  1. 最小物理块数的确定（保证进程正常运行的最小物理块数，当系统为进程分配的物理块少于这个，进程将无法正常运行）

  2. 物理块的分配策略

    1. 固定分配局部置换(为每个进程分配一定数目的物理块，在整个运行期间都不再改变。)
    2. 可变分配全局置换(先为系统的每个进程分配一定数目的物理块，凡产生缺页中断的进程都将获得新的物理块，仅当空闲物理块队列中的物理块用完时，OS才能从内存中选择一页调出。)
    3. 可变分配局部置换 （当某进程发现缺页时，只允许从该进程在内存的页面中选出一页换出，这样就不会影响其它进程的运行。如果进程在运行中频繁地发生缺页中断，则系统须再为该进程分配若干附加的物理块，直至该进程的缺页率减少到适当的程度为止；反之，若一个进程在运行过程中的缺页率特别低，则此时可适当减少分配给该进程的物理块数。 ）

  3. 物理块的分配算法

    1. 平均分配算法
    2. 按比例分配算法
    3. 考虑优先权的分配算法

  4. 页面置换算法：最佳置换算法、FIFO先进先出置换算法、LRU最近最久未使用（计数器法、移位 寄存器方法、堆栈法）、LFU（frequency）最少使用置换算法、Clock 置换算法、改进型 Clock 置换算法

  5. Belody现象：

    分配页面数增多，但缺页率反而提高的异常现象

输入输出系统​

IO设备分类

什么是 SPLOOING 系统​

假脱机真联机

（1）提高了 I/O 的速度

（2）将独占设备改造为共享设备

（3）实现了虚拟设备功能。

文件管理​

文件逻辑结构​

  1. 流式文件
  2. 记录文件
    1. 顺序文件
    2. 索引
    3. 索引顺序

文件物理结构​

  1. 连续
  2. 串联（链接分配方式）
  3. 索引

image-20230627210322213

文件存储空间​

  1. 空闲空间表法
  2. 位示图法
  3. 空闲块链法
  4. 空闲块成组链接法

文件控制块​

文件控制块通常由文件的基本信息、存取控制信息(所有者、权限)、文件使用信息组成。

索引节点​

把文件描述信息单独形成一个称为索引结点的数据结构，简称为i结点。

image-20230627210648838

磁盘管理​

  1. 在文件分配表中为什么要引入“簇”的概念？以“簇”为基本的分配单位有什么好处？

    簇，为了适应磁盘容量不断增大的需要，在进行磁盘分配时，以簇为单位。一个簇应包含扇区的数量与磁盘容量的大小有关

    还能减少FAT表的项数，使FAT表的占用减少

  2. ​ 某操作系统磁盘文件空间共 500 块，若用字长为 32 位的位示图管理磁盘空间，试问： （1）位示图需要多少字？ （2）第 i 字第 j 位对应的块号是多少？ （3）给出申请 /归还一块的工作流程。

    int(500/32)

    (i-1)*32+j号

    申请：扫描位示图，找到空闲块并分配，修改位示图，Map[i,j]=1

  3. 试说明廉价磁盘冗余阵列 RAID 的主要优点。

    1. 可靠性，大部分有冗余
    2. 磁盘IO高
    3. 性能