跳至主要內容

操作系统

大学操作系统大学操作系统大约 29 分钟约 8737 字全民制作人ikun

操作系统

考试

https://jason-xy.cn/2021/06/osreview/open in new window

13b88b5d06a48a8066a47df875029e98
13b88b5d06a48a8066a47df875029e98

辨析题

  1. OS目标：(1)方便性，方便用户使用计算机系统；(2)有效性，提高系统资源的利用率和系统的吞吐量；(3)可扩充性，随着硬件的提升可适应的能力；(3)开放性；
  2. 操作系统的五大功能:
    • 处理器管理:处理器是完成运算和控制的设备。在多道程序运行时，每个程序都需要一个处理器，而一般计算机中只有一个处理器。操作系统的一个功能就是安排好处理器的使用权，也就是说，在每个时刻处理器分配给哪个程序使用是操作系统决定的。
    • 存储管理:计算机的内存中有成千上万个存储单元，都存放着程序和数据。何处存放哪个程序，何处存放哪个数据．都是由操作系统来统一安排与管理的。这是操作系统的存储功能。
    • 设备管理:计算机系统中配有各种各样的外部设备。操作系统的设备管理功能采用统一管理模式，自动处理内存和设备间的数据传递，从而减轻用户为这些设备设计输入输出程序的负担。
    • 作业管理：作业是指独立的、要求计算机完成的一个任务。操作系统的作业管理功能包括两点尸是在多道程序运行IC现货商时，使得备用户合理地共享计算机系统资源22是提供给操作人员一套控制命令用来控制程序的运行o
    • 文件管理：计算机系统中的程序或数据都要存放在相应存储介质上。为了便于管理，操作系统招相关的信息集中在一起，称为文件。操作系统的文件管理功能就是负责这些文件的存储、检索、更新、保护和共享
  3. 并发和并行：并行是指两个或者多个事件在同一时刻发生。并发是指两个或者多个事件在同一时间间隔发生。
    • 并发：并发（Concurrent），在操作系统中，是指一个时间段中有几个程序都处于已启动运行到运行完毕之间，且这几个程序都是在同一个处理机上运行。
    • 并行：并行（Parallel），当系统有一个以上CPU时，当一个CPU执行一个进程时，另一个CPU可以执行另一个进程，两个进程互不抢占CPU资源，可以同时进行，这种方式我们称之为并行(Parallel)。
  4. 分时OS特点：
    • 同时性：计算机系统能被多个用户同时使用；
    • 独立性：用户和用户之间都是独立操作系统的，在同时操作时并不会发生冲突，破坏，混淆等现象；
    • 及时性：系统能以最快的速度将结果显示给用户；
    • 交互作用性：用户能和电脑进行人机对话。
  5. 时间片轮转调度：
    • 如果时间片太大，使得每个进程都可以在一个时间片内就完成，则时间片轮转调度算法退化为先来先服务调度算法，并且会增大进程响应时间。因此时间片不能太大。
    • 如果时间片太小，会导致进程切换过于频繁，系统会花大量的时间来处理进程切换，从而导致实际用于进程执行的时间比例减少。增加系统开销
  6. 实时OS适用场合：工业控制系统，信息查询系统，多媒体系统，嵌入式系统
    • 网络OS：集中式：金融行业。客户机／服务器模式：Novell的NetWare和Microsoft的Windows NT。对等式：简单网络连接，分布式计算。
    • 分时OS：适合办公自动化、教学及事务处理等要求人机会话的场合
  7. OS内核功能，分析（重点）：1. 支撑功能：是指内核可以提供给OS的其它众多模块所需要一些基本功能，以便支撑这些模块工作。下面是三种最基本的支撑功能：（1）中断处理此功能是内核最基本的功能，是整个操作系统活动的基础。OS中许多重要的活动无不依赖于中断，比如系统调用、IO操作、进程调度、设备驱动等，（2）时钟管理比如在时间片轮转调度中，每当时间片用完时，便由时钟管理产生一个中断信号，促使调度程序重新进行调度。还有实时系统的截止时间控制等。（3）原语操作原语（Primitive）是由若干条指令组成的，用于完成一定功能的一个过程。它与一般过程的区别在于：它们是 原子操作。所谓原子操作就是，一个操作中的动作要么全做，要么全不做。也就是，它是一个不可分割的基本单位。因此，原语在执行过程中不允许被中断。原语的作用： 在内核中有许多原语，比如用于对链表进行操作的原语、用于实现进程同步的原语等。2. 管理功能（1）进程管理：进程的调度与分派、创建与撤销等；实现进程同步、进程通信的原语等（2）存储器管理：如将逻辑地址转换为物理地址、内存的分配与回收等（3）设备管理：各类设备的驱动程序等
  1. 支撑功能
    1. 中断处理
    2. 时钟管理
    3. 原语操作
  2. 管理功能
    1. 进程管理
    2. 存储器管理
    3. 设备管理

  1. 调度的计算：

    • CPU利用率=工作时间/总时间=CPU有效工作时间/(CPU有效工作时间+CPU空闲时间)

    • 周转时间=进程完成时间-进程提交时间

    • 带权周转时间=进程周转时间 / 进程运行时间

    • 平均周转时间=作业周转总时间/作业个数；

    • 平均带权周转时间=带权周转总时间/作业个数；

  2. FIFO　优缺点：有利于长作业进程，而不利于短作业进程这是因为若一个长作业先到达系统，就会使许多短作业等待很长的时间，从而引起许多短作业用户的不满。有利于CPU繁忙型作业，不利于I/O，忙的作业。

  3. SJF　优缺点：降低作业的平均等待时间，提高系统吞吐量。对长作业不利；未考虑作业的紧迫程度；对进程估计执行时间难以预测。

  4. 处理机调度影响平均周转时间的因素：调度算法。进程的执行时间。优先级调度。上下文切换时间。阻塞和唤醒时间。多处理器系统。负载平衡

  5. 死锁的定义：死锁（Deadlock），是指多个进程在运行过程中因争夺资源而造成的一种僵局（Deadly- Embrace），当进程处于这种僵持状态时，若无外力作用，它们都将无法再向前推进。如果一组进程中的每一个进程都在等待仅由该组进程中的其他进程才能引发的事件，那么该组进程是死锁的。

  6. 死锁的必要条件（必考）：

    （1）互斥条件：指进程对所分配到的资源进行排它性使用 。

    （2）请求和保持条件：指进程已经保持了至少一个资源，但又提出了新的资源请求 。

    （3）不剥夺条件：指进程已获得的资源，在未使用完之前，不能被剥夺，只能在使用完时由自己释放。

    （4）循环等待条件：指在发生死锁时，必然存在一个进程——资源的环形链

  7. 破坏死锁：
    预防死锁：
    破坏“请求和保持”条件
    摒弃“不剥夺”条件
    摒弃“环路等待”条件

    避免：
    检测：
    解除：

  8. 银行家算法（必考）：需要画出表

  9. 给你n个进程，有m资源，怎么样不会发生死锁：当n(x−1)+1<=mn(x-1)+1<=m,即n<=m−1x−1n<=\frac{m-1}{x-1}时，不会发生死锁

  10. 进程与线程的关系：

    • 进程是对运行时程序的封装，是系统进行资源调度和分配的的基本单位，实现了操作系统的并发；线程是进程的子任务，是CPU调度和分派的基本单位，用于保证程序的实时性，实现进程内部的并发；
    • 线程是操作系统可识别的最小执行和调度单位。每个线程都独自占用一个虚拟处理器：独自的寄存器组，指令计数器和处理器状态。每个线程完成不同的任务，但是共享同一地址空间（也就是同样的动态内存，映射文件，目标代码等等），打开的文件队列和其他内核资源。

  11. 进程与线程的区别：

    • 一个线程只能属于一个进程，而一个进程可以有多个线程，但至少有一个线程。线程依赖于进程而存在。
    • 进程在执行过程中拥有独立的内存单元，而多个线程共享进程的内存。
    • 进程是资源分配的最小单位，线程是CPU调度的最小单位；
    • 进程切换的开销也远大于线程切换的开销。
    • 进程间通信IPC，线程间可以直接读写进程数据段（如全局变量）来进行通信——需要进程同步和互斥手段的辅助，以保证数据的一致性
    • 进程编程调试简单可靠性高，但是创建销毁开销大；线程正相反，开销小，切换速度快，但是编程调试相对复杂。
    • 进程间不会相互影响 ；线程一个线程挂掉将导致整个进程挂掉
    • 进程适应于多核、多机分布；线程适用于多核

  12. 线程共享：堆，全局变量，静态变量，文件等共用资源，寄存器。栈是独享。

  13. 进程控制块PCB：是进程存在的唯一标志。PCB (Process Control Block) 常驻内存。实现间断性允许方式。提供进程管理信息。实现与其他进程通信和同步。PCB中包含的信息：进程标识符，内部标识符，进程调度信息，进程控制信息。

  14. 进程三个状态转换图

  15. 进程同步（三个经典问题，作业的两个）

  16. 信号量（semaphore）是操作系统用来解决并发中的互斥和同步问题的一种方法。

    n>0：当前有可用资源，可用资源数量为n
    n=0：资源都被占用，可用资源数量为0
    n<0：资源都被占用，并且还有n个进程正在排队

  17. 局部性原理：一个良好的计算机程序 常常具有良好的局部性，也就是说，它们倾向于引用邻近于其他最近引用过的数据项的数据项，或者最近引用过的数据项本身。

    • 时间局部性是指如果程序中的某条指令一旦执行，则不久之后该指令可能再次被执行；如果某数据被访问，则不久之后该数据可能再次被访问。强调数据的重复访问。
    • 空间局部性是指一旦程序访问了某个存储单元，则不久之后。其附近的存储单元也将被访问。强调连续空间数据的访问，一般顺序访问每个元素（步长为1）时具有最好的空间局部性，步长越大，空间局部性越差。

  18. 页式管理，地址变换过程（画图），有快表和无快表

    操作系统--请求分页存储管理方式
    操作系统--请求分页存储管理方式

  19. 多少个页表项与什么有关系？
    页号=逻辑地址/页面长度
    页内偏移量=逻辑地址%页面长度

  20. 什么东西决定地址结构？地址结构： 页号+位移量

  21. 动态分区管理，首次适应，最佳适应空闲分区，过程与评价，评价指标

  22. 页式内存中多级页表的性质，收益，付出成本呢

  23. 为什么是段页式而不是页段式

  24. 虚内存的基本概念：虚拟存储器是一种计算机内存管理技术，它将计算机系统中的物理内存和磁盘空间结合起来，形成一个虚拟的内存空间，使得应用程序可以访问比物理内存更大的内存空间。虚拟存储器的实现需要操作系统的支持，它通过将内存中的数据分成若干个页面（或称为页），并将这些页面映射到磁盘上的页面文件中，从而实现了内存和磁盘之间的数据交换。

  25. 页面置换FIFO，LRU，评价指标，缺页中断

  26. IO控制方式：轮询，中断，直接存储器访问，IO通道

  27. 键盘，鼠标选择什么控制？中断

  28. 驱动程序谁负责编写？设备制造商

计算题

银行家算法（必考）：https://blog.csdn.net/wyf2017/article/details/80068608open in new window

img
img

平均周转时间：https://blog.csdn.net/qq_45432665/article/details/105141907open in new window

https://blog.csdn.net/roadtohacker/article/details/115661204open in new window

程序设计题

生产者-消费者，信号量机制

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);
        
        buffer[in]=nextp;
        in=(in+1)%n;
        
        signal(mutex);
        signal(full);
    }while(true);
}

void consumer(){
    do{
        wait(full);
        wait(metux);
        nextc=buffer[out];
        out=(out+1)%n;
        signal(metux);
        signal(empty);
        consume the item  in nextc;
    }while(true);
}

int main(){
    producer();
    consumer();
}

哲学家进餐

semaphore chopstick[5] ={1,1,1,1,1};
第i位哲学家
do{
    wait(chopstick[i]);
    wait(chopstick[(i+1)%5]);
    eat food;
    signal(chopstick[i]);
    signal(chopstick[(i+1)%5]);
}while(true);

读者-写者

semaphore rmutex=1,wmutex=1;
int readcount=0;
void reader(){
    do{
        wait(rmetux);
        if(readcount==0) wait(wmutex);
        readcount++;
        signal(rmetux);
        ...
        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);
}

过桥:

东西向汽车过独木桥，为了保证安全，只要桥上无车，则允许一方的汽车过桥，待一方的车全部过完后， 另一方的车才允许过桥。请用信号量和 P、V操作写出过独木桥问题的同步算法。

//独木桥问题1
semaphore brigde = 1；  // 互斥信号量，表示独木桥的互斥访问
int eastCount = 0;       // 东侧车辆在独木桥上的数量
semaphore eastMutex = 1; // 东侧车辆的互斥信号量，保证eastCount操作的完整执行
int westCount = 0;       // 西侧车辆在独木桥上的数量
semaphore westMutex = 1; // 西侧车辆的互斥信号量，保证westCount操作的完整执行

process 东： 
while（1）{
	P(eastMutex);
	eastCount++;
	if(eastCount == 1)  // 东侧第一个准备上桥的车去抢夺独木桥
		P(brigde);
	V(eastMutex);
	//上桥
	//下桥
	P(eastMutex);
	eastCount--;
	if(eastCount == 0)  // 东侧最后一个已经下桥的车去释放独木桥
		V(bridge);
	V(eastMutex);
}



process 西： 
while（1）{
	P(westMutex);
	westCount++;
	if(westCount == 1)  // xi侧第一个准备上桥的车去抢夺独木桥
		P(brigde);
	V(westMutex);
	//上桥
	//下桥
	P(westMutex);
	westCount--;
	if(westCount == 0)  // 西侧最后一个已经下桥的车去释放独木桥
		V(bridge);
	V(westMutex);
}

如上所述，加入说东侧的第一个人上桥，占领桥之后，还未下桥，那东侧可以有无数个车辆上桥。如果说为了安全起见，我们不允许无数辆汽车上桥，只允许K辆汽车同时在桥上。该问题的完整描述如下：
东西向汽车过独木桥，为了保证安全，只要桥上无车，则允许一方的汽车过桥，待一方的车全部过完后， 另一方的车才允许过桥。为了安全起见，最多允许K（K>=1）辆汽车在桥上。请用信号量和 P、V操作写出过独木桥问题的同步算法。



//独木桥问题2，最多有k辆汽车
semaphore brigde = 1；  // 互斥信号量，表示独木桥的互斥访问
int eastCount = 0;       // 东侧车辆在独木桥上的数量
semaphore eastMutex = 1; // 东侧车辆的互斥信号量，保证count1操作的完整执行
int westCount = 0;       // 西侧车辆在独木桥上的数量
semaphore westMutex = 1; // 西侧车辆的互斥信号量，保证count2操作的完整执行
semaphore count=k		 //桥上最多有K辆汽车
process 东： 
while（1）{
	P(eastMutex);
	eastCount++;
	if(eastCount == 1)  // 东侧第一个准备上桥的车去抢夺独木桥
		P(brigde);
	V(eastMutex);
	p（Count）
	//上桥，下桥			
	V（Count）			
	P(eastMutex);
	eastCount--;
	if(eastCount == 0)  // 东侧最后一个已经下桥的车去释放独木桥
		V(bridge);
	V(eastMutex);
}



process 西： 
while（1）{
	P(westMutex);
	westCount++;
	if(westCount == 1)  // xi侧第一个准备上桥的车去抢夺独木桥
		P(brigde);
	V(westMutex);
	p（Count）
	//上桥，下桥			
	V（Count）
	P(westMutex);
	westCount--;
	if(westCount == 0)  // 西侧最后一个已经下桥的车去释放独木桥
		V(bridge);
	V(westMutex);
}

苹果橘子

作业：用进程同步方法描述苹果橙子问题：
桌子上有一只盘子，每次只能向其中放入一个水果。爸爸专向盘子中放苹果，妈妈专向盘子中放橘子，儿子专等吃盘子中的橘子，女儿专等吃盘子中的苹果。只有盘子为空时，爸爸或妈妈就可向盘子中放一个水果；仅当盘子中有自己需要的水果时，儿子或女儿可以从盘子中取出。

semaphore empty=1,mutex=1,apple=0,orange=0; 

void father(){
     do{
           P(empty);    //等待盘子为空
           P(metux);    //等待获取对盘子的操作
            爸爸向盘中放一个苹果;
           V(mutex);   //释放对盘子的操作
           V(apple);   //通知女儿可以来盘子中取苹果
    }while(TRUE);
}

void mather(){            
     do{
           P(empty);		//等待盘子为空
           P(metux);		//等待获取对盘子的操作
            妈妈向盘中放一个桔子;
           V(mutex);		//释放对盘子的操作
           V(orange);		//通知儿子可以来盘子中取橘子
    }while(TRUE);
}

void son(){                        
     do{
           P(orange);       //判断盘子中是否有桔子
           P(metux);        //等待获取对盘子的操作
            儿子取出盘中的桔子;
           V(mutex);      //释放对盘子的操作
           V(empty);      //盘子空了，可以继续放水果了
    }while(TRUE);
}

void daugther(){ 
     do{
           P(apple);       //判断盘子中是否有苹果
           P(metux);        //等待获取对盘子的操作
            女儿取出盘中的苹果;
           V(mutex);      //释放对盘子的操作
           V(empty);      //盘子空了，可以继续放水果了
    }while(TRUE);
}

void main() {               //四个并发进程的同步执行
	cobegin
	   father(); mather(); son(); daugther();
	coend
}

学习通：

三个进程P1、P2、P3互斥使用一个包含N(N>0)个单元的缓冲区。P1每次用produce()生成一个正整数并用put()送入缓冲区某一空单元中;P2每次用getodd()从该缓冲区中取出一个奇数并用countodd()统计奇数个数;P3每次用geteven()从该缓冲区中取出一个偶数并用counteven()统计偶数个数。请用信号量机制实现这三个进程的同步与互斥活动,并说明所定义信号量的含义。要求用伪代码描述。

semaphore metux = 1; //共享信号量
semaphore odd = 0;//进程P1和P2需要的信号量
semaphore even=0;//进程P1和P3需要的信号量
semaphore empty=N;//共享缓冲区空位
p1(){ //生成正整数
    while(true){
        p(empty);
        num=porduce();
        p(metux);
        put();
        v(metux);
        if(num%2==0) v(even);
        else v(odd);
    }
}

p2(){ //获取奇数统计 奇数
    while(true){
        p(odd);
        p(metux);
        getodd();
        countodd();
        v(metux);
        v(empty);
    }
}

p3(){ //获取偶数统计偶数
    while(true){
        p(even);
        p(metux);
        geteven();
        counteven();
        v(metux);
        v(empty);
    }
}

学习通题目2：

某银行提供1个服务窗口和10个供顾客等待的座位。顾客到达银行时,若有空座位,则到取号机上领取一个号,等待叫号。取号机每次仅允许一位顾客使用。当营业员空闲时,通过叫号选取一位顾客,并为其服务。顾客和营业员的活动过程描述如下:
cobegin
{
     process 顾客i
{
         从取号机获得一个号码;
         等待叫号;
         获得服务;
}

process 营业员
{
         while (TRUE)
         {
                   叫号;
                   为顾客服务;
         }
}
} 
coend
请添加必要的信号量和P、V(或wait()、signal())操作,实现上述过程中的互斥与同步。要求写出完整的过程,说明信号量的含义并赋初值。

代码：

semaphore metux=1,service=0,seets=10;

void customers(){
    p(seets);//申请座位
    p(metux);
    //取号
    v(metux);
    v(service);//等待服务
}

void teller(){
    p(service);//提供服务 
    //服务
    v(seets);
}

void main(){
    cobegin
        customers();
        teller();
    coend
}

第一章 操作系统引论

操作系统分类：

  • 批处理系统：平均周转时间长，没有交互能力
    • 单道批处理系统，内存中始终仅存一道作业运行；减少人工操作，解决了作业的自动接续。
    • 多道批处理系统，在内存中存放多道作业运行，运行结束或出错，自动调度内存中的另一道作业运行；提高了资源利用率和吞吐能力；
  • 分时系统，人机交互、共享主机、便于用户上机，多用户终端
  • 实时系统，及时响应外部事件的请求，在规定的时间内完成对该事件的处理

OS四个特性：

  • 并发
    • 两或多个事件在同一时间间隔内发生
    • 并行是指两或多个事件在同一时刻发生
  • 共享
    • 系统中资源可供内存中多个并发执行的进程共同使用
  • 虚拟
    • 时分复用：虚拟处理机技术， 虚拟设备技术
    • 空分复用：虚拟存储
  • 异步
    • 停停走走，运行进度不可预知

第二章进程的描述与控制

进程：一个在内存中运行的应用程序。每个进程都有自己独立的一块内存空间，一个进程可以有多个线程

线程：进程中的一个执行任务（控制单元），负责当前进程中程序的执行。一个进程至少有一个线程，一个进程可以运行多个线程，多个线程可共享数据。

线程作为调度和分派的基本单位，因而线程是能独立运行的基本单位

进程的组成：

  • 程序段
  • 数据段
  • 程序控制块（PCB）

进程的三种状态：

img
img
  • 运行态→等待态：等待使用资源；如等待外设传输；等待人工干预。
  • 等待态→就绪态：资源得到满足；
  • 如外设传输结束；人工干预完成。
  • 运行态→就绪态：运行时间片到；被抢占

进程互斥：任何时刻，只允许一个进程进入临界区，以此实现进程对临界资源的互斥访问。

临界区：访问临界资源的那段代码称为临界区。

进程同步：使并发执行的主进程之间能有效地共享资源和相互合作，从而使程序的执行具有可再现性。

进程同步问题：

生产者消费者问题：

哲学家进餐问题：

读者写者问题：

进程通信：

  • 共享存储器系统
  • 消息传递系统
  • 管道（Pipe）通信

PCB信息：

  • 进程ID
  • CPU状态
  • 堆栈指针

第三章 处理机调度与死锁

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

带权周转时间=周转时间/服务时间；

平均周转时间=作业周转总时间/作业个数；

平均带权周转时间=带权周转总时间/作业个数；

进程调度算法（低级调度）：

  • 非抢占式调度方法有：先来先服务，短作业优先，非抢占式优先级调度，高响应比优先调度算法

  • 抢占式调度方法有：时间⽚轮转调度，抢占式优先级调度，最短剩余时间优先

  1. 先来先服务FCFS

    • 对待短作业（进程）不公平，如果他们排在队列后面，则其等待时间远大于其执行时间。

  2. 短作业优先SJF

  3. 高响应比优先HRRN

    • 等待时间+要求服务时间=响应时间，故优先级相当于响应比Rp。
    • 算法有利于短作业。该算法既照顾了短作业，又考虑了作业到达的先后次序，不会使长作业长期得不到服务。

  4. 时间片轮转RR

    • FCFS策略+时钟中断+时间片原则

  5. 优先级调度

    • 赋予作业动态优先级，优先级随作业等待时间延长而增加，从而使长作业的优先级在等待期间不断增加。

  6. 多级反馈队列

  7. 实时调度

内存对换（中级调度）：将内存掉入外存

作业调度算法（高级调度）：

  1. 先来先服务FCFS

  2. 短作业优先SJF

  3. 高响应比优先HRRF

负责对进程进行调度的是：处理机管理

实时系统->抢占式优先级调度

分时系统->时间片轮转

死锁的必要条件：

（1）互斥条件：指进程对所分配到的资源进行排它性使用 。

（2）请求和保持条件：指进程已经保持了至少一个资源，但又提出了新的资源请求 。

（3）不剥夺条件：指进程已获得的资源，在未使用完之前，不能被剥夺，只能在使用完时由自己释放。

（4）环路等待条件：指在发生死锁时，必然存在一个进程——资源的环形链 。

解决办法：

银行家算法：

第四章 存储器管理

程序装入方式

  1. 绝对装入方式：编译时，已知程序在内存的具体位置，则编译程序可产生实际存储地址（绝对地址）的目标代码。
  2. 可重定位装入方式(Relocation Loading Mode)
  • 重定位（地址映射）装入内存时，相对地址（数据和指令的地址）要作出相应的修改以得到正确的物理地址，这个修改的过程称为重定位。
  • 静态重定位：地址变换是在装入内存时一次完成的，且以后不能移动。

分区分配存储管理方式的保护措施是设置界地址寄存器。 每个进程都有自己独立的进程空间，如果一个进程在运行时所产生的地址在其地址空间之外，则发生地址越界。 当程序要访问某个内存单元时，由硬件检查是否允许，如果允许则执行，否则产生地址越界中断，由操作系统进行相应处理。

连续分配存储管理方式

连续分配方式，是指为一个用户程序分配一个连续的内存空间。

  • 单一连续分配，只能用于单用户、单任务的操作系统中。
  • 固定分区分配
  • 可变式分区（比固定式分区有改善），消除内部碎片，无法消除外部
  • 可重定位分区分配

可变式分区：

分配算法：

1．首次适应算法FF。

方法：每次链首开始，直到找到满足大小的空闲分区，分割该分区。

特点：有外零头，低址内存使用频繁，查找慢。高地址区保留大分区。

2．循环首次适应算法NF。

方法：从上次找到的空闲分区的下一个开始查找，直到找到满足大小的空闲分区，分割该分区。

特点：空闲分区分布均匀，提高了查找速度；缺乏大的空闲分区。

3．最佳适应算法BF

要求：分区按大小递增排序；分区释放时需插入到适当位置。

方法：从小分区开始，找大小满足要求，但空余最小的分区。

特点：单次分配看似最优，但存在许多难以利用的碎片。总体未必最优。

4．最坏适应算法WF

方法：总是选择最大的分区来分割分配。

特点: 缺乏大的空闲分区。对中小作业有利。查找效率高。

离散分配方式

两种碎片：

  • 内部碎片就是已经被分配出去（能明确指出属于哪个进程）却不能被利用的内存空间；
  • 外部碎片指的是还没有被分配出去（不属于任何进程），但由于太小了无法分配给申请内存空间的新进程的内存空闲区域。

连续分配：连续分配方式会产生内/外碎片

根据离散时的基本单位不同，可分为三种：

  • 分页存储管理，不存在外碎片
  • 分段存储管理
  • 段页式存储管理

分页存储管理方式

彻底消除了外碎片,仅存在很少的内碎片, 提高了内存利用率。

  • 逻辑地址=页号*页面大小+页内地址

  • 页号=逻辑地址/页面大小

  • 页内地址=逻辑地址%页面大小

  • 物理地址=内存块号*块长+页内地址 ；

多级页表：

  • 优点：可以离散存储页表。在某种意义上节省页表内存空间。
  • 缺点：增加寻址次数，从而延长访存时间。

每个作业的页表长度是不同的,由作业所占页的多少而定

分段存储管理方式

用分段的方法来分配和管理用户地址空间,用分页的方法来管理物理存储空间;

不存在内碎片

段页式存储管理方式

每个进程一张段表,每个段一张页表

先将用户程序分段，每段内再划分成若干页，每段有段名（段号），每段内部的页有一连续的页号。

在段页式存储管理方式中，每访问一次数据，需访问三次内存。

第一次访问内存中的段表
第二次访问内存中的页表
第三次访问相应数据。

第五章 虚拟存储器

虚拟存储器最大实际容量= min(计算机地址，内存+辅存)

局部性原理

  • 时间局限性：如果程序中的某条指令一旦执行， 则不久以后该指令可能再次执行；如果某数据被访问过， 则不久以后该数据可能再次被访问。
    产生时间局限性的典型原因，是由于在程序中存在着大量的循环操作。
  • 空间局限性：一旦程序访问了某个存储单元，在不久之后，其附近的存储单元也将被访问。
    程序在一段时间内所访问的地址，可能集中在一定的范围之内，其典型情况便是程序的顺序执行。

特征：

1．多次性：多次性是指一个作业被分成多次调入内存运行。

2．对换性： 对换性是指作业的运行过程中进行换进、换出，换进和换出能有效地提高内存利用率。

3．虚拟性：虚拟性是指能够从逻辑上扩充内存容量，使用户所看到的内存容量远大于实际内存容量。

实现方法：

  1. 请求分页存储管理方式：在分页系统的基础上，增加了请求调页功能和页面置换功能所形成的页式虚拟存储系统。允许只装入部分页面的程序（及数据），便启动运行。以后，再通过调页功能及页面置换功能，陆续地把即将要运行的页面调入内存，同时把暂不运行的页面换出到外存上。

    置换时以页面为单位。

    • 硬件支持：

    ①请求分页的页表机制上增加若干项，作为请求分页的数据结构。

    ②缺页中断机构:当要访问的页面尚未调入内存时，便产生缺页中断，请求调页。

    ③地址变换机构：虚地址到物理地址转换。

    • 软件支持：

    ①实现请求调页的软件

    ②实现页面置换的软件

  2. 请求分段系统：它允许只装入若干段的用户程序和数据，即可启动运行。以后再通过调段功能和段的置换功能，将暂不运行的段调出，同时调入即将运行的段。

    （1）请求分段的段表机制，这是在纯分段的段表机制基础上增加若干项而形成的。

    （2）缺段中断机构

    （3）地址变换机构。

  3. 段页式虚拟存储系统：许多虚拟存储管理系统是建立在段页式系统的基础上的，通过增加了请求调页、页面置换两大功能所形成的段页式虚拟存储系统。

页面置换算法：

  • 最佳置换算法OPT
  • 先进先出（FIFO）页面置换算法
  • 最近最久未使用（LRU）置换算法
  • Clock置换算法
  • 改进型Clock置换算法
  • 其它置换算法

  • 基本地址变换机构可以借助进程的页表将逻辑地址转换为物理地址。

  • 缺页中断机构：在请求分页系统中，每当所要访问的页面不在内存时，便产生一缺页中断，请求OS将所缺之页调入内存。地址转换时，检查页面的页表项中的存在位，如果为0，则产生一个缺页中断。

  • 缺页中断处理过程

（1）操作系统接收到进程产生的缺页中断信号，启动中断处理例程，保留处理机现场；

（2）操作系统通知处理机从外存读取指定的页面；

（3）处理机激活I/O设备；

（4） 检查内存有无足够的空闲空间装入该页面？若有，转（6），否则，执行（5）；

（5） 利用页面置换算法，选择内存中的某个页面，换出内存；

（6） 将指定页面从外存装入内存；

（7） 更新该进程的页表；

（8） 更新快表；

（9）计算物理地址。

第六章 输入输出系统

上次编辑于:
贡献者: yunfeidog