OS笔记

操作系统的四大特征：并发、虚拟、共享和异步。

操作系统所具有的五大功能：处理机管理、存储器管理、设备管理、文件管理和用户接口。

进程

•结构特征

为使程序能并发执行，应为之配置一进程控制块，即PCB。进程实体由程序段、相关的数据段和PCB三部分构成。创建进程实质上就是创建进程实体中的PCB，撤销进程实质上就是撤销进程的PCB。

进程控制块的作用：

进程控制块是进程存在的标志，当系统或父进程创建一个进程时，实际上就是为其建立一个进程控制块。

进程控制块既能标识进程的存在，又能刻画出进程的动态特征，它是一个进程仅有的被系统真正感知的部分。对操作系统而言，所有进程控制块将构成并发执行控制和维护系统工作的依据。

进程控制块中的信息

•进程标识符

进程标识符用于唯一地标识一个进程。

（1）内部标识符。在所有的操作系统中，都为每一个进程赋予一个唯一的数字标识符，它通常是一个进程的序号。

（2）外部标识符由创建者提供，通常是由用户在访问该进程时使用。

•处理机状态

处理机状态信息主要是由处理机的各种寄存器中的内容组成的。处理机运行时，许多信息都存放在寄存器中。当处理机被中断时，所有这些信息都必须保存在PCB中，以便该进程重新执行时，能从断点继续执行。这些寄存器包括：

通用寄存器：用于暂存信息；

指令计数器：存放了要访问的下一条指令的地址；

程序状态字PSW:其中包含了状态信息，如条件码、执行方式、终端屏蔽标志等；

用户栈指针：每个用户进程都有一个或若干个与之相关的系统栈，用于存放过程和系统调用参数及调用地址。

•进程调度信息

在PCB中还存放一些与进程调度和进程对换有关的信息，包括：

进程状态指明进程的当前状态，作为进程调度和对换时的依据；

进程优先级优先级高的进程应先获得处理机

进程调度所需的其它信息与所采用的进程调度算法有关，比如，进程已等待CPU的时间总和、进程已执行的时间总和等；

事件即阻塞原因，指进程由执行状态转变为阻塞状态所等待发生的事件。

•进程控制信息

程序和数据的地址: 指进程的程序和数据所在的内存或外存地址，以便再调度到该程序执行时，能从PCB中找到其程序和数据；

进程同步和通信机制:指实现进程同步和通信必需的机制，如消息队列指针、信号量等；

资源清单：是一张列出了使用CPU以外的、进程所需的全部资源及已经分配到该进程的资源的清单；

链接指针：它给出了本进程（PCB）所在队列中的下一个进程的PCB的首地址。

进程队列：不同状态进程分别组成队列，有：运行队列、就绪队列、等待队列

引起创建进程的事件

§用户登录在分时系统中，用户在终端键入登录命令后，如果是合法用户，系统将为该终端建立一个进程，并把它插入到就绪队列中。

§作业调度在批处理系统中，当作业调度程序按一定的算法调度到某作业时，便将该作业装入内存，为它分配必要的资源，并立即为它创建进程，再插入到就绪队列中。

§提供服务当运行中的用户程序提出某种请求后，系统将专门创建一个进程来提供用户所需要的服务。例如，运行过程中要求打印，系统会创建一个打印进程与该用户进程并发执行。

§应用请求指的是基于应用程序的需求，为它创建一个新进程，以便使新进程以并发运行方式完成特定任务。通过这种方式可以使得几个操作并发执行，以加速任务的完成。

进程的创建

一旦操作系统发现了要求创建进程的事件后，便调用进程创建原语Creat( )来创建进程。进程的创建需要经历以下步骤：

§申请空白PCB。

§为新进程分配资源

§初始化进程控制块

§将新进程插入到就绪队列

进程的终止

1）正常结束

2）异常结束

3）外界干预

进程的终止过程

当系统中出现了要求终止进程的某事件后，OS便调用进程终止原语来终止进程。其步骤包括：

1. 根据被终止进程的标识符，从PCB集合中检索出该进程的PCB，从中读出该进程的状态；

2. 若被终止进程正处于执行状态，应立即终止该进程的执行，并置调度标志为真，用于指示该进程被终止后应重新进行调度；

3. 若该进程还有子孙进程，还应将其所有子孙进程予以终止，以防他们成为不可控制的进程；

4. 将被终止进程所拥有的全部资源，或者归还给父进程，或者归还给系统；

5. 将被终止进程（它的PCB）从所在队列（或链表）中移出，等待其他程序来搜集信息。

进程同步

几个进程若共享同一临界资源，它们必须以互斥的方式使用这个临界资源，即当一个进程正在使用临界资源且尚未使用完毕时，其他进程必须推迟对该资源的进一步操作，在当前进程的使用完成之前，不能从中插进去使用这个临界资源，否则将会造成信息混乱和操作出错。

临界区

不论是硬件临界资源，还是软件临界资源，多个进程必须互斥地对它进行访问。

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

每个进程进入临界区之前，应先对欲访问的临界资源进行检查，看它是否正被访问。如果此刻该临界资源未被访问，进程便可进入临界区对该资源进行访问，并设置它正被访问的标志；如果此刻该临界资源正被某进程访问，则本进程不能进入临界区

信号量机制

整型信号量

思想：定义一个整型量S，除初始化外，仅能通过两个标准的原子操作wait(S)和signal(S)来访问。

wait(S): while S≤0 do no-op;

S:=S-1;

signal(S): S:=S+1;

2. 记录型信号量

产生的原因：在整型信号量机制中的wait操作，只要是信号量S≤0，就会不断地测试。因此，该机制并未遵循“让权等待”的准则，而是使进程处于“忙等”的状态。

思想：用整型变量value代表资源的数目。用进程链表L来链接等待访问临界资源的进程。

记录型信号量的定义：

type semaphore=record

value: integer;

L: list of process;

end

记录型信号量的P、V操作

Procedure wait(S)

Var S: semaphore;

begin

S.value:= S.value-1;

If S.value<0 then block(S.L)

end

Procedure signal(S)

Var S: semaphore;

begin

S.value:= S.value+1;

If S.value≤0 then wakeup(S.L)

end

关于记录型信号量的几点说明：

•每次执行完wait操作后，若S.value<0时，说明该类资源已分配完毕，因此进程应调用block原语，进行自我阻塞，放弃处理机，并插入到信号量链表S.L中。

•每次执行完signal操作后，若S.value≤0时，则表示在该信号量链表中，仍有等待该资源的进程被阻塞，故还应调用wakeup原语，将S.L链表中的第一个等待进程唤醒。

•若S.value的初值为1，表示只允许一个进程访问临界资源，此时的信号量转化为互斥信号量。

信号量的应用

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

1．生产者与消费者问题

问题描述：

在生产者和消费者之间的公用缓冲池中，具有n个缓冲区，这是可利用互斥信号量mutex实现诸进程对缓冲池的互斥使用；利用信号量empty和full分别表示缓冲池中空缓冲区和满缓冲区的数量。又假定这些生产者和消费者相互等效，只要缓冲池未满，生产者便可将消息送入缓冲池；只要缓冲池未空，消费者便可从缓冲池中取走一个消息。

Var mutex,empty,full: semaphore :=1,n,0;
    buffer: array [0,…,n-1] of item;
    in,out: integer:=0,0;
begin
   parbegin
   procedure: begin
                         repeat
                          …
                         produce an item nextp;
                           …
                           wait(empty);
                            wait(mutex);
                            buffer(in):=nextp;
                            in=(in+1) mod n;
                            signal(mutex);
                            signal(full);
                            until false;
     end

consumer: begin
                         repeat
                         wait(full);
                          wait(mutex);
                          nextc:=buffer(out);
                          out:=(out+1) mod n;
                           signal(mutex);
                           signal(empty);
            consumer the item in nextc;
                        until false;
                           end    
                 parend
end

3.读者与写者问题

问题描述：允许多个读进程同时读一个共享对象，因为读操作不会使数据文件混乱。但不允许一个Writer进程和其他Reader进程或Writer进程同时访问共享对象。因为这种访问将会引起混乱。

为实现Reader和Writer进程间在读或写时的互斥而设置了一个互斥信号量Wmutex。另外，再设置一个整型变量readcount表示正在读的进程数目。

Var rmutex,wmutex:semaphore:=1,1;
      readcount:integer:=0;
      begin
      parbegin
      Reader: begin
                    repeat
                    wait(rmutex);
                    if readcount=0 then wait(wmutex);
                       readcount:=readcount+1;
                       signal(rmutex);
                           …
                       perform read operation;
                           …

                     wait(rmutex);
                    readcount:=readcount-1
                    if readcount=0 then signal(wmutex);
                    signal(rmutex);
                until false;
end

writer: begin
       repeat
       wait(wmutex); perform write operation;
signal(wmutex);
until false;
  end
parend
end