进程的描述与控制

前趋图和程序执行

1. 前趋图：即偏序图，具有循环的就不是了

2. 程序顺序执行，就是只有一条链的偏序图

   有顺序性，封闭性（在运行时不会被其他影响），可再现性（不管执行几次都是一样的结果）

3. 并发执行（实际上就是并行），就是一张普通的偏序图，只有不具有前趋关系（不互相依赖）的程序之间才能并发

   有间断性（因为互相制约，所以就可能要等别的程序运行完，就导致走走停停），没有封闭性，不可再现性（结果与并发程序执行的速度有关）

进程的描述

1. 进程的定义和特征

   为了使程序能并发并行，并为了对它描述和控制，就产生了进程。

   进程实体：进程控制块，程序段，相关数据段

   进程控制块（PCB）：用于控制和描述进程，创建和销毁进程实际上就是对PCB在操作

   进程：进程实体的运行过程，是系统进行资源分配和调度的一个基本单位。

   特征：动态性（程序是静态的，而进程是进程实体运行过程），并发性，独立性（独立运行，独立获得资源和独立接受调度），异步性

2. 进程的基本状态及转换

   总共五大状态：

   1. 就绪状态：已经分配到了除CPU之外的所有资源，已经在就绪队列中了，就等运行了
   2. 执行状态：执行
   3. 阻塞状态：发生了某事件（IO请求等）而暂时无法继续执行，就会放弃对处理器的占用，进入阻塞队列，等待事件完成
   4. 创建状态：保证就绪必然是在创建完成后，其中要完成很多工作，如创建PCB，填写PCB等
   5. 终止状态：进入终止态后程序不能再运行，等待其他进程读取他的信息，再由操作系统对它善后并销毁

   

3. 挂起

   由于终端用户的需要，父进程请求，负载分配，操作系统的调用等原因，需要让其挂起，暂时停止执行，也不允许被执行。

   引入了两个新状态：静止就绪和静止阻塞

   其中，如果在创建时发现资源（如内存）不足，就会直接进入静止就绪状态，此时进程并未创建完成。

   

4. 进程管理中的数据结构

   为了管理进程，因此创建了一个用于管理进程的数据结构：内存表、设备表、文件表和用于进程管理的进程表（PCB）。

   当一个进程获得PCB的时候，才表示他能够运行，PCB就是进程存在于系统的唯一标志。用于保存现场信息，实现了暂停。提供进程管理和调度的所有信息，操作系统通过PCB进行管理。实现与其他进程的通信。

   由四大部分组成：

   1. 进程标识符：唯一的标示一个程序

      外部标识符：由创建者提供，用于标示家族关系，用户关系等。

      内部标识符：由系统提供，用于管理进程。

   2. 处理机状态：即处理器的上下文，主要由寄存器中的内容组成

      通用寄存器，指令计数器，程序状态字PSW，用户栈指针。这些信息保存在PCB中用于恢复。

   3. 进程调度信息：当前状态，进程优先级，调度相关信息和阻塞原因等

   4. 进程控制信息：程序和数据的地址，进程同步和通信，资源清单，链接指针（指向下一个PCB）

   一般有三种组织PCB的方式：线性表，链表（用不同的指针指向标示不同的链表，如阻塞，就绪等等），索引方式（一张线性表，再加上很多张不同功能的索引表里面指向实际的PCB的序号）

进程控制

1. 操作系统内核

   处理机的执行状态一般分为两种：

   1. 管态：系统态/内核态，能执行一切命令，访问所有寄存器，内核也在管态运行。

   2. 目态：用户态，只能执行规定的命令，访问指定的寄存器，应用程序一般都在目态运行。

      通过这种区分，可以对管态程序进行保护并提高运行效率。

   OS内核一般提供以下功能：

   1. 中断处理，时间管理，原语操作（原子操作）
   2. 资源管理功能：进程管理，存储器管理和设备管理

2. 进程的创建

   一般把创建进程的称为父进程，被创建的是子进程。这样就会形成一个进程家族树。

   当子进程被取消时，就要归还资源，父进程取消时，所有子进程也要取消。PCB中记录了这些关系。

   但Windows并不是层次结构的，而是创建时会获得一个句柄，获得了句柄就能操控。

   引发进程创建：用户登录（创建用户进程），作业调度，提供服务（阻塞要求系统提供服务器服务），应用请求（唯一的用户主动创建进程，前三种都是系统创建的）

   创建的过程：创建空PCB，获得标识符；分配资源，（进程需要将自己需求的资源告诉父进程和操作系统）；初始化PCB（初始化标识符，处理器信息，控制信息）；将其插入就绪队列

3. 进程的终止

   引发进程终止：正常结束（产生一个中断通知操作系统运行完毕）；异常结束（发生异常事件，如错误）；外界干预（操作员或操作系统干预；父进程请求；父进程终止）

   终止的过程：根据标识符检索PCB并获取状态；若在运行，就终止；如果有孩子进程，就终止；归还资源给操作系统或父进程；移出队列

4. 进程的阻塞和唤醒

   引发事件：请求共享资源失败；等待操作完成；新数据尚未到达；等待新任务到达

   阻塞的过程：进程主动调用阻塞原语将自己阻塞，更改状态，插入阻塞队列，重新调度并切换。

   唤醒的过程：由其他进程调用唤醒原语，将进程移出阻塞队列，更改状态，插入就绪队列。

5. 进程的挂起与激活

   相较于阻塞，会多加一步将PCB复制到某指定内存区域帮助用户或父进程查看情况。

   根据使用的策略不同，唤醒的时候也会产生不同的调度情况。

进程同步

通过进程同步可以让并发执行的程序的无序变得有序。

1. 基本概念

   同步实际上就是要解决进程之间的制约关系。

   两种制约：

   1. 间接相互制约：需要使用共享系统资源（硬件临界资源）（OS要求必须先提交请求，经过OS批准才能使用）
   2. 直接相互制约：进程相互合作（使用两个进程共同持有的资源，软件临界资源）

   但是，不管是哪种制约，实际上都是因为临界资源（共享资源）产生的。

   临界区：代码中访问临界资源的代码

   进入区：临界区前判断临界资源使用的代码

   退出区：临界区后将临界资源访问恢复的代码

   剩余区：其他代码

   而所有的同步机制都应该遵循：空闲让进，忙则等待，优先等待，让权等待（不占有CPU地等待）

2. 硬件同步机制

   1. 关中断

      让其在进入临界区的时候将中断响应关闭，这样就不会被打断了，但是这是滥用机制，且会影响系统效率，并且不适用于多处理器系统

   2. Test and Set

      

      当且仅当old为false的时候才能使用临界区。不管怎样，反正经过这个函数，lock总会变成true，也就挺原子的了。

   3. Swap

      实际上和TS差不多，只不过把操作替换成了swap。

   但是上述两种都是忙等，并没有做到让权等待，因为他一直在测试时候能够使用。

3. 信号量机制

   1. 整数信号量：总共两个原子操作，一个wait(P)，一个signal(V)，wait就是等待到能使用了，就减少一个能使用量，而signal就是增加一个使用量。

      

   2. 记录性信号量

      整数信号量仍然是没有实现让权等待。为了实现等待，一个数字是不够的，还需要一个链表记录所有等待的进程。如果取走资源后，就将所有其他等待的block，完成后在wakeup他们。就实现了让权等待。

      

   3. AND型信号量：对于使用的所有资源，一次性一起分配，只要有一个不行，就都不行

   4. 信号量集：将上述的这些抽象起来

      Swait(S1,t1,d1…)，S1表示信号量名，t1表示需要≥t1才允许分配，d1表示分配量。

      Ssignal(S1,d1…)，将d1个量归还给S1。

4. 信号量应用

   可以实现锁，前趋关系。

5. 管程机制

   使用信号量会使信号量大量分布在代码之中，难以管理。

   1. 定义

      不如直接将共享资源用共享数据资源包装起来。

      管程：代表共享资源的数据结构以及操作这个共享资源的一系列操作构成的一个操作系统的资源管理模块。

      由四个部分组成：名称，共享数据结构的结构说明，操作过程，初始化操作。

      有着模块化，抽象数据结构，信息遮蔽等诸多有点。

   2. 条件变量

      当一个进程开始等待，其他进程就会进入管程，即便这个进程的条件已经满足了，也得等其他进程搞定。因此引入条件变量，明确等待的原因，根据原因放进各个等待队列中，当条件一满足立即唤醒，加快效率。

      Hoare采用先立即执行唤醒的这个程序。

经典进程同步问题

1. 生产者消费者问题：要注意wait的顺序，否则可能死锁。
2. 等等

进程通信

信号量虽然也能进行通信，但是是比较低级的，因为效率低且不透明。

而OS也提供了高效的通信方式。

1. 进程通信的类型

   1. 共享存储器系统

      通过共享数据结构：通过公用某些数据结构进行通信，效率低下是低级通信。

      通过共享存储区：在内存中划出一块共享存储区域，进程都可通过共享区读或写信息，操作由程序负责而非OS。在读写不再需要后，再将这一片区域还给共享存储区。

   2. 管道通信系统

      通过一个文件，发送者在结尾一直写，接受者在开头一直读，能有效传输大量数据。但对管道的读写必须是互斥的，为了能让别人能写或者能读，写或读完一定量后就去休息，并通知另一方，并且需要确认管道的对方时候存在。

   3. 消息传递系统

      以一定格式将数据封在消息中，并通过操作系统提供的接口完成消息传递。即可以直接通过OS提供的原语，也可以通过共享一个邮箱进行消息的发送和接收。

   4. 客户机-服务器系统

      1. 套接字

         原本发明是为了解决多对进程同时通信和物理线路的多路复用问题，一般基于文件型，通过一个套接字关联到一个特殊的文件。

         但现在基本都发展到了网络方面的通信，基于网络型。

      2. 远程过程调用和远程方法调用

         远程过程调用允许一台主机上的进程调用另一台主机系统上的进程。

         在这个过程中总共有四个进程，除了上述的两个，还有本地和远程的网络守护进程，一般情况下都处于等待。首先先将这个调用转化成客户存根（类似于一个标签），再由远程服务器转化为对应的本地调用。

2. 消息传递通信的实现方式

   1. 直接消息传递

      总共有两种原语。

      对称寻址方式：以显式的方式提供接受者和发送者，但不利于进程定义的模块化。

      非对称寻址方式：发送者需要指定接受者，但接受者却不需要指定发送者。

      格式：可以采用变长的信息格式，也可以是定长的短消息。

      同步方式：

      1. 双方都阻塞：只有要发消息或接收消息时才唤醒，在双方关系紧密的时候使用
      2. 接收方阻塞：发送方只要管发送就好了，而接收方只有接收到了才唤醒，最广泛
      3. 双方都不阻塞：平常都各干各事，要发送了或接收了才搞一下。

      通信链路：在发送前用建立连接原语建立一条链路或者无需显式建立，发送的时候OS自动会建立，而这条链路既可以是单向的也可以是双向的。

   2. 信箱通信

      即可实时通信也可以实现非实时通信。

      结构：一个信箱头（存放信箱的描述信息）和信箱体（存放消息）。有创建，销毁和发送接收原语，发送和接收和直接消息的对称差不多，只不过是发送者和接受者都是信箱了。

      总共有3种信箱：

      1. 私有邮箱：进程创建，只能创建者读，其他进程能发送到此邮箱
      2. 公用邮箱：操作系统创建，供所有进程使用
      3. 共享邮箱：只有共享者能读写

      信箱的发送者和接受者可以是1对1，1对N，N对1，N对N。

3. 消息缓冲队列

   内部要用锁或者信号量实现。发送者就是构造消息，然后锁上消息队列，然后扔到消息队列上，然后解锁。接受者就是反过来。

线程的基本概念

由于进程是一个可拥有资源的独立单位，并且他能够独立运行且可独立调度和分配，因此他的创建，撤销，和切换的耗费很大。因此便提出了线程，仅仅能独立调度和分配，但不占有独立资源。

线程称为轻型进程或进程元，切换的时候保存量很少，代价更低；可以在进程中并发执行；共享进程的所有资源；独立性更低，各自的内存地址空间和资源都可以被其他线程读或写；能够支持一个进程在多个处理器上跑。

线程的状态：执行，就绪，阻塞。

线程控制块TCB：与进程不同的是，其有线程专用存储区，用于线程切换是存放现场信息，和堆栈指针，需要两个指针，一个指向运行在用户态时的内容，一个是运行在管态时的情况。

而在这种情况下，进程就只是一个拥有资源的基本单位了（包含地址空间，实现同步机制，打开的文件和申请到的IO设备和一张由核心进程维护的地址映射表，用于实现程序逻辑地址到物理地址的映射。现在，传统的进程方法被称为单线程方法，现代的都是多线程的。进程也不再是可执行的实体，但我们说其在执行实际上是其中的一个线程在执行。

但进程有一部分还是比线程好的，他安全，隔离（不会互相影响，如崩溃），并且调度支持更好。

线程的实现

1. 内核支持线程KST

   为每一个内核线程设置一个TCB。

   优点：能够同时调度同一进程的多个线程并行执行，不会因为一个线程阻塞而影响一整个进程，切换（系统切换，大概指的是那些跑在管态的程序）较快且执行速度快。

   缺点：但是对于用户切换较慢，因为要将其从用户态转到内核态上。

2. 用户级线程ULT

   所有对线程的操作都与内核无关，内核完全不知道用户级线程的存在。

   优点：无需模式切换，并且可以写一个专门针对于这个进程的调度方式，与内核完全无关，可以通用。

   缺点：调度是以进程为单位进行的，因为实际上并不能实现进程内的并行，并且也会因为一个线程的阻塞而导致进程阻塞。

3. 组合方式

   可以让用户级线程对部分或全部内核支持线程进行多路复用。

   多对一：将进程的所有用户进程映射到一个内核线程上，实际上没什么提升，但会稍微快一点，并且开销小。但仍然是单线程的实际上。

   一对一：并发功能很强，但是开销很大。

   多对多：根据情况而变化，很灵活，优点兼具

4. KST实现

   在内核空间上在创建一个进程的时候就给他分配一个任务数据区PTDA，用来放TCB，通过存储在内核就实现了内核线程，其他与进程类似。

5. ULT的实现

   在用户空间上实现，都运行在一个中间系统上，总共有两种方式实现中间系统。

   1. 运行时系统

      实际上就是管理和控制线程的函数的集合，用户级线程在切换时不用转入核心态，而是直接通过运行时系统提供的函数进行切换，非常快，而当要请求系统调用的时候，也是通过运行时系统间接处理。

   2. 内核控制线程

      这种线程被称为轻型进程LWP。LWP可通过系统调用来获得内核提供的服务。

      因此每一个用户级线程运行的时候就把他连接到这个转接口上，就具有了内核支持线程的所有属性。一般会将LWP做成一个缓冲池，每一个LWP连接到一个内核级线程上，而用户级线程则通过LWP去使用内核级线程。

      当用户级线程不需要与内核通信的时候就不需要LWP，但如果要通信，就必须要连接到LWP上。如果一个LWP阻塞了，也就是对应的内核级线程阻塞了，进程并没有被阻塞，因为可以继续分配一个新的LWP运行，除非所有的LWP全部阻塞，但这也仅仅会导致无法访问内核而已。

6. 线程的终止和开始

   一开始一般只有一个线程运行，逐渐创建出其他的线程。

   而终止的时候线程并不会释放其占有的资源，因为，他可能还会被其他的线程恢复运行。当且仅当他被其他线程弄得脱离了进程，才会释放其占有的资源。