目录
- 1. 进程排队
- 2. 进程状态的表述
- 2.1. 进程状态
- 2.2 运行状态
- 2.3. 阻塞状态
- 2.4. 挂起状态
- 3. Linux下具体的进程状态
- 3.1. 运行状态R
- 3.2. 可中断睡眠状态S
- 3.3. 不可中断睡眠状态D
- 3.4. 停止状态T
- 3.5. 死亡状态X
- 3.6. 僵尸状态Z
- 4. 孤儿进程
- 5. 优先级
- 6. Linux的调度与切换
- 6.1. 四个概念
- 6.2. 进程切换
- 6.3. 进程调度
1. 进程排队
- 进程排队:指的是操作系统将等待资源的进程组织成队列,以便按照特定的调度策略来决定哪个进程可以获取资源并继续执行,即:将进程放入到等待资源的队列中进行排队。
进程排队,表示进程不是一直在运行的,是在等待某种软硬件"资源"。eg:scanf,等待键盘资源。
即使进程被调度到CPU上执行,它也不会一直运行下去。在多任务操作系统中,进程的执行是分时的,每个进程会分配到一定的时间片来执行,当时间片用完,操作系统会暂停运行当前进程。
-
进程排队,一定是进程的task_struct(PCB)进行排队。
-
进程的task_struct(PCB)可以放入到多种数据结构中。
进程的PCB既可以被放入到全局的双链表中,又可以被放入到特定的队列中。当进程被放入到全局的双链表中,OS会在进程的每个PCB中创建链表节点的对象;当进程被放入到特定的队列中,OS会在队列的数据结构中创建或复用双链表节点,在PCB中设置队列节点的链接。
2. 进程状态的表述
前言:教材中描述进程状态的模型和实际操作系统(如:Linux)中实现的进程状态模型可能会有差异。
2.1. 进程状态
- 进程状态:本质是一个整形类型的变量,它定义在task_struct结构体中,用来描述进程的不同的不同状态。
- 进程状态,决定着进程的后续操作和它在操作系统的行为。
2.2 运行状态
运行状态:进程已经准备好随时被调度。即:正在CPU上执行以及在运行队列中等待被调度的进程。
💡Tips:一个CPU一个运行队列。
2.3. 阻塞状态
阻塞状态:进程暂时无法继续执行,在等待某种软硬件"资源"。
💡Tips:每个硬件都有自己的队列!
-
当进程在等待软硬件资源的时候,资源没有就绪,操作系统就会先将进程的task_struct设置为阻塞状态、再将task_struct链入到等待资源的等待队列中。
-
状态的变迁,引起的是PCB会被操作系统变迁到不同的队列中!
-
硬件的就绪状态,本质是硬件的资源准备好执行任务的状态,操作系统作为硬件的管理者,负责监控和管理这些硬件资源的状态。
硬件资源就绪,对于键盘的输入,通常是指键盘的中断机制已触发,表明有新的输入数据已经准备好了。
键盘的输入处理流程如下:硬件资源就绪(键盘输入准备完毕)→ OS通过驱动程序将数据从外设(键盘)搬到内存(内核输入缓冲区)→ 用户程序通过系统调用接口(scanf)将数据从内存搬到用户空间。
2.4. 挂起状态
挂起状态:进程被暂时停止执行,它的状态被保存,以便在将来某个时刻恢复。分为内部挂起、外部挂起。
-
外部挂起:也称为阻塞挂起。当系统资源紧张,如:内存空间不足,OS会将进程的代码和数据保存到磁盘的swap分区,以释放内存供其他进程使用,此时进程状态为挂起状态。当内存资源变的可用时,OS会将对应的代码和数据重新加载到内存中,并将其状态由挂起变为运行,以便它可以被调度执行。
-
唤出过程:当内存资源紧张时,OS会将内存中数据(等待资源的进程的代码和数据)交换到磁盘的swap分区中,以释放内存空间,这个过程称为唤出。
-
唤入过程:当需要恢复执行此进程时,就会将磁盘的swap分区保存的内容回到内存中,使进程可以继续执行,这个过程称为唤出。
问1:创建一个新进程,是先创建进程的PCB,还是先把进程的代码和数据加载到内存中?
答:先创建进程的PCB,再把进程的代码和数据加载到内存中,确保了OS对进程的创建和管理。
问2:磁盘的swap分区的大小是越大越好吗?
答:不是,会导致性能下降、资源浪费等问题。与内存相比,磁盘速度慢的多,如果swap分区很大,会导致OS过度依赖它,而频繁的唤入唤出操作会显著降低系统的性能,因为磁盘的IO速度远低于内存的读写速度。
- swap分区不能设置过大,通常大小等于内存大小或内存大小的一半。
3. Linux下具体的进程状态
/*
* The task state array is a strange "bitmap" of
* reasons to sleep. Thus "running" is zero, and
* you can test for combinations of others with
* simple bit tests.
*/
static const char * const task_state_array[] = {
"R (running)", /* 0 */
"S (sleeping)", /* 1 */
"D (disk sleep)", /* 2 */
"T (stopped)", /* 4 */
"t (tracing stop)", /* 8 */
"X (dead)", /* 16 */
"Z (zombie)", /* 32 */
};
3.1. 运行状态R
运行状态R:进程正在运行或者准备运行。它可能正在CPU上执行,或者在运行队列中等待被调度。
-
grep是单独指令,是程序,只有被运行,变成进程,它才会执行过滤操作,所以它的状态总是运行状态R。
-
前台进程(带+),可以被键盘(ctrl + c)终止;后台进程(不带+),不可以被键盘终止,可以通过发信号(kill -9 进程的PID),才可终止后台进程 ;前台进程 -> 后台进程:./程序 & 。
3.2. 可中断睡眠状态S
可中断睡眠S:也称为浅度睡眠或睡眠状态,意味着进程正在等待某个事件的完成,如: I/O操作、定时器到期(sleep函数)等,它可以被信号中断,如:ctrl + c、kill -9终止进程。
💡Tips:可中断睡眠睡眠S == 阻塞状态。
#include<stdio.h>
#include<unistd.h>
int main()
{
while(1)
{
printf("I am a process, id: %d\n", getpid());
sleep(1);
}
}
问:为什么这个进程处于睡眠状态?
答:sleep函数会将进程由运行状态变为睡眠状态,等待指定的时间,进程会被OS唤醒。printf函数的执行速度通常是非常快的,因为CPU的执行速度很快,而printf是向显示器打印,需要访问外设,printf可能会等待I/O操作完成时使进程短暂的进入睡眠状态。
3.3. 不可中断睡眠状态D
不可中断睡眠D:也称为深度睡眠或磁盘休眠状态,它通常会等待硬件操作(如:磁盘I/O)完成,不能响应信号,直到它所等待的事件完成。
💡Tips:不可中断睡眠睡眠D == 阻塞状态。
eg:当一个进程发起磁盘的写入操作时,当内存资源十分吃紧,如果此进程处于睡眠状态S,OS就会将此进程杀掉,可能会导致数据丢失,所以此进程的状态被设置于不可中断睡眠状态D,OS不可以杀掉此进程,进程等待磁盘的结果以作出相应的应答。
3.4. 停止状态T
停止状态T:意味着进程已经被暂停或者正在被追踪,通常是因为接受到一个信号,或者是在调试器中被断点所拦截。
💡Tips:停止状态T == 阻塞状态。
- 可以通过发送SIGSTOP信号(kill -19)给进程来停止进程,通过发送SIGCONT信号(kill -18)让处于暂停状态的进程继续运行。
3.5. 死亡状态X
死亡状态X:意味着进程已经终止,且资源已经被回收,它只是一个返回状态,不再存在于进程列表中。
3.6. 僵尸状态Z
僵尸状态:进程已经退出,但其父进程尚未调用wait( )来收集其退出信息。即: 进程是已退出但未清理的状态,等待父进程回收资源。
- 前提:子进程比父进程先退出。只要子进程退出了,父进程还在运行,但父进程没有读取子进程退出信息,子进程就进入Z状态,当父进程回收了子进程的资源,子进程由Z状态变为X状态。
处于僵尸状态的进程会一直保存在进程列表中。通常情况下,进程先变为Z状态,再变为X状态。
-
当一个Shell( bash )会话结束时,如果没有显示的调用wait( )回收子进程的资源,而Shell作为父进程,会自动调用wait( )来清理所有已经终止的子进程的资源,避免留下僵尸进程,后台进程除外。
-
当进程退出后,先会释放进程的代码和数据,进程的PCB不能被释放,因为它里面存储着结果数据,只有当父进程完成了资源的回收和状态的读取,PCB才会被释放。
#include<stdio.h>
#include<unistd.h>
#include<sys/types.h>
#include<stdlib.h>
#include<wait.h>
int main()
{
pid_t id = fork();
if(id < 0) return 1;
else if(id == 0)
{
//子进程
int cnt = 5;
while(cnt--)
{
printf("I am child process, pid: %d, ppid:%d\n",getpid( ),getppid());
sleep(1);
}
exit(0);
}
else
{
//父进程
int cnt = 10;
while(cnt--)
{
printf("I am father process, pid: %d, ppid:%d\n",getpid (),getppid());
sleep(1);
}
}
wait(NULL);
printf("father wait child done...\n");
sleep(5);
}
//现象:父子进程同时运行5s, 5s后子进程退出(变Z状态), 父进程在运行5s, 5s后父进程回收子进程资源(子进程由Z->X状态), 5s后父进程退出
a. 为什么要有僵尸状态Z?
- 创建进程是希望这个进程执行特定任务,子进程在完成工作后,往往需要向父进程报告结果或者状态信息(子进程必须由结果数据保存在自己的PCB中) , 从而使父进程能够根据子进程的执行结果作出适当的响应。
b. 什么是僵尸状态Z?
- 进程已经退出,但是当前进程的状态需要自己维持住,供父进程读取。
c. 如果父进程不读取子进程的退出数据呢?
- 僵尸状态的进程会一直存在,而维护退出状态本质是用数据维护,存储在进程的PCB,所以task_struct对象也要一直存在,而数据结构对象本身就要占用内存,会造成内存泄漏。
4. 孤儿进程
孤儿进程:父进程比子进程先退出,子进程就称为"孤儿进程"。
- 孤儿进程被PID为1的进程(操作系统)领养,由OS回收其资源。
#include<stdio.h>
#include<unistd.h>
#include<sys/types.h>
int main()
{
pid_t id = fork();
if(id < 0) return 1;
else if(id == 0)
{
//子进程
int cnt = 10;
while(cnt--)
{
printf("I am child process, pid: %d, ppid:%d\n",getpid( ),getppid());
sleep(1);
}
exit(0);
}
else
{
//父进程
int cnt = 5;
while(cnt--)
{
printf("I am father process, pid: %d, ppid:%d\n",getpid (),getppid());
sleep(1);
}
}
}
5. 优先级
优先级:CPU资源分配的先后顺序。
-
前提:进程要访问某种资源,进程通过一定的方式(排队),确认享受资源的先后顺序。
-
为什么要存在优先级?因为资源相对过少。
-
优先级本质是一个整数类型的变量,数值越小,优先级越高,具有优先执行的权力。
-
优先级PRI(new) = 优先级PRI(old) + nice。
Linux系统允许用户调整进程的优先级,但不能直接修改pri,而是修改进程的nice值。
nice值:是进程优先级的修正数据,!=进程优先级;优先级PRI(old)为默认优先级(值为80)。
- Linux优先级默认值为80,优先级的范围为[60 , 99],nice值的范围为[-20,19],一共40个。
Linux为什么调整优先级是要受限制的?
答:如果不受限制,则用户能够随意提高自己的进程优先级调整的非常高,那么很可能他们会过度提升自己的进程,使其始终处于高优先级的状态,导致常规进程难以得到CPU资源,产生进程饥饿现象。
💡Tips:任何分时系统(基于时间片进行轮转执行),确保了进程调度的公平性和系统的稳定性!
ps -l
- 功能:显示当前登录用户的所有进程的信息。
UID:代表执行者的身份、PID:进程的唯一标识符、PPID:子进程的父进程的唯一标识符、PRI:进程的优先级、NI:进程优先级的修正数据。
top -> r -> 输入进程的PID -> 输入nice值
- 功能:用top命令更改已存在进程的nice值,从而调整进程的优先级。
renice nice 进程的PID
- 功能:更改已存在进程的nice值,从而调整进程的优先级。
6. Linux的调度与切换
6.1. 四个概念
现代操作系统可以分成不同类别,分时操作系统和实时操作系统是两种重要的类型。
对于分时OS,进程都是基于时间片进行轮转执行的。每个就绪进程在轮到自己时,将会获得一个时间片来执行,如果一个进程在时间片结束时还没有执行完,它就会立即被暂停,CPU将被分配给下个进程,造成多个进程在"同时"运行的假象。
对于实时OS,采用的是优先级驱动的调度策略,要求OS对用户有超高响应,其中一旦高优先级的进程一旦就绪,将立即抢占CPU执行,如:车载系统。
-
竞争性:系统中进程的数量多、而CPU资源少量,所以进程之间对于共享资源是具有竞争属性的。
-
独立性:多进程在运行期间互不影响。每个进程在执行时都有自己的私有执行环境,包括代码、数据等资源,它们各自独享自己的执行资源。
-
并行:多个进程在多个CPU下,分别同时进行运行。
-
并发:多个进程在一个CPU下采用进程切换的方式,在一段时间内,多个进程看起来同时执行。
6.2. 进程切换
进程切换 = 保护进程的硬件上下文 + 进程的硬件上下文恢复。是OS在多任务环境中实现进程间公平调度和并发执行的关键机制。
-
进程在运行的过程中,会产生大量的临时数据,小部分被存储在CPU的寄存器中,大部分被存储在内存中。
-
进程的硬件上下文:在某一时刻,CPU执行进程时,所有硬件状态信息的集合。如:CPU内部的寄存器中存储的所有临时数据等。
-
保存进程的硬件上下文:当一个进程的时间片结束、主动放弃CPU(等待某种资源scanf)、有更高优先级的进程就绪需要暂时停止执行,OS会保存该进程的硬件上下文到进程的PCB中。
-
进程的硬件上下文恢复:在保存完当前进程的上下文后,OS会选择下一个要运行的进程,如果该进程是第二次被调度,就会将该进程的PCB中上下文重新加载到CPU上,CPU会从上次的运行位置继续运行。
💡Tips:所有的保存都是为了最终的恢复,所有的恢复都是为了继续上次的运行位置继续执行。
- CPU中的寄存器从物理上是被所有进程共享,在任意时刻,CPU的寄存器由当前正在执行的进程独占使用,而寄存器内部保存的数据,是被该进程私有的。即:CPU中的寄存器只能有一套,寄存器内部保存的数据可以有多套。
💡Tips:寄存器 != 寄存器的内容。
6.3. 进程调度
背景:Linux的进程调度O(1)算法,需要考虑优先级、进程饥饿、以及效率等问题,这主要是通过是特定的数据结构和算法设计来实现的。
一、####数据结构
- queue[140]
这是个优先级数组(prio_array),它是一个长度为140的指针数组,每个元素包含一个链表头,该链表包含具有相同优先级的所有就绪进程,即:每个元素对应一个优先级队列,每个队列中的进程具有相同的优先级,它维护了140个优先级队列。
实时优先级:0~99,用于实时进程,以确保它们能够及时响应并完成任务。
普通优先级:100~139,通过nice值[-20,19]可以调整进程在该范围内的优先级,用于非实时进程,遵循时间片轮转调度策略,确保进程公平的共享CPU资源。
- bitmap[5]
这是一个位图(prio_map),用于快速检测哪些优先级队列是非空的。它是一个5个整数的数组,每个整数有32个比特位,共有5*32=160个比特位 > 140,位图操作都是在比特级别进行的,时间复杂度为O(1),非常高效。
位图中的每个比特位的位置,对应着一个优先级队列;每个比特位的内容,表示这个队列是否为空。即:检测某个优先级队列中是否有进程,转为为检测对应比特位是否为1。
- nr_active
这是一个计数器,用于记录当前活跃进程队列中进程的总数。
struct q
{
int nr_active;
int bitmap[5];
task_struct queue[140];
}
二、####算法实现
- 优先级
通过优先级数组和位图,调度器,可快速定位到最高优先级的非空队列。当需要调度下一个进程时,调度器首先会遍历位图,直到找到’第n位’为1才会停下,再访问queue数组中的下标值为’第n位’的元素,取出该队列中第一个进程进行运行。
- 避免进程饥饿
OS会将时间片耗尽的进程放到过期队列中,不让他们一直占用活跃队列的位置,确保其他进程被调度到CPU上执行;新增进程也会被加入到过期队列,不论这个新进程的优先级高低,避免了较高优先级的进程抢占CPU资源。而CPU只会执行活跃队列中的进程,当活跃队列上的进程都被执行完毕,两队列交换。
- 效率
因为bitmap[5]数组的存在,调度器只需要遍历bitmap[5]数组,而不是整个queue[140]数组,大大减少了遍历的次数。位图的查询操作时间复杂度为O(1),意味着无论多少个优先级队列,调度器只需要遍历bitmap[5],就可以快速找到非空优先级队列,大大提高了查找效率。
三、活跃进程队列、过期进程队列
-
活跃进程队列:包含了当前准备就绪,可以立即被执行的进程。
-
过期进程队列:包含了时间片耗尽,但未执行完毕的进程。
四、active指针、expired指针
-
active指针永远指向活跃队列、expired指针永远指向过期队列。
-
进程的时间片一直存在,就会使活跃队列的进程一直在减少、过期队列的进程一直在增多。
struct q
{
int nr_active;
int bitmap[5];
task_struct queue[140];
}
struct q array[2];
struct q* active = &array[0]; //活跃队列
struct q* expired = &array[1]; //过期队列
swap(&active, &expired); //更改的只是指针变量的内容,队列内容并未改变