操作系统

计算机基础
操作系统

操作系统

一、 概述

二、 进程管理

问：进程

进程(Process)是计算机中已运行程序的实体。程序本身只是指令的集合，进程才是程序(那些指令)的真正运行。用户下达运行程序的命令后，就会产生进程。同一程序可产生多个进程(一对多关系)，以允许同时有多位用户运行同一程序，却不会相互冲突。进程需要一些资源才能完成工作，如CPU使用时间、存储器、文件以及I/O设备，且为依序逐一进行，也就是任何时间内仅能运行一项进程。

通常进程有如下5种状态，其中前3种是进程的基本状态。

  • 运行状态:进程正在处理器上运行。在单处理器环境下，每一时刻最多只有一个进程处于运行状态。
  • 就绪状态:进程已处于准备运行的状态，即进程获得了除处理器之外的一切所需资源，一旦得到处理器即可运行。
  • 阻塞状态:又称为等待状态，进程正在等待某一事件而暂停运行，如等待某资源为可用(不包括处理器)或等待输入/输出完成。即使处理器空闲，该进程也不能运行。
  • 创建状态:进程正在被创建，尚未转到就绪状态。
  • 结束状态:进程正从系统中消失。可能是进程正常结束或其他原因中断退出运行。

进程的三个基本状态之间是可以相互转换的。具体地说，当一个就绪进程获得处理机时，其状态由就绪变为执行；当一个运行进程被剥夺处理机时，如用完系统分给它的时间片、出现更高优先级别的其他进程，其状态由运行变为就绪；当一个运行进程因某事件受阻时，如所申请的资源被占用、启动I/O传输未完成，其状态由执行变为阻塞；当所等待事件发生时，如得到申请的资源、I/O传输完成，其状态由阻塞变为就绪。

问：进程的特征

  • 并发性：指多个进程实体同存于内存中，且在一段时间内同时运行。并发性是进程的重要特征，同时也成为操作系统的重要特征。
  • 动态性：进程的实质是进程实体的一次执行过程，因此，动态性是进程最基本的特征。
  • 独立性：进程实体是一个独立运行、独立分配资源和独立接受调度的基本单位。
  • 异步性：指进程按各自独立的、不可预知的速度向前推进，或者说实体按异步方式运行。

问：进程与程序的区别

  • 进程是程序及其数据在计算机上的一次运行活动，是一个动态的概念。进程的运行实体是程序、离开程序的进程没有存在的意义。从静态角度看，进程是由程序、数据和进程控制块(PCB)三部分组成的。而程序是一组有序的指令集合，是一种静态的概念。
  • 进程是程序的一次执行过程，它是动态地创建和消亡的，具有一定的生命期，是暂时存在的；而程序则是一组代码的集合，它是永久存在的，可长期保存。
  • 一个进程一可以执行一个或几个程序，一个程序也可以构成多个进程。进程可创建进程，而程序不可能形成新的程序。
  • 进程与程序的组成不同。进程的组成包括程序、数据和进程控制块。

创建新进程时会创建新的地址空间:子进程是父进程的复制品，在fork之后子进程获得父进程的数据空间、堆和栈的复制。而线程使用当前的地址空间。

例1：请问下面的程序一共输出多少个”-“()

#include<stdio.h>
#include<sys/types.h>
#include<unistd.h>
int main(void){
    int i;
    for(i=0; i<2; i++){
        fork();
        printf("-");
    }
    return 0;
}

答案：8个。
程序一开始，产生一个进程P1执行此程序，P1进入程序后，此时i=0，于是进入循环体，fork()产生一个子进程P2，接着P1执行下一条语句输出一个"-"(其实是放入缓冲区，等合适的时候再输出，我们将此"-"记为a)；

P2成为一个独立的子进程，继承P1的诸如环境变量、PC等环境，P2也执行下一条语句输出一个"-"(其实是放入缓冲区，等合适的时候再输出，我们将此"-"记为b)，同时P2中此时i=1，继续执行for循环---P2先fork()出一个子进程P3，然后P2再执行下一条语句输出一个"-"(其实是放入缓冲区，等合适的时候再输出，我们将此"-"记为c)。

P3进程为P2的子进程，它会复制其父进程P2的诸如环境变量、PC等环境，它执行下一条语句(输出语句)本应该输出一个"-"，但事实上因为这里P3会继承P2的缓冲区，而P2的缓冲区中有个'-'(P2调用fork产生P3时缓冲区里有b)，所以P3会输出两个'-'。

P1产生子进程P2后，继续下一轮循环，当i=1时，fork()产生另一个它的子进程P4，同时P1执行输出语句输出一个'-'。

P4为P1的一个子进程，它会继承P1的缓冲区，P1缓冲区中已经有一个'-'(P1调用fork产生P4时缓冲区里有a)，所以P4执行输出语句时会输出两个'-'。

上述输出语句本应该都输出一个'-'，有时却输出两个'-'，是因为"printf("-")"语句不是立即输出，而是先将输出放入缓冲区。所以，在fork的时候，缓存被复制到了子进程空间，导致子进程的输出缓冲区己经有了一个'-'。

例2：请问下而的程序一共输出多少个”-“()？

#include<stdio.h>
#include<sysltypes.h>
#include<unistd.h>
int main(void){
    int i;
    for(i=0; i<2; i++){
        fork();
        printf("-\n");
    }
    return 0
}

答案：6个
输出'\n'会刷新缓冲区，故正常输出6个。

问：线程

线程，有时被称为轻量级进程(Light weight Process，LWP)，是程序执行流的最小单元。一个标准的线程由线程ID、当前指令指针(PC)、寄存器集合和堆栈(stack)组成。另外，线程是进程中的一个实体，是被系统独立调度和分派的基本单位，线程自己不拥有系统资源，只拥有一点在运行中必不可少的资源，但它可与同属一个进程的其他线程共享进程所拥有的资源。

线程共享的进程环境包括:进程代码段、进程的公有数据(如全局变量，利用这些共享的数据，线程很容易的实现相互之间的通信)、进程打开的文件描述符、信号的处理器、进程的当前目录和进程用户ID与进程组ID。

线程拥有这许多共性的同时，还拥有自己的个性。有了这些个性，线程才能实现并发性。这些个性包括:

  • 线程ID：每个线程都有自己的线程ID，这个ID在本进程中是唯一的。进程用此来标识线程。
  • 寄存器组的值：由于线程间是并发运行的，每个线程有自己不同的运行线索，当从一个线程切换到另一个线程上时，必须将原有线程的寄存器集合的状态进行保存，以便将来该线程在被重新切换时能得以恢复。
  • 线程的堆栈(stack)：堆栈是保证线程独立运行所必须的。线程函数可以调用函数，而被调用函数中又是可以层层嵌套的，所以线程必须拥有自己的函数堆栈，使得函数调用可以正常执行，不受其他线程的影啊。在一个进程的线程共享堆区(heap)。
  • 错误返回码
  • 线程的信号屏蔽码
  • 线程的优先级

一个线程可以创建和撤销另一个线程，同一进程中的多个线程之间可以并发执行。由于线程之间的相互制约，致使线程在运行中呈现出间断性。线程也有就绪、阻塞和运行三种基本状态。每一个程序都至少有一个线程，若程序只有一个线程，那就是程序本身。线程是程序中一个单的顺序控制流程。在单个程序中同时运行多个线程完成不同的工作，称为多线程。

引入线程后，进程的内涵发生了改变，进程只作为除CPU以外系统资源的分配单元，线程则作为处理器的分配单元。在同一进程中，线程的切换不会引起进程的切换，但从一个进程中的线程切换到另一个进程中的线程时，将会引起进程的切换。

例1：有关多线程，多进程的描述错误的是()。

A.子进程获得父进程的数据空间，堆和栈的复制品
B.线程可以与同进程的其他线程共享数据，但是它拥有自己的栈空间且拥有独立的执行序列
C.线程执行开销小，但是不利于资源管理和保护
D.进程适合在SMP机器上进行，而线程则可以跨机器迁移

答案：D。
线程不能跨机器迁移。

问：进程与线程的区别

(1) 调度:在传统操作系统中，拥有资源和独立调度的基本单位都是进程。引入线程后，线程是独立调度的基本单位，进程是拥有资源的基本单位。在同一进程中，线程的切换不会引起进程切换。在不同进程中进行的线程切换，则会引起进程切换。

(2) 拥有资源:不论是传统的还是引入线程的操作系统，进程都是拥有资源的基本单位，线程不拥有资源(也有一点必不可少的资源)，但线程可以共享其隶属进程的系统资源。

(3) 并发性:在引入线程的操作系统中，不仅进程可以并发执行，而且同一进程内的多个线程也可以并发执行，从而使操作系统具有更好的并发性，大大提高了系统吞吐量。

(4) 系统开销:创建和撤销进程时，系统都要为之分配或回收资源，如内存空间、I/O设备等，因此操作系统所付出的开销远远大于创建或撤销线程的开销。类似地，在进程切换时，涉及当前执行进程CPU环境的保存以及新调度的进程CPU环境的设置；而线程切换时只需保存和设置少量寄存器内容，因此开销很小。另外，由于同一进程内的多个线程共享进程的地址空间，因此这些线程之间的同步与通信比较容易实现，甚至无须操作系统的干预。

(5) 地址空间和其他资源(如打开的文件):进程的地址空间之间互相独立，同一进程的各线程间共享进程的资源，某进程内的线程对于其他进程不可见。

(6) 通信方面:进程间通信需要借助操作系统，而线程间可以直接读/写进程数据段(如全局变量)来进行通信。

举例：若系统中只有用户级线程，则处理机调度单位是进程。
原因：如果系统只有用户态线程，则线程对操作系统是不可见的，操作系统只能调度进程；如果系统中有内核态线程，则操作系统可以按线程进行调度；

例1

问：进程的重要性与进程的销毁顺序

进程的重要性依次是：前台进程>可见进程>服务进程>后台进程>空进程。进程销毁的顺序为逆方向。

问：进程控制原语

原语是由若干条机器指令所构成，用以完成特定功能的一段程序，为保证其操作的正确性，它应当是原子操作，即原语是一个不可分割的操作。所以，原语在执行的过程中，是不可以被中断的。

操作系统对进程的管理和控制主要是通过控制原语言实现的，包括：进程创建，进程阻塞，唤醒进程和进程终止四个原语。

问：调度的基本准则

调度的基本准则包括CPU利用率、系统吞吐量、周转时间、等待时间、响应时间等。

  • 系统吞吐量表示单位时间内CPU完成作业的数量。
  • 周转时间为作业完成时刻减去作业到达的时刻。
  • 等待时间是指进程处于等待处理器状态的时间之和，等待时间越长，用户满意度越低。
  • 响应时间是指从用户提交请求到系统首次产生响应所用的时间。

问：调度算法

典型调度算法包括：先来先服务算法(FCFS)，短作业优先算法(SJF)、优先级调度算法、高响应比优先调度算法、时间片轮转算法、多级反馈队列调度算法。

注意：

  • 高响应比优先调度算法中，响应比=(等待时间+服务时间)/服务时间
  • 短作业优先算法的平均等待时间、平均周转时间最少。

一道很好的题目：



问：进程通信与进程同步

多个进程可以共享系统中的各种资源，但其中许多资源一次只能被一个进程使用，我们把一次仅允许一个进程使用的资源称为临界资源。许多物理设备都属于临界资源，如打印机等。对临界资源的访问，必须互斥的进行，在每个进程中，访问临界资源的那段代码称为临界区(Critical Section)。

(1) 进程通信与同步有如下一些目的

  • 数据传输:一个进程需要将它的数据发送给另一个进程;
  • 共享数据:多个进程想要操作共享数据，一个进程对共享数据的修改，别的进程应该立刻看到;
  • 通知事件:一个进程需要向另一个或一组进程发送消息，通知它(它们)发生了某种事件(如进程终止时要通知父进程)。
  • 资源共享:多个进程之间共享同样的资源。为了做到这一点，需要内核提供锁和同步机制;
  • 进程控制:有些进程希望完全控制另一个进程的执行(如Debug进程)，此时控制进程希望能够拦截另一个进程的所有陷入和异常，并能够及时知道它的状态改变。

(2) 进程间、线程间的通信方式

Linux下进程间通信的方式

  • 管道(Pipe)及有名管道(named pipe):管道可用于具有亲缘关系的进程间的通信，有名管道克服了管道没有名字的限制，因此，除具有管道所具有的功能外，它还允许无亲缘关系进程间的通信;
  • 信号(Signal):信号是比较复杂的通信方式，用于通知接受进程有某种事件发生，除了用于进程间通信外，进程还可以发送信号给进程本身；Linux除了支持UNIX早期信号语义函数sigal外，还支持语义符合Posix标准的信号函数sigaction；
  • Message(消息队列):消息队列是消息的链表，包括Posix消息队列System V消息队列。有足够权限的进程可以向队列中添加消息，被赋予读权限的进程则可以读走队列中的消息。消息队列克服了信号承载信息量少，管道只能承载无格式字节流以及缓冲区大小受限等缺点。
  • 共享内存:使得多个进程可以访问同一块内存空间，是最快的可用IPC形式。是针对其他通信机制运行效率较低而设计的。往往与其他通信机制，如信号量结合使用，来达到进程间的同步及互斥。
  • 信号量(semaphore)：主要作为进程间以及同一进程不同线程之间的同步手段。
  • 套接字(Socket)：更为一般的进程间通信机制，可用于不同机器之间的进程间通信。起初是由UNIX系统的BSD分支开发出来的，但现在一般可以移植到其他类UNIX系统上:Linux和System V的变种都支持套接字。

Linux线程间通信的方式：互斥量(Mutex)，信号量，条件变量。

Windows进程间通信的方式：管道、共享内存、消息队列、信号量、socket

Windows线程间通信的方式：临界区(Critical Section)，互斥量(Mutex)、信号量(Semaphore)和事件(Event)。

例1

(3) 临界区(Critical section)与互斥量(Mutex)的区别

  • 临界区只能用来同步本进程内的线程，而不可用来同步多个进程中的线程；互斥量(Mutex)、信号量(Semaphore)、事件(Event)都可以被跨越进程使用来进行同步数据操作;
  • 临界区是非内核对象，只在用户态进行锁操作，速度快；互斥体是内核对象，在核心态进行锁操作，速度慢。
  • 临界区和互斥体在Windows平台都下可用，Linux下只有互斥量可以使用。

例1：

在win32平台下，Event、Semaphore、Mutex能够实现进程同步，Critical Section无法实现进程同步。

问：死锁

(1) 死锁的概念

所谓死锁是指多个进程因竞争资源而造成的一种僵局(相互等待)，若无外力作用，这些进程都将无法向前推进。现实生活中一个简单的例子:交通阻塞，两股相向而行的车流都想通过已被对方占用的道路，结果双方都不能前进。

(2) 死锁的原因

  • 系统资源的竟争
  • 进程推进顺序非法

(3) 死锁产生的必要条件

产生死锁必须同时满足以下四个条件，只要其中任意一个条件不成立，死锁就不会发生。

  • 互斥条件:进程要求对所分配的资源进行排他性控制，即在一段时间内某资源仅为一个进程所占有。此时若有其他进程请求该资源，则请求进程只能等待。
  • 不剥夺条件:进程所获得的资源在未使用完毕之前，不能被其他进程强行夺走，即只能由获得该资源的进程自己来释放。
  • 请求和保持条件:又称为部分分配条件。进程每次申请它所需要的一部分资源，在等待新资源的同时，进程继续占有已分配到的资源。
  • 循环等待条件:存在一种进程资源的循环等待链，链中每个进程已获得的资源同时被链中下一个进程所清求。即存在一个处于等待状态的进程集合{P1，P2，P3，…，Pn}，其中Pi等待的资源被P(i+1)占有，Pn等待的资源被P0占有。

(4) 死锁处理策略

  • 预防死锁:设置某些限制条件，破坏产生死锁的四个必要条件中的一个或几个。
  • 避免死锁:在资源的动态分配过程中，用某种方法防止系统进入不安全状态。银行家算法是著名的死锁避免算法。
  • 死锁的检测及解除:无须采取任何限制性措施，允许进程在运行过程中发生死锁，通过系统的检测机制及时地检测出死锁的发生，然后采取某种措施解除死锁。
    • 死锁的检测可利用资源分配图来描述。
    • 死锁的解除主要方法如下：资源剥夺法、撤销进程法、进程回退法。

问：锁的类型

例1

三、 内存管理

操作系统对内存的划分和动态分配，就是内存管理的概念。内存管理的功能有:

  • 内存空间的分配与回收，包括内存的管理和共享。
  • 地址转换，把逻辑地址转换成相应的物理地址。
  • 内存空间的扩充，利用虚拟存储技术或自动覆盖技术，从逻辑上扩充内存。
  • 存储保护，保证各道作业在各自的存储空间内运行，互不干扰。

问：GB、MB和KB换算

1GB=1024MB

1MB=1024KB

问：逻辑地址空间与物理地址空间

编译后，每个目标模块都是从0号单元开始编址，称为该目标模块的相对地址(或逻辑地址)。当链接程序将各个模块链接成一个完整的可执行目标程序时，链接程序顺序依次按各个模块的相对地址构成统一的从0号单元开始编址的逻辑地址空间。

物理地址空间是指内存中物理单元的集合，它是地址转换的最终地址，进程在运行时执行指令和访问数据都要通过物理地址来存取主存。当装入程序将可执行代码装入内存时，必须通过地址转换将逻辑地址转换成物理地址，这个过程称为地址重定位。

问：静态重定位和动态重定位

对程序进行重定位的技术按重定位的时机可分为两种：静态重定位和动态重定位。现在一般计算机系统中都采用动态重定位方法。

(1) 静态重定位：是在目标程序装入内存时，由装入程序对目标程序中的指令和数据的地址进行修改，即把程序的逻辑地址都改成实际的地址。对每个程序来说，这种地址变换只是在装入时一次完成，在程序运行期间不再进行重定位。

优点：是无需增加硬件地址转换机构，便于实现程序的静态连接。在早期计算机系统中大多采用这种方案。

缺点：

  • 程序的存储空间只能是连续的一片区域，而且在重定位之后就不能再移动。这不利于内存空间的有效使用。
  • 各个用户进程很难共享内存中的同一程序的副本。

(2) 动态重定位：是在程序执行期间每次访问内存之前进行重定位。这种变换是靠硬件地址变换机构实现的。通常采用一个重定位寄存器，其中放有当前正在执行的程序在内存空间中的起始地址，而地址空间中的代码在装入过程中不发生变化。

优点：

  • 程序占用的内存空间动态可变，不必连续存放在一处。
  • 比较容易实现几个进程对同一程序副本的共享使用。

缺点：是需要附加的硬件支持，增加了机器成本，而且实现存储管理的软件算法比较复杂。

例1：能实现紧凑技术的存储管理方式为？

A. 可变分区管理  B. 分区存储管理  C. 页式存储管理  D. 可重定位存储管理

答案：D

内存分配管理方式

内存分配管理方式包括连续分配管理方式与非连续分配管理方式。

  • 连续分配方式，是指为一个用户程序分配一个连续的内存空间。它主要包括单一连续分配、固定分区分配和动态分区分配。
  • 非连续分配管理方式允许一个程序分散地装入到不相邻的内存分区中，根据分区的大小是否固定分为分页存储管理方式和分段存储管理方式。分页存储管理方式中，又根据运行作业时是否要把作业的所有页而都装入内存才能运行分为基本分页存储管理方式和请求分页存储管理方式。

问：动态分区分配

(1) 首次适应(First Fit)算法

空闲分区以地址递增的次序链接。分配内存时顺序查找，找到大小能满足要求的第一个空闲分区。

该算法优先使用低址部分空闲区，在低址空间造成许多小的空闲区，在高地址空间保留大的空闲区。

(2) 最佳适应(Best Fit)算法

空闲分区按容量递增形成分区链，找到第一个能满足要求的空闲分区。

(3) 最坏适应(Worst Fit)算法，又称为最大适应(Largest Fit)算法

空闲分区按容量递减形成分区链，找到第一个能满足要求的空闲分区，也就是找出最大的分区。

(4) 邻近适应(Next Fit)算法，又称为循环首次适应算法

该算法是首次适应算法的变种，不同之处是分配时从上次查找结束的位置开始继续查找。

该算法能使内存中的空闲区分布得较均匀。

问：基本分页存储管理方式

固定分区会产生内部碎片，动态分区会产生外部碎片，这两种技术对内存的利用率都比较低。我们希望内存的使用能尽量避免碎片的产生，这就引入了分页的思想:把主存空间划分为大小相等且固定的块，块相对较小，作为主存的基本单位。每个进程也以块为单位进行划分，进程在执行时，以块为单位逐个申请主存中的块空间。

分页的方法从形式上看，像分区相等的固定分区技术，分页管理不会产生外部碎片。但它又有本质的不同点:块的大小相对分区要小很多，而且进程也按照块进行划分，进程运行时按块申请主存可用空间并执行。这样，进程只会在为最后一个不完整的块申请一个主存块空间时，才产生主存碎片，所以尽管会产生内部碎片，但是这种碎片相对于进程来说也是很小的，每个进程平均只产生半个块大小的内部碎片(也称页内碎片)。

分页存储的几个基本概念：

(1) 页面和页面大小。

进程中的块称为页(Page)，内存中的块称为页框(Page Frame，或页帧)。外存也以同样的单位进行划分，称为块(Block)。进程在执行时需要申请主存空间，就是要为每个页面分配主存中的可用页框，这就产生了页和页框的一一对应。

为方便地址转换，页面大小应是2的整数幂。同时页面大小应该适中，如果页面太小，会使进程的页面数过多，这样页表就过长，占用大量内存，而且也会增加硬件地址转换的开销，降低页面换入/换出的效率；页面过大又会使页面内碎片增大，降低内存的利用率。所以页面的大小应该适中，考虑到空间效率和时间效率的权衡。

(2) 地址结构。

分页存储管理的逻辑地址结构如下图所示：



地址结构包含两部分:前一部分为页号P，后一部分为页内偏移量M。地址长度为32位，其中0~11位为页内地址，即每页大小为4KB;12~31位为页号，地址空间最多允许有2^20页。

(3) 页表。

为了便于在内存中找到进程的每个页面所对应的物理块，系统为每个进程建立一张页表，记录页面在内存中对应的物理块号，页表一般存放在内存中。在配置了页表后，进程执行时，通过查找该表，即可找到每页在内存中的物理块号。可见，页表的作用是实现从页号到物理块号的地址映射。

问：基本分段存储管理方式

段式管理方式按照用户进程中的自然段划分逻辑空间。例如，用户进程由主程序、两个子程序、栈和一段数据组成，于是可以把这个用户进程划分为5个段，每段从0开始编址，并分配一段连续的地址空间(段内要求连续，段间不要求连续，因此整个作业的地址空间是二维的)。其逻辑地址由段号S与段内偏移量W两部分组成。

在下图中，段号为16位，段内偏移量为16位，则一个作业最多可有2^16=65536个段，最大段长为64KB。



在页式系统中，逻辑地址的页号和页内偏移量对用户是透明的，但在段式系统中，段号和段内偏移量必须由用户显示提供，在高级程序设计语言中，这个工作由编译程序完成。

问：段页式管理方式

页式存储管理能有效地提高内存利用率，而分段存储管理能反映程序的逻辑结构并有利于段的共享。如果将这两种存储管理方法结合起来，就形成了段页式存储竹理方式。

在段页式系统中，作业的地址空间首先被分成若干逻辑段，每段都有自己的段号，然后再将每一段分成若干大小固定的页。对内存空间的管理仍然和分页存储管理一样，将其分成若干和页面大小相同的存储块，对内存的分配以存储块为单位。

在段页式系统中，作业的逻辑地址分为三部分:段号、页号和页内偏移量。为了实现地址变换，系统为每个进程建立一张段表，而每个分段有一张页表。段表表项中至少包括段号、页表长度和页表起始地址，页表表项中至少包括页号和块号。此外，系统中还应有一个段表寄存器，指出作业的段表起始地址和段表长度。在进行地址变换时，首先通过段表查到页表起始地址，然后通过页表找到页帧号，最后形成物理地址。

问：虚拟存储器的定义和特征

基于局部性原理，在程序装入时，可以将程序的一部分装入内存，而将其余部分留在外存，就可以启动程序执行。在程序执行过程中，当所访问的信息不在内存时，由操作系统将所需要的部分调入内存，然后继续执行程序。另一方面，操作系统将内存中暂时不使用的内容换出到外存上，从而腾出空间存放将要调入内存的信息。这样，系统好像为用户提供了一个比实际内存大得多的存储器，称为虚拟存储器。之所以将其称为虚拟存储器，是因为这种存储器实际上并不存在，只足由于系统提供了部分装入、请求调入和置换功能后(对用户完全透明)，给用户的感觉是好像存在一个比实际物理内存人得多的存储器。

虚拟内存的实现有以下三种方式:

  • 请求分页存储管理
  • 请求分段存储管理
  • 请求段页式存储管理

段页式虚拟存储器一方面具有段式虚拟存储器的主要优点。例如，用户程序可以模块化编写，程序段的共享和信息的保护都比较方便，程序可以在执行时再动态链接等。另一方面也具有页式虚拟存储器的主要优点。例如:主存储器的利用率比较高，对辅助存储器的管理比较容易等。

不管哪种方式，都需要有一定的硬件支持。一般需要的硬件支持有以下个方面：

  • 一定容量的内存和外存；
  • 页表机制(或段表机制)，作为主要的数据结构；
  • 中断机构，当用户程序要访问的部分尚未调入内存，则产生中断；
  • 地址变换机构，逻辑地址到物理地址的变换。

例1：

问：请求分页管理方式

请求分页系统建立在基本分页系统基础之上，为了支持虚拟存储器功能而增加了请求调页功能和页面置换功能。请求分页是目前最常用的一种实现虚拟存储器的方法。

在请求分页系统中，只要求将当前需要的一部分页面装入内存，便可以启动作业运行。在作业执行过程中，当所要访问的页面不在内存时，再通过调页功能将其调入，同时还可以通过置换功能将暂时不用的页面换出到外存上，以便腾出内存空间。为了实现请求分页，系统必须提供一定的硬件支持。除了需要一定容量的内存及外存的计算机系统，还需要有页表机制、缺页中断机构和地址变换机构。

常见的置换算法有一下三种:最佳置换算法(OPT)、先进先出页面置换算法(FIFO)、最近最久未使用置换算法(LRU)。

问：页面置换算法

  • OPT(Optimal Replacement)
  • FIFO(First in First out)
  • LRU(Least Recently Used)，和使用时间相关，和使用次数（频率）无关
  • LFU(Least Frequently Used)，和使用次数(频率)相关，和使用时间无关

网络上的一个简要的总结

(1) 最佳置换算法(OPT)

最佳置换算法(Optimal, OPT)所选择的被淘汰页面将是以后永不使用的，或者是在最长时间内不再被访问的页面，这样可以保证获得最低的缺页率。但由于人们目前无法预知进程在内存下的若干页面中哪个是未来最长时间内不再被访问的，因而该算法无法实现。

最佳置换算法可以用来评价其他算法。假定系统为某进程分配一了三个物理块，并考虑有以下页面号引用串:7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1，7，0，1，进程运行时，先将7，0，1三个页面依次装入内存。进程要访问页面2时，产生缺页中断，根据最佳置换算法，选择第18次访问才需调入的页面7予以淘汰。然后，访问页面0时，因为已在内存中所以不必产生缺页中断。访问页面3时又会根据最佳置换算法将页面淘汰，以此类推，如下图所示。从图中可以看出采用最佳置换算法时页面置换情况。



(2) 先进先出页面置换算法(FIFO)

优先淘汰最早进入内存的页而，亦即在内存中驻留时间最久的页面。该算法实现简单，只需把调入内存的页面根据先后次序链接成队列，设置一个指针总指向最旱的页面。但该算法与进程实际运行时的规律不适应，因为在进程中，有的页面经常被访问。

这里仍用上而的实例，采用FIFO算法进行页面置换。进程访问页面2时，把最一早进入内存的页面7换出。然后访问页面3时，再把2，0，1中最先进入内存的页面0换出。由图2_2可以看出，利用FIFO算法时进行了12次页面置换，比最佳置换算法正好多一倍。



(3) 最近最久未使用置换算法(LRU)

选择最近最长时间未访问过的页面予以淘汰，它认为过去一段时间内末访问过的页面，在最近的将来可能也不会被访问。该算法为每个页而设置个访问字段，来记录页面自上次被访问以来所经历的时间，淘汰页面时选择现有页面中值最大的予以淘汰。

再对上面的实例采用LRU算法进行页面置换，如图2-4所示。进程第一次对页面2访问时，将最近最久未被访问的页而7置换出去。然后访问页而3时，将最近最久未使用的页面1换出。



在上图中，前5次置换的情况与最佳置换算法相同，但两种算法并无必然联系。实际上，LRU算法根据各页以前的情况，是”向前看”的，而最佳置换算法则根据各页以后的使用情况，是”向后看”的。LRU性能较好，但需要寄存器和栈的硬件支持。LRU是堆栈类的算法。理沦上可以证明，堆栈类算法不可能出现Belady异常。FIFO算法基于队列实现，不是堆栈类算法。

问：Belady’s Anomaly

Belady’s Anomaly，即Belady异常或者Belady现象。 所谓Belady现象是指：在页面置换中，当发生缺页时的置换算法采用FIFO(先进先出)算法时，有时会出现分配的页面数增多但缺页率不减反增的异常现象。只有FIFO算法可能出现Belady异常，而LRU和OPT算法永远不会出现Belady异常。

例如：访问页面序列为：1，2，3，4，1，2，5，1，2，3，4，5。当分配页面数位3时，缺页9次；当分配页面数位4时，缺页10次。



问：抖动

在页面置换过程中的一种最糟糕的情形是，刚刚换出的页面马上又要换入主存，刚刚换入的页面马上就要换出主存，这种频繁的页面调度行为称为抖动，或颠簸。如果一个进程在换页上用的时间多于执行时间，那么这个进程就在颠簸。

频繁的发生缺页中断，其主要原因是某个进程频繁访问的页面数目高于可用的物理页帧数目。虚拟内存技术可以在内存中保留更多的进程以提高系统效率。但系统必须很”聪明”地管理页面分配方案。在稳定状态，几乎主存的所有空间都被进程块占据，处理机和操作系统可以直接访问到尽可能多的进程。但如果处理不当，处理机的大部分时间都将用于交换块，即请求调入页面的操作，而不是执行进程的指令，这就会大大降低系统效率。

问：工作集

工作集(或驻留集)是指在某段时间间隔内，进程要访问的页面集合。经常被使用的页面需要在工作集中，而长期不被使用的页面要从工作集中被丢弃。为了防止系统出现抖动现象，需要选择合适的工作集大小。

工作集模型的原理是:让操作系统跟踪每个进程的工作集，并为进程分配大于其工作集的物理块。如果还有空闲物理块，则可以再调一个进程到内存以增加多道程序数。如果所有工作集之和增加以至于超过了可用物理块的总数，那么操作系统会暂停一个进程，将其页面调出并且将其物理块分配给其他进程，防止出现抖动现象。

正确选择工作集的大小，对一存储器的利用率和系统吞吐量的提高，都将产生重要影响。

问：磁盘

磁盘是可共享设备，一段时间内允许多个用户进行交叉访问，同一时刻只能有一个进程访问。

问：磁盘平均存取时间

平均存取时间=寻道时间+延迟时间+传输时间

例1

问：RAID阵列

RAID 0：无差错控制的带区组

要实现RAID0必须要有两个以上硬盘驱动器，RAID0实现了带区组，数据并不是保存在一个硬盘上，而是分成数据块保存在不同驱动器上。在所有的级别中，RAID 0的速度是最快的。但是RAID 0没有冗余功能的，如果一个磁盘(物理)损坏，则所有的数据都无法使用。



RAID 1：镜象结构

当主硬盘损坏时，镜像硬盘就可以代替主硬盘工作。镜像硬盘相当于一个备份盘，可想而知，这种硬盘模式的安全性是非常高的，RAID 1的数据安全性在所有的RAID级别上来说是最好的。但是其磁盘的利用率却只有50%，是所有RAID级别中最低的。



RAID5：分布式奇偶校验的独立磁盘结构

RAID5最大的好处是在一块盘掉线的情况下，RAID照常工作，相对于RAID0必须每一块盘都正常才可以正常工作的状况容错性能好多了。因此 RAID5是RAID级别中最常见的一个类型。RAID5校验位即P位是通过其它条带数据做异或(xor)求得的。计算公式为 P=D0xorD1xorD2…xorDn，其中p代表校验块，Dn代表相应的数据块，xor是数学运算符号异或。



RAID10：高可靠性与高效磁盘结构

RAID 10是先镜射再分区数据。是将所有硬盘分为两组，视为是RAID 0的最低组合，然后将这两组各自视为RAID 1运作。RAID 10有着不错的读取速度，而且拥有比RAID 0更高的数据保护性。



四、 文件管理

硬链接和软链接

https://www.nowcoder.com/profile/7404313/test/8129531/15818?onlyWrong=0

五、 输入输出(I/O)管理

问：I/O控制方式

  • 程序直接控制方式
  • 中断驱动方式：允许I/O设备主动打断CPU的运行并请求服务，从而解放CPU，使得CPU向I/O控制器发送读命令后可以继续做其他有用的工作。

  • DMA方式：在中断驱动方式中，I/O设备与内存之间的数据交换必须要经过CPU中的寄存器，所以速度受限，而DMA(直接存储器存取)方式的基本思想是在I/O设备和内存之间开辟直接的数据交换通路，彻底解放CPU。

    DMA方式的特点：

    (1) 基本单位是数据块

    (2) 所传送的数据，是从设备直接送入内存的，或者相反。

    (3) 仅在传送一个或多个数据块的开始和结束时，才需要CPU干预，整块数据的传送是在DMA控制器的控制下完成的。

  • 通道方式

通道能够完成内存与外设之间数据的传输。

问：独享设备、共享设备和虚拟设备

  • 独享设备：在一个用户作业未完成或退出之前，此设备不能分配给其他作业用。所有字符设备都是独享设备。如输入机、磁带机、打印机等。——很明显：需要装驱动。
  • 共享设备：多个用户作业或多个进程可以”同时”从这些设备上存取信息。软硬盘、光盘等块设备都是共享设备。——无需驱动。
  • 虚拟设备：通过软件技术将独享设备改造成共享设备。例如：通过SPOOLing技术将一台打印机虚拟成多台打印机。——实质还是独享设备，需要驱动。

问：单缓冲和双缓冲

https://www.nowcoder.com/profile/7404313/test/8073949/24035?onlyWrong=0

问：I/O子系统的层次结构

操作系统的I/O 子系统通常由 4 个层次组成，每一层明确定义了与邻近层次的接口，其合理的层次组织排列顺序是：用户级 I/O 软件、设备无关软件、设备驱动程序、中断处理程序

七、 其他

进程间的通信方式

  • 管道( pipe )：管道是一种半双工的通信方式，数据只能单向流动，而且只能在具有亲缘关系的进程间使用。进程的亲缘关系通常是指父子进程关系。
  • 信号量( semophore ) ： 信号量是一个计数器，可以用来控制多个进程对共享资源的访问。它常作为一种锁机制，防止某进程正在访问共享资源时，其他进程也访问该资源。因此，主要作为进程间以及同一进程内不同线程之间的同步手段。
  • 消息队列( message queue ) ： 消息队列是由消息的链表，存放在内核中并由消息队列标识符标识。消息队列克服了信号传递信息少、管道只能承载无格式字节流以及缓冲区大小受限等缺点。
  • 共享内存( shared memory ) ：共享内存就是映射一段能被其他进程所访问的内存，这段共享内存由一个进程创建，但多个进程都可以访问。共享内存是最快的 IPC 方式，它是针对其他进程间通信方式运行效率低而专门设计的。它往往与其他通信机制，如信号两，配合使用，来实现进程间的同步和通信。
  • 套接字( socket ) ： 套解口也是一种进程间通信机制，与其他通信机制不同的是，它可用于不同及其间的进程通信。
  • RPC

内存分配方式有三种：

（1）从静态存储区域分配。内存在程序编译的时候就已经分配好，这块内存在程序的整个运行期间都存在。例如全局变量，static变量。

（2）在栈上创建。在执行函数时，函数内局部变量的存储单元都可以在栈上创建，函数执行结束时这些存储单元自动被释放。栈内存分配运算内置于处理器的指令集中，效率很高，但是分配的内存容量有限。

（3） 从堆上分配，亦称动态内存分配。程序在运行的时候用malloc或new申请任意多少的内存，程序员自己负责在何时用free或delete释放内存。动态内存的生存期由我们决定，使用非常灵活，但问题也最多

相联存储器

相联存储器（associative memory),也称为按内容访问存储器（content addressed memory)或简称为TLB(Translation Lookaside Buffer)，它是一种不根据地址而是根据存储内容来进行存取的存储器,可以实现快速地查找块表

大端存储和小端存储

https://www.nowcoder.com/profile/7404313/test/7907952/14799?onlyWrong=0

案例1：

union X{
    int x;
    char y[4];
};

在小端序的机器中,如果定义X a; 
a.x=0x11223344;//16 进制，则a.y[3]=0x11

在union 中所有的数据成员共用一个空间，同一时间只能储存其中一个数据成员，所有的数据成员具有相同的起始地址。

管道

管道是指用于连接一个读进程和一个写进程以实现进程之间通信的一种共享文件。向管道提供输入的是发送进程，也称为 写进程，负责向管道输入数据，数据的格式是字符流。接受管道 数据的接受进程为读进程。

12. 零碎的东西

孤儿进程：一个父进程退出，而它的一个或多个子进程还在运行，那么那些子进程将成为孤儿进程。孤儿进程将被init进程(进程号为1)所收养，并由init进程对它们完成状态收集工作。
僵尸进程：一个进程使用fork创建子进程，如果子进程退出，而父进程并没有调用wait或waitpid获取子进程的状态信息，那么子进程的进程描述符仍然保存在系统中。这种进程称之为僵死进程。
如果进程不调用wait / waitpid的话， 那么保留的那段信息就不会释放，其进程号就会一直被占用，但是系统所能使用的进程号是有限的，如果大量的产生僵死进程，将因为没有可用的进程号而导致系统不能产生新的进程. 此即为僵尸进程的危害，应当避免。
孤儿进程是没有父进程的进程，孤儿进程这个重任就落到了init进程身上 ，init进程就好像是一个民政局，专门负责处理孤儿进程的善后工作。每当出现一个孤儿进程的时候，内核就把孤 儿进程的父进程设置为init，而init进程会循环地wait()它的已经退出的子进程。这样，当一个孤儿进程凄凉地结束了其生命周期的时候，init进程就会代表党和政府出面处理它的一切善后工作。 因此孤儿进程并不会有什么危害。

链接：https://www.nowcoder.com/questionTerminal/8c8bcba738eb4facbdfdb22f47961bee
来源：牛客网

Redhat 9所支持的安装方式有
光盘安装 (常规情况) 硬盘安装 (无光驱情况)
网络安装-NFS方式 (适合于批量安装大量服务器，和kickstart自动安装一起使用)
网络安装-FTP方式 (适合于批量安装大量服务器，和kickstart自动安装一起使
网络安装-HTTP方式 (适合于批量安装大量服务器，和kickstart自动安装一起使

问：可重入函数

https://www.nowcoder.com/profile/7404313/test/8114731/56534?onlyWrong=0

问：并发

https://www.nowcoder.com/profile/7404313/test/8114731/44749?onlyWrong=0

分享到 评论