操作系统期末复习

1、进程和线程的概念

典型的进程定义有：

（1）进程是程序的一次执行。（2）进程是一个程序及其数据在处理机上顺序执行时所发生的活动。（3）进程是程序在一个数据集合上运行的过程，它是系统进行资源分配和调度的一个独立单位。

2、进程的基本状态及状态转换的原因

状态转换：

① 空 ->新状态 新创建的进程首先处于新状态。

② 新状态 ->就绪状态 当系统允许增加就绪进程时，操作系统接纳新建状态进程，将它变为就绪状态，插入就绪队列中。

③ 就绪状态 -> 执行状态 当处理机空闲时，将从就绪队列中选择一个进程执行，该选择过程称为进程调度，或将处理机分派给一个进程，该进程状态从就绪转变为执行。

④ 执行状态 -> 终止状态 执行状态的进程执行完毕，或出现诸如访问地址越界、非法指令等错误，而被异常结束，则进程从执行状态转换为终止状态。

⑤ 执行状态 -> 就绪状态 分时系统中，时间片用完，或优先级高的进程到来，将中断较低优先级进程的执行。进程从执行状态转变为就绪状态，等待下一次调度。

⑥ 执行状态 -> 阻塞状态 执行进程需要等待某事件发生。通常，会因为进程需要的系统调用不能立即完成，如读文件、共享虚拟内存、等待I/O操作、等待另一进程与之通信等事件而阻塞。

⑦ 阻塞状态 -> 就绪状态 当阻塞进程等待的事件发生，就转换为就绪状态。进入就绪队列排队，等待被调度执行。

3.PCB的作用

进程控制块：进程控制块的作用是使一个在多道程序环境下不能独立运行的程序（包含数据），成为一个能独立运行的基本单位，一个能与其它进程并发执行的进程。

4.进程控制的原语操作

（1）进程的创建原语

调用进程创建原语Create（ ）按下述步骤创建一个新进程

(2)进程的终止原语

正常结束:

批处理中用Holt指令，分时中用Logs off指令

（3）进程的唤醒和阻塞原语

引起进程阻塞的事件:

(1）请求系统服务：提出I/O服务时，并不立即满足该进程的要求时，转变为阻塞状态来等待

(2）启动某种操作：当进程启动某种操作后，在该操作完成之后才能继续执行

(3）新数据尚未到达：对于相互合作的进程而言。

(4）无新工作可做。如发送进程

进程阻塞过程:

(1)正在执行的进程，当发现上述某事件时，由于无法继续执行，于是进程便通过调用阻塞原语block( )把自己阻塞

(2)把进程控制块中的现行状态由“执行”改为“阻塞”，并将PCB插入阻塞队列

(3)转调度程序进行重新调度，将处理机分配给另一就绪进程，并进行切换

进程唤醒过程：

当被阻塞进程所期待的事件出现时，则由有关进程（比如，用完并释放了该I/O设备的进程）调用唤醒原语wakeup（ ），将等待该事件的进程唤醒

(4)进程的挂起和激活过程

5.进程互斥、临界区、进程同步的基本概念、同步准则

进程互斥：

进程互斥是进程之间的间接制约关系。当一个进程进入临界区使用临界资源时，另一个进程必须等待。只有当使用临界资源的进程退出临界区后，这个进程才会解除阻塞状态。

临界资源：

一次仅允许一个进程访问的资源为临界资源 。

临界区：

把在每个进程中访问临界资源的那段代码称为临界区。

进程同步：

进程同步是一个操作系统级别的概念，是在多道程序的环境下，存在着不同的制约关系，为了协调这种互相制约的关系，实现资源共享和进程协作，从而避免进程之间的冲突，引入了进程同步。

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

同步准则：

1)空闲让进

2)忙则等待

3)有限等待

4)让权等待

6.记录型信号量

记录型信号量机制，则是一种不存在“忙等”现象的进程同步机制

记录型信号量的数据结构: 

type  semaphore = record
                  value  ：integer；
                  L：list  of  process；
 end

记录型信号量的wait（S）操作:

procedure  wait（  S  ）
    var  S：  semaphore；
       begin   
           S.value:＝S.value-1;
           if  S.value＜0  then  block（S.L）;
       end
// S.value＜0，该类资源已经分配完毕，进程必须放弃处理机，自我阻塞。

记录型信号量的signal（S）操作:

procedure  signal（S）
  var  S:semaphore； 
  begin
      S.value:＝S.value+1；
      if  S.value≤0  then   wakeup(S.L)；
  end
// S.value≤0 ，在信号量链表中，仍有等待该资源的进程被阻塞。

7.信号量的应用

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

为使多个进程能互斥地访问某临界资源，只须为该资源设置一互斥信号量mutex，并设其初始值为1，然后将各进程访问该资源的临界区CS置于wait（mutex）和signal（mutex）操作之间即可。

利用信号量实现进程互斥的进程可描述如下：

Var  mutex：semaphore:=1；
          begin
          parbegin

             process1：begin
                 repeat
                      wait（mutex）；
                      critica1  section
                      signal（mutex）；
                     remainder  section  until false;
             end
             process2：begin
                        repeat
                            wait（mutex）;
                            critical  section
                            signal（mutex）;
                            remainder section until false；
              end
   parend 
   end

wait（mutex）和signal（mutex）必须成对出现；

缺少wait（mutex）导致系统混乱，不能保证对临界资源的互斥访问；

缺少signal（mutex）会使临界资源永远不释放，等待该资源的进程不能被唤醒。

2.利用信号量实现前趋关系

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；}

void main( ){
    semaphore a,b,c,d,e,f,g;
    a.value=b.value=c.value=0;
    d.value=e.value=f.value=g.value=0;
    cobegin
         p1( ); p2( ); p3( ); p4( ); p5( ); p6( );
    coend;
}

8.经典进程同步问题；生产者与消费者问题

生产者和消费者进程共享一个大小固定的缓冲区，其中，一个或多个生产者生产数据，并将生产的数据存入缓冲区，并有一个消费者从缓冲区中取数据。

假设缓冲区的大小为n（存储单元的个数），它可以被生产者和消费者循环使用

分别设置两个指针in和out，指向生产者将存放数据的存储单元和消费者将取数据的存储单元，如图

image-20230616160458024

1.利用记录型信号量解决生产者一消费者问题

 int  in=0, out=0;
 item    buffer [n];
 semaphore	mutex=1, empty=n, full=0;   
 
void producer( );
void consumer( );

void main( ){
      cobegin
             producer( ); consumer( );
      coend
}
void producer( ){
    do{
      			…
		Produce an item in nextp;
              		…
wait(empty);
wait(mutex);
buffer(in):=nextp;
in:=(in+1) mod n;
signal(mutex);
signal(full);
}while(TRUE);
}
void consumer{
	do{
	      wait(full);
wait(mutex);
nextc:=buffer(out);
out:=(out+1) mod n;
signal(mutex);
signal(empty);
Consumer the item in nextc;
     ……
}while(TRUE);
}

2.利用AND信号量解决生产者—消费者问题

  int  in=0, out=0;
  item    buffer[ n ];
  semaphore   mutex=1;
  semaphore  empty=n, full=0;

  void producer( ){
       do{
			…
		 produce an item in nextp;
			…
		Swait(empty, mutex);
		buffer[in] = nextp;
 in = (in+1) % n;
   Ssignal(mutex, full);
      }while(TRUE);
   } //end producer


void consumer{
   do{
	   Swait(full, mutex);
	   nextc = buffer[out];
	   out = (out+1) % n;
	   Ssignal(mutex, empty);
	   consumer the item in nextc;
     }while(TRUE);
}

9.进程间通信的原理和实现方法 信箱

进程间通信的原理和实现方法

1.共享存储器系统

（1）基于共享数据结构的通信方式。 （2）基于共享存储区的通信方式。

2.消息传递系统

是目前的主要通信方式，信息单位：消息（报文）实现：一组通信命令（原语），具有透明性->同步的实现。

实现方式的不同，而分成:（1）直接通信方式 （2）间接通信方式

3.管道（Pipe）通信

管道：连接一个读进程和一个写进程之间通信的共享文件。

功能：大量的数据发收。注意：（1）互斥（2）同步 （3）对方是否存在

消息传递通信的实现方法

1.直接通信方式

这是指发送进程利用OS所提供的发送命令，直接把消息发送给目标进程。系统提供下述两条通信命令（原语）：

Send （Receiver， message）；

Receive（Sender， message）；

2.间接通信方式

指进程之间利用信箱的通信方式。发送进程发送给目标进程的消息存放信箱；接收进程则从该信箱中，取出对方发送给自己的消息；消息在信箱中可以安全地保存，只允许核准的目标用户随时读取。 系统为信箱通信提供了若干条原语，分别用于信箱的创建、撤消和消息的发送、接收等。

优点：在读/写时间上的随机性写进程 ->信箱（中间实体）->读进程原语

消息的发送和接收

Send (mailbox, message)

Receive (mailbox, message)

信箱

信箱分为以下三类：

（1）私用信箱（2）公用信箱（3）共享信箱

在利用信箱通信时，在发送进程和接收进程之间，存在以下四种关系：

（1）一对一关系。 （2）多对一关系，客户/服务器交互。 （3）一对多关系， 广播方式。（4）多对多关系。

第四章

10.重定位的基本概念：为什么要引入

为解决链接地址跟运行地址不同的问题。

装入内存时，相对地址（数据、指令地址）要作出相应的修改以得到正确的物理地址，这个修改的过程称为重定位。

11.如何提高内存利用率：离散分配、对换机制、动态链接、虚拟存储器、存储器共享

离散分配

离散分配方式的引入：

连续分配方式会产生内/外零头

为解决零头问题又要进行紧凑等高开销活动

什么是离散分配：

程序在内存中不一定连续存放

离散分配的体现:

内存一块可以装入程序一页连续的多个页不一定装入连续的多个块中注：系统中页块的大小是不变的。

离散分配的优点：

没有外零头不受连续空间限制，每块都能分出去仅有小于一个页面的内零头

程序大小一般不是页大小的整数倍

由于进程的最后一页经常装不满一块而形成了不可利用的碎片，称之为“页内碎片”或称为“内零头”。

对换

对换指把内存中暂不能运行的进程或暂时不用和程序和数据，换到外存上，以腾出足够的内存空间，把已具备运行条件的进程，或进程所需要的程序和数据，换入内存。

对换是系统行为，是提高内存的利用率的有效措施。常用于多道程序系统或小型分时系统中，与分区存储管理配合使用。

对换的实现：

可在系统中设一对换进程，以执行换进内存、换出至外存操作。

对换的分类：

“整体对换”（进程对换）：

对换以整个进程为单位，用于分时系统，以解决内存紧张的问题；

“页面对换/分段对换”：

对换以“页”或“段”为单位进行“部分对换”，该方法是实现请求分页及请求分段存储器的基础，支持虚存系统。

为实现对换，系统需要三方面的功能：对换空间的管理、进程的换入、进程的换出

对换空间的管理：

外存被分为两部分，文件区和对换区

文件区用于存放文件，对它的管理应重在如何提高存储空间的利用率。所以对它采取离散分配方式。

对换区存放从内存换出的进程，它们在外存的存放时间较短，换入、换出频繁。对对换区的管理应重在提高进程的换入换出速度。因此采用连续分配方式。

为了能对对换区中的空闲盘块进行管理，在系统中应配置相应的数据结构，以记录外存的使用情况

空闲分区表或空闲分区链。基本单位都是盘块

对换区的分配采用连续分配方式，分配与回收与动态分区方式时内存的分配与回收方法雷同

进程的换出与换入：

换出（swap out）

选择：首先选择阻塞或睡眠状态的进程，若有多个，按优先级由低到高进行选择。若没有此状态进程，则选择就绪状态的，仍然按优先级由低到高进行选择。为避免某进程被频繁的换入换出，还应考虑进程在内存中的驻留时间，优先选择驻留时间长的进程。

换入（swap in）

①从 PCB集合中查找“就绪且换出”的进程，有多个，则选择换出时间最长的。

②根据进程大小申请内存，成功则读入，否则要先执行换出，再换入。

③若还有可换入进程，则转向①。直至无“就绪且换出”进程或无法获得足够内存空间为止。

动态链接

与之相对的静态链接：

在程序运行之前，先将各目标模块及它们所需的库函数，链接成一个完整的装入模块（又称执行模块），以后不再拆开。

装入时动态链接：

用户源程序经编译后所得到的目标模块，是在装入内存时，边装入边链接的。即在装入一个目标模块时，若发生一个外部模块调用，将引起装入程序去找出相应的外部目标模块，并将其装入内存。

优点：

  1. 便于软件版本的修改和更新。只需修改各个目标模块，不必将装入模块拆开，非常方便。
  2. 便于实现目标模块共享。即可以将一个目标模块链接到几个应用模块中，从而实现多个应用程序对该模块的共享。

运行时动态链接(Run-Time Dynamic Linking）：

将某些目标模块的链接推迟到执行时才进行，即在执行过程中，若发现一个被调用模块尚未装入内存时，由OS去找到该模块，将它装入内存，并链接到调用模块上。

优点：执行过程中未被用到的目标模块，都不会被调入内存和被链接到装入模块上，不仅可加快程序的装入过程，而且可节省大量的内存空间

虚拟存储器

虚拟存储器：

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

程序执行的局部性原理：

程序的执行总是呈现局部性。即，在一个较短的时间段内，程序的执行仅限于某个部分；相应的，它所访问的存储空间也局限于某个区域。因此，只要保证进程执行所需的部分程序和数据驻留在内存，一段时间内进程都能顺利执行

局限性又表现在下述两个方面：

(1) 时间局限性

如果程序中的某条指令一旦执行，则不久以后该指令可能再次执行；如果某数据被访问过， 则不久以后该数据可能再次被访问产生时间局限性的典型原因，是由于在程序中存在着大量的循环操作

(2) 空间局限性

一旦程序访问了某个存储单元，在不久之后，其附近的存储单元也将被访问程序在一段时间内所访问的地址，可能集中在一定的范围之内，其典型情况便是程序的顺序执行

虚拟存储器的基本工作情况

1）基于局部性原理。一个作业运行前，仅将那些当前要运行的页面（段）装入内存启动运行，其余暂在外存。

2）若运行所需页面（段）不在内存，则利用请求调页（段）功能将其调入内存。

3）若此时内存满，则利用置换功能，将内存中暂时不用的部分页面（段）调至外存，再将所需页面（段）调入。

4）这样，可实现大程序在小内存中运行，也可实现内存中同时装入更多的进程并发执行。

虚拟存储器的实现方法

一、请求分页系统

它是在纯分页系统的基础上增加了请求调页、页面置换两大功能所形成的页式虚拟存储系统。

为了实现请求调页、页面置换两大功能，系统必须提供如下的硬件支持：

  1. 请求分页的页表机制。
  2. 缺页中断机构。
  3. 地址变换机构。

此外，实现请求调页、页面置换两大功能还需得到OS的支持。

二、请求分段系统

它是在纯分段系统的基础上增加了请求调段、分段置换两大功能所形成的段式虚拟存储系统。

为了实现请求调段、分段置换两大功能，系统必须提供如下的硬件支持：

  1. 请求分段的段表机制。
  2. 缺段中断机构。
  3. 地址变换机构。

此外，实现请求调段、分段置换两大功能还需得到OS的支持。

三、段页式虚拟系统

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

12.动态分区分配方式：分配、回收算法

动态分区分配（可重定位分区分配）是指根据进程的实际需要，动态地为之分配连续的内存空间。即分区的边界可以移动，分区的大小是可变的

分区的数目固定大小是可变的，允许分区的数目和大小都是可变的。

分区分配算法: