进程相关问题

最近在准备夏令营的相关事宜，所以开始复习操作系统的相关知识。初时学习操作系统，觉得知识特别庞杂，不过这次复习起来却轻车熟路，当时很多不明觉厉的知识都开始清晰起来，过了一遍之后甚至觉得知识太少了。

考研、工作的面试中操作系统的知识是必问的，而在操作系统中，我觉得：进程线程的管理、存储管理、文件管理是其中最核心的部分，所以我的复习也主要集中与此。

程序执行

程序执行主要有顺序执行和并发执行两种方式：

• 程序顺序执行时具有：顺序性、封闭性、可再现性三个重要特征。可以用前驱图来描述程序执行的先后顺序，但需要注意的是，前驱图是个DAG，也就是说前驱图中不能出现环，也就无法描述程序中的循环。
• 程序并发执行时的特性无疑不同于顺序执行，主要有：间断性、失去封闭性、不可再现性。

引入进程

在多道程序设计的环境中，需要引入进程的概念。

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

• 结构
  进程实体 = 进程控制块（PCB）+ 程序段 + 相关数据段
• 特征
  • 动态性（最基本的特征）：进程是进程实体执行的一次动态过程
  • 并发性
  • 独立性：进程是独立接受资源和独立接受调度的基本单位
  • 异步性

不同与程序

• 进程是一个动态的概念
• 进程是暂时的
• 进程可以真实的描述并发
• 进程有创建其他进程的功能
• 同一个程序运行在不同的数据上，那么他就是不同的进程

进程的状态

进程的状态 =
\begin{cases}
执行  \\
就绪= \begin{cases}
    静止就绪& \\
    活动就绪&
    \end{cases} \\
阻塞= \begin{cases}
    静止阻塞& \\
    活动阻塞&
    \end{cases}
\end{cases}

状态的切换

进程控制块

存放进程管理和控制信息的数据结构称为进程控制块，随进程建立而建立随进程撤销而撤销。进程控制块是进程的唯一标识。

信息：

• 进程标识符
• 处理机状态
  • 程序计数器
  • 通用寄存器信息
  • 用户堆栈指针
  • 程序状态字
• 进程调度信息
  • 进程状态
  • 进程优先级
  • 其他信息
• 进程控制信息
  • 程序和数据地址
  • 同步和通讯机制

组织方法

• 链式：就绪、阻塞、空白队列，使用专门的寄存器保存队列首元素指针，队列元素间通过指针相连
• 索引：建立：就绪、阻塞、空白索引表，使用专门的寄存器保存表的首地址

进程控制

进程控制由OS的内核通过一组原语（系统调用，执行时不会被打断）来实现。

原语不会被打断，是通过关中断实现的

进程创建

1. 申请空白PCB
2. 分配资源
3. 初始化PCB
4. 将进程插入就绪队列

进程终止

1. 终止进程（包括子孙进程）
2. 释放资源
3. 将PCB从队列中移出

进程阻塞与唤醒

• 阻塞：PCB状态改为阻塞，插入阻塞队列
• 唤醒：PCB队列改为就绪，插入就绪队列

进程挂起与激活

• 挂起：执行或活动就绪则改为静止就绪，活动阻塞改为静止阻塞
• 激活：静止阻塞改为活动阻塞，静止就绪改为活动就绪

进程同步

进程间的制约关系：

• 间接制约：资源合作
• 直接制约：进程合作

临界资源：必须互斥访问的资源

临界区；访问临界资源的代码

信号量的机制

整形信号量

整形信号量没有让权等待的机制，导致忙等

记录性信号量

• 生产者消费者问题

假定在生产者和消费者之间的公用缓冲池具有n个缓冲区，可利用互斥信号量mutex实现诸进程对缓冲池的互斥使用，利用信号量empty和full分别表示缓冲池中空缓冲池和满缓冲池的数量。

producer
begin
    wait(empty)
    wait(mutex)
    ...
    signal(mutex)
    signal(full)
end

consumer
begin
    wait(full)
    wait(mutex)
    ...
    signal(mutex)
    signal(empty)
end

注意：

1. wait(mutex)与signal(mutex)必须成对出现
2. wait(empty)必须出现在wait(mutex)之前，否则会死锁

• 哲学家就餐问题

五个哲学家共用一张圆桌，分别坐在周围的五张椅子上，在桌子上有五只碗和五只筷子，他们的生活方式是交替地进行思考和进餐。平时，一个哲学家进行思考，饥饿时便试图取用其左右最靠近他的筷子，只有在他拿到两只筷子时才能进餐。进餐毕，放下筷子继续思考。

begin
    wait (chopstick[i]);
    wait (chopstick[(i+1)%5]);
    ...
    eat;
    ...
    signal (chopstick[i]);
    signal (chopstick[(i+1)%5]);
end

这时不会出现两人同时拿起同一只筷子的情况（不会发生混乱），但是会造成死锁。为了解决死锁需要引入更多的限制，比如:"至多只允许有四位哲学家同时去拿左边的筷子"等等。

或者采用AND性信号量机制

begin
    Swait(chopstick[ ( i +1) mod 5] , chopstick[ i ] );
    ...
    eat;
    ...
    Ssignal(chopstick[ ( i +1) mod 5] , chopstick[ i ] );   
end

• 读者写者问题

允许多个进程同时读一个共享对象，但不允许一个Writer进程和其他Reader进程共享对象，或者多个Write进程同时访问共享对象。

reader
begin
    wait(rmutex)
    if(readercount==0) wait(wmutex)
    //访问了临界资源readercount，所以要在wait操作后
    readercount++
    signal(rmutex)
    ...
    read
    ...
    wait(rmutex)
    readercount--
    if(readercount==0) signal(wmutex)
    signal(rmutex)
end

writer
begin
    wait(wmutex);
    ...
    write 
    ...
    signal(wmutex);
end 

• 管程

是一种封装好的程序结构，他将临界资源封装在内部，提供接口给外部保证进程互斥访问临界资源,使得临界资源的访问控制变得很方便。

但是我也没弄懂这东西，所以细节就不多阐述了。

线程

引入线程的目的在于解决程序并发执行时，切换进程时空开销过大的问题，进一步提高系统的并发程度。

回顾一下进程的属性中很重要的一点，进程是资源分配的基本单位，这也就导致了进程在创建甚至是切换时，都必须付出很大的时空开销保存与进程相关的资源的状态信息。

因此人们引入了线程的概念，将调度单位和资源分配单位分开。线程作为调度单位，进程作为资源分配单位。

线程只用于少量必须的资源如：程序计数器、一组寄存器等。同一个进程中的多个进程同时共享进程的资源，一个线程可以创建和撤销其他线程。每个进程都至少包含一个线程。

• 用户级线程

内核完全不知道用户级线程的存在，只能感知到线程属于的进程的存在，线程的创建、撤销都不需要内核的参与，这样节省了内核去切换线程的时间开销，但是也带来了弊端。

内核不知道线程的存在，所以处理机的分配是以进程为单位的，进程内的线程共享分配给进程的时间片。用户线程也不能将线程分散到多个处理器上。同时由于一个线程触发阻塞会导致整个进程阻塞。

• 内核级线程

内核线程建立和销毁都是由操作系统负责、通过系统调用完成的。线程管理的所有工作由内核完成，应用程序没有进行线程管理的代码，只有一个到内核级线程的编程接口。这些线程可以在全系统内进行资源的竞争。