操作系统复习

第一章

操作系统的基本特性

  • 并发

  • 共享

  • 虚拟

  • 异步

操作系统的主要功能

  • 处理机管理功能
  • 存储器管理功能
  • 设备管理功能
  • 文件管理功能
  • 操作系统和用户的接口：联机命令接口和程序接口

第二章

进程的定义

  • 进程是程序的一次执行
  • 进程是一个程序及其数据在处理机上进行顺序执行所发生的我活动
  • 进程是具有独立功能的程序在一个数据集合上运行的过程，它是资源分配和调度的独立单位

程序与进程的联系与区别

联系：

  • 程序是进程产生的前提
  • 程序的每次执行产生不同的进程
  • 进程是程序功能的体现
  • 通过多次执行，程序可对应多个进程，通过调用关系，进程可包括多个程序

区别：

  • 进程是动态的，程序是静态的，程序是有序代码的集合，进程是程序的一次执行
  • 进程是暂时的，程序是永久的，进程是一个状态的变化过程，程序可长久保存
  • 进程和程序的组成不同：进程由程序段+数据段+PCB，程序是有序代码的集合

进程的特征

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

同步机制遵循的功能

  • 空闲让进
  • 忙则等待
  • 有限等待
  • 让权等待：不能进入临界区要释放资源

生产者消费者

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
int in=0,out=0;
item buffer[n];
semaphore mutex=1,empty=n,full=0
void producer(){
    do{
        produce an item nextp;
        //消耗一个缓冲区
        wait(empty);
        wait(mutex);
        //互斥访问，产生一个商品
        signal(mutex);
        signal(full);//增加一个商品
    }while(true)
}


void consumer(){
    do{
        wait(full);
        wait(mutex);
        signal(mutex);
        signal(empty);//消耗一个空闲缓冲区
    }
}

哲学家就餐

1
2
3
4
5
6
7
8
9
10
11
12
13
semaphore chopstick[5]={1,1,1,1,1}; //五个筷子有五个互斥信号量
//左边筷子 i
//右边筷子 （i+1）%5

//第i位哲学家
do{
    wait(chopstick[i]);  //左筷子
    wait(chopstick[(i+1)%5]);
    //eat
    signal(chopstick[i]);
    signal(chopstick[(i+1)%5]);
    //think
}

读者-写者问题

P(r)

P(w)

V(r)

P(r)

V(w)

V(r)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
semaphare rmutex=1,wmutex=1;
int readcount=0;
void reader(){
    wait(rmutex);
    if(readcount==0) wait(wmutex); //tips,第一个读进程读文件组织写进程
    readcount++;
    signal(rmutex);
    //reading
    
    wait(rmutex);
    readcount--;
    if(readcount==0) singal(wmutex); //没有读进程才可以写
    signal(rmutex)
}


void writer(){
    wait(wmutex);
    //writing
    signal(wmutex);
}

进程通信的类型

  • 共享存储器系统
  • 管道通信系统
  • 消息传递系统
  • 客户机-服务器系统

线程和进程的区别：

  1. 调度。传统操作系统，进程作为资源调度和分派的基本单位，但在引入了线程的操作系统中，线程作为资源调度和分派的基本单位。线程的切换不会引起进程的切换
  2. 并发。进程之间可以并发，一个进程中的不同线程也可以并发执行，提高系统的资源利用率和吞吐量
  3. 独立性。在同一进程中的不同线程之间的独立性要比不同进程之间的独立性低得多
  4. 拥有资源。线程几乎不拥有资源，只有少量必要的资源，线程是系统中拥有资源的基本单位。
  5. 系统开销。进程开销大，线程开销少
  6. 多处理机系统。可以将进程中的不同线程分配到处理机

管程

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

  • 为了解决临界区分散所带来的管理和控制问题，管程将分散在各进程中的临界区集中起来并加以控制管理。

  • 管程一次只允许一个进程进入管程内。

第三章

处理机调度的层次

  • 高级调度（作业调度）
  • 中级调度（内存调度）：对换
  • 低级调度（进程调度）

调度算法（计算平均周转时间）

  • 先来先服务

  • 短作业优先

  • 高响应比优先：（等待时间+要求服务时间）/要求服务时间

  • 时间片轮转调度算法

  • 多级队列调度

  • 多级反馈队列算法：多个就绪队列，按优先级和时间片

死锁必要条件

  • 互斥条件
  • 请求和保持条件
  • 不可抢占条件
  • 循环等待条件

死锁处理策略

  • 预防死锁

    • 破坏请求和保持条件：
      • 第一种协议：一次性申请全部资源
      • 第二种协议：先运行，逐步请求和释放资源
    • 破坏不可抢占条件：释放自己的资源
    • 破坏循环等待条件：资源分配法

  • 避免死锁

    • 银行家算法

  • 死锁检测：资源分配图

  • 死锁解除：抢占资源、终止进程

银行家算法

数据结构：

  1. Available：可用资源量
  2. Max：进程i所需最大资源数量
  3. Allocation：进程已分配的资源数
  4. Need：Max-Allocation
  5. Request：请求

安全性算法

work=Available

work+=Allocation

finish =false

finish=true

第四章

存储器层次结构

寄存器、高速缓存、主存储器、磁盘缓存、固定磁盘、可移动存储介质

程序的装入

  • 绝对装入
  • 可重定位装入
  • 动态运行时装入

连续分配存储管理方式

  • 单一连续分配
  • 固定分区分配方式
  • 动态分区分配方式

动态分区分配算法

  • 最佳适应算法
  • 最坏适应算法
  • 首次适应算法
  • 循环首次适应算法

第五章

虚拟存储器定义

具有请求调入和置换功能，可以在逻辑上扩大存储空间的存储器系统

特征

  • 多次性
  • 对换性
  • 异步性

页面置换算法

  • FIFO
  • LRU
  • OPT

缺页率

  • 页面大小，越小越高
  • 分配的物理块数
  • 页面置换算法
  • 程序固有特性

对换

把内存中暂时不能运行的进程或者暂时不用的程序和数据换出到外存上，以便腾出足够的内存空间，再把已具备运行条件的进程或者进程所需的程序或者数据换入。对换是改善内存利用率的有效措施，它可以直接提高处理机的录用率和吞吐量

抖动

频繁发生缺页。系统内同时运行的进程太多，分配给每个进程的物理块数太少，不能满足正常运行要求，致使进程频繁出现缺页。

第六章

I/O软件层次结构

  • 用户层软件
  • 设备独立性软件
  • 设备驱动程序
  • 中断处理程序
  • 硬件

I/O系统接口

  • 流设备接口
  • 块设备接口
  • 网络通信接口

中断处理过程

  • 测定有无未响应的中断信号
  • 保护当前被中断程序的CPU环境
  • 转入当前中断服务程序
  • 中断处理
  • 恢复CPU环境并退出中断

引入缓冲机制作用

缓和，减少，解决，提高

  • 缓和CPU和I/O设备速度不匹配的矛盾
  • 减少对CPU的中断频率 放宽对CPU响应时间的限制
  • 解决数据粒度不匹配的问题
  • 提高CPU与I/O设备之间的并行性

I/O控制方法

  • 使用轮询的可编程的I/O控制
  • 使用中断的可编程I/O控制方式
  • 直接存储器访问方式 DMA方式
  • I/O通道控制方式

磁盘调度算法

  • 先来先服务
  • 最短寻道时间优先
  • SCAN 扫描算法
  • CSCAN 循环扫描算法

Spooling系统

组成：

  • 输入井和输出井
  • 输入进程和输出进程
  • 输入缓冲区和输出缓冲区
  • 井管理程序
    (井管理程序！)

特点：

  • 提高I/O速度
  • 将独占设备改造成共享设备
  • 实现了虚拟设备功能
    (实现了虚拟设备功能)*

流程：

  • 输入进程将信息从输入设备送到输入井
  • 输出进程将信息从输出井送到输出设备
  • 主机仅和输入井和输出井交换信息，提高了信息处理效率

第八章

外存组织方式

  • 连续组织方式
  • 连接组织方式
  • 索引组织方式

文件存储空间管理

  • 空闲表法
  • 空闲链表法
  • 位示图法
  • 成组链接法

提高磁盘I/O速度

  • 磁盘高速缓存
  • 其他方法
    • 提前读
    • 延迟写
    • 优化物理块分布
    • 虚拟盘
  • 廉价磁盘冗余阵列RAID
    • 可靠性高，采用容错技术
    • 磁盘I/O速度高，采用并行交叉存取方式
    • 性价比高

提高磁盘可靠性的技术

  • 第一容错技术
  • 第二容错技术
  • 基于集群技术的容错功能

试卷

  • 程序顺序执行特点：顺序性，封闭性，可再现性

  • 程序并发执行特点：中断性，失去封闭性，不可再现性

  • 虚拟技术：通过硬件和软件的功能扩充，把原来独占的设备改造成为若干用户可以共享的设备，这种技术成为虚拟技术

  • 用户与操作系统的接口主要是：_联机命令接口___和__程序接口

  • 引入__中断机制__是为了实现CPU与外部设备的并行工作

  • 异步：无法预测进程向前推进的速度

  • 文件存储空间的基本分配单位是磁盘块

  • SCAN有效避免了饥饿现象

  • CSCAN算法规定磁头单向移动减少延迟时间

  • 寻道时间和旋转延迟占据磁盘访问时间的绝大部分，与所读写的数据多少无关

  • 地址转换工作是由___硬件__ 完成的

  • UNIX文件系统对磁盘空间的管理采用__空闲块成组链接法__

  • UNIX文件系统采用__混合索引分配方式__

  • 提高内存利用率主要通过__虚拟存储器__实现

  • 系统调用是通过__软中断__进入操作系统

DMA方式的特点

  • 减少CPU对I/O的干预，进一步提高CPU与I/O设备的并行性
  • 数据传输的基本单位是块
  • 所传送的数据是从设备直接送入内存的
  • 仅在传送一个或多个数据块的开始和结束时才需要CPU的干预。

请求分页存储管理的硬件支持

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

请求分段存储管理的硬件支持

  • 段表机制
  • 缺页中断机构
  • 地址变换机构

页式存储管理的逻辑地址格式

页号页内地址
页号的位数：2的位数次方表示有多少个页
页内地址位数：每页大小，2的多少次方表示位数

页表项中对应的每项的位数是物理块号
物理块号＝物理空间大小/每页大小(＝物理块大小)

盘块数

盘块数＝磁盘大小(盘块大小)/盘块号大小
文件大小＝盘块数×盘块大小

书

引起进程阻塞和唤醒的事件

  • 向系统请求共享资源失败。此时进程因无法运行而阻塞
  • 等待某操作的完成。需要等待某一操作执行后才能运行，就要先阻塞
  • 新数据尚未到达。阻塞
  • 等待新任务到达。阻塞

某些题目

  • 操作系统提供给编程人员的接口是(系统调用)
  • 操作系统内核的资源管理不包括作业管理
  • 分页存储管理 存在内部碎片，无外部碎片，提高内存利用率
  • 一般存储器特点：一次性，驻留性
  • 虚拟存储器的运行速度接近内存，成本接近外存
  • 磁盘访问时间
    • 寻道时间：磁盘移动时间和磁臂启动时间之和
    • 旋转延迟时间：指定扇区移动到磁头下面所经历的时间
    • 数据传输时间： 取决于数据的多少和磁盘旋转速度