操作系统复习（1）https://developer.aliyun.com/article/1530633
三,处理机调度和死锁
3.1 处理机调度概述
作业通常是指用户在一次计算过程中或者一次事物处理过程中要求计算机系统所做工作的集合,包括用户程序、所需的数据及命令等。进程是具有独立功能的可并发执行的程序在一个数据集合上的运行过程,是系统进行资源分配和调度的独立单位。作业和进程之间的区别和联系如下:
1.作业是用户向计算机提交的任务实体,而进程则是完成用户任务的执行实体,是向操作系统申请分配资源的基本单位。
2.一个作业可以由多个进程组成,且一个作业至少由一个进程组成。
调度层次
高级调度
调度作业
中级调度
调度内存
低级调度
调度进程
3.2 调度算法 🎃
先来先服务(FCFS)
选择队头的进程为之分配处理机
缺点:很多很多,比如第一个进程很长的话后面会有很多进程一直在等待,而且也没有考虑进程的重要性啥的
短作业优先调度(SJF)
作业所要求的的运行时间越短,越优先执行
缺点:
- 很难估计作业所需运行时间
- 忽视了作业等待时间,可能会使作业的等待时间过长
- 无法实现人机交互(我的理解是程序的运行次序都定死了)
- 不能使紧迫的作业得到及时处理和FCFS同样的缺点
优先级调度算法
貌似前面的俩家伙都算是优先级调度算法
但是这里的优先级是基于进程的紧迫程度
优先级调度算法类型
（1）非抢占式优先权调度算法
系统一旦把处理机分配给优先权最高的进程后，便一直执行下去，至完成。
（2）抢占式优先权调度算法
只要系统中出现一个新的就绪进程，就进行优先权比较 。若出现优先权更高的进程，则立即停止当前执行，并将处理机分配给新到的优先权最高的进程。
(你强,但是我比你更强😼,直接interrupt you)
优先级类型
- 静态优先级进程创建时候确定依据:
- 进程类型(系统>用户)
- 进程对资源的要求(少的优先)
- 用户要去
- 动态优先级
- 随着时间的推迟,进程的优先级会发生变化
- 高响应比优先调度(HRRN)
优先级 = 等待时间 + 要求服务时间 要求服务时间 优先级=\frac{等待时间+要求服务时间}{要求服务时间}优先级=要求服务时间等待时间+要求服务时间
轮转调度算法(RR)😫
没看懂书上的
多级队列调度算法
不同
四,进程同步🧐
4.1 进程同步和互斥
基本概念
- 临界资源
临界资源是一次只允许一个进程访问的资源,各个进程以互斥的方式实现共享 - 临界区
每个资源访问临界区的那段代码就是临界区,每次都只有一个进程进入临界区,就比如打印机,每次正在使用的人只有一个
临界资源的访问过程分为4个部分:
a.进入区。负责检查是否可以进入临界区,设置正在访问临界资源的标志。(相当于上了把锁)
b.临界区。访问临界资源的那段代码。
c.退出区。负责解除正在访问临界资源的标志。
d.剩余区。做其他处理。
同步机制应该遵循的准则
这些准则的目的是为了实现进程互斥的进入自己的临界区
- 空闲让进
- 忙则等待
- 有限等待 (我只等有限的时间,超过这个时间就不等了)
- 让权等待 (这个不是必须的) 我不能进入自己的临界区了,就释放掉处理器那些资源,以防进入忙等
信号量机制😥
这是为了解决同步和互斥问题的
信号量机制是一种功能较强的机制，可用来解决互斥和同步问题，它只能被两个标准的原语wait(S)和signal(S)访问，也可记为“P操作”和“V操作”。
1. 整型信号量
整型信号量被定义为一个用于表示资源数目的整型量S。P和V操作可描述为:
wait(S){
while(S<=0); 这里是如果S资源<=0的情况下是一直在等待资源的到来
S=S-1;}
signal(S){
S=S+1}
该机制并未遵循“让权等待”的准则，而是使进程处于“忙等”的状态。
2. 记录型信号量
记录型信号量是不存在“忙等”现象的进程同步机制。除需要一个用于代表资源数目的整型变量value外，再增加一个进程链表L,用于链接所有等待该资源的进程。
typedef struct{ int value; struct process *L} semaphore; void wait(semaphore S){s. value - - ; if(S. value<0){add this process to S.L; //如果资源<0就挂到阻塞队列里面去 block(S. L);}} void signal (semaphore *S){ S. value++; if(S.value<=0){ //释放资源的时候如果value<=0那说明队列中有进程还在被阻塞,然后就释放队列中的第一个进程 remove a process to S.L; wakeup(P); }}
信号量的应用
1.互斥
相当于一把锁的作用,拿资源的时候上锁,使用完资源释放锁
2.同步
如果进程是先执行v操作的话,s+1变为1,然后可以进行p2执行C2,如果是先执行p操作的话s=-1,会把自己阻塞,只有p1执行v操作后才会释放阻塞
这样保证了c1一定是在c2之前执行的.
总结:
（1）同步信号量，值为资源可以使用的个数，信号量小于0，则线程进行等待，信号量大于0，表示可用资源个数。初始值一般为0.
（2）互斥信号量只有两个值0或1，0表示资源正在被占用，线程等待。1表示，资源没有被使用，线程可以进入。初始值为1
4.2 使用信号量解决同步问题
基本解题步骤
PV操作题目分析的步骤:
①关系分析。找出题目中描述的各个进程，分析它们之间的同步、互斥关系。
②整理思路。根据各进程的操作流程确定操作的大致顺序。
③设置信号量。设置需要的信号量，并根据题目条件确定信号量的初值。
如何实现
互斥的实现是在同一个进程中进行一对PV 操作。
同步的实现是在两个进程中进行，在一个进程中执行P操作，在另一个进程中执行v操作。
生产者消费者问题
需要注意的是互斥操作在一个个进程内成对出现,同步操作在不同进程之间同步出现
为什么这样安排？可能是因为互斥操作必须紧邻“临界区”的缘故。互斥操作要紧邻临界区，才能充分地发挥作用。这里也就是把产品放入缓冲区或者拿出缓冲区的操作
读者-写者问题
两个并发进程共享一个文件，当两个或两个以上的读进程共同访问数据时不会产生副作用。但多个写进程同时访问数据可能会导致数据不一样。因此要求：允许多个读者可以同时对文件进行读操作。只允许一个写者往文件里写信息，在任一写者完成操作前不允许其他读者或写者工作，写者执行操作前应该给让所以其余的读者或写者退出。
算法：在上锁前进行判断，第一个读进程负责加锁，最后一个读进程负责解锁，其中还有个互斥信号量保证对读者数量的互斥操作,在这两个过程中要设置互斥变量来保证检查与赋值一气呵成。在写进程的前后设置PV，在读进程前设置PV，保证读写进程有序进行，不会出现饥饿。
哲学家就餐问题
圆桌上两个哲学家中间有一根筷子，每个哲学家只能用他两边的筷子吃饭，一旦缺少一根进程就会被阻塞。
算法：设置信号量数组chopstick[5] = {1,1,1,1,1},每个哲学家i左边的筷子编号为i，右边的筷子编号为（i+1）%5.每个哲学家先对左右两边的筷子进行P操作，在完成进程后再对两边进行V操作。
如果不加条件，如果所有哲学家并发用餐就会出现死锁现象。
可以添加的条件：1.限制最大进餐人生；2，对于奇数号哲学家先拿左边的筷子，对于偶数号的哲学家先拿右边的筷子。（用争抢防止阻塞）；3.仅当哲学家左右两只筷子都可用时才允许他抓起筷子
4.3 管程
管程（Monitor）是一种用于实现并发控制的编程机制。它提供了一种结构化的方式来管理共享资源的访问，并确保线程之间的同步和互斥。管程机制最初由荷兰计算机科学家Edsger Dijkstra在1965年提出，并在之后的几十年中得到了广泛应用和研究。
管程的基本思想是将共享资源和对该资源的操作封装在一个单元内部。这个单元包含了用于操作共享资源的一组过程或方法，以及用于同步和互斥的机制。通过使用管程，可以确保只有一个线程能够同时访问共享资源，从而避免了竞态条件和数据不一致性的问题。
管程机制通常包括以下几个关键要素：
- 数据结构：管程内部包含一个或多个共享资源，可以是变量、队列、缓冲区等。这些数据结构被管程的过程所使用和操作。
- 过程（Procedure）：管程内部定义了一组过程或方法，用于对共享资源进行操作。每个过程都是原子性的，一次只能由一个线程执行。通过调用这些过程，线程可以安全地访问和修改共享资源。
- 条件变量（Condition Variable）：管程中的条件变量用于实现线程之间的等待和通知机制。线程可以通过等待一个条件变量来释放对共享资源的占用，并暂时阻塞。当某个条件满足时，其他线程可以通过通知条件变量来唤醒等待的线程。
- 互斥锁（Mutex）：管程通常使用互斥锁来实现对共享资源的互斥访问。只有获取了互斥锁的线程才能执行管程内部的过程。其他线程必须等待互斥锁的释放才能执行管程中的操作。
管程机制的优点在于提供了一种高级抽象的并发控制方式，使得程序员能够更方便地编写并发代码。通过将共享资源和操作封装在管程内部，可以减少竞争条件和死锁等并发问题的出现。此外，管程的条件变量和互斥锁提供了线程之间的同步和互斥机制，可以确保线程按照预期的顺序访问共享资源。
需要注意的是，管程并不是一种语言提供的原生机制，而是一种抽象的概念。不同的编程语言和环境提供了不同的实现方式，如Java中的synchronized关键字和wait/notify机
在Java中，可以使用synchronized关键字和wait()/notify()方法来实现管程的功能。下面是一个使用管程的简单示例：
class Monitor { private int sharedData; public synchronized void processData() { // 管程过程：对共享资源进行操作 // 在管程过程中可以使用synchronized关键字确保互斥访问 // 例如，这里可以修改sharedData的值 sharedData = 10; // 唤醒等待的线程 notify(); } public synchronized void waitForData() throws InterruptedException { // 管程过程：线程等待共享资源的条件 // 在管程过程中可以使用synchronized关键字确保互斥访问 // 例如，这里可以检查sharedData的值是否满足特定条件 while (sharedData != 10) { // 等待共享资源满足条件 wait(); } // 共享资源满足条件，执行后续操作 } }
在上述示例中，Monitor类代表了一个简单的管程，其中包含了两个管程过程：processData()和waitForData()。这两个过程都使用了synchronized关键字，以确保在同一时间只有一个线程可以进入管程执行过程。
在processData()过程中，共享资源sharedData被修改，并通过notify()方法唤醒等待的线程。
在waitForData()过程中，线程会等待共享资源满足特定条件。如果共享资源的值不满足条件，线程会调用wait()方法进入等待状态，释放锁并让其他线程执行。一旦共享资源满足条件，其他线程通过notify()方法唤醒等待的线程。
请注意，以上示例仅为演示如何使用synchronized、wait()和notify()来实现管程的基本功能。在实际开发中，可能需要更复杂的管程实现，例如使用ReentrantLock和Condition等类来实现更灵活的管程机制。
语言基本上本身不提供管程的实现
在其他编程语言中，有些语言提供了原生的管程机制，而有些语言则需要使用特定的库或框架来实现管程功能。以下是一些常见编程语言的管程实现方式：
- C/C++：C/C++本身没有原生的管程机制。但是可以使用线程库（如pthread）提供的互斥锁（mutex）和条件变量（condition variable）来实现管程。通过使用互斥锁和条件变量，可以实现对共享资源的互斥访问和线程之间的同步。
- Python：Python提供了
threading模块和Lock、Condition等类来支持管程的实现。可以使用Lock类来实现互斥访问，使用Condition类来实现等待和通知机制。 - C#：C#提供了
Monitor类来实现管程。可以使用Monitor类的方法如Enter()、Exit()、Wait()和Pulse()来实现互斥访问和线程等待和通知。 - Rust：Rust通过标准库提供了
std::sync::Mutex和std::sync::Condvar等类型，用于实现管程。Mutex用于实现互斥访问，Condvar用于实现线程等待和通知。 - Go：Go语言的并发模型本身就提供了原生的管程机制。通过使用关键字
go和chan，可以实现对共享资源的互斥访问和线程之间的同步。
需要注意的是，具体实现方式可能因编程语言和使用的库或框架而有所不同。某些编程语言可能提供了更高级的管程实现，例如活跃对象（Active Object）模型或消息传递机制。在选择编程语言和实现管程时，可以根据具体需求和语言特性来进行选择。
管程相对于普通方式实现同步和互斥具有以下优点：
- 结构化：管程提供了一种结构化的编程方式，将共享资源、操作和同步机制封装在一个单元内部。这样可以更清晰地组织代码，使得并发控制的逻辑更易于理解和维护。
- 简化同步：使用管程可以简化同步的实现。管程内部的互斥锁和条件变量可以由编程语言或框架提供，减少了手动实现同步的复杂性。开发者可以专注于共享资源的操作，而无需显式处理底层的同步机制。
- 避免竞态条件：管程通过互斥访问共享资源，确保同一时间只有一个线程可以访问。这样可以避免竞态条件的出现，即多个线程同时对共享资源进行修改导致不确定的结果。
- 避免死锁：管程内部的同步机制可以帮助避免死锁的发生。通过使用条件变量来等待和通知线程，可以确保线程之间按照预期的顺序进行同步，避免了死锁的可能性。
- 提高可扩展性：管程提供了一种高级抽象，可以更容易地实现并发控制。通过将共享资源和相关操作封装在管程内部，不同的线程可以独立地调用管程过程，从而提高了代码的可扩展性和重用性。
总而言之，管程提供了一种结构化、简化和安全的方式来实现并发控制。它可以帮助开发者避免常见的并发问题，提高代码的可读性和可维护性，同时提供了更高层次的抽象，使并发编程更加容易和安全。
