操作系统概述

课程要求
1. 课程主要内容
概述
1. 可扩展性
发展历史
1. 进程
2. 内存管理
3. 信息保护和安全
4. 调度和资源管理
5. 现代操作系统的特征
6. 容错性
7. 多处理器和多核操作系统设计考虑因素
进程
1. 进程状态
  1. 进程的两状态模型
  2. 五状态模型
2. 进程描述
3. 进程控制
4. UNIX SVR4
  1. fork()
线程
1. 为什么有线程
2. 线程的特征与优点
3. 线程分类
单处理器调度
1. 重要的调度算法
  1. FCFS
实时系统与实时调度
并发
1. 并发的原理
互斥
1. 软件方法
2. 硬件方法
信号量实现同步与互斥
1. 用信号量解决互斥-同步问题的一般步骤
2. 生产者/消费者问题
  1. 缓冲区的空间数为
  2. 缓冲区的空间数为 1
死锁
1. 解决死锁
2. 哲学家就餐问题
内存管理
1. 基本分页和分段
2. 虚拟内存
文件系统
1. UNIX 文件管理
  1. 索引结点结构
  2. 文件分配
作业1
作业2
作业3
作业4
作业5
作业6
作业7
作业8
Project
《计算机操作系统》2018-2019学年第二学期期中考试试卷（Ａ卷）
实验

希望能坚持。

course

课程要求

课程主要内容

操作系统概述
进程管理
存储管理
设备管理
文件管理

概述

操作系统的三个目标：

方便: 使计算机更容易使用.
有效: 以更有效的方式使用计算机系统资源.
扩展能力: 在不妨碍服务的前提下, 有效地开发, 测试和引入新的系统功能.

它提供了下面的服务:

程序开发
程序运行
I/O 设备访问
文件访问控制
系统访问
错误检测和响应
记账

三种重要接口是 ISA, ABI, API.

由于计算机可以看作是一组资源, 因此操作系统可以看作是资源管理器, 控制计算机的基本功能, 但是是一种不同寻常的控制:

操作系统是由处理器执行的一段程序或者一组程序
操作系统经常会释放控制, 而且必须依赖处理器 (processor) 才能恢复控制. 操作系统控制处理器使用其他系统资源, 并控制其他程序的执行时机. 其实就是不同程序对处理器的占用调度分配.

因此 OS 需要完成的资源管理包括:

内存的分配管理
I/O的访问控制
对文件的访问控制和使用
对处理器的分配

操作系统通过接口向用户提供服务.

可扩展性

操作系统因下面的特性而不断发展:

硬件升级和新型硬件的出现
新服务
纠错: 引入补丁(patch)纠错. ( patch 本身也会引入新的错误 )

发展历史

监控程序的功能:

作业的自动续接

内存保护
定时器
特权指令
中断

两种运行模式:

用户模式: 不允许执行特权指令
内核模式: 可执行特权指令以及访问受保护的内存区域.

1: 为什么要有两种运行模式(user mode 和 kernel mode)?

答: 为了安全性(保护操作系统重要的数据结构, 防止在用户模式下访问到关键的内存执行到关键的指令, 而对操作系统造成破坏)/错误隔离/性能优化.

2: 如何知道当前是哪种模式?

答: 通过特殊的处理器状态标志(存在寄存器中)以及硬件机制来判断. 类似的有状态字寄存器PSW.

batch processing 指的是一批作业要能自动处理完成, 也就是完成一个作业之后要能够自动续接.

简单批处理系统通过串行处理, 是 读-执行指令-写 的串行序列(处理器必须等待I/O完成后才能继续处理), 实际利用的时间只有执行指令的时间, 其他时间都在等I/O, 而执行指令的速度非常快, 导致系统利用率非常低.

多道批处理(batch processing)系统就是并发处理, 处理器在空闲时间去执行其他指令. 这其中比较重要的硬件是I/O中断和DMA. 除此之外, 由于需要并行处理, 因此需要将待执行的若干作业存储起来, 需要内存管理, 也需要设计合适的调度算法(作业调度程序负责).

1: 并发和并行的区别:

并发指的是在一段时间内可以同时执行若干作业.

并行指的是某一时刻可以同时执行.

并行可以看作是并发的子集.

2: 为什么在多道批处理中需要有中断和DMA的支持?

中断: 当I/O完成后操作系统会正在进行I/O操作的进程发出I/O中断, 处理器被中断, 操作系统接管对处理器的控制权.

DMA: 由于作业存在存储器中, 因此需要频繁地直接访问存储器, 而DMA可以允许外设直接访问系统内存, 不需要CPU接入, 可以大大提高数据传输的效率.

计组没学好是这样的😭

分时系统:

采用多道程序设计技术处理多个交互作业
多个用户共享处理器时间
多个用户可以通过终端同时访问系统(操作系统控制用户程序在很短的时间内交替执行)
时间片技术.

分时与多道的联系是什么? 分时是在多道的基础上设计的, 都是为了提高处理器利用率.

进程

1: 什么是进程?

一个正在执行的程序.
计算机中正在运行的程序的一个实体
可分配给处理器并由处理器执行的一个实体
由一个单一顺序线程, 一个当前状态, 一组相关系统资源所表征的活动单元. 表征是什么意思? 活动单元又是什么意思?

可以看到进程是一个动态的概念.

什么是线程?

答: 线程是计算机程序中的一种执行单元，它是进程的一部分。一个进程可以包含多个线程，每个线程独立执行特定的任务。与进程不同的是，线程共享相同的内存空间，可以直接访问进程的资源和数据。

什么叫做表征? 什么叫做活动单元?

答: 表征就是表示的意思.

2: 为什么要有进程? (实际上是类似于数据库中事务的特性) 可能会存在下面的问题:

不正确的同步
失败的互斥
不确定的程序操作
死锁

3: 进程的组成.

一段可执行的程序
程序所需要的数据
程序执行的上下文(进程状态, 操纵系统用来管理和控制进程所需的所有数据), 是一个比较复杂的数据结构.

线程是什么?

什么是进程挂起?

内存管理

操作系统使用

虚拟内存(允许程序以逻辑方式访问存储器, "以逻辑方式"的含义是不考虑物理内存可用的空间数量)
文件系统(实现长期存储)

来实现下面的功能:

进程隔离
自动分配和管理
支持模块化程序设计
保护和访问呢控制
长期存储

分页机制用来解决因进程大小不一致难以将进程紧密地压入内存的问题, 同时:

提供了虚地址和物理地址之间的动态映射
进程由若干固定大小的页组成
程序通过虚地址访存字, 虚地址由页号和页中的偏移量(类似在词典查阅单词的方式)组成

信息保护和安全

四类典型安全问题:

可用性: 保护系统不被中断
保密性: 保证用户不能读取未授权访问的数据
数据完整性: 保护数据不被未授权修改
认证: 设计用户的身份的正确认证和消息或数据的合法性

调度和资源管理

任何资源分配和调度策略都必须考虑三个因素:

公平性
有差别的响应性: 区分提供不同服务的部件
有效性: 获得最大吞吐量和最小响应时间; 在分时情形下, 可以容纳尽可能多的用户.

现代操作系统的特征

微内核: 只给内核分配一些最基本的功能, 包括地址空间, 进程间通信和基本的调度, 优点是

简化了实现
提供了灵活性
适用于分布式环境.

多线程: 把执行一个应用程序的进程划分为可以同时在运行的多个线程.

线程是什么? 线程和进程的区别是什么?

对称多处理:

多个进程和线程可以并行运行
多个处理器对用户来讲是透明的(共享内存和I/O并可执行同一任务)
操作系统在不同的处理器上调度不同的进程或线程, 并负责它们之间的同步

优点:

性能: 多个处理器可以在不同的处理器上同时运行
可用性: 单个处理器的失效不会导致机器停止
渐增性: 系统性能可以随着添加新的处理器而提高
扩展性: 生产商根据处理器的数量提供不同价格与性能的产品.

分布式操作系统

面向对象的设计

容错性

容错性指系统或部件发生软硬件错误时, 能够继续正常运行的能力. 操作系统采用下面的技术提高容错性:

进程隔离: 进程的内存, 文件存取和执行过程相互隔离
并发机制: 保证进程通信或协作时的正确性
虚拟机
检测点(一个 backup)和回滚机制 (退回检测点) (和数据库的事务部分很像)

多处理器和多核操作系统设计考虑因素

什么八股文, 不想写了.

进程

进程都有什么状态? 进程的这些状态是如何互相转换的? 产生这些转换的原因是什么? 操作系统管理控制进程都需要哪些信息?

进程的两个基本元素: 程序代码与和代码相关的一组数据, 除此之外还有进程控制块(PCB), 进程控制块:

包含了进程的元素
可以中断和恢复进程的执行(好像中断从未发生过一样)
由操作系统创建和管理
是支持多进程的重要工具

进程执行的任意时刻, 都可以用 标识符, 状态, 优先级, 程序计数器, 内存指针, 上下文数据, I/O状态信息, 记账信息(处理器时间总和, 使用的时钟数总和, 时间限制, 记帐号等) 这些元素来表征, 这些元素存在 PCB 中.

可以说 PCB 集合定义了操作系统的状态。

进程的基本特征:

动态性: 本质特征
并发性
独立性: 各进程的地址空间相互独立, 除非采用进程间通信手段
异步性: 按各自独立的不可预知的速度向前推进

异步是什么意思?

进程和程序的区别是什么?

答: 进程=进程控制块+程序+相关数据. 进程动态而程序静态, 注意进程和程序之间不存在一一对应关系(一个应用程序可以对应多个进程的执行, 在 Windows 的任务管理器中可以看到例子).

进程状态

如何描述进程? 列出进程执行的指令序列, 可以描述单个进程的行为, 这样的指令序列被称为进程轨迹(trace).

定义进程的轨迹后, 可以用多个进程执行的轨迹来描述处理器的行为, 分派器可以将处理器从一个进程切换到另一个进程.

进程的两状态模型

进程有运行态和非运行态.

进程的创建和终止

五状态模型

将非运行态分为两个状态: 就绪态(ready)和阻塞态(blocked), 一共是五个状态:

运行态
就绪态
阻塞态
新建态
退出态

进程描述

这部分关注的信息是, 操作系统要控制并管理资源, 需要哪些信息? 用什么结构来控制和管理? 如果这个资源是进程, 信息具体是什么呢? 管理进程的具体结构是什么?

进程的物理存在是: 进程的位置和进程的属性, 操作系统通过这两点管理和控制进程.

PCB, Data, Stack, Code 的集合称为进程映像(process image).

PCB 控制的元素包括:

进程标识信息, 典型的是标识符(ID), 包括
- 当前进程的PID
- 父进程的PID
- 用户ID
用来对进程索引, 在做某些事的时候指明和区分每个进程.
处理器状态信息, 主要是一些寄存器, 包括:
- 用户可见寄存器(下面的两个寄存器用户不可见): 用户模式下机器语言可以访问的寄存器.
- 控制和状态寄存器, 就是 PSW, 需要参考计组中的内容.
- 栈指针: 栈保存参数和过程调用或系统调用的地址, 栈指针指向栈顶.
进程控制信息: 操作系统控制和协调各种活动进程所需的额外信息.

进程控制

这部分探讨的问题是, 操作系统是如何具体管理和控制进程的? 这包括进程的创建和切换, 是如何创建的? 因为什么发生了进程切换? 以及:

进程创建时操作系统和进程会出现哪些变化?

进程切换时操作系统和进程会出现哪些变化?

使用两种模式的原因是保护操作系统和重要的操作系统表(如PCB)不受用户程序的干扰.

模式切换的原因是系统调用或者中断:

中断出现 PC置为中断处理程序的开始地址 user转为kernel, 以便中断处理能执行特权指令.

模式切换不一定导致进程切换, 比如 I/O 中断来了之后, 处理完 I/O 中断还会继续处理原进程. 还有 getpid().

如果当前的进程状态变化(就绪或阻塞), 则回进程切换.

进程切换的步骤:

1. 保存处理器上下文环境, 保存到PCB中.

2. 更新当前处于运行状态的PCB.

3. 将进程的PCB已知相应队列

4. 选择另一个进程执行

5. 更新PCB的信息(原来的进程信息改成切换成的新的进程的信息)

6. 更新内存管理数据结构

7. 恢复被选择进程的上下文环境

UNIX SVR4

用文字描述上图的状态转换.

`fork()`

一个进程使用系统调用 fork 来创建一个新的进程, 新的进程称为子进程, 其内存内容与调用它的进程(称为父进程)相同. 在父进程中, fork 返回子进程的PID, 在子进程中, fork 返回零. 子进程会复制父进程的 image, 拥有一份独立的 copy.

调用 fork() 之后, 从 fork 所在的语句开始, 下面的所有语句将同时在父子进程中执行.

#include<stdio.h>
#include<sys/types.h>
#include<unistd.h>
int global = 4;
void main(void) {
    int  pid; 
    int vari = 5;
    printf("before fork\n");
    if ((pid = fork()) < 0) {
        printf("fork error\n");
        exit(0);
    } else if (pid == 0) {
    global++;
    vari--;
    }
    printf("global=%d,vari=%d\n", global, vari);
}

上面这段代码中, 即使 global 是全局变量, 但是子进程中对 global 的改变不会影响父进程中 global 的值.

线程

为什么有线程

由于进程的两个特点(资源所有权, 调度/执行)是相互独立的, 为了区分这两个特点:

调度并分派的单位称为线程
拥有资源所有权的单位称为进程

多线程是指在操作系统在单个进程内支持多个并发执行路径的能力.

线程的特征与优点

1: 线程与特征极为相似, 线程所具有的特征为:

线程执行状态
未运行时保存的线程上下文, 是寄存器的环境, 保存为了便于下一次调用时恢复信息.
执行栈
静态存储空间, 以及与进程内其他线程共享的内存和资源的访问

2: 进程中所有的线程共享该进程的状态和资源.

多线程进程模块中, 每个线程都有一个线程控制块TCB, 用户栈和内核栈, 在所有线程之外有一个进程控制块PCB.

3: 线程的优点是各方面的速度更快, 包括

创建: 创建线程的时间更少.
终止: 终止线程的时间更少.
线程间切换: 花费时间小于进程间切换.
通信效率更高: 线程共享很多内存和文件, 无需调用内核就可以通信.

4: 在支持线程的操作系统中, 调度和分派是在线程基础上完成: 挂起/终止进程会挂起/终止进程内所有的线程(因为所有线程共用一个地址空间).

5: 类似于进程, 线程的主要状态为 运行/就绪/阻塞, 与线程状态相关的基本操作为 派生/阻塞/解除阻塞/结束(这些都是动词, 宾语为线程):

派生类似于 fork, 新创建的进程可以派生出一个线程, 进程内部的线程也可以派生出另一个线程.
解除阻塞会将被阻塞的线程移入就绪队列中.

6: 线程同步指的是, 一个进程内的线程:

共用地址空间和资源
一个线程对共享资源的修改都会影响到其他线程

线程分类

1: 用户级线程 (ULT) 优点:

线程切换不需要内核模式的特权, 节省了两次状态转换的开销
调度策略因应用程序不同而不同, 可以量身定做调度算法
可以运行在任何操作系统上

缺点:

执行系统调用时不仅会阻塞这个线程, 也会阻塞这个线程中的所有进程. 将应用程序写成一个多进程程序而非多线程程序可以解决这个缺点.
不能使用多处理器技术. 使用 jacketing 技术, 把一个产生阻塞的系统调用转化为一个非阻塞的系统调用, 可以解决这个缺点.

2: 内核级线程 (KLT) 中, 应用程序没有线程管理的工作.

优点:

内核可以把同一个进程内的多个线程调度到多处理器上
当一个线程阻塞时, 内核可以调度同一进程内的其他线程
内核例程本身也可以是多线程的

缺点: 将控制权从一个线程切换到另一个线程时, 需要切换到内核模式.

可以用混合方法.

单处理器调度

1: 调度就是把进程分配到处理器上执行的方式, 一个好的调度算法要满足响应时间快, 吞吐量大, 处理器效率高.

2: 调度的类型包括长程调度, 中程调度, 短程调度, 它们在计算机中有对应的程序, 这些程序的作用分别是:

长程调度程序决定哪个程序可以进入系统中处理, 控制系统的并发度(指有多少进程在等待处理器). 就是用来将刚创建好的进程调度到就绪队列中.
中程调度程序实现了一部分的交换功能(即进程的换入换出), 在挂起状态与非挂起状态之间执行.
短程调度程序精确地决定下次执行哪个进程.

可以看出短程调度执行得最为频繁, 当导致当前进程阻塞或被抢占的事件发生时就需要调用短程调度程序.

3: 与调度规则相关的概念:

响应时间: 用户提交一个请求开始, 到接收进程的响应之间的时间间隔, 等于 $输入传送时间处理时间响应传送时间$ .
周转时间: 又称驻留时间, 一个进程从提交到完成之间的时间间隔. 周转时间包括等待调度(包括在外存和内存等待), 等待资源和阻塞的时间, 往往包括响应时间, 因为进程完成之前用户可能会多次请求, 进程会多次响应.
截止时间: 某任务最迟开始的时间, 或者必须完成的最迟时间, 这两个定义是等价的.
吞吐量: 单位时间内系统完成的进程数.
处理器利用率: 处理器处于忙状态的时间与总的时间的比值.

在周转时间的基础上, 可以定义带权周转时间 , 其中表示进程的周转时间, 表示系统为进程提供的服务时间(或者说占用处理器的时间), 显然往往有 .

在所有系统中, 面向用户的规则都非常重要, 而在单用户系统中, 面向系统的重要性就要低一些.

4: 调度的决策模式包括

抢占: 在进程执行过程中被操作系统中断并转换为就绪状态. 可能导致抢占的原因: 1) 更高优先级的进程处于就绪状态; 2) 中断发生后唤醒一个进程; 3)周期性的时间中断;
非抢占: 只有当执行完毕或者因I/O等被阻塞时才会释放处理器. (即进程主动放弃处理器)

5: 调度的选择函数: 可以理解为进程的优先级的计算方式. 设表示目前为止进程在系统里的等待时间, 表示目前为止花费的执行时间, 表示进程所需的总服务时间, 这个数据需要基于历史数据估计或者用户提供.

重要的调度算法

进程的饥饿指的是进程长时间得不到执行或者是执行速度非常缓慢导致长时间无法执行完毕.

SRT 的到达时抢占是指在任意时刻处于运行状态的都是剩余时间最短的进程，如果进程 A 运行的过程中某个时刻进程 B 的剩余时间成为最短的，那么 B 就会抢占 A.

FCFS

调度规则, 调度的决策模式, 调度算法, 实时系统和实时调度

需要学会画 round-robin 的调度图, 搞清楚进程在队列之间的切换就好.

各种调度的特点：

选择函数
决策模式: 包括抢占 (又称为剥夺) 和 非抢占 (进程仅在主动放弃时才会中断)
吞吐量
响应时间
开销
对进程影响: 区分对短进程, 长进程和I/O密集型进程的有利与不利
饥饿: 无饥饿指的是在就绪队列中的进程总是能得到调度, 不论等待时间多久

实时系统与实时调度

1: 实时任务分类

2: 实时操作系统特点

可确定性
可响应性
用户控制
可靠性
失效弱化

3: 实时调度:

调度方法: 下次允许调度哪个任务
抢占方式

4: 实时调度的调度方法

静态表驱动调度法: 按照任务周期到达的时间, 执行时间, 完成截止时间以及任务的优先级指定调度表. 比如动车各个时刻是固定的, 可以指定车站中动车的发车时间. 缺陷: 任意一个调度改动后都会影响调度表的修改. 比如动车某一辆除了问题, 那么与之相关的所有的动车的发车时刻都会受到影响.
静态优先级抢占调度法: 实时系统中一般根据任务的时间约束赋予优先级, 比如RM算法.

并发

并发指的是系统在同一段时间内可以执行多个作业, 定义比并行要弱一些.

在单处理器多道程序系统中, 虽然在任意时刻只能有一个进程占用处理器, 但是由于时间片机制的存在, 在一段时间内, 从外部看来好像是多个进程一起执行, 因此可以认为单处理器多道程序系统中也存在并发.

并发的原理

并发的原理部分主要介绍单处理器多道程序系统是如何在交替执行进程的同时保证不发生错误, 这些错误可能包括:

死锁

饥饿

忙等

同时访问或修改共享资源

这一部分很像数据库中事务的执行, 要保证事务的ACID特性, 进程同样有类似的特性.

原子性, 一致性(), 隔离性(互斥), 持久性.

1: 如果需要保护共享的全局变量, 唯一的方法是控制访问该变量的代码.

2: 进程间的关系包括:

竞争
通过共享合作(共享不当可能导致输出错误)
通过通信合作(通信顺序不当可能导致沉默)

进程之间的感知程度都有哪些? 对应的进程关系是什么? 在该关系下, 可能会存在哪些问题?

互斥

互斥的要求(即访问临界区的原则):

空闲让进: 临界区空就进.
忙则等待: 任意时刻只允许一个进程在临界区/临界区不空就等.
有限等待: 进程不能饥饿/死锁, 在有限时间内能进入临界区.
让权等待: 在临界区里不能呆的时间太长(不能占着茅坑不拉屎).

软件方法

爱斯基摩人的小屋只能容纳一人, 当小屋有人时, 在门口竖旗表示有人. (用厕所好像也能举例子).

Dekker 算法和 Peterson 算法.

硬件方法

硬件方法：

中断禁用: 为保证互斥, 只需要保证进程在执行时不被中断即可.
机器指令
- compare & swap
- exchange

中断禁用不能用在多处理器中, 而且代价比较高, 会导致程序效率大幅度下降.

信号量实现同步与互斥

1: 信号量值的含义:

信号量初始化为当前的可用资源数

信号量小于零时, 它的绝对值表示被阻塞的进程个数.

用信号量解决互斥-同步问题的一般步骤

确定所有的信号量

生产者/消费者问题

描述:

生产者产生数据
消费者消耗数据

生产者需要的资源为缓冲区剩余空间个数, 消费者需要的资源为缓冲区的数据个数.

保证:

生产者-生产者, 消费者-消费者, 生产者-消费者互斥地访问缓冲
满不生产, 空不消费.

注意:

先申请资源信号量, 再申请互斥信号量. 否则可能会发生死锁.

缓冲区的空间数为

当缓冲区的空间数不小于 2 时, 除了使用缓冲区的互斥信号量外, 还需要两个资源信号量(空间资源信号量和数据资源信号量).

缓冲区的空间数为 1

当缓冲区的空间数仅为 1 时, 只用一个缓冲区的互斥信号量是不够的, 因为这样可能会发生死锁

死锁

1: 死锁是一组相互竞争系统资源或进行通信的进程间的永久阻塞.

2: 一种引发死锁的原因是资源的竞争, 首先对资源分类:

可重用资源. 一次仅供一个进程安全使用且不因使用而耗尽的资源.

比如处理器, 内存和外存, I/O通道等.
可消耗资源. 可被创建(生产)和销毁(消耗)的资源, 且消费进程得到可消耗资源后, 该资源就不再存在.

如中断, 信号, 消息, 以及I/O缓冲区中的信息.

对于进行通信的进程, 当双方都等对方先发消息而不主动发消息, 就会导致沉默, 是一种死锁.

3: 死锁的必要条件：

互斥.
占有且等待. 一个进程等待其他进程时, 继续占有已分配的资源.
不可抢占.

充分条件：

循环等待. 在资源分配图中存在一个闭合的进程链, 使得每个进程至少占有下一个进程所需的一个资源.

4: 通过资源分配图可以判断是否存在死锁, 称为资源分配图的化简. 对于一个资源分配图, 找到全部请求都能满足的进程, 删去该进程的分配边和请求边(进程的request和资源的held by), 重复执行, 只扫不能化简. 若存在非孤立点, 则存在死锁.

解决死锁

通过防止充分条件或必要条件的发生来阻止死锁的发生.

必要条件的互斥不能禁止, 禁止互斥可能会引发错误(如同时写).

	死锁预防	死锁避免	死锁检测

死锁预防

防止占有且等待: 要求进程一次性地申请所有需要的资源, 当要求无法满足时, 就阻塞该进程, 知道能申请到所有需要的资源.
防止不可抢占. 若一个占有某些资源的进程在申请其他资源的时候被拒绝, 则
- 释放最初占有的资源
- 要求另一个进程释放资源
防止循环等待. 给资源定义优先级, 即定义一个请求资源的顺序.

死锁避免

允许三个必要条件, 并动态地进行检查是否会导致死锁. 需要预知资源的请求.

定义 , , .

进程启动拒绝. 若有一个进程请求会导致死锁, 则不启动该进程.
资源分配拒绝. 银行家算法: 搜索安全序列.

死锁检测

死锁检测算法.

定义为当前进程对类资源的请求数. 算法流程如下:

标记中全为的行 .
令临时变量 .
寻找进程满足 (即寻找是否存在可分配资源的进程).
若能找到满足 3 中的进程 , 则标记进程 , 并令 (找到可以分配资源的进程, 分配后等该进程执行完毕, 将已分配的资源释放掉), 并转到 3.
若找不到满足 3 中的进程 , 终止算法.

死锁解除

检测到死锁后, 有下面的解决方法:

撤销进程. 撤销所有死锁进程或连续撤销死锁进程直到不发生死锁.
回退. 将进程回退到前面定义的某些检查点, 并重新启动所有进程.
抢占. 连续抢占进程直到不存在死锁.

优先对哪些死锁的进程执行上述方案?

消耗处理器时间少

输出少

分配资源少

剩余执行时间长

优先级最低

等等.

哲学家就餐问题

内存管理

程序存储在外存或 cache 中, 内存管理的主要操作是处理器把程序装入到内存中执行, 因此不同程序(进程)在内存中的组织和分配方式是首先要考虑的, 最朴素的方法是将内存划分为若干区域, 每次给要装入到内存的程序分配一整块, 根据块的特点有:

固定分区: 将内存划分为大小固定的块 (因此数量确定), 这些块大小相等或大小不等.
- 所有分区都满且没有进程处于就绪态或运行态: OS 换出一整个进程的所有分区, 再装入另一个进程.
- 程序太大超过最大分区的大小: 使用覆盖技术设计程序, 使得程序只有一部分在内存中.
- 程序太小: 也要占据一个完整的分区, 导致内部碎片的产生. 内部碎片是分区内部并未装入数据块的部分.
- 分区大小不等时可缓解这两个问题, 但是装入进程时装入不同大小的块的策略对性能的影响也是不同的,
动态分区:
- 外部碎片: 在分区外的存储空间变成了越来越多的碎片.
- 放置算法: 对于要装入内存的程序
  1. 最佳适配: 选择大小最接近的块
  2. 首次适配: 从头扫描内存, 选择大小足够的第一个块.
  3. 下次适配: 从上一次放置的位置开始扫描, 选择大小足够的第一个块.
  性能: $首次适配下次适配最佳适配$ .
Buddy System. 一种二分的策略. 整个内存大小为 Byte. 如果来的块的大小为

基本分页和分段

基本分页方式中, 页框大小等于页号

逻辑地址为 $页号偏移量$
物理地址为 $页框号偏移量$
页表是页框号到页号的映射, 可以通过页号找到页框号

这类似于字典, 每一页白纸可以看作是页框, 某个单词的实际页数+行数可以视作其物理地址. 以开头的单词是中间的若干页, 某个以为开头单词的逻辑地址为该单词相对于第一页以为开头的单词的页数+行数. 比如逻辑地址为的单词, 页表中有 , 那么物理地址为 .

设内存为字节, 分页且页框(或者页)大小为字节, 则偏移量为逻辑地址的后位, 内存中一共有个页框, 页框号为逻辑地址的前位. 页表是页框号到页号的映射, 通过页表和页框号获取页号, 与位偏移量进行拼接得到物理地址. 对于十进制数, 需要通过取整和取余来获取页号和偏移量的十进制表示.

虚拟内存

文件系统

UNIX 文件管理

掌握：

UNIX 文件类型

索引节点 Inode 的结构

混合索引方式相关计算

UNIX 路径解析

索引结点结构

文件分配

FreeBSD 系统最小的块大小为 4KB 时, 块地址项长度为 8B, 则每一块可以存放个块地址项.

直接块有 12 个, 总容量为 .
一级间接块有 1 个, 块中有 512 个块地址项, 指向 512 个块, 总容量为 .
二级间接块有 1 个, 一共有个块, 总容量为 .
三级间接块有 1 个, 一共有个块, 总容量为 .

每个块可存个地址项, 则 $直接一级二级$

给定字节偏移量求物理地址, 设块的大小为 .

首先计算其所在逻辑块号为 , 以及块内偏移量为 .

根据的大小判断该逻辑块为直接块/一级/二级/三级, 对进行拆分.

对于 350000, 计算其所在的块数(逻辑块号)为 , 且 , , 且 , 则在二级间接块的第 0 个一次间接块的第 75 个表项中, 其中的盘块号为 333, 则物理地址为盘块号 333 中的第 816 字节.

作业1

1.归纳整理操作系统的基本功能。

作为资源管理器, 包括内存的分配管理, I/O的访问控制, 对文件的访问控制, 对处理器的分配.

2.论述批处理、分时和实时三种操作系统的基本特征。

批处理: 有监控程序, 对一批程序进行自动处理, 分为简单批处理和多道批处理

简单批处理: 处理器必须等待I/O指令完成才能继续处理, 处理器经常处于空闲状态

多道批处理: 多道性, 调度性, 无序性, 无交互能力

分时: 多路性, 独立性, 及时性, 交互性

实时: 可确定性, 可响应性, 用户控制, 可靠性, 故障弱化能力

3.为什么会有进程？分析理解进程的概念、上下文的含义。

进程存在的原因是, 系统中在同一时间会有许多作业在运行, 为了防止不正确的同步/失败的互斥/不正确的程序操作/死锁等情况的发生, 需要设计系统级的机制来监控各个作业的运行.

4.论述现代操作系统的特征。

5.解释单体内核和微内核的区别。

6.进程调度程序、时钟中断处理程序和命令解释程序在哪种模式下执行？

进程调度程序和时钟中断程序: 内核模式

命令解释程序: 用户模式 (比如shell中的命令)

7.分析系统调用时的模式切换过程？

作业2

需要注意题目前的论述二字, 一定要详细说明.

1.论述程序、进程、线程的区别与联系

2.论述进程控制块(PCB)的作用、存储内容

3.论述进程的基本特征。

4.以图为例，分析五状态进程模型

5.为什么引入挂起状态，其与阻塞状态的本质区别是什么？

6.论述进程切换与模式切换的区别。什么情况下会发生进程切换，什么情况下会发生模式切换。

7.什么是中断？中断的处理过程如何？

8.什么是系统调用？

9.比较不同类型线程的优缺点。

10.说明fork()函数的作用，并举例说明。

可能会考的其他问题：

进程的轨迹是什么？如何描述处理器的行为？分派器的作用是什么？

进程可以由什么内容来表征？这些内容存在PCB的哪一部分？

进程实体/进程映像是什么？包含哪些典型元素？

进程都有哪些状态？每个状态代表着什么含义？这些状态是如何相互转换的（或者说什么事件会触发这些状态之间的转换）？

操作系统可能因为哪些原因创建进程？操作系统创建进程的具体过程的步骤是什么？创建进程时若资源不足会发生什么？

进程可能因为哪些原因或事件而终止？操作系统终止进程的过程是什么？

进程在什么条件下会被阻塞？进程的阻塞和唤醒的具体过程是什么？

分析进程的七状态模型。

进程可能因为哪些原因被挂起？挂起的进程有哪些特点？挂起进程所需的代理的作用是什么？

操作系统的控制结构的作用是什么？操作系统都有哪些控制结构？

操作系统在管理和控制进程时必须知道进程的位置和进程的属性，这被称为进程的物理存在，进程的物理存在具体包含哪些内容？

为什么要使用用户模式和控制模式两种模式？

保护操作系统和重要的操作系统表（比如PCB）不受用户程序的干扰。

叙述进程切换的步骤。

为什么要引入线程？叙述线程的优点。

叙述用户级线程、内核级线程以及混合方法的内容。

作业3

1.周转时间和响应时间有什么区别？

2.高响应比优先调度算法的主要优点是什么？

3.为什么说多级反馈队列调度算法能较好地各种用户需求？

4.进程A、B、C、D和E到达时间、服务时间如下表所示，试计算分别采用FCFS、RR(q=1)、RR()、SPN、SRT、HRRN、FB()、FB()调度算法时，进程A、B、C、D和E的周转时间、带权周转时间，以及平均周转时间、平均带权周转时间，并对结果进行简要分析。

进程	到达时间	服务时间
A	0	3
B	2	6
C	4	4
D	6	5
E	8	2

作业4

信号量部分伪代码规范:

信号量用 semaphore 声明, 读者写者问题中的 conut 就用 int 声明即可.

所有进程的函数返回值类型都为 void.

记得加分号.

主函数按照下面的写法:
1
2
3
void main(){
    parbegin(p1,p2,p3); // 所有同时执行的进程
}

1：什么是临界资源、临界区，临界区的使用原则有哪些？

2：简述信号量的含义及作用。

3：请用P、V操作描述下列过程

4：图书馆有N个座位，一张登记表，要求(1)阅读者进入时登记，取得座位号；(2)出来时注销。请用P、V操作描述一个读者的使用过程。

5： 4个并发执行的进程P1、P2、P3和P4合作解决数据计算问题：.

(1)P1不断产生随机数并放入的缓冲区A中；

(2)P2、P3分别读取缓冲区A中的数据并计算其平方值、立方值，然后分别放入缓冲区B、C中；

(3)P4读取缓冲区B、C中的数据，将其相加，并输出；

(4)缓冲区A、B、C的容量为1。

用P，V操作实现其同步过程。

下面的代码是错误的, 因为要求 P2, P3 取的是同一个数, 而下面 P2 和 P3 取的不是同一个数:

Wrong Answer pA, pB, pC 分别表示生产者对三个缓冲区使用(存数)的信号量, cA, cB, cC 分别表示消费者对三个缓冲区使用(取数)的信号量. 伪代码如下:

pA=1
pB=1
pC=1
cA=0
cB=0
cC=0

p1()
{
    while (true)
    {
        P(pA);
        // Produce a number randomly and put it in buffer A.
        V(cA);
    }
}

p2()
{
    while (true)
    {
        P(cA);
        P(pB);
        // Get the number in buffer A and calculate its square, and put it in buffer B
        V(cB);
        V(pA);
    }
}

p3()
{
    while (true)
    {
        P(cA);
        P(pC);
        // Get the number in buffer A and calculate its cube, and put it in buffer C
        V(cC);
        V(pA);
    }
}

p4()
{
    while (true)
    {
        P(cB)
        p(cC)
        // Get two numbers from buffer B and C respectively, and get the sum of them
        V(pC)
        V(pB)
        // output final result
    }
}

Correct Answer

P1 需要等 P2 和 P3 都取数后才能再生产数, 注意没有要求 P2, P3 对 A 互斥访问.

gotA_2 = 1; // 表示P2是否从A中取过数
gotA_3 = 1; // 表示P3是否从A中取过数
getA_2 = 0; // 表示P2是否可以从A中取数
getA_3 = 0; // 表示P3是否可以从A中取数

full_B = 0; // 缓冲区B是否满
full_C = 0; // 缓冲区C是否满
empty_B = 1; // 缓冲区B是否空
empty_C = 1; // 缓冲区C是否空

P1()
{
    while (true)
    {
        P(gotA_2);
        P(gotA_3);
        // 产生数放到A中
        V(getA_2);
        V(getA_3); // 通知P2,P3可以取数了
    }
}
P2()
{
    while (true)
    {
        P(getA_2);
        // 取数
        P(empty_B);
        // 算平方放进B
        V(gotA_2);
        V(full_B);
    }
}

P3()
{
    while (true)
    {
        P(getA_3);
        // 取数
        P(empty_C); // buffer C 空才能放数
        // 算立方放进 C
        V(gotA_3);
        V(full_C);
    }
}

P4()
{
    while (true)
    {
        P(full_B);
        // 取数
        V(empty_B);
        P(full_C);
        // 取数
        V(empty_C);
        // 计算输出
    }
}
void main(){
    parbegin{P1,P2,P3,P4};
}

注意 P4 不要写成

P(full_B);
P(full_C);
V(empty_C);
V(empty_B);

这样效率会低, 无需同时取数再算和, 分别取即可.

6: 桌上有一空盘，最多允许存放一只水果。爸爸可向盘中放一个苹果或放一个桔子；儿子专等吃盘中的桔子，女儿专等吃苹果。用P、V操作实现爸爸、儿子、女儿三个并发进程的同步。

7: 用P、V原语实现过独木桥问题，独木桥最大承重为N人。

8: 某寺庙，有小、老和尚若干，有一水缸，由小和尚提入水缸供老和尚饮用。水缸可容10桶水，水取自同一井中。水井径窄，每次只能容一个水桶取水，水桶总数为3个。每次入、取缸水仅为1桶，且不可同时进行。试给出有关老和尚从缸取水和小和尚打水、入水的算法描述。

9：有3个进程P1、P2、P3，P1负责生产螺杆，并放入工作台A中；P2负责生产螺母，并放入工作台B中；P3负责从工作台A中取出1个螺杆、从工作台B中取出2个螺母，并组装后输出。工作台A、B的容量分别为10和20，不允许多个进程同时使用同一工作台，且每次操作只能放入或取出一个元件（螺杆或螺母）。请基于信号量机制实现P1、P2、P3间的互斥和同步活动，要求用伪代码描述。

10： 3位参赛者(performer)参与脱口秀表演，现场有5个评委(judge)，每次只能一个人表演，每当表演结束，各个评委开始评判，将分数输入系统，每次仅允许一个评委输入，仅当5个评委都完成打分，下一次表演才能开始。请用信号量机制实现以上角色的互斥和同步活动，并给出相关信号量的定义和主程序main()，要求用伪代码描述。

Solution 注意先确定进程的数目, 生产者为 3, 消费者为 5, 则

semaphore empty[5]={1,1,1,1,1}; // 评委打过分(即消费者是否消费过生产者产生的资源)
semaphore full[5]={0,0,0,0,0}; // 表演者表演过(生产者生产的资源)
semaphore mutex=1; // 评委互斥打分

void performer(int i){
    while(true){
        for(int j=0;j<5;j++){
            P(empty[j]);
        }
        perform();
        for(int j=0;j<5;j++){
            P(full[j]);
        }
    }
}

void judge(int i){
    P(full[i]);
    P(mutex);
    打分;
    V(mutex);
    V(empty[i]);
}

void main(){
    parbegin{performer(0),...,performer(2),judge(0),...,judge(4)};
}

生产者/消费者问题例三例四.

读者和写者问题示例3.

11: 元宵节爸爸组织兄妹两人猜灯谜，爸爸每出一个谜面，兄妹俩猜答,每人只答一次，出于礼貌，兄妹俩不能同时回答，当两人都回答以后，爸爸公布灯谜答案，然后始出下一个谜面，重复.上述猜谜活动。请用信号量方式，实现爸爸和子女之间的互斥同步流程，注意给出相关信号量定义和注释，要求用伪代码描述。

guess_son=0 // 儿子能否猜谜
guess_daughter=0 // 女儿能否猜谜
ans_son=1 // 儿子是否回答过
ans_daughter=1 // 女儿是否回答过
s=1 // 互斥回答

dad(){
    while(true){
        P(ans_son);
        P(ans_daughter);
        if(游戏刚开始);
            // 出谜面
        else{
            //公布答案
            // 出谜面
        }
        V(guess_son);
        V(guess_daughter);
    }
}

son(){
    while(true){
        P(guess_son);
        P(s);
        // 猜谜
        V(s);
        V(ans_son);
    }
}

daughter(){
    while(true){
        P(guess_daughter);
        P(s);
        // 猜谜
        V(s);
        V(ans_daughter);
    }
}

生产者和消费者的动作也要详细写捏, 否则会扣分的捏.

作业5

1.分别举例说明什么是可重用资源和可消耗资源？

2.请论述产生死锁的充分必要条件。

3.如何防止占有且等待条件？

4.如何防止防止循环等待条件？

5.死锁避免、检测和预防之间的区别是什么？

6.什么是安全序列、安全状态？

7.根据伪代码，画出资源分配算法流程图，包括其中银行家算法流程。

8.请简要论述死锁检测流程。

假定系统中有5个进程P1、P2、P3、P4和P5；3类资源A、B和C,其资源数量分别为17、5和20。T0时刻的资源分配情况如下：

	最大资源需求	已分配资源数量

P1 P2 P3 P4 P5	5 5 4 4 4	5 3 0 0 2	9 6 11 5 4	2 4 4 2 3	1 0 0 0 1	2 2 5 4 4

系统采用银行家算法实施死锁避免策略，试根据问题7的流程分析如下问题：

① T0时刻是否为安全状态？若是，请给出安全序列。

② T0时刻若进程P2请求资源（0，3，4），是否能实施资源分配？为什么？

③ T0时刻若进程P4请求资源（2，0，1），是否能实施资源分配？为什么？

作业6

简述存储管理的基本功能？

2.什么是重定位，为什么需要重定位？

3.逻辑地址和物理地址之间有什么区别？

4.页和页框之间有什么区别？

5.页和段之间有什么区别？

6.系统使用简单分页，内存大小为字节，页大小为字节，逻辑地址空间包含页。

a. 逻辑地址有多少位？

b. 一个页框有多少字节

c. 物理地址中的多少位是页框号？

d. 页表中有多少个表项？
1. 在使用下列内存管理方案的情况下，分别写出逻辑地址0001010010111010转换为物理地址的过程。
1. 分页系统，页面大小为 256 字节，页表中页框号是页号的四分之一
2. 分段系统，分段的大小为1K，段表中该段的基址 = 22 + 4096 * 段号
在一个简单的分段系统中，包括如下段表：

段号	起始地址	长度（字节）
0	660	248
1	1752	422
2	222	198
3	996	604

对如下的每一个逻辑地址，确定其对应的物理地址或者说明段错误是否发生：

a.0, 198 b.2, 156 c.1, 530 d.3, 444 e. 0, 222

作业7

1.简单分页和虚拟分页有何区别？

2.什么是抖动？怎么解决

3.为何在使用虚拟内存时，局部性原理至关重要？

4.在虚拟分页存储管理中，页表项有哪些典型元素？

5.驻留集和工作集有何区别？

6.假设页面大小为4KB，页表项大小为4B。要映射64位的地址空间，如果顶级页表能在一页中存储，需要多少级页表？

7.完成PPT中3.6.2二级页表示例3，请采用十进制方式，并与

参考答案比较，自判（此题不提交）。

7.考虑如下的页面访问序列：7,0,1,2,0,3,0,4,2,3,0,3,2

假设系统为该进程分配了3个页框，并采用局部置换策略。请分别采用先进先出算法、最近最少使用算法、时钟算法和最佳置换算法，画出类似图8.14的图形，并计算每种算法的缺页中断次数和缺页率？只计算页框初始填满后发生的缺页中断，访问总次数从初始页框填满后开始计算。

8.某计算机采用32位段页式虚拟存储器，按字节编址，每个段最多可以有4K页，页大小为8KB，物理主存容量为1024MB。请回答以下问题：（1）给出逻辑地址结构并说明理由。（2）计算逻辑地址0X4EB9FDE3的段号，段内页号及页内偏移值（最后计算结果须用十六进制表示）。

9: 32位系统页式管理，多级页表。页面1KB，页表项4字节。某进程的页表内容如下页图所示，最外层页表基址为106496。计算逻辑地址201852553的物理地址。

作业8

有哪几种基本I/O控制方式，分别适用于哪些场合？
试说明DMA的工作流程。
引入缓冲的主要原因是什么？
逻辑I/O和设备I/O有什么区别？如何实现设备的独立性？
何谓虚拟设备？
试说明SPOOLing系统的组成。
面向块和面向流的设备有何区别，举一些例子
磁盘读或写时有哪些延迟因素？
一个磁盘的参数如下：每个扇区512字节，每道96个扇区，每面110道，共8个面可用，计算存储300000条120字节长的逻辑记录需要多少磁盘空间（扇区、磁道和盘面），忽略文件头记录和磁道索引，并假设记录不能跨越两个扇区。
考虑第9题中的磁盘系统，假设磁盘转速是360rpm，处理器处理一次I/O中断的时间是2.5µs。

（1）处理器采用中断驱动I/O方式从磁盘读一个扇区，每个字节中断一次，则处理器用于处理I/O中断的时间占数据传输时间的百分比是多少？

（2）如果采用DMA方式从磁盘读数据，假设每个扇区中断一次，则处理器用于处理I/O中断的时间占数据传输时间的百分比是多少？

Project

设计和实现一个基本的用户级线程库, 完成包括线程的创建, 撤销, 调度等基本功能, 对外提供接口, 同时设计测试用例, 对相关功能加以验证.

《计算机操作系统》2018-2019学年第二学期期中考试试卷（Ａ卷）

一、简答题

PCB主要存储内容是什么？为什么说PCB是操作系统感知进程存在的唯一依据？（20分）
什么是死锁，死锁的预防与死锁的避免有什么区别。（20分）

二、分析题

请用信号量机制给出一种哲学家就餐问题的正确解决方案，并说明该方案为什么可以避免死锁。（30分）
现有3个并发进程R、M、P，它们共享一个可循环使用的、大小为N的缓冲区B。进程R负责从输入设备读信息，每读一个字符后，把它存入缓冲区B的一个单元中；进程M负责处理读入的字符，若发现读入的字符中有空格符，则把它改成“.”；进程负责把处理后的字符取出兵打印输出。请用P、V操作实现其同步过程。（30分）

实验

Next at t=5245917341
(0) [0x0000000000faa06c] 000f:000000000000006c (unk. ctxt): jz .+2 (0x10000070)       ; 7402
<bochs:2> 05245917341e[WGUI ] Sim client size(0, 0) != stretched size(720, 400)!
sreg
es:0x0017, dh=0x10c0f300, dl=0x00003fff, valid=1
        Data segment, base=0x10000000, limit=0x03ffffff, Read/Write, Accessed
cs:0x000f, dh=0x10c0fb00, dl=0x00000002, valid=1
        Code segment, base=0x10000000, limit=0x00002fff, Execute/Read, Accessed, 32-bit
ss:0x0017, dh=0x10c0f300, dl=0x00003fff, valid=1
        Data segment, base=0x10000000, limit=0x03ffffff, Read/Write, Accessed
ds:0x0017, dh=0x10c0f300, dl=0x00003fff, valid=3
        Data segment, base=0x10000000, limit=0x03ffffff, Read/Write, Accessed
fs:0x0017, dh=0x10c0f300, dl=0x00003fff, valid=1
        Data segment, base=0x10000000, limit=0x03ffffff, Read/Write, Accessed
gs:0x0017, dh=0x10c0f300, dl=0x00003fff, valid=1
        Data segment, base=0x10000000, limit=0x03ffffff, Read/Write, Accessed
ldtr:0x0068, dh=0x000082fd, dl=0x92d00068, valid=1
tr:0x0060, dh=0x00008bfd, dl=0x92e80068, valid=1
gdtr:base=0x0000000000005cb8, limit=0x7ff
idtr:base=0x00000000000054b8, limit=0x7ff
<bochs:3> xp /2w 0x0000000000005cb8+13*8
[bochs]:
0x0000000000005d20 <bogus+       0>:    0x92d00068      0x000082fd
<bochs:4> xp /2w 0x00fd92d0+2*8
[bochs]:
0x0000000000fd92e0 <bogus+       0>:    0x00003fff      0x10c0f300
<bochs:5> creg
CR0=0x8000001b: PG cd nw ac wp ne ET TS em MP PE
CR2=page fault laddr=0x0000000010002fa8
CR3=0x0000000000000000
    PCD=page-level cache disable=0
    PWT=page-level write-through=0
CR4=0x00000000: smep osxsave pcid fsgsbase smx vmx osxmmexcpt osfxsr pce pge mce pae pse de tsd pvi vme
EFER=0x00000000: ffxsr nxe lma lme sce
<bochs:6> xp /2w 0x40*4
[bochs]:
0x0000000000000100 <bogus+       0>:    0x00fa7027      0x00000000
<bochs:7> xp /2w 0x00fa7000+3*4
[bochs]:
0x0000000000fa700c <bogus+       0>:    0x00fa6067      0x00000000
<bochs:8> xp /w 0xfa6000+4
[bochs]:
0x0000000000fa6004 <bogus+       0>:    0x80911010
<bochs:9> setpmem 0x00fa6004 4 0
<bochs:10> xp /w 0xfa6000+4
[bochs]:
0x0000000000fa6004 <bogus+       0>:    0x00000000
<bochs:11> 05245917341e[WGUI ] Sim client size(0, 0) != stretched size(720, 400)!
c
06024800000e[WGUI ] Sim client size(0, 0) != stretched size(720, 400)!

2023-07-25

以上