admin 管理员组文章数量: 887021
之后会发布基于基础知识的大部分算法的模拟代码合集，敬请关注。
进程基础
进程的基本概念
-
程序顺序执行的特征：
1）顺序性：处理机严格按照程序所规定的顺序执行，每一步操作必须在下一步操作开始前执行
2）封闭性：程序在封闭的环境下运行，程序独占资源，资源的状态由程序决定，程序一旦开始执行，外界环境不会影响程序的执行结果。
3）可再现性：只要程序的初始条件和环境相同，程序的执行结果就相同。
-
程序的并发执行的特征：（顺序执行会浪费资源）
1）间断性：程序共享系统的资源，以及为完成同一个任务共同合作，并发执行的程序之间相互制约，（不是运行完一个在运行另一个）
2）失去封闭性：各程序共享系统资源，资源的状态由各程序所决定。
3）不可再现性：由于失去了封闭性，（即初始的环境状态和条件相同，程序的执行结果却可能不同），该特征超级垃圾，必须想办法避免。
-
进程的概念：
具有独立功能的程序在某一个数据集合上的执行过程，它是系统进行资源分配和调度的一个独立单位。
-
进程的特征：
-
结构特征：
PCB（进程控制块），与进程共存亡，用于记录进程的基本情况和活动过程，一般常驻内存 程序段（一般为需要的时候动态调入内存），描述要完成的功能 数据段（一般为需要的时候动态调入内存），操作的对象即工作区 -
动态性：进程最基本的特征，进程不是静态的，而是动态的，它由创建而产生，由调度（这里主要指进程调度，而不是作业调度）而执行，由撤销而消亡
-
并发性：指多个进程实体存于内存中，且能在同一时间段内执行，（这里同操作系统的并发性）
-
独立性：进程实体是一个能独立运行，独立获得资源和独立接收调度的基本单位
-
异步性：同操作系统的异步性
-
-
进程的三种基本状态：
- 就绪状态：进程已经分配到除了CPU之外的所有资源，只要获得CPU便可以立刻执行，处于就绪状态的进程维持一个就绪队列。
- 执行状态：已经获得CPU，正在执行的进程。（单处理机系统中，同一时刻只能有一个进程处于执行状态，多处理机系统中，可以同时有多个进程处于执行态）
- 阻塞状态/等待状态：在执行的过程中由于发生某些事件（I/O请求，申请缓存等），暂时无法执行的进程，是由于进程本身引起的阻塞。处于阻塞状态的进程可以维持一个阻塞队列。
- 进程是自己阻塞自己的，但是阻塞的进程需要其他进程将其唤醒
-
三种基本状态的转换：
就绪—>执行：进程调度，获得CPU资源
执行—>就绪：在分时操作系统中时间片花完
执行—>阻塞：I/O请求，申请缓存等，自己被迫进入阻塞状态
阻塞—>就绪：I/O完成，造成阻塞的原因得到解决（又变成只差CPU的状态）
-
进程的创建状态和终止状态
创建状态：进程成为就绪状态之前的状态
终止状态：当一个进程到达了自然结束点，或者遇到无法客服的困难，或者被操作系统所终结等的时候，就进入了终止状态。
-
挂起操作及引入的原因：
1）进程被挂起之后处于静止状态。
2）引入的原因：
- 终端用户的需要：当终端用户想要暂停自己程序的运行的时候
- 父进程请求：当父进程想要挂起某个子进程的时候
- 负荷调节的需要：当实时系统中的工作负荷较重，系统可以将某些不重要的进程挂起，保证程序的正常运行。
- 操作系统的需要：操作系统有事需要将某些进程挂起，已检查运行过程中资源的使用情况
3）引入挂起操作后，进程的状态转换：
（1）阻塞态可以通过释放变为就绪态。活动阻塞释放变为活动就绪，静止阻塞释放变为静止就绪。
（2）活动态和静止态可以进行相互转换，活动到静止称为挂起，静止到活动可以称为激活。活动态和静止态最本质的区别为活动态在内存中，静止态暂时调出内存，进入外存
（3由执行态可以直接变为静止就绪态，即时间片用完，直接调离内存
（4）静止态（外存）必须通过激活变为非静止态（调入内存）才能够参与进程的三台转换。
4）进程挂起之后不是原封不动的将进程移出内存，而是会先将一些必要的信息写入外存。再释放PCB
-
进程管理中的数据结构
-
操作系统中用于管理控制的数据结构：内存表，设备表，文件表，进程表（程序控制快PCB）
-
进程控制块PCB的作用：
1）作为独立运行基本单位的标志
2）能实现间断性的运行方式
3）提供进程管理所需要的全部信息
4）提供进程调度所需要的全部信息
5）实现与其他进程的同步和通信
-
进程控制块中的信息：
进程标识符：唯一表示一个进程，有两种：
1）外部标识符：方便用户对进程的访问，通常有数字和字母组成
2）内部标识符：方便系统对进程的访问，每一个进程有一个唯一的数字标识符。
处理机状态：（主要指的是处理机中寄存器的状态）
1）通用寄存器：又称为用户寄存器，用户的程序可以访问，用于暂存信息，一般为8~32个
2）指令计数器：存放了将要访问的下一条指令的地址。
3）程序状态字（PSW）：含有状态信息，条件码，执行方式（指在系统还是用户状态下执行），中断屏蔽标志（允不允许在执行的过程中被打断）
4）用户栈指针：每个用户进程都有系统栈，用于存放过程和系统调用参数及调用地址。
进程调度信息
1）进程状态：指明了进程的当前状态
2）进程优先级：即一个整数，用于描述进程使用CPU的优先级，数字越大，优先级越高
3）其他信息：与采用的进程调度算法有关
4）事件：指进程由执行状态变为阻塞状态所等待发生的事件。
进程控制信息
1）程序和数据的地址：由于程序段和数据段并不是常驻内存的，而是使用的时候才调入，因此需要保存其地址
2）进程同步和通信机制：
3）资源清单：一张清单列出了该进程在运行期间所需的全部资源（除了CPU资源），另一张列出了分配到该进程的资源的清单。
4）链接指针：给出了本进程（PCB）所在队列中的下一个进程的PCB的首地址。
-
进程控制块的组织方式：
线性方式：不重要
链接方式：类似静态链表，把具有同一状态的PCB用其中的链接字链接成一个队列
注：进程资源的分配并不是在该进程执行之前将该进程所需的资源全部分配给他，而是在其执行的过程中进行动态的分配。
-
进程与程序的区别与关系
- 进程与程序的区别：
- 进程是一个动态的概念（有 “ 生命 ” ），程序是静态的概念。
- 进程可以具有并行性（在多处理器的系统中），但是程序没有
- 进程是竞争系统资源的基本单位
- 进程与程序的关系：
- 一个程序对应多个进程，一个进程又可以为多个程序服务。
进程控制
1.基本知识
- 进程控制是进程管理中最基本的功能，主要包括进程的创建，进程的终止和运行中的进程的状态转换等功能。进程控制一般是由OS的内核中的原语来实现的。
2.进程的创建
-
进程的层次结构
-
进程图
-
引起进程创建的事件
1）用户登录：在分时系统中，用户成功登录，系统将为该用户分配新的进程
2）作业调度：在多道批处理系统中，作业调度程序将某些作业调度内存，并且为他们创建进程
3）提供服务：运行中的用户程序提出某种请求
4）应用请求：由用户进程自己创建，帮助自己完成特定的任务
-
==进程的创建过程：==OS调用进程创建原语Create创建一个新进程
1）申请空白PCB：新进程获得一个唯一的数字标识符（对于操作系统）
2）为新进程分配器运行所需的资源：包括物理资源和逻辑资源
3）初始化进程控制块PCB：
（1）初始化标识符信息：系统分配的标识符信息装入PCB
（2）初始化处理机状态信息：主要为一些寄存器
（3）初始化处理机控制信息：一般初始化为就绪状态
（4）如果进程就绪队列允许，将进程插入就绪队列
3.进程的终止
-
引起进程终止的事件：
1）正常结束
2）异常结束：1）越界错误（访问自己范围外的），2）保护错误（访问自己无权利访问的）3）非法指令：试图运行不存在的指令，4）特权指令；5）运行超时；6）等待超时；7）算术运算错；8）I/O故障
3）外界的干预：1）操作员或者操作系统干预；2）父进程的请求（父进程的权利大于子进程）3）父进程的终止：当父进程终止时，其所有子进程也应当终止。
-
==进程终止的过程：==OS调用进程终止原语
1）根据要终止的进程的标识符，搜索出该进程的PCB，从中获得该进程所处的状态
2）如果该进程正处于执行状态，立刻终止该进程，并且置调度标志为真，表示在该进程结束后应该进行重新调度（即不要让CPU空闲）
3）若该进程有子孙进程，让其所有子孙进程都终止。
4）被终止进程所拥有的所有资源归还给父进程或者操作系统
5）将终止进程的PCB从所在队列中移除，等待其他程序来收集信息。
4.进程的阻塞与唤醒
-
引起进程阻塞和唤醒的事件：阻塞和唤醒是相对应的
1）向系统请求共享资源失败
2）等待某种操作的完成
3）新数据尚未到达
4）等待新任务的到达
-
进程阻塞的过程：进程通过调用阻塞原语block==将自己==阻塞
1）进入block后立即停止执行
2）保存现场
3）将进程控制块中的现行状态改为阻塞，并将PCB插入阻塞队列
4）转调度程序，进行重新调度
-
进程唤醒的过程：当阻塞的进程所期待的事件发生时，有关进程（不是本身）调用唤醒原语wakeup，将等待该事件的进程唤醒。唤醒之后进入就绪队列。
1）将被阻塞的进程从等待该事件的阻塞队列中移除
2）将PCB的现行状态由阻塞改为就绪
3）然后再将该PCB插入就绪队列中
4）转进程调度或者返回
-
block原语和wakeup原语是一对作用刚好相反的原语，必须成对使用。
5.进程的挂起与激活
-
进程的挂起过程：当出现了引起进程挂起的事件之后，OS利用挂起原语将指定的进程挂起（即调出内存）
首先检查进程的状态（不同的状态采取不同的处理方式），若该进程正处于活动就绪状态，将其改为静止就绪态；若该进程处于活动阻塞状态，将该进程改为静止阻塞状态；若该进程处于执行状态，将其改为静止就绪状态，调度程序重新进行调度。
-
进程的激活过程：
1）首先将进程从外存调入内存，
2）检查进程所处的状态，如果进程处于静止就绪，将其改为活动就绪，如果处于静止阻塞，将其改为活动阻塞
3）检查进程的优先级，如果优先级高，可以进行抢占当前运行进程的资源
4.进程同步
1.进程同步的基本概念
-
进程同步的目的：1）按照一定的规则共享系统资源；2）对多个相关进程在执行次序上进行协调，是程序具有可再现性。
-
两种形式的制约关系：
1）间接相互制约关系：多个进程在并发执行时，由于共享系统的临界资源而相互制约，如磁带机，打印机，表格等。（互斥）
2）直接相互制约关系：多个进程为完成同一任务而相互合作（同步）
-
**临界资源：**一次仅允许一个进程使用的共享资源。例如打印机，磁带机，表格等。
-
互斥和同步的概念：
1）互斥：并发的多个进程由于竞争同一资源而产生的相互排斥的关系
2）同步：进程间共同完成一项任务时直接发生相互作用的关系
-
临界区：每个进程中访问临界资源的那段代码
/*一个访问临界资源的循环进程*/
while(true)
{
进入区：//对欲访问的临界资源进行检查，查看其是否正被访问，如果此刻临界资源未被访问，进程便可以进入临界区对临界资源进行访问，并设置它正被访问的标志，如果此刻临界资源正被访问，则不能进入临界区。即后边的wait（）操作
临界区：//执行临界资源的那段代码
退出区：//将临界区正被访问的标志恢复为未被访问的标志，signal（）操作
剩余区：//除上述三个区之外的代码叫做剩余区
}-
同步机制应遵循的原则：
1）空闲让进
2）忙则等待
3）有限等待：不能一直等
4）让权等待：进程不能进入临界区，就应当释放==处理机==，让权指让出处理机
2.硬件同步机制
3.信号量机制：Dijkstra提出
-
信号量：
- 是一种数据结构
- 值与相应资源的使用情况有关
- 仅与P，V操作有关，P，V代表两种原子操作，P为等候原语wait（S）,V为释放原语signal（S）。
- wait操作即在申请资源，signal操作是释放资源
- wait操作其实就是进入临界区之前的进入区，signal操作是从临界区出来之后的退出区
- 原子操作的特点，操作一开始执行，半中间不可以打断，原语即为原子操作。
-
整型信号量
- 概念：Dijkstra把整型信号量定义为一个用于表示资源数目的整型量S。
/*等候原语*/ wait(S){ while(S <= 0); //当S<=0的时候便一直处于等待状态，直到获得相应的资源，不符合让权等待的原则 S--; //获得资源后，资源的数目减一，S表示该类资源可用的数目 } /*释放原语*/ signal(S){ S++; //释放资源后，资源的数目加一 }-
优缺点：
优点：实现简单
缺点：违背了同步机制中的让权等待原则，浪费资源（只要S<=0，就会等待）
-
**记录型信号量：**当前用的最多的
- 特点：采用了记录型的数据结构
/*记录型数据结构*/ typedef struct{ int value; //>=0的时候，表示系统中可用资源的数量，<0的时候其绝对值表示因为该资源而阻塞的进程的数目 struct process_control_block *list; //维持阻塞队列的指针 }semaphore; /*等待原语*/ wait(semaphopre *S){ S->value--; //一个进程过来，首先将S->value--； if(S->value < 0){ //<0表示资源已经用光，将该进程加入阻塞队列 block(S->list); } } /*释放原语*/ signal(semaphore *S){ S->value++; //释放资源，S->value++； if(S->value <= 0){ //S->value++之后，还<=0，直接唤醒一个阻塞的进程，唤醒的进程拥有了该资源的使用权（不需要再次执行P操作），然后进入就绪队列。如果>0，直接将资源释放即可 wakeup(S->list); } }-
wait操作：每次都相当于进程请求一个单位的该类资源
signal操作：每次都相当于释放一个单位资源
-
当S->value的初值为1的时候，表示只允许一个进程访问临界资源，信号量转化为互斥型信号量
-
优点：通过维持阻塞队列的指针，使得满足了让权等待的原则，弥补了整型信号量的缺点
-
**缺点：**只适用于对单一资源的管理，如果一个进程需要请求多类资源的时候，很容易产生死锁。
-
AND型信号量：解决记录型信号量会发生的死锁的问题
- 当一个进程需要两个或者更多的共享资源来完成一个目标的时候，多个进程之间可能会发生阻塞（刚开始前半部分资源占有了，但是后半部分资源无法获得，自己再阻塞自己，即发生了死锁）
- AND的解决思想：将一个进程运行过程中所需要的全部资源一次性都分给他，待进程使用完之后，在一起进行释放。（即一起申请，一起释放）
/*等候原语：全分配*/ Swait(S1, S2, …, Sn) { While(TRUE) { //多类资源同时满足的时候才进行分配，先判断再分配。 if (S1 >=1 and … and Sn>=1 ){ for( i=1 ;i<=n; i++) Si - -; break; } else{ Place the process in the waiting queue associated with the first Si found with Si <1,and set the progress count of this process to the beginning of Swait operation （将即将阻塞的进程挂到第一个不能满足他的资源的阻塞队列，然后设置该进程的起始地址为Swait操作的开始） } } } /*释放原语：全释放*/ Ssignal(S1, S2, …, Sn){ while(TRUE){ for (i=1; i<=n; i++) { Si++ ; Remove all the process waiting in the queue associated with Si into the ready queue（将因为该资源得不到满足而阻塞的所有进程都从阻塞队列释放进入就绪队列，重新进行排队） } } }注意：
1）在分配资源的时候首先判断是否所有资源均全部满足相应的条件，满足才进行分配。
2）释放的时候是将因为该资源得不到满足而阻塞的所有进程都从阻塞队列释放进入就绪队列，重新进行排队，因为OS需要根据调度算法重新选取新的进程占据CPU
-
信号量集
Swait(S1, t1, d1; …; Sn, tn, dn)
if (S1>= t1 and … and Sn>= tn) then
for i:=1 to n do
Si:= Si - di ;
endfor
else
Place the executing process in the waiting queue of the first Si with Si < ti and set its program counter to the beginning of the Swait Operation
endif注意：
1）继承了AND型信号量的思想，先判断是否所有所需资源均满足条件。满足才进行分配。
2）引入了下限值的概念。Si表示可用的资源的数量；ti表示想要分配资源成功至少需要的该资源的数目（ti（下限值）包括两部分，一部分是系统执行该进程所需，另一部分是该进程所请求的，因此一般大于di）；di表示该进程所请求的该类资源的数目。
4.信号量的应用
1、利用信号量实现进程互斥
semaphore mutex =1;
begin
parbegin
process 1: begin
repeat
wait(mutex);
critical section
signal(mutex);
remainder section
until false;
end
process 2: begin
repeat
wait(mutex);
critical section
signal(mutex);
remainder section
until false;
end
parend
end注意：
1）利用信号量实现进程互斥地访问某种资源。首先应将mutex设为1
2）wait操作和signal操作必须成对地出现，如果缺少wait操作可能会造成系统的混乱；如果缺少signal操作，那么该资源永远不会得到释放，因该资源而被阻塞的进程也将永远不会被唤醒。
2、利用信号量实现前驱关系图（进程同步）
如下图：
semaphore a, b, c, d, e, f, g = 0, 0, 0, 0, 0, 0, 0;
begin
parbegin
begin S1; signal(a); signal(b); end;
begin wait(a); S2; signal(c); signal(d); end;
begin wait(b); S3; signal(e); end;
begin wait(c); S4; signal(f); end;
begin wait(d); S5; signal(g); end;
begin wait(e); wait(f); wait(g); S6; end;
parend
end注意：
1）信号量的初值必须被设置为0，必须等某个进程之前的进程完之后，释放资源，后边的进程才能够执行。
经典的进程同步问题
普通版：一类进程作为生产者，生产产品，生产的产品放入一个缓冲区，消费者从缓冲区中取出产品，需要保证生产者不可以向满的缓冲区中添加产品，消费者不可以从空的缓冲区中取出产品。同一时刻只可以有一个生产者生产产品或者消费者消费产品。
升级版可以实现同一个时刻既有生产者生产产品，又有消费者消费产品。但是绝对不可以同一时刻多个生产者生产产品或者多个消费者消费产品。同时使用count记录缓冲区中产品的数量。
-
生产者消费者问题
1）生产者进程和消费者进程都以异步方式运行， 但它们之间必须保持同步。
2）可利用互斥信号量$mutex$实现诸进程对缓冲池的互斥使用（不可以同时既向缓冲区中放入数据，又从缓冲区中拿出数据）；利用资源信号量empty和full分别表示缓冲池中空缓冲池和满缓冲池的数量。 假定这些生产者和消费者相互等效
/* in表示放入数据的地址，out表示取出数据的地址 buffer[n]：表示大小为n的缓冲池（由多个缓冲区组成） mutex，mutex1，mutex2：互斥型信号量，初值为1 empty，full：资源型信号量，empty表示空缓冲区的数量，full表示满缓冲区的数量 item：表示一个数据项 */ Int in=0,out=0; Item buffer[n]; Semaphore mutex1=1,mutex2 = 1,empty=n,full=0; //生产者 Void producer(){ do{ 生产一个产品放入nextp; /* * 进入区 * 先申请资源信号量，在申请互斥信号量 * mutex1控制同一个时间段内只能有一个生产者生产产品 */ wait(empty); wait(mutex1); /*临界区*/ buffer[in]=nextp; in=(in+1) % n; /*退出区*/ signal(mutex1); signal(full); /*对计数器count的互斥访问*/ wait(mutex); count++; signal(mutex); }while(TRUE) } //消费者 Void consumer(){ do{ /*进入区*/ wait(full); wait(mutex2); //消费者对缓冲区的互斥访问 /*临界区*/ nextc =buffer[out]; //只有一份 out =(out+1) mod n; /*退出区*/ signal(mutex2); signal(empty); /*对计数器count的互斥访问*/ wait(mutex); count--; signal(mutex); 消费 nextc中的产品; }while(TRUE) } Void main(){ cobegin proceducer(); consumer(); coend }注意：
1）每个程序的互斥操作wait（）和signal（）必须成对的出现。
2）输入进程不可以向满的缓冲池中输入数据，计算进程不可以从空的缓冲池中取数据
3）在每个程序中的多个wait操作顺序不能颠倒，必须先执行对资源信号量的wait操作，在进行对互斥信号量的wait操作，否则可能引起进程死锁。
4）可以使用三个互斥信号量mutex、mutex1、mutex2实现同一时刻既有生产者生产，又有消费者消费。
-
读者—写着问题
该问题涉计两类进程，第一类进程是读进程Reader，另一类进程是写进程Writer，多个读进程可以同时读一个文件（共享资源），多个写的进程不可以同时写一个文件（对写互斥），并且读的时候不能写，写的时候不能读（对读互斥）。
1）问题核心：保证一个Writer进程必须与其他进程互斥地访问共享对象的同步问题。
2）只要求读文件的进程称为“Reader进程”，其它进程则称为“Writer进程”。
3）允许多个进程同时读一个共享对象，但不允许一个Writer进程和其他Reader进程或Writer进程同时访问共享对象（共享对象并不是临界资源，因为他允许多个进程对其访问）
/* 记录型信号量解决读者—写者问题 rmutex：读进程对Readcount的互斥 wmutex：writer对reader和writer的互斥 readcount：表示正在读的进程数目，只有当readcount=0的时候才需要申请wmutex权限，大于0的时候不需要 */ semaphore rmutex=1, wmutex =1; int readcount =0; Void Reader(){ do{ wait(rmutex); //防止多个reader进程对readcount的访问 if (Readcount==0){ //如果readcount不等于0，表示有进程正在进行读操作，绝对没有写操作 wait(wmutex); } Readcount ++; signal(rmutex); … 读; … wait(rmutex); Readcount - -; if (Readcount==0){ //只有等于0的时候才需要释放资源，使得写进程可以工作 signal(wmutex); } signal(rmutex); }while(TRUE); } Void writer(){ do{ wait(wmutex); //申请写权限的资源 写; signal(wmutex); }while(TRUE); } Void main(){ cobegin reader(); writer(); Coend }利用信号量集的机制实现读者-写者问题
int RN; semaphore L = RN; //表示读者的数量 mx = 1； //对写者进行互斥的访问 void Reader(){ while(true){ Swait(L, 1, 1); //申请一个读者进程 Swait(mx, 1, 0); //判断当前是否有写者进程在写，该出相当于一个开关 operation... Ssignal(L, 1); } } void Writer(){ while(true){ //此处首先申请一个mx，如果当前系统中无写者进程，则该语句必定执行成功，Reader进程中的 //Swait（mx, 1, 0）便处于关闭状态，只需要等系统中的读进程执行完毕，(L, RN，0)执行成 //功，打开开关即可。 Swait(mx, 1, 1; L, RN, 0); operation...； //释放一个写进程 Ssignal(mx, 1); } } void main(){ cobegin Reader(); Writer(); coend; } -
哲学家的进餐问题
五个哲学家共用一张圆桌，分别坐在周围的五张椅子上，在桌子上有五只碗和五只筷子，他们的生活方式是交替地进行思考和进餐。平时，一个哲学家进行思考，饥饿时便试图取用其左右最靠近他的筷子，只有在他拿到两只筷子时才能进餐。进餐毕，放下筷子继续思考。
/* 记录型信号量解决问题 */ //每一只筷子均为临界资源 semaphore chopstick[5]={1,1,1,1,1}; //所有的信号量均被初始化为1，第i位哲学家的活动可描述为： do{ wait(chopstick[i]); //拿左手的筷子 wait(chopstick[(i+1) mod 5] ); //拿右手的筷子 … eat; … signal(chopstick[i]); //放左手 signal(chopstick[(i +1)mod 5]); //放右手 … think; }while(TRUE);存在的问题：假如五位哲学家同时饥饿而各自拿起左边的筷子时，就会使五个信号量chopstick均为0，当他们再试图去拿右边的筷子时，都将因无筷子可拿而无限等待。进入死锁状态。
解决办法：
**1）**至多只允许有四位哲学家同时去拿左边的筷子，最终能保证至少有一位哲学家能够进餐，并在用毕后释放出他用过的两只筷子，从而使更多的哲学家能够进餐。
semaphore chopstick[5]={1，1，1，1，1}; semaphore count=4; void philosopher(int i) { while(true) { think(); wait(count); //请求进入房间进餐 wait(chopstick[i]); //请求左手边的筷子 wait(chopstick[(i+1)%5]); //请求右手边的筷子 eat(); signal(chopstick[(i+1)%5]); //释放右手边的筷子 signal(chopstick[i]); //释放左手边的筷子 signal(count); //退出房间释放信号量 } }**2）**仅当哲学家的左右两只筷子均可用时，才允许他拿起筷子进餐。
/* 使用AND型信号量解决，本质当同时拥有两只筷子的时候才允许拿起筷子进餐 */ semaphore chopstick[5]={1,1,1,1,1}; Philosopher i do{ think; Swait(chopstick[(i+1)mod 5],chopstick[i ]); //同时分配两只筷子 eat; Ssignal(chopstick[(i+1)mod 5], chopstick[i ] ); //同时放下两只筷子 }while(TRUE)**3）**规定奇数号哲学家先拿他左边的筷子，然后再去拿右边的筷子；偶数号哲学家则相反。
semaphore chopstick[5]={1,1,1,1,1}; //第i 位哲学家的活动可描述为： do{ //奇数位哲学家先拿左手的筷子 if i mod 2=1 { wait(chopstick[ i ]); wait(chopstick[ ( i +1) mod 5] ) } //偶数位哲学家先拿右手边的筷子 else { wait(chopstick[ ( i +1) mod 5] ); wait(chopstick[ i ]) } eat; signal(chopstick[ i ]); signal(chopstick[(i +1)mod 5]); … think; }while(TRUE)
处理机调度
- 调度层次
- 高级调度（作业调度）
- 中级调度（进程调度）
- 低级调度
- 作业调度
- FCSF先来先服务，作业等待时间得长短。比较有利于长作业（进程），而不利于短作业（进程）。
- SJF短作业优先，作业的运行时间。
- 优点：能有效的降低作业的平均等待事件，提高系统吞吐量。
- 缺点：对长作业不利；该算法完全未考虑作业的紧迫程度，因而不能保证紧迫性作业（进程）会被及时处理；由于作业（进程）的长短含主观因素，不一定能真正做到短作业优先。
-
- 高响应比优先
优先权=等待时间+要求服务时间/要求服务时间
-
- RR轮转调度算法，时间片的确定要适中
- 多级反馈队列
- EDF最早截至时间优先
下图中有两个周期性任务，任务A的周期时间为20ms，每个周期的处理时间为10ms；任务B的周期时间为50ms，每个周期的处理时间为25ms
-
- LLF最低松弛度优先
松弛度=必须完成时间-其本身的运行时间-当前时间
进程切换条件：有任务完成；有任务松弛度降到0。
- 死锁
- 定义：是指多个进程在运行过程中因为争夺资源而造成的一种僵局，当进程处于这种状态时，若无外力作用，他们都将无法再向前推进
- 原因：竞争资源（不可抢占资源，可消耗资源），进程间推进顺序非法。
- 产生死锁得必要条件：互斥条件、请求和保持条件、不可抢占（不可剥夺）条件、环路等待条件
- 处理死锁的基本方法：
- 预防死锁：破坏产生死锁得必要条件，其中破坏互斥条件是最不实际的
- 破坏“请求和保持”条件：系统规定所有进程在开始运行之前，都必须一次性的申请其在整个运行过程所需的全部资源
- 破坏“不剥夺”条件
- 破坏“环路等待”条件：所有进程对资源的请求必须严格按照资源序号递增的次序提出
- 预防死锁：银行家算法、安全性算法
- 检测死锁：资源分配图，死锁定理
- 解除死锁：剥夺资源（从其他进程剥夺足够数量的资源给死锁进程以解除死锁状态。），撤销进程（最简单的是让全部进程都死掉；温和一点的是按照某种顺序逐个撤销进程，直至有足够的资源可用，使死锁状态消除为止。）
- 预防死锁：破坏产生死锁得必要条件，其中破坏互斥条件是最不实际的
- 银行家算法
- 安全状态
-
- 银行家算法
T0时刻的安全性：用安全性算法对T0时刻的资源分配情况进行分析，存在着一个安全序列{P1,P3,P4,P2,P0}，故系统是安全的
P1发出资源请求向量Request1(1,0,2)，系统按银行家算法检查:
（1）Request1(1,0,2)<=Need1(1,2,2)
（2）Request1(1,0,2)<=Available1(3,3,2)
（3）系统先假定可为P1分配资源，并修改向量Available，Allocation1，Need1
（4）再利用安全性算法检查此时系统是否安全。如下表:
由安全性检查得知，能找到一个安全序列{P1,P3,P4,P0,P2}，因此，系统是安全的，可以立即将P1所申请的资源分配给它。
死锁定理：S状态为死锁状态的充分条件是当且仅当S状态的资源分配图是不可完全简化的。<死锁定理>
存储器
重定位
程序的装入
- 绝对装入方式
- 可重定位的装入方式（静态）
- 动态运行时装入方式（动态）重定位寄存器
内存的分配方式
- 连续的分配方式
- 离散的分配方式
连续的分配方式
- 单一连续分配：一道程序在内存中，内存浪费严重
- 固定分区分配：程序变多缺点：会产生内碎片
- 动态分区分配（重点）不能消除外碎片 思想：按需分配
- 可重定位的分区分配
- 在动态分区分配方式上增加一个紧凑（拼接碎片）功能
- 以动态运行时装入方式为前提
动态分区分配算法
首次适应算法FF
FF算法要求空闲分区表以地址递增的次序排列。在分配内存时，从表首开始顺序查找，直至找到一个大小能满足要求的空闲分区为止；然后按照作业的大小，从该分区中划出一块内存空间分配给请求者，余下的空闲分区仍留在空闲分区表中。若从头到尾不存在满足要求的分区，则分配失败。
优点：优先利用内存低址部分的内存空间
缺点：低址部分不断划分，产生小碎片（内存碎块、内 存碎片、零头）；每次查找从低址部分开始，增 加了查找的开销
循环首次适应算法NF
在分配内存空间时，从上次找到的空闲分区的下一个空闲分区开始查找，直到找到一个能满足要求的空闲分区，从中划出一块与请求大小相等的内存空间分配给作业。
优点：使内存空闲分区分布均匀，减少查找的开销
缺点：缺乏大的空闲分区
最佳适应算法BF
所谓“最佳”是指每次为作业分配内存时，总是把能满足要求、又是最小的空闲分区分配给作业，避免“大材小用”。要求将所有的空闲分区按其容量以从小到大的顺序形成一空闲分区链。
缺点：产生许多难以利用的小空闲区
离散的分配方式
分页存储管理方式
（可能在最后一页产生内碎片）进程分页，内存分块（页和块等大小）
页表
页式地址映射
（逻辑地址转换城物理地址）
地址转换机构（页表在内存，页表寄存器快表。页表很庞大时采取两级或多级页表）
有快表有页表，先查快表；没有快表查页表
分段存储管理方式
（不可能有内碎片产生，外碎片不可避免）进程分段，各段在内存。段与段之间离散分配，某一段在内存中连续分配
计算：给定逻辑地址合成物理地址段表
段页式存储管理方式
进程分段，段内分页，内存分块
-
- 分页和分段的主要区别
相似点：采用离散分配方式，通过地址映射机构实现地 址变换
不同点：页是信息的物理单位，分页是为了满足系统的 需要；段是信息的逻辑单位，含有一组意义相对完 整的信息，分段是为了满足用户的需要。
页的大小固定且由系统确定，由系统把逻辑地址分为页号和页内地址，由机器硬件实现；段的长度不固定，取决于用户程序，编译程序对源程序编译时根据信息的性质划分。
分页的作业地址空间是一维的；分段的作业地址空间是二维的。
输入输出系统
I/O设备：输入输出和存储功能的设备
I/O设备的分类
按传输的速度：
低速设备（如键盘、鼠标、语音输入输出设备） 中速设备（如行式打印机、激光打印机等）
高速设备（如磁带机、磁盘机、光盘机等）。
设备按信息交换的单位分类
块设备：用于存储信息。对于信息的存取总是以数据块为单位。典型例子是磁盘。该类设备基本特征是传输速率较高，另一特征是可寻址。
字符设备：用于数据的输入和输出。基本单位是字符。如交互式终端、打印机等。其基本特征是传输速率较低，另一特征是不可寻址。
设备按其共享属性分类
独占设备：指在一段时间内只允许一个用户、进程访问的设备，即临界资源。应互斥的访问之。
共享设备：指在一段时间内允许多个进程同时访问的设备。对每一时刻而言仍然是一个进程访问。如磁盘。
虚拟设备：指通过虚拟技术将一台独占设备变换为若干台逻辑设备，供若干个用户（进程）同时使用。
设备按其使用特性分类：
存储设备、输入＼输出设备
I/O通道
其主要目的是为了建立独立的I/O操作，去解放CPU。在设置通道后，CPU只需向通道发送一条I/O指令。通道完成任务后向CPU发中断信号。
控制功能：CPU与设备控制器
数据传输：内存与外设
I/O控制方式
- 程序I/O方式，使用轮询的可编程I/O方式。CPU浪费
- 终端驱动I/O方式，使用中断的可编程I/O方式。CPU用较短的时间进行中断处理。
- 直接存储器访问方式(MDA),以数据块为单位，高效。缺点：不连续的数据块，不能一次处理
- I/O通道控制方式，通道时硬件，配合着通道程序
设备分配
- 前提：大中型计算机
- DS：设备控制表、控制器控制表、通道控制表、系统设备表
- 独占设备分配步骤：分配设备、分配控制器、分配通道
SPOOLing技术（假脱机）
定义
为缓和CPU的高速性与I/O设备低速性间的矛盾而引入了脱机输入、脱机输出技术。该技术是利用专门的外围控制机，将低速设备上的数据传送到高速磁盘上；或者相反。这样就可以在主机的直接控制下实现脱机输入输出。此时外围操作与CPU对数据的处理同时进行，我们把这种在联机情况下实现的同时外围操作称为SPOOLing（Simultaneaus Periphernal Operating On—Line），或称为假脱机操作。
组成
- 输入井和输出井。是磁盘上开辟的两个大存储空间。输入井模拟脱机输入的磁盘设备，输出井模拟脱机输出时的磁盘。
- 输入缓冲区和输出缓冲区。在内存中开辟两个缓冲区，输入缓冲区暂存由输入设备送来的数据，后送输入井；输出缓冲区暂存从输出井送来的数据，后送输出设备。
- 输入进程和输出进程。利用两个进程模拟脱机I/O时的外围处理机。
- 井管理程序。用于控制作业与磁盘井之间信息的交换。
特点
- 提高了I/O的速度。利用输入输出井模拟成脱机输入输出，缓和了CPU和I/O设备速度不匹配的矛盾。
- 将独占设备改造为共享设备。并没有为进程分配设备，而是为进程分配一存储区和建立一张I/O请求表。
- 实现了虚拟设备功能。多个进程同时使用一台独占设备，虚拟成了多台设备。
- 打印机是独占设备，通过虚拟技术实现“共享”的模拟
- 缓冲区管理
- 引入
- 缓和CPU与I/O设备间速度不匹配矛盾。
- 减少对CPU的中断频率，放宽对CPU中断响应时间的限制
- 提高CPU和I/O设备之间的并行性。
方法
- 单缓冲（效率低）
- 双缓冲区（效率比较高，当输入输出速度不匹配时效率受影响）
- 循环缓冲区（解决输入和输出速度相差甚远的影响）
- 缓冲池（解决多进程缓冲过程中内存利用率的问题）
磁盘管理
9个进程先后提出读盘请求访问的磁道号为：55；58；39；18；90；160 150 38 184目前磁头停留在100道。
先来先服务（FCFS）
- 优点：公平、简单
- 缺点：未对寻道进行优化
最短寻道时间优先（SSTF）
- 优点：寻道优化
- 缺点：可能导致某些进程发生“饥饿”。
扫描SCAN算法
- 优点：较好的寻道性能
- 缺点：“不巧”的进程严重推迟
循环扫描算法CSCAN
- 优点：进程的延迟变小了
FSCAN算法本算法是N-Step-SCAN算法的简化。
文件管理
版权声明：本文标题：超硬核！操作系统学霸笔记，考试复习面试全靠它 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.freenas.com.cn/jishu/1728431547h1242860.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。
发表评论