考研复习之操作系统

- 9 分钟前
CS Notes

【考查目标】

  1. 掌握操作系统的基本概念、基本原理和基本功能，理解操作系统的整体运行过程。
  2. 掌握操作系统进程、内存、文件和I/O管理的策略、算法、机制以及相互关系。
  3. 能够运用所学的操作系统原理、方法与技术分析问题和解决问题，并能利用C语言描述相关算法。

概述

操作系统：控制和管理整个计算机系统的硬件和软件资源，并合理地组织调度计算机的工作和资源的分配，以提供给用户和其他软件方便的接口和环境的程序集合。

操作系统提供的用户接口：

操作系统发展历程

计算机系统中，CPU执行两种程序：操作系统内核程序和外层应用程序。

特权指令：计算机中不允许用直接执行的指令，如I/O指令、置中断指令等。

操作系统内核：计算机上配置的底层软件。

核心态（管态）与用户态（目态）是操作系统的两种运行级别。核心态运行操作系统程序，用户态运行用户程序。核心态指令实际上包括系统调用类指令和一些针对时钟、中断和原语的操作指令。

系统调用的执行过程

CPU状态之间的切换：

PS：如果程序的运行由用户态转到核心态，会用到访管指令。访管指令应用在用户态，所以不可能是特权指令。

进程管理

进程

  1. 定义：进程是进程实体的运行过程，是系统进行资源分配的一个基本单位。
    • 程序段
    • 数据
    • PCB：程序控制块，是进程存在的唯一标志。
  2. 特征
    • 动态性：由创建而产生，由调度而执行，由撤销而消亡。
    • 并发性：多个进程实体同存于内存中，且在一段时间内同时运行。程序并不具有。
    • 独立性：进程实体是一个能独立运行、独立获得资源和独立接受调度的基本单位。
    • 异步性：进程按各自独立的、不可预知的速度向前推进。
  3. 进程和程序的比较
    • 程序是有序代码的集合，是一个静态的概念。进程是程序的一次执行过程，是一个动态概念。
    • 进程是一个状态变化的过程，是有生命期的。而程序是永久的，可以长久保存。
    • 组成不同。进程由数据段、数据、PCB组成，而程序只是代码的有序集合
    • 进程与程序是密切相关的。通过多次执行，一个程序可对应多个进程。但进程与它本身所运行的程序只能是一对一的关系。
    • 进程能更真实的描述并发，程序不能。
    • 进程可以创建其他进程，程序不能形成新的程序

进程的状态与转换

进程的创建

一个进程可以创建另一个进程

  1. 申请空白PCB，获得唯一的数字标识符
  2. 分配资源，包括各种物理和逻辑资源
  3. 初始化PCB：标识信息、处理机状态、控制信息
  4. 如果进程就绪队列能够接纳新进程，插入就绪队列

Alt text

进程的终止

  1. 根据标识符从PCB集合中检索出该进程PCB，读出该进程的状态
  2. 若执行态，立即终止该进程的执行，并置调度标志为真，用于指示该进程被终止后应重新进行调度
  3. 若有子孙进程，所有子孙进程也终止
  4. 被终止进程拥有的所有资源归还父进程或系统
  5. 进程(PCB)从队列(链表)中移出

进程的阻塞和唤醒

Alt text

进程通信

进程通信指的是进程间的信息交换，PV操作是低级通信方式，高级通信方式是指以较高的效率传输大量数据的通信方式。

  1. 共享存储（Shared-Memory System）

在通信的进程之间存在一块可直接访问的共享空间，进程通过在共享空间进行读、写操作进行信息交换。共享空间的读写需要互斥同步工具，基于数据结构的共享是低级方式，基于存储器的共享是高级方式。

进行运行期间一般不能访问其他进程的空间，需要特殊的系统调用实现；而进程内的线程是自然共享进程空间的。

  1. 消息传递

进程间的数据交换以格式化的 Message 为单位，通过系统提供的 send 发送消息原语和 receive 接收消息原语实现。

实现方式

	send(receiver,message); //发送一个消息给接收进程
	receive(sender,message);//接收sender发来的消息

	send(mailbox,message);//将一个消息发送到指定邮箱
	receive(mailbox,message);//从指定邮箱中接收一个消息
  1. 管道通信

管道：用于连接一个读进程和一个写进程以实现它们之间通信的一个共享文件。

输入进程以字符流形式将大量的数据送入管道；输入进程从管道中接收数据。管道拥有互斥、同步和确认对方存在的协调能力。

线程

引入线程之后，线程是操作系统独立调度的基本单位，线程自己不拥有系统资源，只拥有一点在运行中必不可少的资源，但它可与同属一个进程的其他线程共享所有资源。

同一进程中的多个线程间可以并发执行，一个线程可以创建和撤销另一个线程。一个线程被创建后便开始了它的生命周期，只至终止会经理阻塞态、就绪态和运行态等各种状态变化。

线程分为用户级线程和内核级线程。

用户级线程中，内核意识不到线程的存在。通常，应用程序从单线程开始，在该线程中开始运行，在其运行的任何时刻，可以通过调用线程库中的派生例程创建一个在相同进程中运行的新线程。

内核级线程中，线程管理的所有工作由内核完成。应用程序只有一个到内核级线程的编程接口。

组合方式中，线程创建在用户空间完成，调度和同步也在用户空间中进行。应用程序中的线程映射到一些内核级线程上。

多线程模型 ：实现用户级线程和内核级线程的连接方式。

处理机调度

作业调度往往发生在一批作业已运行完毕并推出系统，又需要重新调入一批作业进入内存时，大约几分钟一次；而进程调度是最基本的调度，运行频率也最高。

进程调度分为非剥夺式调度和剥夺式调度。第一种方式下，一旦把CPU分配给一个进程，那么该进程就会保持CPU直到终止或转换到阻塞态；而抢占式可以在一个进程执行过程中，为某个更重要或更紧迫的程序分配CPU资源。

调度的基本准则

调度算法

  1. FCFS先来先服务调度算法：从后备作业队列（进程就绪队列）调度队头进程，非抢占式算法。

FCFS对长作业有利，对短作业不利；I/O繁忙型作业由于要频繁访问IO端口，每次访问都要放弃CPU，等I/O访问完后要重新等待下一次调度（此时排到了就绪队列的队尾），所以要等待很久才能重新被调度。因此先来先服务有利于CPU繁忙型作业而不利于I/O繁忙型作业。

  1. SJF调度算法：根据就绪队列中作业（进程）运行时间长短调度，选择最短的。

该算法对长作业十分不利，很容易产生“饥饿”现象；SJF调度算法的平均等待时间和平均周转时间最少。

  1. 优先级调度算法：从后备作业队列（进程就绪队列）中选择优先级最高的作业（进程）。

静态优先级一旦分配，在执行过程中不变；动态优先级在执行过程中动态改变。

  1. 高响应比优先调度算法（作业调度）

高响应比优先算法是结合了FCFS和SJF的算法。优先级相当于响应比RP。

Alt text

  1. 时间片轮转调度算法（进程调度）：就绪队列中的队头进程每运行一个时间片就让出CPU，并返回到就绪队列的末尾继续排队。

如果时间片足够大，以至于所有进程都能在一个时间片内执行完成，那么此时就相当于FCFS；如果时间片过小，处理机将需要频繁切换进程，增大了调度开销。

  1. 多级反馈队列调度算法：既能使高优先级的作业得到响应又能使短作业（进程）迅速完成。
    1. 设置多个就绪队列，为各个队列赋予不同的优先级。赋予各个队列进程执行时间片的大小的也不同，优先权越高的队列中，执行时间片就越小。
    2. 只有在优先级高的队列中没有进程时才会到下一个队列。
    3. 当一个新进程进入内存后，将其放入第一队列队尾，按FCFS排队等待调度。当轮到它执行是，若在该时间片内完成便撤离系统，否则把该进程转入下一队列队尾，直至完成。
    4. 在低优先级的队列中的任务在运行时，又有新到达的任务，那么在运行完这个时间片后，CPU马上分配给新到达的任务，即算法支持抢占式。

多级反馈队列调度算法

进程同步

临界资源：一次仅允许一个进程使用的资源。

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

while(TURE){
	进入区//检查临界资源是否正在被访问
	临界区
	退出区//将临界区正被访问的标志恢复为未被访问标志
	剩余区
}

同步：为完成某种任务而建立的两个或多个进程，在某些位置上协调它们的工作次序而等待、传递信息所产生的制约关系。

互斥：有进程访问临界资源时其他进程必须等待。

同步机制应遵守的规则

软件实现方法

硬件实现方法

  1. 中断屏蔽：当一个进程在访问临界区时，关中断 -> 访问 -> 开中断。这种方式会大大降低计算机的执行效率。
  2. TestAndSet指令：原子操作，锁机制。为每个临界资源设置lock变量，当有进程在访问某临界变量时，利用TestAndSet检查并修改&lock，访问结束后lock = false;
  3. Swap指令：交换两个字（字节）的内容。每个临界资源有一个lock，每个进程再设置局部变量key。
	 key = true;
	 while( key != false ){
		 Swap(&lock, &key);
	 } 
	 critical section;
	 lock = false;

硬件进入临界区耗费CPU时间，不能实现让权等待，从等待进程中随机选择一个进入临界区，很可能导致饥饿。

信号量机制

整型信号量

定义一个用于表示资源数目的整型量S，除初始化外仅能通过wait(S)和signal(S)来访问

	wait(S){//申请
		while(S<=0);
		S--;
	}
	signal(S){//释放
		S++;
	}

S=0 表示系统中该类临界资源刚好被全部占用，而且没有进程在等待该临界资源。

S<0时会不断的测试

记录型信号量：解决让权等待

除了一个用于表示资源数目的整形变量value外，增加一个进程链表L，用于链接所有等待进程。

	typedef struct{
		int value;
		struct process_control_block *list;//阻塞队列
	}semaphore;
	wait(semaphore *S){
		S->value--;
		if(S->value < 0)
			block(S->list);//阻塞原语
	}
	signal(semaphore *S){
		S->value++;
		if(S->value<=0)
			wakeup(S->list);//唤醒原语
	}

AND型信号量：解决死锁

将进程在整个运行过程中需要的所有资源，一次性全部地分配给进程，待进程使用完后再一起释放。只要尚有一个资源未能分配给进程，其它所有可能为之分配的资源，也不分配给他。

Swait(S1, S2, …, Sn)
    if S1≥1 and … and Sn≥1 then
        for i=1 to n do
        Si=Si-1;
        endfor
    else
     把进程放入第一个阻塞原因的资源等待队列
    endif
Ssignal(S1, S2, …, Sn)
      for i=1 to n do
      Si=Si+1;
      从对应释放资源的等待队列中唤醒一个进程
  endfor;

信号量集

在AND型信号量的基础上进行扩充，进程对信号量Si的测试值为ti(用于信号量的判断，即Si≥ ti表示资源数量低于ti时不予分配)，占用值为di(用于信号量的增减，即Si= Si-di和Si= Si+di)。

	Swait(S1,t1,d1,…,Sn,tn,dn);
	Ssignal(S1,Dn,…,Sn,dn);
利用信号量实现互斥、前趋(前趋图)关系

互斥信号量：初始化mutex=1;

mutex值 意义
1 临界资源空闲
0 有一个进程进入临界区运行
-1 有一个已经在运行，有一个还在等

前趋图

p1(){S1;signal(a);signal(b);}
p2(){wait(a);S2;signal(c)；signal(d);}
p3(){wait(b);S3;signal(e);}
p4(){wait(c);S4;signal(f);}
p5(){wait(d);S5;signal(g);}
p6(){wait(e);wait(f);wait(g);S6;}
main(){
	semaphore a,b,c,d,e,f,g;
	a.value=b.value=c.value=d.value=e.value=f.value=g.value=0;
	p1();p2();p3();p4:();p5();p6();
}

生产者-消费者问题：满不能生产，空不能消费

C语言实现源码

信号量解决实际问题步骤

管程

管程：由一组数据以及定义在这组数据上的对这组数据的操作组成的软件模块，这组操作能初始化并改变管程中的数据和同步进程。

死锁

死锁：多个进程因竞争资源而造成的一种僵局。

引起死锁的原因
产生死锁的必要条件

死锁预防

破坏必要条件中的其中一个，互斥不能变，所以破坏其他三个。

死锁避免

银行家算法

数据结构

算法思想：

(1) 如果Request i[j]≤Need[i, j]，便转向步骤(2)； 否则认为出错，因为它所需要的资源数已超过它所宣布的最大值。　　 (2) 如果Request i[j]≤Available[j]，便转向步骤(3)； 否则，表示尚无足够资源，Pi须等待。 (3) 系统试探着把资源分配给进程Pi 　

Available[j]=Available[j] - Request i[j];　  　
Allocation[i, j]=Allocation[i, j]+Request i[j]; 
Need[i, j] = Need[i, j] - Request i[j];

系统执行安全性算法，检查此次资源分配后系统是否处于安全状态。若安全，才正式将资源分配给进程Pi，以完成本次分配；否则，将本次的试探分配作废，恢复原来的资源分配状态，让进程Pi等待。

安全性算法
	Work[j] = Work[j]+Allocation[i][j];
	Finish[i]=true;
	go to step2;

银行家算法C语言实现

死锁检测

资源分配图

死锁定理：

  1. 在资源分配图中，找出一条有向边与它相连，且该有向边对应资源的申请数量 <= 系统中已有空闲资源数量，若满足，消去它所有的请求变和分配边，使其成为一个孤立的点。
  2. 进程Pi锁释放的资源，可以唤醒某些因为等待这些资源而阻塞的进程，原来阻塞的进程可以变成非阻塞进程继续简化资源分配图。
  3. 当且仅当资源分配图不可完全简化时，当前状态为死锁状态。

死锁解除：剥夺资源、撤销进程、进程回退（回退时进程自愿释放资源）。

文件管理

概念

文件：以计算机硬盘为载体，存储在计算机上的信息集合。在用户进行输入、输出中，以文件为基本单位。

文件属性：名称、标识符、类型、位置、大小、保护（访问控制信息）、时间、日期和用户标识。

所有文件的信息都保存在目录结构中，目录结构也保存在外存上 。通常，目录条目只包括文件名及其唯一标识符，通过标识符定位其他属性的信息。

操作系统通过系统调用实现对文件的创建、读/写、定位（寻址）、删除和截断。这6个基本操作可以组合执行文件操作。比如文件复制操作，可以由创建新文件、从文件读出并写入到新文件。

系统要求在首次使用文件时，使用系统调用 open 将指明文件的属性（包括该文件在外存上的物理位置）从外存拷贝到内存 打开文件目录表 中的一个标目中，并将该表目的标号返回给用户。也就是说，在open调用完成之后，操作系统对该文件的任何操作，都不再需要文件名，只需要open调用返回的指针。

文件的逻辑结构

文件的逻辑结构讲的是在文件内部，逻辑上数据时如何组织起来的。

索引顺序文件

目录结构

目录实际上是文件外部的逻辑结构的问题，目录是特殊的有结构文件。通过树形结构实现目录的重名问题。

文件控制块：存放控制文件需要的各种信息的数据结构，以实现”按名存取”。一个FCB就是 一个文件目录项。

文件目录项中每个目录项仅由文件名和指向该文件所对应的索引结点的指针构成。

目录结构分为单级目录结构、两级目录结构、多级目录结构和无环图目录结构。

文件共享

  1. 基于索引结点的共享方式（硬链接）：上述无环图目录结构。当文件主删除文件时，源文件不会真正被删除。
  2. 利用符号链实现文件共享（软链接）：系统创建一个 LINK 类型的新文件，新文件中只包含被链接文件F的路径名。在这种方式下，只有文件拥有者才拥有指向索引结点的指针，即只有文件主才可以真正删除文件，且当删除源文件时，创建的 LINK 类型文件不会被删除。想象桌面快捷方式，当删除源文件时，快捷方式依然存在，但文件已不存在了；删除快捷方式，源文件依然存在。

文件保护

文件保护通过口令保护、加密保护和访问控制等方式实现。口令和加密防止文件内容被窃取，访问控制用于用户对文件的访问方式。

基于身份访问的最普通的方式时为每个文件和目录增加一个访问控制列表，以规定每个用户及其所允许的访问类型。用户可分为拥有者、组和其他用户三种类型。

口令是在文件建立FCB时附上相应口令，同时告诉允许共享该文件的其他用户。

对于多级目录结构，不仅需要保护单个文件，还需要保护字目录内的文件，即需要提供目录保护机制。

文件系统实现

文件系统层次结构

文件系统层次结构

目录实现

目录查询是通过在磁盘上反复操作完成的，需要不断进行I/O操作。为了减少I/O操作，把当前使用的文件目录复制到内存，以后要使用该文件中只要在内存中操作。

  1. 线性列表
  2. hash 表

文件实现（物理）

文件分配方式：对磁盘非空闲块的管理
  1. 连续分配：每个文件在磁盘上占有一组连续的块。这种排序使访问磁盘时所需要的寻道数和寻道时间最小。目录文件包括文件名、起始块号和长度。访问第 n 个记录，访问磁盘 1 次即可。

连续分配

显然，连续分配支持随机存取和顺序访问。但文件长度不适宜动态增加，因为一旦文件末尾后的盘块分给了其他文件，增加时就需要大量移动盘块。而且易产生外部碎片，因此只适用于长度固定的文件。

  1. 链接分配：离散分配，便于文件的增、删、改。

隐式链接分配

  1. 索引分配：把每个文件的所有的盘块号都集中放在一起构成索引块表（类似页表）。索引结点类似页表项，索引块类似页（个人理解）。
    1. 链接方案：索引块本身为磁盘块，处理大文件可以将多个索引块链接起来。非常低效。
    2. 多层索引（类似多级页表）：访问第 n 个记录，m 级索引需访问磁盘 m + 1 次。
    3. 混合索引：多种索引分配方式相结合的分配方式。

索引分配

文件存储空间管理：对磁盘空闲块的管理
  1. 空闲表法：类似于内存空闲分区表，每个空闲区对应一个空闲表项，包括表项序号、起始空闲盘好和空闲盘块数。回收时与内存紧凑也一样。
  2. 空闲链表法
    1. 空闲盘区链：盘区可能包含多个盘块
    2. 空闲盘块链
  3. 位示图法 ：利用二进制的 1 bit来表示磁盘中一个盘块的使用情况，磁盘上所有的盘块都有 1bit 与其对应。 0 表示空闲，1表示已分配。
  4. 成组链接法：空闲盘块号栈，存放当前可用的一组空闲盘块的盘块号，以及栈中尚有的空闲盘块号数目。文件区中的所有空闲盘块分成若干组，最后一组存放 0 作为空闲盘块链的结束标志。

成组链接法

I/O管理

I/O系统的层次结构和模型

I/O系统的分层：

四种I/O控制方式计组

缓冲区

缓冲区

缓冲区位于内存区域。当缓冲区数据非空时，不能往缓冲区冲入数据，只能从缓冲区把数据传出；必须把缓冲区充满之后，才能把数据从缓冲区传出。

单缓冲区：在设备和处理机之间设置 1 个缓冲区。

单缓冲区工作示意图

如果数据从磁盘写入缓冲区的时间大于CPU处理该数据的时间，一次操作的总时间就是 M + T；如果数据从磁盘写入缓冲区的时间小于CPU处理时间，一次操作的总时间为 C + T。故单缓冲区处理每块数据用时为MAX( C, T ) + M。

双缓冲区 ：设立两个缓冲区，设备输入数据时，先送第一缓冲区，满了后送第二缓冲区。此时可以把第一缓冲区的数据送至CPU进行计算。

双缓冲区工作示意图

双缓冲区处理一块数据的时间为 MAX( C + M, T)。当M+C < T 时，即数据处理时间小于I/O写入数据时间，设备可以连续输入；当 M+C > T 时，CPU不必等待设备输入。

两台机器间通信双向数据传输两台机器中都需要分别设置接受缓冲区和发送缓冲区。

环形缓冲区

环形缓冲区：包含多个大小相等的缓冲区，每个缓冲区中有一个链接指针指向下一个缓冲区，最后一个缓冲区指向第一个缓冲区构成环形。

缓冲池

缓冲池：多个系统共用的缓冲区组成，三个队列：空缓冲队列、装满输入数据的缓冲队列（输入队列）和装满输出数据的缓冲队列（输出队列）。

输入进程要输入时，从空缓冲队列摘下一个空缓冲区，把输入数据写到其中，写满后挂到输入队列队尾；输出进程从输出队列取一个装满数据的缓冲区，当数据提取完后，再将其挂到空缓冲队列队尾。

设备分配与回收

SPOOLing技术

SPOOLing技术式操作系统中采用的一项将独占设备虚拟成共享设备的技术。

SPOOLing

总的来说，SPOOLing的工作路线为：

参考资料：《王道2019考研操作系统》、《计算机操作系统（第四版）》

主存管理与磁盘管理见计算机存储系统

Related Posts

Inger Notes © 2024
rss facebook twitter github gitlab youtube mail spotify lastfm instagram linkedin google google-plus pinterest medium vimeo stackoverflow reddit quora qq quora wechat