第1页 / 共23页
第2页 / 共23页
第3页 / 共23页
第4页 / 共23页
第5页 / 共23页
第6页 / 共23页
第7页 / 共23页
第8页 / 共23页
操作系统基础.docx
操作系统基础
1.1、进程与线程的概念？
1.2、进程与线程的区别？
1.3、进程间通信的方式：
1.4、线程间的通信方式
1.5、线程的优势？
1.6、进程的五种基本状态？什么是活动阻塞，静止阻塞，活动就绪，静止就绪？
1.7、正常进程、孤儿进程和僵尸进程
1.8、单核机器上写多线程程序，是否需要考虑加锁，为什么？
1.9、线程需要保存哪些上下文，SP、PC、EAX这些寄存器是干嘛用的？
1.10、多进程和多线程的区别？使用场景是什么？
1.11、游戏服务器应该为每个用户开辟一个线程还是一个进程，为什么？
1.12、简述多线程的同步，锁的机制
1.13、什么是协程？
1.14、如何实现线程池
1.15、fork调用实例
1.16、死循环+来连接时新建线程的方法效率有点低，怎么改进？
1.17、Epoll
1.18、select,poll,epoll的区别
2.0、死锁发生的条件以及如何解决死锁
2.1、避免死锁
2.2、预防死锁
2.3、常见死锁相关算法
2.3、银行家算法（避免死锁）
2.4、资源有序分配法（预防死锁）
2.5、资源分配图化简法（检测死锁）
2.6、解除死锁的两种方法
2.7、Linux的4种锁机制？互斥锁和读写锁的区别？
3.1、页面置换方式
3.2、虚拟地址空间
3.3、程序的内存结构
3.4、缺页中断
3.5、系统调用（用户态、核心态）
3.6、用户态到内核态的转化原理
3.7、微内核与宏内核
3.8、结构体对齐，字节对齐
3.9、什么是大端小端？如何判断大端小端？
3.10、LRU的实现思想
4.1、并发(concurrency)和并行(parallelism)的区别？
4.2、windows消息机制
4.3、从源码到可执行文件的过程
4.4、静态链接和动态链接
4.5、GDB调试用过吗，什么是条件断点
5.1、简述5种I/O模型
5.2、异步编程的事件循环是什么？
6.1、Bitmap
6.2、Bitmap排序
6.3、Bitmap算法流程
6.4、Bitmap应用
7.1、linux和windows的比较
7.2、Linux常用命令
Created By No.5
操作系统基础
1.1、进程与线程的概念？
进程是对运行时程序的封装，是系统进行资源调度和分配的的基本单位，实现了操作系统的并发；
线程是进程的子任务，是 CPU 调度和分派的基本单位，用于保证程序的实时性，实现进程内部的并发；线程是操作
系统可识别的最小执行和调度单位。每个线程都独自占用一个虚拟处理器：独自的寄存器组，指令计数器和处理器状态。
每个线程完成不同的任务，但是共享同一地址空间（也就是同样的动态内存，映射文件，目标代码等等），打开的文件
队列和其他内核资源。
1.2、进程与线程的区别？
1、一个线程只能属于一个进程，而一个进程可以有多个线程，但至少有一个线程。线程依赖于进程而存在。
2、进程在执行过程中拥有独立的内存单元，而多个线程共享进程的内存。（资源分配给进程，同一进程的所有线程共享
该进程的所有资源。同一进程中的多个线程共享代码段（代码和常量），数据段（全局变量和静态变量），扩展段（堆
存储）。但是每个线程拥有自己的栈段，栈段又叫运行时段，用来存放所有局部变量和临时变量。）
3、进程是资源分配的最小单位，线程是 CPU 调度的最小单位；
4、系统开销：由于在创建或撤消进程时，系统都要为之分配或回收资源，如内存空间、I／o 设备等。因此，操作系统所
付出的开销将显著地大于在创建或撤消线程时的开销。类似地，在进行进程切换时，涉及到整个当前进程 CPU 环境
的保存以及新被调度运行的进程的 CPU 环境的设置。而线程切换只须保存和设置少量寄存器的内容，并不涉及存储
器管理方面的操作。可见，进程切换的开销也远大于线程切换的开销。
5、通信：由于同一进程中的多个线程具有相同的地址空间，致使它们之间的同步和通信的实现，也变得比较容易。进程
间通信 IPC，线程间可以直接读写进程数据段（如全局变量）来进行通信——需要进程同步和互斥手段的辅助，以保
证数据的一致性。在有的系统中，线程的切换、同步和通信都无须操作系统内核的干预
6、进程编程调试简单可靠性高，但是创建销毁开销大；线程正相反，开销小，切换速度快，但是编程调试相对复杂。
7、进程间不会相互影响 ；线程一个线程挂掉将导致整个进程挂掉
8、进程适应于多核、多机分布；线程适用于多核
1.3、进程间通信的方式：
进程间通信主要包括管道、系统 IPC（包括消息队列、信号量、信号、共享内存等）、以及套接字 socket。
1.管道：
管道主要包括无名管道和命名管道:管道可用于具有亲缘关系的父子进程间的通信，有名管道除了具有管道所具有的
功能外，它还允许无亲缘关系进程间的通信
1.1 普通管道 PIPE：
1)它是半双工的（即数据只能在一个方向上流动），具有固定的读端和写端
2)它只能用于具有亲缘关系的进程之间的通信（也是父子进程或者兄弟进程之间）
3)它可以看成是一种特殊的文件，对于它的读写也可以使用普通的 read、write 等函数。但是它不是普通的文件，
并不属于其他任何文件系统，并且只存在于内存中。
1.2 命名管道 FIFO：
1)FIFO 可以在无关的进程之间交换数据
2)FIFO 有路径名与之相关联，它以一种特殊设备文件形式存在于文件系统中。
2. 系统 IPC：
2.1 消息队列
消息队列，是消息的链接表，存放在内核中。一个消息队列由一个标识符（即队列 ID）来标记。 (消息队列克
服了信号传递信息少，管道只能承载无格式字节流以及缓冲区大小受限等特点)具有写权限得进程可以按照一定得规
则向消息队列中添加新信息；对消息队列有读权限得进程则可以从消息队列中读取信息；
特点：
1)消息队列是面向记录的，其中的消息具有特定的格式以及特定的优先级。
2)消息队列独立于发送与接收进程。进程终止时，消息队列及其内容并不会被删除。
3)消息队列可以实现消息的随机查询,消息不一定要以先进先出的次序读取,也可以按消息的类型读取。
Created By No.5
2.2 信号量 semaphore
信号量（semaphore）与已经介绍过的 IPC 结构不同，它是一个计数器，可以用来控制多个进程对共享资源的
访问。信号量用于实现进程间的互斥与同步，而不是用于存储进程间通信数据。
特点：
1)信号量用于进程间同步，若要在进程间传递数据需要结合共享内存。
2)信号量基于操作系统的 PV 操作，程序对信号量的操作都是原子操作。
3)每次对信号量的 PV 操作不仅限于对信号量值加 1 或减 1，而且可以加减任意正整数。
4)支持信号量组。
2.3 信号 signal
信号是一种比较复杂的通信方式，用于通知接收进程某个事件已经发生。
2.4 共享内存（Shared Memory）
它使得多个进程可以访问同一块内存空间，不同进程可以及时看到对方进程中对共享内存中数据得更新。这种
方式需要依靠某种同步操作，如互斥锁和信号量等
特点：
1)共享内存是最快的一种 IPC，因为进程是直接对内存进行存取
2)因为多个进程可以同时操作，所以需要进行同步
3)信号量+共享内存通常结合在一起使用，信号量用来同步对共享内存的访问
3.套接字 SOCKET：
socket 也是一种进程间通信机制，与其他通信机制不同的是，它可用于不同主机之间的进程通信。
1.4、线程间的通信方式
临界区：通过多线程的串行化来访问公共资源或一段代码，速度快，适合控制数据访问；
互斥量 Synchronized/Lock：采用互斥对象机制，只有拥有互斥对象的线程才有访问公共资源的权限。因为互斥对象只
有一个，所以可以保证公共资源不会被多个线程同时访问
信号量 Semphare：为控制具有有限数量的用户资源而设计的，它允许多个线程在同一时刻去访问同一个资源，但一般
需要限制同一时刻访问此资源的最大线程数目。
事件(信号)，Wait/Notify：通过通知操作的方式来保持多线程同步，还可以方便的实现多线程优先级的比较操作
1.5、线程的优势？
线程产生的原因：
进程可以使多个程序能并发执行，以提高资源的利用率和系统的吞吐量；但是其具有一些缺点：
1、进程在同一时间只能干一件事
2、进程在执行的过程中如果阻塞，整个进程就会挂起，即使进程中有些工作不依赖于等待的资源，仍然不会执行。
因此，操作系统引入了比进程粒度更小的线程，作为并发执行的基本单位，从而减少程序在并发执行时所付出的时
空开销，提高并发性。
和进程相比，线程的优势如下：
从资源上来讲，线程是一种非常"节俭"的多任务操作方式。在 linux 系统下，启动一个新的进程必须分配给它独立的
地址空间，建立众多的数据表来维护它的代码段、堆栈段和数据段，这是一种"昂贵"的多任务工作方式。
从切换效率上来讲，运行于一个进程中的多个线程，它们之间使用相同的地址空间，而且线程间彼此切换所需时间
也远远小于进程间切换所需要的时间。据统计，一个进程的开销大约是一个线程开销的 30 倍左右。
从通信机制上来讲，线程间方便的通信机制。对不同进程来说，它们具有独立的数据空间，要进行数据的传递只能
通过进程间通信的方式进行，这种方式不仅费时，而且很不方便。线程则不然，由于同一进城下的线程之间共享数据空
间，所以一个线程的数据可以直接为其他线程所用，这不仅快捷，而且方便。
除以上优点外，多线程程序作为一种多任务、并发的工作方式，还有如下优点：
1、使多 CPU 系统更加有效。操作系统会保证当线程数不大于 CPU 数目时，不同的线程运行于不同的 CPU 上。
2、改善程序结构。一个既长又复杂的进程可以考虑分为多个线程，成为几个独立或半独立的运行部分，这样的程序
才会利于理解和修改。
Created By No.5
1.6、进程的五种基本状态？什么是活动阻塞，静止阻塞，活动就绪，静止就绪？
1）创建状态：进程正在被创建
2）就绪状态：进程被加入到就绪队列中等待 CPU 调度运行
3）执行状态：进程正在被运行
4）等待阻塞状态：进程因为某种原因，比如等待 I/O，等待设备，而暂时不能运行。
5）终止状态：进程运行完毕
状态转换条件：
创建——>就绪
就绪——>执行 （调度）
执行——>阻塞 （等待某事件而睡眠）
阻塞——>就绪 （因等待事件发生而唤醒）
执行——>就绪 （时间片到，或者高优先级）
执行——>终止 （结束）
1）活动阻塞：进程在内存，但是由于某种原因被阻塞了。
2）静止阻塞：进程在外存，同时被某种原因阻塞了。
3）活动就绪：进程在内存，处于就绪状态，只要给 CPU 和调度就可以直接运行。
4）静止就绪：进程在外存，处于就绪状态，只要调度到内存，给 CPU 和调度就可以运行。
状态转换条件：
活动就绪 ——> 静止就绪
活动阻塞 ——> 静止阻塞
——> 静止就绪
执行
（内存不够，调到外存）
（内存不够，调到外存）
（时间片用完）
1.7、正常进程、孤儿进程和僵尸进程
1）正常进程
正常情况下，子进程是通过父进程创建的，子进程再创建新的进程。子进程的结束和父进程的运行是一个异步
过程，即父进程永远无法预测子进程到底什么时候结束。 当一个进程完成它的工作终止之后，它的父进程需要调用
wait()或者 waitpid()系统调用取得子进程的终止状态。
unix 提供了一种机制可以保证只要父进程想知道子进程结束时的状态信息， 就可以得到：在每个进程退出的时
候，内核释放该进程所有的资源，包括打开的文件，占用的内存等。 但是仍然为其保留一定的信息，直到父进程通
过 wait / waitpid 来取时才释放。保存信息包括：
1、进程号 the process ID
2、退出状态 the termination status of the process
3、运行时间 the amount of CPU time taken by the process 等
2）孤儿进程
一个父进程退出，而它的一个或多个子进程还在运行，那么那些子进程将成为孤儿进程。孤儿进程将被 init 进
程(进程号为 1)所收养，并由 init 进程对它们完成状态收集工作。
3）僵尸进程
一个进程使用 fork 创建子进程，如果子进程退出，而父进程并没有调用 wait 或 waitpid 获取子进程的状态信息，
那么子进程的进程描述符仍然保存在系统中。这种进程称之为僵尸进程。
僵尸进程是一个进程必然会经过的过程：这是每个子进程在结束时都要经过的阶段。
如果子进程在 exit()之后，父进程没有来得及处理，这时用 ps 命令就能看到子进程的状态是“Z”。如果父进程
能及时 处理，可能用 ps 命令就来不及看到子进程的僵尸状态，但这并不等于子进程不经过僵尸状态。
如果父进程在子进程结束之前退出，则 init 将会以父进程的身份对僵尸状态的子进程进行处理。
Created By No.5
危害：
如果进程不调用 wait / waitpid 的话，那么保留的那段信息就不会释放，其进程号就会一直被占用，但是系统所
能使用的进程号是有限的，如果大量的产生僵死进程，将因为没有可用的进程号而导致系统不能产生新的进程。
外部消灭：
通过 kill 发送 SIGTERM 或者 SIGKILL 信号消灭产生僵尸进程的进程，它产生的僵死进程就变成了孤儿进程，
这些孤儿进程会被 init 进程接管，init 进程会 wait()这些孤儿进程，释放它们占用的系统进程表中的资源
内部解决：
1、子进程退出时向父进程发送 SIGCHILD 信号，父进程处理 SIGCHILD 信号。在信号处理函数中调用 wait 进
行处理僵尸进程。
2、fork 两次，原理是将子进程成为孤儿进程，从而其的父进程变为 init 进程，通过 init 进程可以处理僵尸进程。
1.8、单核机器上写多线程程序，是否需要考虑加锁，为什么？
在单核机器上写多线程程序，仍然需要线程锁。
因为线程锁通常用来实现线程的同步和通信。在单核机器上的多线程程序，仍然存在线程同步的问题。因为在抢占
式操作系统中，通常为每个线程分配一个时间片，当某个线程时间片耗尽时，操作系统会将其挂起，然后运行另一个线
程。如果这两个线程共享某些数据，不使用线程锁的前提下，可能会导致共享数据修改引起冲突。
1.9、线程需要保存哪些上下文，SP、PC、EAX 这些寄存器是干嘛用的？
线程在切换的过程中需要保存当前线程 Id、线程状态、堆栈、寄存器状态等信息。其中寄存器主要包括 SP PC EAX
等寄存器，其主要功能如下：
SP:堆栈指针，指向当前栈的栈顶地址
PC:程序计数器，存储下一条将要执行的指令
EAX:累加寄存器，用于加法乘法的缺省寄存器
1.10、多进程和多线程的区别？使用场景是什么？
进程是资源分配的最小单位，而线程时 CPU 调度的最小单位。多线程之间共享同一个进程的地址空间，线程间通信
简单，同步复杂，线程创建、销毁和切换简单，速度快，占用内存少，适用于多核分布式系统，但是线程间会相互影响，
一个线程意外终止会导致同一个进程的其他线程也终止，程序可靠性弱。而多进程间拥有各自独立的运行地址空间，进
程间不会相互影响，程序可靠性强，但是进程创建、销毁和切换复杂，速度慢，占用内存多，进程间通信复杂，但是同
步简单，适用于多核、多机分布。
多进程模型的优势是 CPU，适用于 CPU 密集型。同时，多进程模型也适用于多机分布式场景中，易于多机扩展
多线程模型主要优势为线程间切换代价较小，因此适用于 I/O 密集型的工作场景，因此 I/O 密集型的工作场景经常会
由于 I/O 阻塞导致频繁的切换线程。同时，多线程模型也适用于单机多核分布式场景。
1.11、游戏服务器应该为每个用户开辟一个线程还是一个进程，为什么？
游戏服务器应该为每个用户开辟一个进程。因为同一进程间的线程会相互影响，一个线程死掉会影响其他线程，从
而导致进程崩溃。因此为了保证不同用户之间不会相互影响，应该为每个用户开辟一个进程
1.12、简述多线程的同步，锁的机制
同步的时候用一个互斥量，在访问共享资源前对互斥量进行加锁，在访问完成后释放互斥量上的锁。对互斥量进行
加锁以后，任何其他试图再次对互斥量加锁的线程将会被阻塞直到当前线程释放该互斥锁。如果释放互斥锁时有多个线
程阻塞，所有在该互斥锁上的阻塞线程都会变成可运行状态，第一个变为运行状态的线程可以对互斥量加锁，其他线程
将会看到互斥锁依然被锁住，只能回去再次等待它重新变为可用。在这种方式下，每次只有一个线程可以向前执行
1.13、什么是协程？
Created By No.5
协程，又称微线程，纤程，英文名 Coroutine。协程看上去也是子程序，但执行过程中，在子程序内部可中断，然后
转而执行别的子程序，在适当的时候再返回来接着执行。
例如：
def A() :
print '1'
print '2'
print '3'
def B() :
print 'x'
print 'y'
print 'z'
由协程运行结果可能是 12x3yz。在执行 A 的过程中，可以随时中断，去执行 B，B 也可能在执行过程中中断再去执
行 A。但协程的特点在于是一个线程执行
协程和线程区别：
那和多线程比，协程最大的优势就是协程极高的执行效率。因为子程序切换不是线程切换，而是由程序自身控制，
因此，没有线程切换的开销，和多线程比，线程数量越多，协程的性能优势就越明显。
第二大优势就是不需要多线程的锁机制，因为只有一个线程，也不存在同时写变量冲突，在协程中控制共享资源不
加锁，只需要判断状态就好了，所以执行效率比多线程高很多。
在协程上利用多核 CPU 呢——多进程+协程，既充分利用多核，又充分发挥协程的高效率，可获得极高的性能。
1.14、如何实现线程池
1.设置一个生产者消费者队列，作为临界资源
2.初始化 n 个线程，并让其运行起来，加锁去队列取任务运行
3.当任务队列为空的时候，所有线程阻塞
4.当生产者队列来了一个任务后，先对队列加锁，把任务挂在到队列上，然后使用条件变量去通知阻塞中的一个线程
1.15、fork 调用实例
1、概念：
Fork：创建一个和当前进程映像一样的进程可以通过 fork( )系统调用：
成功调用 fork( )会创建一个新的进程，它几乎与调用 fork( )的进程一模一样，这两个进程都会继续运行。在子进程中，成
功的 fork( )调用会返回 0。在父进程中 fork( )返回子进程的 pid。如果出现错误，fork( )返回一个负值。
最常见的 fork( )用法是创建一个新的进程，然后使用 exec( )载入二进制映像，替换当前进程的映像。这种情况下，
派生（fork）了新的进程，而这个子进程会执行一个新的二进制可执行文件的映像。这种“派生加执行”的方式是很常见
的。
在早期的 Unix 系统中，创建进程比较原始。当调用 fork 时，内核会把所有的内部数据结构复制一份，复制进程的页
表项，然后把父进程的地址空间中的内容逐页的复制到子进程的地址空间中。但从内核角度来说，逐页的复制方式是十
分耗时的。现代的 Unix 系统采取了更多的优化，例如 Linux，采用了写时复制的方法，而不是对父进程空间进程整体复
制。
2、fork 实例
int main(void){
pid_t pid;
signal(SIGCHLD, SIG_IGN);
printf("before fork pid:%d\n", getpid());
int abc = 10;
pid = fork();
Created By No.5
if (pid == -1) {
//错误返回
perror("tile");
return -1;
//父进程空间
}
if (pid > 0) {
abc++;
printf("parent:pid:%d \n", getpid());
printf("abc:%d \n", abc);
sleep(20);
}
else if (pid == 0) {
//子进程空间
abc++;
printf("child:%d,parent: %d\n", getpid(), getppid());
printf("abc:%d", abc);
}
printf("fork after...\n");
}
1.16、死循环+来连接时新建线程的方法效率有点低，怎么改进？
提前创建好一个线程池，用生产者消费者模型，创建一个任务队列，队列作为临界资源，有了新连接，就挂在到任
务队列上，队列为空所有线程睡眠。改进死循环：使用 select epoll 这样的技术
1.17、Epoll
epoll 在 Linux2.6 内核正式提出，是基于事件驱动的 I/O 方式，相对于 select 来说，epoll 没有描述符个数限制，
使用一个文件描述符管理多个描述符，将用户关心的文件描述符的事件存放到内核的一个事件表中，这样在用户空
间和内核空间的 copy 只需一次。
Linux 中提供的 epoll 相关函数如下：
int epoll_create(int size);
int epoll_ctl(int epfd, int op, int fd, struct epoll_event *event);
int epoll_wait(int epfd, struct epoll_event * events, int maxevents, int timeout);
1. epoll_create 函数创建一个 epoll 句柄，参数 size 表明内核要监听的描述符数量。调用成功时返回一个 epoll
句柄描述符，失败时返回-1。
2. epoll_ctl 函数注册要监听的事件类型。四个参数解释如下：
epfd 表示 epoll 句柄
op 表示 fd 操作类型，有如下 3 种
EPOLL_CTL_ADD 注册新的 fd 到 epfd 中
EPOLL_CTL_MOD 修改已注册的 fd 的监听事件
EPOLL_CTL_DEL 从 epfd 中删除一个 fd
fd 是要监听的描述符
event 表示要监听的事件
epoll_event 结构体定义如下：
struct epoll_event {
__uint32_t events; /* Epoll events */
epoll_data_t data; /* User data variable */
};
Created By No.5
typedef union epoll_data {
void *ptr;
int fd;
__uint32_t u32;
__uint64_t u64;
} epoll_data_t;
3. epoll_wait 函数等待事件的就绪，成功时返回就绪的事件数目，调用失败时返回 -1，等待超时返回 0。
epfd 是 epoll 句柄
events 表示从内核得到的就绪事件集合
maxevents 告诉内核 events 的大小
timeout 表示等待的超时事件
epoll 是 Linux 内核为处理大批量文件描述符而作了改进的 poll，是 Linux 下多路复用 IO 接口 select/poll 的增强版本，
它能显著提高程序在大量并发连接中只有少量活跃的情况下的系统 CPU 利用率。原因就是获取事件的时候，它无须遍历
整个被侦听的描述符集，只要遍历那些被内核 IO 事件异步唤醒而加入 Ready 队列的描述符集合就行了。
epoll 除了提供 select/poll 那种 IO 事件的水平触发（Level Triggered）外，还提供了边缘触发（Edge Triggered），
这就使得用户空间程序有可能缓存 IO 状态，减少 epoll_wait/epoll_pwait 的调用，提高应用程序效率。
水平触发（LT）：默认工作模式，即当 epoll_wait 检测到某描述符事件就绪并通知应用程序时，应用程序可以不立
即处理该事件；下次调用 epoll_wait 时，会再次通知此事件
边缘触发（ET）： 当 epoll_wait 检测到某描述符事件就绪并通知应用程序时，应用程序必须立即处理该事件。如果
不处理，下次调用 epoll_wait 时，不会再次通知此事件。（直到你做了某些操作导致该描述符变
成未就绪状态了，也就是说边缘触发只在状态由未就绪变为就绪时只通知一次）。
LT 和 ET 原本应该是用于脉冲信号的，可能用它来解释更加形象。Level 和 Edge 指的就是触发点，Level 为只要处
于水平，那么就一直触发，而 Edge 则为上升沿和下降沿的时候触发。比如：0->1 就是 Edge，1->1 就是 Level。
ET 模式很大程度上减少了 epoll 事件的触发次数，因此效率比 LT 模式下高。
1.18、select,poll,epoll 的区别
操作方式
底层实现
IO 效率
select
遍历
数组
poll
遍历
链表
epoll
回调
哈希表
每次调用都进行线性遍历，
时间复杂度为 O(n)
每次调用都进行线性遍历，时
间复杂度为 O(n)
事件通知方式，每当 fd 就绪，系统注册
的回调函数就会被调用，将就绪 fd 放到
readyList 里面，时间复杂度 O(1)
fd 拷贝
最大连接数 1024（x86）或 2048（x64）
每次调用 select，都需要把
fd 集合从用户态拷贝到内核
态
无上限
无上限
每次调用 poll，都需要把 fd 集
合从用户态拷贝到内核态
调用 epoll_ctl 时拷贝进内核并保存，之
后每次 epoll_wait 不拷贝
2.0、死锁发生的条件以及如何解决死锁
死锁是指多个进程因竞争资源而造成的一种僵局（互相等待），若无外力作用，这些进程都将无法向前推进。例如，
在某一个计算机系统中只有一台打印机和一台输入设备，进程 P1 正占用输入设备，同时又提出使用打印机的请求，但此
时打印机正被进程 P2 所占用，而 P2 在未释放打印机之前，又提出请求使用正被 P1 占用着的输入设备。这样两个进程
相互无休止地等待下去，均无法继续执行，此时两个进程陷入死锁状态。
死锁发生的四个必要条件如下
互斥条件：
Created By No.5
进程对所分配到的资源不允许其他进程访问，若其他进程访问该资源，只能等待，直至占有该资源的进程使用完成
后释放该资源；
请求和保持条件：
进程获得一定的资源后，又对其他资源发出请求，但是该资源可能被其他进程占有，此时请求阻塞，但该进程不会
释放自己已经占有的资源
不可剥夺条件：
进程已获得的资源，在未完成使用之前，不可被剥夺，只能在使用后自己释放
环路等待条件：
进程发生死锁后，必然存在一个进程-资源之间的环形链
2.1、避免死锁
死锁避免的基本思想：系统对进程发出的每一个系统能够满足的资源申请进行动态检查，并根据检查结果决定是否
分配资源，如果分配后系统可能发生死锁，则不予分配，否则予以分配，这是一种保证系统不进入死锁状态的动态
策略。
如果操作系统能保证所有进程在有限时间内得到需要的全部资源，则系统处于安全状态否则系统是不安全的。
安全状态：如果系统存在 由所有的安全序列{P1，P2，…Pn},则系统处于安全状态。一个进程序列是安全的，如果
对其中每一个进程 Pi(i >=1 && i <= n)他以后尚需要的资源不超过系统当前剩余资源量与所有进程
Pj(j < i)当前占有资源量之和，系统处于安全状态则不会发生死锁。
不安全状态：如果不存在任何一个安全序列，则系统处于不安全状态。
2.2、预防死锁
我们可以通过破坏死锁产生的 4 个必要条件来预防死锁，由于资源互斥是资源使用的固有特性是无法改变的。
破坏“不可剥夺”条件：
一个进程不能获得所需要的全部资源时便处于等待状态，等待期间他占有的资源将被隐式的释放重新加入到 系统的
资源列表中，可以被其他的进程使用，而等待的进程只有重新获得自己原有的资源以及新申请的资源才可以重新启
动，执行。
破坏“请求与保持条件”：
第一种方法静态分配即每个进程在开始执行时就申请他所需要的全部资源。第二种是动态分配即每个进程在申请所
需要的资源时他本身不占用系统资源。
破坏“循环等待”条件：
采用资源有序分配其基本思想是将系统中的所有资源顺序编号，将紧缺的，稀少的采用较大的编号，在申请资源时
必须按照编号的顺序进行，一个进程只有获得较小编号的进程才能申请较大编号的进程。
2.3、常见死锁相关算法
银行家算法：避免死锁
资源有序分配法：预防死锁
资源分配图化简法：检测死锁
撤销进程法：解决死锁
2.3、银行家算法（避免死锁）
银行家算法是从当前状态出发，按照系统各类资源剩余量逐个检查各进程需要申请的资源量，找到一个各
类资源申请量均小于等于系统剩余资源量的进程 P1。然后分配给该 P1 进程所请求的资源，假定 P1 完成工
作后归还其占有的所有资源，更新系统剩余资源状态并且移除进程列表中的 P1，进而检查下一个能完成工
作的客户，......。如果所有客户都能完成工作，则找到一个安全序列，银行家才是安全的。若找不到这样
的安全序列，则当前状态不安全。
相关数据结构
相关推荐
2023年江西萍乡中考道德与法治真题及答案.doc
2012年重庆南川中考生物真题及答案.doc
2013年江西师范大学地理学综合及文艺理论基础考研真题.doc
2020年四川甘孜小升初语文真题及答案I卷.doc
2020年注册岩土工程师专业基础考试真题及答案.doc
2023-2024学年福建省厦门市九年级上学期数学月考试题及答案.doc
2021-2022学年辽宁省沈阳市大东区九年级上学期语文期末试题及答案.doc
2022-2023学年北京东城区初三第一学期物理期末试卷及答案.doc
2018上半年江西教师资格初中地理学科知识与教学能力真题及答案.doc
2012年河北国家公务员申论考试真题及答案-省级.doc
2020-2021学年江苏省扬州市江都区邵樊片九年级上学期数学第一次质量检测试题及答案.doc
2022下半年黑龙江教师资格证中学综合素质真题及答案.doc
