专业课程-操作系统

内容纲要

操作系统期末重点

第一章-操作系统引论

操作系统的目标和作用

OS目标

方便性、有效性、可拓展性、开放性

OS作用

  1. 通过管理计算机资源,提高资源利用率和系统吞吐量
  2. 作为用户和计算机硬件之间的接口
  3. 实现了对计算机资源的抽象

操作系统的发展历程

  1. 无配置操作系统

  2. 单道批处理系统
    优缺点

    • 解决了人机矛盾和CPU与I/O设备速度不匹配的问题
    • 系统资源得不到充分利用
  3. 多道批处理系统

    目标:为了进一步提高资源利用率和系统吞吐量
    优缺点

    • 资源利用率高
    • 系统吞吐量大
    • 平均周转周期长
    • 无交互能力
  4. 分时系统

    一台主机连接了多个配有显示器和键盘的终端,并由此组成系统

  5. 实时系统

    系统及时响应外部事件的请求,在规定时间内完成对该事件的处理,并控制所有实时任务协调一致地运行

微型操作系统的发展

  1. 单用户单任务操作系统

    • CP/M
    • MS-DOS
  2. 单用户多任务操作系统

    • Windows1.0、2.0
    • Windows3.0、3.1
    • Windows95、98
    • WindowsXP(集成Internet浏览器)
    • WIndowsNT等面向网络的操作系统
  3. 多用户多任务操作系统

    • UNIXOS
    • SolarisOS
    • LinuxOS

多道批处理、分时、实时系统的特征

  1. 多道批处理系统具有高的资源利用率和系统吞吐量
  2. 分时系统能获得及时响应
  3. 实时系统具有实时特征

操作系统的基本特性

  1. 并发

    并行:指两个或多个事件在同一时刻发生
    并发:指两个或多个事件在同一时间间隔内发生
    进程:指在系统中能独立运行并作为资源分配的基本单位

  2. 共享

    指系统中的资源可供内存中多个并发执行的进程共同使用

    • 互斥共享方式
    • 同时访问方式
  3. 虚拟:代码执行的局部性

  4. 异步:指进程是以人们不可预知的速度向前推进的

如何理解进程执行时走走停停的现象

  1. 由于进程的异步性,并发的进程相互穿插执行
  2. 时间片的存在,进程交替进行
  3. 计算机资源的共享导致中断

操作系统的主要功能

  1. 处理机管理:创建和撤销进程
  2. 存储器管理:内存分配及回收、内存保护、地址映射和内存扩充等功能
  3. 设备管理:缓冲管理、设备分配、设备处理和虚拟设备等功能
  4. 文件管理:管理文件存储空间、目录管理、文件读写管理以及文件的共享和保护等功能
  5. 操作系统与用户之间的接口:用户接口和程序接口

用户在程序设计中若要得到系统功能必须经过系统调用

第二章-进程的描述与控制

前趋图和程序执行

  1. 前趋图(前趋结点、后继节点)

  2. 顺序执行

    • 顺序性:严格按照规定顺序执行
    • 封闭性:执行时独占全机
    • 可再现性:方便调试
  3. 并发执行

    • 间断性:进程间的相互制约
    • 失去封闭性:进程间共享资源
    • 不可再现性:程序的执行顺序难以预知

进程的描述

用PCB(Process Control Block进程控制块)数据结构描述进程的基本情况和活动过程,进而控制和管理进程实体

*进程实体+ = 程序段 + 相关的数据段 + PCB

进程的定义与特征

  1. 进程定义

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

    进程是进程实体的运行过程,是系统进行资源分配和调度的一个独立单位

  2. 进程特征

    • 动态性:进程的实质是进程实体的执行过程
    • 并发性:指多个进程实体同存于内存中
    • 独立性:单个进程能独立运行
    • 异步性:进程按异步方式运行
    • 结构特征:一个进程实体由程序、数据和PCB组成
  3. 程序和进程的区别

  • 程序是一组有序指令的集合,存放于某种介质,其本身不具有活动的含义,因而是静态的
  • 进程是进程实体的执行过程,它因创建而产生,因调度而执行,由撤销而消亡,有一定的生命周期,因而是动态的

进程的基本状态及转换

  1. 进程的三种基本状态:

    • 就绪状态:进程已经获得了除CPU外其他资源,只要调度即可投入执行
    • 执行状态:单CPU任一时刻处于执行状态的进程只能有一个
    • 阻塞状态:进程受阻,进入暂停状态
  2. 进程的创建和终止:

    • 创建状态:
      • 申请PCB(进程控制块)
      • 分配资源
      • 初始化PCB
      • 插入存储队列
    • 终止状态:
      • 等待操作系统进行善后处理
      • 将PCB清零并将空间返还给系统

状态转换图
五个状态及其转换图

挂起操作和进程状态的转换

挂起状态:把一个进程从内存转到外存
激活状态:把一个进程从外存转到内存

  1. 挂起/激活操作的引入
    • 终端用户需要
    • 父进程请求
    • 负荷调节的需要
    • 操作系统的需要
  2. 挂起/激活操作引起的状态转换
    • 活动就绪->静止就绪
    • 活动阻塞->静止阻塞
    • 静止就绪->活动就绪
    • 静止阻塞->活动阻塞

七个状态及其转换图

进程管理中的数据结构

  1. 操作系统中用于管理控制的数据结构
    • 内存表
    • 设备表
    • 文件表
    • 进程表
  2. 进程控制块PCB的作用
    • 作为独立运行基本单位的标志
    • 能实现间断性运行方式
    • 提供进程管理所需的信息
    • 提供进程调度所需信息
    • 实现与其他进程的同步和通信
  3. 进程控制块的信息
    • 进程标识符
      • 外部标识符
      • 内部标识符
    • 处理机状态
    • 进程调度信息
  4. 进程控制信息
  5. 进程控制块的组织方式
    • 线性方式
    • 链接方式
    • 索引方式

进程控制

操作系统内核

OS内核:常驻内存的、紧靠硬件层次的软件模块

  1. 支撑功能:给其它众多模块提供基本功能,支撑其工作
    • 中断处理
    • 时钟管理
    • 原语操作:若干条指令组成,用于完成一定功能的过程
  2. 资源管理功能
    • 进程管理
    • 存储器管理
    • 设备管理

进程的创建

  1. 进程的层次结构:进程创建了子进程,获得句柄用来控制子进程
  2. 进程图
  3. 引起进程创建的事件
    • 用户登录
    • 作业调度
    • 提供服务(如用户请求打印文件,创建打印进程)
    • 应用请求
  4. 进程的创建过程
    • 申请空白PCB
    • 为进程分配资源
    • 初始化PCB
    • 插入存储队列

进程的终止

  1. 引起进程终止的事件
    • 正常结束
    • 异常结束
    • 外界干预
  2. 进程的终止过程
    • 根据标识符找到PCB并读取其状态
    • 若在执行,则终止执行并置调度状态为true
    • 若还有子孙进程,则同时终止子孙进程
    • 归还进程拥有的资源
    • 将终止进程的PCB从相应队列移出

进程的阻塞和唤醒

  1. 引起进程阻塞和唤醒的事件
    • 向系统请求共享资源失败
    • 等待某种操作完成
    • 新数据尚未到达
    • 等待新任务到达
  2. 进程的阻塞过程:进程通过block原语将自己阻塞
    • 若在执行,停止执行
    • 将PCB插入阻塞队列
  3. 进程的唤醒过程:有关进程调用wakeup原语唤醒进程
    • 移除阻塞队列
    • 将PCB状态改为就绪,插入就绪队列

阻塞和就绪应当成对出现,防止进程永久阻塞

进程的挂起与激活

  1. 引起进程挂起和激活的事件
    • 终端用户需要
    • 父进程请求
    • 负荷调节的需要
    • 操作系统的需要
  2. 进程的挂起过程:把一个进程从内存转到外存
    • 活动就绪->静止就绪
    • 活动阻塞->静止阻塞
  3. 进程的激活过程:把一个进程从外存转到内存
    • 静止就绪->活动就绪
    • 静止阻塞->活动阻塞

进程同步

主要任务

使多个相关进程在执行次序上进行协调,使并发执行的诸进进程能按照一定规则共享系统资源并能很好地互相合作,从而使程序的执行具有*可再现性

进程同步的基本概念

  1. 两种形式的制约关系

    • 间接相互制约关系
    • 直接相互制约关系
  2. 临界资源:如打印机、硬盘等,进程之间应采用互斥的方式进行资源共享(互斥共享

  3. 临界区:访问临界资源的那段代码

    为避免进程访问正在被访问的临界资源,应该在进入临界区前,添加判断临界资源状态和设置临界资源被访问状态的代码,即进入区,则恢复状态的代码为退出区,剩余的代码即为*剩余区

    访问临界资源的循环进程用代码表述如下:

    While(true){
        进入区->判断并设置资源状态
        临界区->访问临界资源
        退出区->恢复资源状态
        剩余区->其他代码部分
    }
  4. 同步机制应遵守的规则

    • 空闲避让
    • 忙则等待
    • 有限等待:避免死”等“
    • 让权等待:进程不能进入临界区时,立即释放处理机,避免死“忙”

硬件同步机制

  1. 关中断
  2. 利用Test-And-Set指令(原语)实现互斥
  3. 利用Swap指令实现实现进程互斥

信号量机制

  1. 整数型信号量

    wait(S){
        while(S <= 0);
        S—-;
    }
    signal(S){
        S++;
    }
  2. 记录型信号量

    解决了应用整数型信号量,可能存在的忙等情况

    wait(semaphore *S){
        S->value—-;//进程请求一个单位的资源,该系统资源数目-1
        if(S->value < 0){   //如果系统资源不足/分配完毕,进程阻塞,让权等待
            block(S->list); //插入信号链表S->list中
            //S->value的绝对值即为被阻塞进程的数量
        }
    }
    signal(semaphore *S){
        S->value++;     //进程释放一个单位的资源,该系统资源数目+1
        if(S->value <= 0){  //如果仍有因等待该资源被阻塞的进程,唤醒一个进程
            wakeup(S->list);
        }
    }
    //因此,如果设定初值S->value = 1,表示只允许一个进程访问临界资源,此时信号量转换为互斥信号量
  3. AND型信号量

    解决了应用记录型信号量,如果多个并发进程共享多个临界资源可能出现的死锁现象

  4. 信号量集

    能分配n个资源,解决了应用AND型信号量只能每次只能分配一个资源的限制

信号量的应用

  1. 利用信号量实现进程互斥

    Semaphore mutex = 1;
    P(){
        While(true){
            wait(mutex);
            临界区;
            signal(mutex);
            剩余区;
        }
    }
  2. 利用信号量实现前趋关系

管程(Monitors)机制

  1. 管程定义
  2. 条件变量

经典进程的同步问题

生产者消费者问题

  1. 记录型信号量

    int in = 0,out = 0;
    item buffer[n];
    //互斥信号量初始值 = 1,资源可用数信号量empty = n,已用资源数信号量full = 0
    semaphore mutex = 1,empty = n,full = 0;
    void prodecer(){
        do{
            producer an item nextp;
            wait(empty);
            wait(mutex);
            buffer[in] = nextp;
            in = (in+1) % n;
            signal(mutex);
            signal(full);
        }while(true);
    }
    void consumer(){
        do{
            wait(full);
            wait(mutex);
            nextc = buffer[out];
            out = (out+1) % n;
            signal(mutex);
            signal(empty);
            consumer the item in nextc;
        }while(true);
    }
    void main(){
        begin
            prodecer();
            consumer();
        end
    }
  2. AND型信号量

    int in = 0,out = 0;
    item buffer[n];
    //互斥信号量初始值 = 1,资源可用数信号量empty = n,已用资源数信号量full = 0
    semaphore mutex = 1,empty = n,full = 0;
    void prodecer(){
        do{
            producer an item nextp;
            Swait(empty,mutex);
            buffer[in] = nextp;
            in = (in+1) % n;
            Ssignal(mutex,full);
        }while(true);
    }
    void consumer(){
        do{
            Swait(full,mutex);
            nextc = buffer[out];
            out = (out+1) % n;
            Ssignal(mutex,empty);
            consumer the item in nextc;
        }while(true);
    }
    void main(){
        begin
            prodecer();
            consumer();
        end
    }

哲学家进餐问题

  1. 记录型信号量

    semaphore fork[5] = {1,1,1,1,1};
    void philosophers_i(){ //i=1,2,3,4,5
        while(true){
            think();
            hungry();
            P(fork[i]);
            p(fork[(i+1)%5]);
            eat();
            V(fork[i]);
            V(fork[(i+1)%5]);
        }
    }
  2. AND型信号量

    semaphore chopstick[5] = {1,1,1,1,1};
    do{
        think();
        Swait(chopstick[(i+1)%5],chopstick[i]);
        eat();
        Signal(chopstick[(i+1)%5],chopstick[i]);
    }while(true);

读者-写者问题

保证一个Writer进程必须与其它进程互斥地访问共享对象的同步问题

semaphore rmutex = 1,wmutex = 1;
int readcount = 0;
void reader(){
    do{
        wait(rmutex);
        if(readcount == 0) wait(wmutex);
        readcount++;
        signal(rmutex);

        perform read operation;

        wait(rmutex);
        readcount--;
        if(readcount == 0) signal(wmutex);
        signal(rmutex);
    }while(true);
}
void writer(){
    do{
        wait(wmutex);
        perform write operation;
        signal(wmutex);
    }while(true);
}
void main(){
    begin
        Reader();
        Writer();
    end
}

线程的基本概念

  1. 引入线程概念后
    • 资源分配的基本单位是进程,CPU分配的基本单位是线程
    • 拥有资源的基本单位是进程,调度的基本单位是线程
  2. 线程和进程的引入原因
    • 进程:使多个程序能并发执行,以提高资源利用率
    • 线程:减少程序在并发时付出的时空开销,使OS具有更好的并发性

进程的描述与控制相关习题

  1. 进程由阻塞到就绪状态,程序也会跟着移来移去吗?为什么?

    不会,PCB会进行移动,而进程对应的程序并不会移动。
    因为PCB中记录着程序的断点信息,程序能够根据断点信息继续执行而不必移动。

  2. 画出状态变迁图

  3. 简述对进程同步和互斥的理解

    进程互斥是一种制约关系,指若干进程因相互争夺独占型资源而产生的竞争制约关系。
    进程同步是一种合作关系,指为完成共同任务的并发进程基于某个条件来协调其活动,因为需要在某些位置上排定执行的先后次序而等待、传递信号或消息所产生的协作制约关系。
    进程的互斥关系是一种特殊的进程同步关系,即逐次使用互斥共享资源,也是对进程使用资源的次序的一种协调。

  4. 如何理解多个程序执行执行时CPU走走停停的现象?

    单个CPU任何时刻只能执行一个程序,当多个程序交织在一起时:
    (1) 由于进程的异步性,并发的进程相互穿插执行
    (2) 时间片的存在,进程交替进行
    (3) 计算机资源的共享导致中断
    因而会产生走走停停的现象

  5. 什么原因导致操作系统具有异步特征

    操作系统的异步性体现在三个方面:
    一是进程的异步性,进程以人们不可预知的速度向前推进。
    二是程序的不可再现性,即程序执行的结果有时是不确定的
    三是程序执行时间的不可预知性,即每个程序何时执行,执行顺序以及完成时间是不确定的。

  6. A、B从信箱取信问题

    类似生产者-消费者问题

    //对A、B信箱互斥访问的信号量
    semaphore mutexA = 1,mutexB = 1;
    //表示A、B信箱内邮件数量的信号量
    semaphore fullA = x,fullB = y;
    //表示A、B信箱内可放置邮件数量的信号量
    semaphore emptyA = M-x,emptyB = N-y;
    void A(){
        while(true){
            //拿取信,类似消费者过程,数量-1,可放置数量+1
            P(fullA);       //A信箱邮件数量-1
            P(mutexA);      //正在互斥访问A信箱
            getletter();    //从A信箱拿取信
            V(metexA);      //解除A信箱互斥访问状态
            V(emptyA);      //A信箱可放置邮件数量+1
    
            answer();       //回答并设置问题
    
            //放置信,类似生产者过程,可放置数量-1,数量+1
            P(emptyB);      //B信箱可放置信的数量-1
            P(metuxB);      //正在互斥访问B信箱
            putletter();    //放置信到B信箱
            V(mutexB);      //解除B信箱互斥访问状态
            V(fullB);       //B信箱信的数量+1
        }
    }
    void B(){
        while(true){
            //拿取信,类似消费者过程,数量-1,可放置数量+1
            P(fullB);       //B信箱邮件数量-1
            P(mutexB);      //正在互斥访问A信箱
            getletter();    //从B信箱拿取信
            V(metexB);      //解除B信箱互斥访问状态
            V(emptyB);      //B信箱可放置邮件数量+1
    
            answer();       //回答并设置问题
    
            //放置信,类似生产者过程,可放置数量-1,数量+1
            P(emptyA);      //A信箱可放置信的数量-1
            P(metuxA);      //正在互斥访问A信箱
            putletter();    //放置信到A信箱
            V(mutexA);      //解除A信箱互斥访问状态
            V(fullA);       //A信箱信的数量+1
        }
    }
    void main(){
        begin
            A();
            B();
        end
    }
  7. 银行家算法

    • 该状态是否安全
    • 若进程P2提出请求Request(0,2,1),系统能否将资源分配给它

第三章-处理机调度与死锁

对于大型系统运行时的性能问题(系统吞吐量、资源利用率、作业周转时间和响应的及时性),很大程度上取决于处理机调度性能的好坏

处理机调度的层次和调度算法的目的

处理机调度的层次

  1. 高级调度
    • 又称长程调度或作业调度,调度对象是作业
    • 将外存作业调入内存
    • 主要用于多道批处理系统
  2. 低级调度
    • 又称短程调度或进程调度,调度对象为进程或内核级线程
    • 决定就绪队列哪个进程应获得处理机,并由分派程序将处理机分配给被选中进程
    • 在多道批、分时、实时系统中都配备这级调度
  3. 中级调度
    • 又称中程调度或内存调度
    • 目的是提高内存利用率和系统吞吐量
    • 把暂时不能运行的进程调至外存等待,此时进程状态称为就绪驻外存(挂起)状态
    • 当进程可运行时,再调入内存,修改状态为就绪状态

根据运行频率,有长程、中程、短程调度

处理机调度算法的目标

  1. 资源利用率(提高资源利用率,保持CPU忙碌状态)
    $CPU利用率 = \frac{CPU有效工作时间}{CPU有效工作时间+CPU空闲等待时间}$
  2. 公平性(同类型进程提供相同服务)
  3. 平衡性(保持系统资源使用的平衡性)
  4. 策略强制执行(如安全策略的强制执行)

作业与作业调度

  1. 典型的作业:编译作业步、链接装配作业步、运行作业步
  2. 作业控制块JCB
  3. 作业运行的三个阶段和状态
    • 后备状态
    • 运行状态
    • 完成状态

作业调度的主要任务

  1. 接纳多少作业
  2. 接纳哪些作业

作业调度算法

作业周转时间 = 作业完成时间-作业到达时间

  1. 先来先服务算法(FCFS)
    • 只考虑作业等待时间,忽视运行时间
    • FCFS常和其它算法结合使用
    • 如按优先级算法设置队列,每个队列的调度都基于FCFS算法
  2. 短作业优先算法(SJF)
    • 只考虑作业运行时间,忽视等待时间
    • 不能得到最小平均周转时间
    • 缺点
      • 必须预知作业的运行时间
      • 对长作业非常不利
      • 人机无法实现交互
      • 未考虑作业的紧迫程度
  3. 优先级调度算法(PSA)
    • 可作为作业调度和进程调度算法
    • 基于外部赋予的优先级
  4. 高响应比优先调度算法(HRRN)
    • 引入动态优先级,兼顾短作业和长作业
    • $优先权=\frac{等待时间+要求服务时间}{要求服务时间} = \frac{响应时间}{要求服务时间}$
    • SJF:作业等待时间相同,则要求服务时间(运行时间)越短,优先级越高
    • FCFS:作业要求服务时间相同,则等待时间越长,优先级越高
    • 对于长作业,当等待时间足够长时,也会增加优先级
    • 每次调度都要进行响应比的计算,增大开销

进程调度

进程调度的任务、机制和方式

  1. 调度任务
    • 保存处理机的现场信息
    • 按某种算法选取进程
    • 把处理器分配给进程
  2. 调度机制
    • 排队器
    • 分派器
    • 上下文切换器
  3. 调度方式
    • 非抢占方式
    • 抢占方式
      • 优先权原则
      • 短进程优先原则
      • 时间片原则

轮转调度(RR)算法

基于时间片的轮转调度算法

  1. 基本原理:为就绪队列所有进程分配时间片,轮转调度
  2. 切换时机
    • 没用完时间片就完成,将其清出就绪队列,调度新进程
    • 用完时间片任务未完成,移至就绪队列队尾
  3. 时间片大小的确定:影响平均周转时间

优先级调度算法

给进程分配一个优先级

  1. 优先级调度算法类型
    • 非抢占式优先级调度算法
    • 抢占式优先级进程调度算法
  2. 优先级的类型
    • 静态优先级(整数0~255):创建进程时确定,此后不变
    • 动态优先级:可以动态变化

多队列调度算法

  1. 单队列调度:低级算法是固定的、单一的
  2. 多队列调度
    • 满足系统中不同用户对进程调度策略的不同要求
    • 对每个队列执行不同的调度算法

多级反馈队列调度算法

不必知道进程执行时间,还可以较好满足各种类型进程的需要,因而它是目前公认的一种较好的进程调度算法

  1. 调度机制

    • 设置多个就绪队列
    • 每个队列都采用FCFS
    • 按队列优先级调度队列的诸进程
  2. 调度算法的性能(根据用户/队列分配时间片大小)

    • 终端用户
    • 短批处理用户
    • 长批处理用户
  3. 调度算法的优点

    • 所有类型的作业都能短时间内启动,用户能获得响应
    • 终端用户和短批处理用户能在较短时间内完成
    • 系统吞吐量高
    • 长批处理作业能最终得到处理

基于公平原则的调度算法

  1. 保证调度算法:提供明确性能保证
  2. 公平分享算法:分享给每个进程相同的处理机时间

实时调度

实现实时调度的基本条件

  1. 提供必要信息
  2. 系统处理能力强
  3. 采用抢占式调度机制
  4. 具有快速切换机制
    • 快速响应中断
    • 快速的任务分派能力

实时调度算法的分类

  1. 按实时任务性质分类

    • 硬实时调度算法
    • 软实时调度算法
  2. 按调度方式分类

    • 非抢占式调度算法
    • 抢占式调度算法
      • 基于时钟中断
      • 立即抢占的优先级调度算法
  3. 最早截止时间优先算法(EDF)

    • Earliest Deadline First
    • 等待时间 = 结束时间 - 到达(开始)时间 - 执行时间
    • 主要用于非抢占调度方式
  4. 最低松弛度优先算法(LLF)

    • Least Laxity First
    • 根据任务的紧急(松弛)程度确认优先级

      任务的截止时间为200ms,执行时间为50ms,则在150ms前必须完成,松弛程度 = 150ms

    • $松弛度 = 截止时间-当前时间-执行时间$
    • 主要用于抢占调度方式
  5. 优先级倒置(priority inversion problem)

    • 优先级倒置的形成:高优先级进程被低优先级进程堵塞或延迟
    • 优先级倒置的解决方法:动态优先级继承

死锁概述

资源问题

  1. 可重用性资源:如设备、文件,需要进行互斥访问(申请、使用、释放)
  2. 可消耗性资源:如进程间通信的消息
  3. 可抢占性资源:不会引发死锁
  4. 不可抢占性资源:如打印机,不能强行收回,只能由进程自行释放

计算机系统中的死锁

  1. 竞争不可抢占性资源引起死锁
  2. 竞争可消耗性资源引起的死锁
  3. 进程推进顺序不当引起的死锁

死锁的定义、必要条件和处理方法

  1. 定义

    如果一组进程中的每一个进程都在等待仅有该进程组中的其它进程才能引发的事件
    那么该组进程是死锁的(Deadlock)

  2. 必要条件

    • 互斥条件
    • 请求和保持条件
    • 不可抢占条件
    • 循环等待条件
  3. 处理方法

    • 预防死锁
    • 避免死锁
    • 检测死锁
    • 解除死锁

预防死锁

由于互斥条件是非共享设备所必须的,所以主要是后三个条件

  1. 破坏“请求和保持”条件
    • 第一种协议:所有进程在开始运行之前,必须一次性申请其在整个运行过程中所需的所有资源

      优点:简单、易行、安全
      缺点(1):资源被严重浪费,严重恶化了资源利用率
      缺点(2):是进程经常会发生饥饿现象(等待某资源的进程迟迟不能开始运行)

    • 第二种协议:进程只获得运行初期所需资源便开始运行,运行过程中逐步释放已有资源或请求其它资源
  2. 破坏“不可抢占”条件
    • 强制进程释放不可抢占的资源,如未打印完成的打印进程

      缺点:会付出很大代价,延长进程周转时间、增大系统开销、降低系统吞吐量

  3. 破坏“循环等待”条件
    • 对系统资源进行线性排序后,规定每个进程必须按序号递增的顺序请求资源,避免了资源申请产生环路

      如磁带机序号为3,打印机序号为5,想要同时申请磁带机和打印机,需先申请磁带机、再申请打印机

避免死锁

系统安全状态

当系统处于安全状态时,可能发生死锁
当系统处于不安全状态时,可能发生死锁

  1. 安全状态
    允许进程动态申请资源,但在分配之前需要计算此次资源分配的安全性
  2. 安全状态之例
  3. 由安全状态向不安全状态转换

利用银行家算法避免死锁

最具代表性的避免死锁的算法是Dijkstra的银行家算法

  1. 银行家算法中的数据结构

    • 可利用资源向量Available
      • A[m]表示可利用的m种资源,Available[Ri] = K 表示第R_i种资源的数目有K个
    • 最大需求矩阵Max
      • Max[i,j] = K 表示进程i需要R_i的资源数目为K
    • 分配矩阵Allocation
      • Allocation[i,j] = K 表示进程i当前已分得R_i类资源的数目为K
    • 需求矩阵Need
      • Need[i,j] = K 表示进程i尚需分配R_i类资源的数目为K
  2. 银行家算法

    //请求向量Request_i是进程P_i的请求向量
    //Request_i[j] = K 表示进程i需要K个R_j类型的资源
    //收到进程i对R_j类型资源的请求
    Receive(Requset_i[j]);  
    //如果请求的资源数目小于该进程尚需分配的资源数目,即为合理,否则视为出错
    if(Request_i[j] <= Need[i,j]){
        //如果请求数量在资源可利用数量的合理范围内,允许分配,否则等待有足够资源
        if(Request_i[j] <= Available[j]){
            //更新可利用资源数量
            Available[j] += Request_i[j];
            //更新已分配资源数量
            Allocation[i,j] += Request_i[j];
            //更新尚需分配资源的数量
            Need[i,j] -= Request_i[j];
        }
    }
    //执行安全性算法
    Execute Secure();
  3. 安全性算法

    Available Work[m]; //表示系统可提供给进程运行所需的各类资源数量
    for(int i = 0; i < m; ++i) Work[i] = Available[i];  //初始化Work数量
    Bool Finish = false;    //初始化为false
    //遍历n个进程,从进程集合中找到一个能满足下述条件的进程
    for(int i = 0;i < n; ++i){
        //找到未执行过的、能满足安全性条件的进程
        if(Finish = false && Need[i,j] <= Work[j]){
            //更新程序运行可提供的R_j资源数目
            Work[j] += Allocation[i,j];
            //标识系统有足够资源分配给进程i
            Finish[i] = true;
        }
    }

死锁的检测与解除

死锁的检测

  1. 资源分配图
  2. 死锁定理
  3. 死锁监测中的数据结构

死锁的解除

  1. 抢占资源
  2. 终止进程
    • 终止所有死锁进程
    • 逐个终止进程
  3. 付出代价最小的死锁解除算法

第四章-存储器管理

层次结构

多层结构的存储器系统

  1. 存储器的多层结构
    • CPU寄存器
    • 主存
    • 辅存
  2. 可执行存储器

多层结构的存储器系统

主存储器与寄存器

  1. 主存储器
  2. 寄存器

高速缓冲与磁盘缓存

  1. 高速缓存
  2. 磁盘缓存

程序的装入和链接

编译、链接、装入

  1. 程序的装入
    • 绝对装入方式
    • 可重定位装入方式
    • 动态运行时装入方式(装入内存的所有地址仍是逻辑地址)
  2. 程序的链接
    • 静态链接
    • 装入时动态链接
    • 运行时动态链接

连续分配存储管理方式

  1. 单一连续分配

    单道程序环境下,存储器管理方式分为系统区和用户区。系统区提供给OS使用,用户区由一道程序独占。

  2. 固定分区分配

    多道程序环境下,多个用户分区放置多道程序
    为了便于内存分配,通常将分区按照大小进行排队,为之建立一张分区使用表

  3. 动态分区分配(可变分区分配)
    • 数据结构
      • 空闲分区表
      • 空闲分区链
    • 算法
    • 分区分配操作
      • 分配内存
      • 回收内存
  4. 基于顺序搜索的动态分区分配算法
    • 首次适应(FF-First Fit)算法
      • 每次从链首开始查找
      • 优点:倾向于优先利用低址部分的空闲分区,从而保留了高址部分的大空闲分区
      • 缺点:低址部分不断被划分,产生碎片,增大了查找可用空闲分区时的开销
    • 循环首次适应(NF-Next Fit)算法
      • 每次从上一次查找结束的位置开始查找
      • 优点:使空闲分区分布得更均匀,减少了查找开销
      • 缺点:缺乏大的空闲分区
    • 最佳适应(BF-Best Fit)算法
      • 将空闲分区按照容量从小到大排序,查找的结果总是最佳的
      • 缺点:每次切割的剩余部分总是最小的,这样就会留下许多难以利用的碎片
    • 最坏适应(WF-Worest Fir)算法
      • 将空闲空间按照容量从大到小排序,每次从大的空闲区分割一部分
      • 优点
        • 能避免使剩下的空闲区不至于太小,产生碎片可能性最小,对中、小作业有利
        • 每次查找只需要判断第一个分区能否满足要求即可,查找效率高
      • 缺点:缺乏大的空闲分区
  5. 基于索引搜索的动态分区分配算法
    • 快速适应(QF-Quick Fit)算法
    • 伙伴系统(Buddy System)
      • 优点:时间性能好,且对空闲分区进行合并,减少了小的空闲分区,提高了空闲分区的可使用率
      • 缺点:空间性能较差
    • 哈希算法

      大、中型系统适用索引搜索的动态分区分配方法。当前OS普遍采用Hash算法,多处理机OS中,伙伴系统仍被广泛采用

  6. 动态可重定位分区分配
    • 紧凑
      • 多个分散的小分区(连续分配产生的碎片)拼接成一个大分区
      • 分区的物理地址会变化,相应的逻辑地址需要重定位
    • 动态重定位
      • 地址变化是在程序执行期间,随着对每条指令或数据的访问自动进行的
      • 重定位寄存器:使地址的转换不影响到指令的执行速度
      • 程序执行时真正的访问地址=相对值+重定位寄存器中地址
    • 动态重定位分区分配算法
      • 与动态分区算法相近,仅增加了紧凑功能

对换

离散分配存储管理方式

允许将一个进程直接分散地装入到许多不相邻的分区中,无需紧凑且能充分利用空间

分页存储管理方式

将用户程序的的地址空间分成若干个固定大小的区域,称为“页”或“页面”

分页存储管理的基本方法
  1. 页面和物理块
    • 页面
      • 分页存储管理进程将进程的逻辑地址空间分成若干个页,并为各页加以编号
      • 在为进程分配内存时,以块为单位,将若干页填入可以不邻接的块中
      • 页内碎片:进程的最后一页经常填不满一块,从而形成不可利用的碎片
    • 页面大小
      • 过小:
        • 优点:减少内存碎片占用空间,提高内存利用率
        • 缺点:每个进程占有较多页面,导致进程的页表过长,占用大量内存,降低页面换进换出的效率
      • 过大:
        • 优点:减少页表长度,提高页面换进换出的效率
        • 缺点:使页内碎片占用空间增大 ,降低内存利用率
      • 适宜:
        • 页面大小应是2的幂
        • 通常为1KB-8KB
  2. 地址结构
    • 分页地址 = 页号+位移量(页内地址)
    • 如:页号24位,表示地址空间最多有1M页;
    • 如:位移量12位,表示每页的大小最多有1KB

      已知逻辑地址A,页面大小为L,求页号和页内地址
      $页号 p = INT(\frac{A}{L})$
      $偏移量(页内地址) d = [A] mod L$

  3. 页表
    • 页面映像表:存储每个页面所对应的物理块
    • 作用:实现从页号到物理块号的地址映射
地址变换机构

基本任务:实现从逻辑地址到物理地址的转换

逻辑地址 = 页号 + 页内地址
物理地址 = 物理块号 + 块内地址

页面和物理块的大小相同,页内地址 = 块内地址,页号和物理块号的映射由页表实现
因此地址变换任务是借助于页表来完成的

  1. 基本的地址变换机构
    • 为节省空间,页表大多驻留在内存
    • 页表寄存器只存放页表的始址和页表长度
    • 在单处理机环境下,多个进程却只需要一个页表寄存器
    • 两次访问内存
      • 第一次访问:查找指定页的物理块号
      • 第二次访问:对所得地址进行读写操作
  2. 具有快表的地址变换机构
    • 联想寄存器(快表):存放当前访问的页表项
    • CPU访问数据所耗费的时间明显减少
访问内存的有效时间

内存的有效访问时间:发出访问请求到取出数据所花费的总时间

两级和多级页表

解决页表占用空间大的问题

  • 离散分配页表所需的内存空间
  • 只将部分页表项调入内存,其它驻留在磁盘,需要时调入

多级页表的优点

  • 加快地址变换速度
  • 减少页表所占连续地址空间
  1. 二级页表

    • 32位逻辑地址空间的分页系统,页面大小为4KB,页表项数可达1MB
    • 离散分配页表形成二级页表,称为外层页表,
  2. 多级页表

    • 64位逻辑空间的分页系统,2^64太大,一般用2^45位进行寻址,采用三级及多级页表
反置页表

分段存储管理方式

将用户程序的的地址空间分成若干个大小不同的段

分段存储管理方式的引入
  1. 方便编程
  2. 信息共享
  3. 信息保护
  4. 动态增长
  5. 动态链接
分段系统的基本原理
  1. 分段:地址结构 = 段号+段内地址
  2. 段表
  3. 地址变换机构
  4. 分页和分段的主要区别
    • 页是信息的物理单位,段是信息的逻辑单位
    • 页的大小固定且由系统决定,段的长度不固定且决定于所写程序
    • 分页的用户程序地址空间是一维线性地址,分段是二维非线性地址
信息共享
  1. 分页系统对程序和数据的共享
  2. 分段系统中程序和数据的共享
段页式存储管理方式
  1. 基本原理:分段和分页相结合
  2. 地址变换过程
    • 地址结构 = 段号+页号+页内地址
    • 三次访问内存
      • 访问内存中的段表,获取页表始址
      • 访问内存中的页表,获取物理块号
      • 访问指定地址,从中读取/写入数据

存储器管理相关习题

  1. 有四个作业,每个作业执行时间为 2h,求其平均周转时间

    单次平均周转时间为$\frac{2+4+6+8}{4} = 5 h$

  2. 有三个作业

    作业 到达时间 CPU时间
    1 8.8 1.5
    2 9.0 0.4
    3 9.5 1.0

    (1)当作业全部到达后再进行调度,按照高响应比优先算法,求调度顺序:2、1、3

    $作业1优先权 = \frac{9.5-8.8+1.5}{1.5} = 1.47$
    $作业2优先权 = \frac{9.5-9.0+0.4}{0.4} = 2.25$
    $作业2优先权 = \frac{0+1.0}{1.0} = 1$
    依据3个作业的优先权,调度顺序为作业2、作业1、作业3

    (2)在(1)的条件下,求各作业的周转时间:1.5、1.7、2.2

    先执行作业2,那么$作业2的周转时间 = (8.8+1.5)-8.8 = 1.5$
    再执行作业1,那么$作业1的周转时间 = (1.5+0.4-(9.0-8.8)) = 1.7$
    最后执行作业3,那么$作业3的周转时间 = (1.7+1.0-(9.5-9.0) = 2.2)$

  3. 银行家算法
    (1)状态是否安全
    (2)若进程P2提出请求request(1,2,2,2)后,系统是否将资源分配给它?
    银行家算法例题

  4. 下列存储管理方式能使存储碎片尽可能少,而且使内存利用率尽可能高的是A

    • A. 分页
    • B. 可变(动态分区分配)
    • C. 固定
    • D. 段页

      尽可能少指的是碎片无法避免
      /可变动态分区分配能够没有碎片,可避免碎片,不选

  5. 动态分区分配有几种方法,最容易产生内存碎片的方法为最佳

第五章-虚拟存储器

虚拟存储器概述

由于作业需要全部装入内存后才能运行,为了解决作业太大及作业太多的问题,可以从物理上扩充内存或者逻辑上扩充内存 (虚拟存储器)

常规存储管理方式的特征和局部性原理

  1. 常规存储管理方式的特征
    • 一次性
    • 驻留性
  2. 局部性原理
    • 概念:在一较短时间内,程序的执行仅局限于某个部分,相应的地,它所访问的存储空间也限制在某个区域
    • 时间局限性:某指令和数据被访问/执行,不久后可能再次访问/执行(典型情况是程序中存在大量循环操作)
    • 空间局限性:某存储单元被访问,不久后其附近存储单元也将被访问(典型情况是程序的顺序执行)
  3. 虚拟存储器的基本工作情况

虚拟存储器的定义与特征

  1. 虚拟存储器的定义

    指具有请求调入功能和置换功能,能从逻辑上对容量加以扩充的存储器系统

    • 容量由内存和外存之和决定
    • 运行速度接近于内存速度
    • 每位的成本接近于外存
  2. 虚拟存储器的特征
    • 多次性
    • 对换性
    • 虚拟性
  3. 虚拟存储器的实现方法
    • 分页请求系统
    • 请求分段系统

请求分页存储管理方式

请求分页中的硬件支持

  1. 请求页表机制
    • 页表项结构 = 页号+物理块号+状态位P+访问字段A+修改位M+外存地址
      • 状态位P:指示是否调入内存,供程序访问参考
      • 访问字段A:标识该页在一段时间内被访问的次数或多久未被访问
      • 修改位M:标识该页在调入内存后是否被修改过
    • 缺页中断机构
    • 地址变换机构
      1. 快表中未找到该页的页表项,到内存中查找页表
      2. 查看页表项的状态位
      3. 若该页已调入内存,则将页表项写入快表,快表已满则换页
      4. 若该页未调入内存,产生缺页中断,请求OS从外存调该页入内存
  2. 请求分页的内存分配
    • 最小物理块数的确定
      • 能保证进程政策运行所需的最小物理块数
    • 内存分配策略
      • 固定分配局部置换
      • 可变分配全局置换
      • 可变分配局部置换
    • 物理块分配算法
  3. 页面调入策略
    • 何时调入
    • 从何处调入
    • 页面调入过程
  4. 缺页率

页面置换算法

抖动现象

  • 刚被换出的页很快又要调入
  • 不适当的页面只换算法导致

好的页面置换算法应该有较低的更换频率

  1. 最佳置换算法和先进先出置换算法
    • 最佳(Optimal)置换算法
      • 理论上的算法,用于评价其他算法
    • 先进先出(FIFO)置换算法
      • 没什么好说的,先进先出
  2. 最近最久未使用和最少使用置换算法
    • 最近最久未使用(Least Recently Used)置换算法
      • 记录一个页面自上次被访问以来经过的时间t
    • 最少使用(Least Frequently Used)置换算法
  3. Clock置换算法

    • 简单的Clock算法

      void Clock(){
          //查询指针p
          while(p->next){
              p = p->next;
              //判断访问位P
              if(p->P == 1){  //近期已访问
                  p->P = 0;   //置零,再停留一段时间
              }else{
                  ChangePage();//将该页换出
              }
          }
      }
    • 改进型Clock算法

页面缓冲(Page Buffering Algorithm)算法

  1. 影响页面换进换出效率的若干因素
    • 页面置换算法
    • 写回磁盘的频率
    • 读入内存的频率
  2. 页面缓冲算法PBA
    • 显著降低页面换入、换出频率,使磁盘I/O次数大幅减少
    • 页面换入、换出的开销减少,因而能够使用简单置换策略

虚拟存储器相关习题

  1. 试述缺页中断和页面淘汰算法之间的关系

    页面淘汰一定是由缺页中断引起
    缺页中断则不一定引起页面淘汰

  2. 页面走向为

    1 2 3 4 2 1 1 5 2 3 4
    采用LRU置换算法 1 2 3 4 2 1 1 5 2 3 4
    1 1 1 4 4 4 4 5 5 5 4
    2 2 2 2 2 2 2 2 2 2
    3 3 3 1 1 1 1 3 3
    y y y y n y n y n y y

    缺页次数 = 8
    缺页率= 8/11 = 73%

  3. 设某计算机的逻辑地址空间和物理地址空间均为64KB,按字节编址。若某进程最多需要6页数据存储空间,页的大小为1KB,操作系统采用固定分配局部置换策略为此进程分配4个页框。 页号 页框号 装入时刻 访问位
    0 7 150 1
    1 5 230 1
    2 2 200 1
    3 15 100 1

    当给进程执行到时刻260时,要访问逻辑地址为17ACH的数据,请回答下列问题
    (1) 该逻辑地址对应的页号是多少?
    (2) 若采用先进先出(FIFO)置换算法,该逻辑地址对应的物理地址是多少?要求给出计算过程。
    (3) 若采用时钟(Clock)置换算法,该逻辑地址对应的物理地址是多少?要求给出计算过程。(设搜索下一页的指针沿着顺时针方向移动,且当前指向2号页框,示意图如下)

    (1)
    由页面大小为 1KB = 1024B
    页内偏移量位数 = log2(1024) = 10 位
    逻辑地址大小位64KB = 641024B
    逻辑地址位数 = log2(64
    1024) = 16位
    那么页号位数 = 16-10 = 6位
    逻辑地址17ACH化成二进制为 0001 0111 1010 1100
    则页号 = 000101B = 5
    (2)
    由于采用FIFO算法,该页需置换的页面为7号页框的0号页
    则对应物理地址的页号为 0001 11B
    由(1)得,对应的页偏移地址 = 11 1010 1100B
    则该逻辑地址17ACH对应的物理地址为0001 1111 1010 1100B即1FACH
    (3)
    由于四个页面访问位都为1,第一轮查找都不会被换出,在第二次查找到2号页框时,访问位为0,换出2号页
    对应物理地址的页号为 0000 10B
    对应的页偏移地址 = 11 1010 1100B
    则该逻辑地址17ACH对应的物理地址为0000 1011 1010 1100B即0BACH


发表评论