操作系统知识复习

操作系统知识复习

主要涉及的知识有PV 操作和进程死锁文件管理

PV 操作和进程死锁

进程的概述和进程的状态

进程是一个程序关于某个数据集的一次运行。通俗的说,当打开了两个 QQ 时,其程序是一个,但创建了两个互不相关的进程。进程是运行中的程序,具有动态性和并发性的特点。进程也是系统资源分配、调度、管理的最小单位(现在的操作系统中还引入了线程钟,即轻量级进程,它是处理器分配的最小单位)。

一个进程从创建而产生到撤销而消亡的整个生命周期,可以用一组状态加以刻画。为了便于管理进程,把进程划分为3种状态。亦是进程的运行态就绪态阻塞态

运行态:占用处理器的时间,代表正在运行。

就绪态:具备运行的条件,正在等待某件事的完成。

等待态(阻塞态):不具备运行条件,正在等待某事件的完成。

一个进程在创建完成后将处于就绪态。在执行过程中,每个进程任意一时刻当且仅当处于上面的三种状态的其中一种。

在操作系统中通常使用进程控制块(PCB)来标记进程,因此从某种意义上来说进程是由进程控制块,程序,数据构成。

信号量与 P、V操作

在操作系统种,进程之间经常存在互斥(都需要共享独占性资源时)和同步(完成异步的两个进程的协作)两种关系。为了有效的处理这两种情况,W.Dijkstra 在1965年提出了信号量 P 、V 操作的概念。

信号量:是一种特殊的变量,表现形式是一个整型 S 和一个队列。

P 操作:也称为 down()、wait() 操作,使 S=S-1,若 S<0,进程暂停执行,放入信号量的等待队列;

V 操作:也称为 up()、signal() 操作,使 S=S+1,若S>0,唤醒等待队列中的一个进程。

信号量、P操作、V操作的结合常见于:完成互斥控制完成同步控制生产者-消费者问题阅读者和写入者这四种情况。

完成互斥控制

它其实就是保护共享资源,不让多个进程同时访问这个共享资源,换句话说,就是阻止多个进程同时进入访问这些资源的代码段,这个代码段称为临界区(也称管程),而这种一次仅允许一个进程访问的资源称为临界资源。对于临界区的代码就是:

P(信号量)

临界区

V(信号量)

由于只允许一个进程进入,因此信号量中整型值的初始值应该为1。该值表示可以允许多个进程进入。当该值<0时,其绝对值就是等待使用的进程数,也就是等待队列中的进程数。而当一个进程从临界区出来时,就会将整型值加1,如果等待队列中还有进程,则调入一个新的进程进入(唤醒)。

完成同步控制

最简单的同步方式是进程 A 在另一个进程 B 到达 L2 以前,不应前进行超过点L1,这样就可以使用程序:

进程A    进程B

...           ...

L1:P(信号量)  L2:V(信号量

因此要确保进程 B 执行 V 操作之前,不让进程 A 的运行超过 L1 ,信号量的初始值就应该为0,这样,如果进程 A 先执行到 L1,那么执行 P 操作后,信号量的整型值就会小于 1,也就会停止执行。直到进程 B 执行到 L2 时,将信号量的整型值减 1,并唤醒它以继续执行。

生产者-消费者问题

生产者-消费者是一个经典的问题,它不仅要解决生产者与消费者进程的同步关系,还要处理缓冲区的互斥关系,因此通常需要三个信号量来实现。其中,两个用来管理同步:empty 信号量 (说明空闲的缓冲区数量,最早没有产生东西,因此其初始值应为缓冲区的最大数) 和 full 信号量(说明已填充的缓冲区数量,其初始值应为0)。另一个 mutex 信号量用来管理互斥,以保证同时只有一个进程在写缓冲区(因此其初始值应为1)。

生产者    消费者

loop        loop

...            ...

生产一个产品:p(full)

p(empty);          p(mutex);

p(mutex);          从缓冲区中取一个产品;

将新产品放入缓冲区;    V(mutex);

V(mutex);          V(empty);

V(full);               使用产品;

...                       ...

Endloop endloop

注:如果对缓冲区的读写无须进行互斥控制的话,那么就可以省去 mutex 信号量。

阅读者和写入者问题

假设有一个数据集被多个并行进程共享,其中有些进程只是读这个数据集,而有些进程则需要修改这个数据集的内容。这里存在着一个什么洋的并发关系呢?阅读者互相不影响,但写入这则是互斥访问的。因此,解决这个问题的最简单的方法是:当没有写入者在访问共享数据集时,阅读者可以进入访问,否则必须等待。下面则是一个读者优先的解法(其中信号量 access 用来控制写入互斥;而信号量 rc 则用来控制 re(读者统计值)的互斥访问):

阅读者    写入者

loop        loop

P (rc)      ...

ReaderCount=ReaderCount+1; P(access);

if (ReaderCount == 1) 修改数据;

P (access);   V(accress);

V (rc); ...

访问数据;   endloop

P (rc);

ReaderCount=ReaderCount-1;

if (ReaderCount == 0)

V (access);

V (rc);

endloop

理解P、V操作

信号量与 P 、V 操作是用来解决并发问题的,而在并发问题中最重要的是互斥和同步两个关系,也就是说,只要这两个关系存在,信号量就有用武之地。

一般来说,一个互斥或同步关系可以使用一个信号量来解决,但要注意经常会忽略一些隐藏的同步关系。例如,在生产者--消费者问题当中,就有两个同步关系,一是判断是否还有足够的空间给生产者存放产物,另一个是判断是否有足够的内容让消费者使用。

信号量的初始值通常是表示资源的可用数。而且对于初始值为0的信号量,通常会做V操作。

在使用资源之前,将会使用 P 操作。在资源用完之前,将会使用 V 操作。在互斥关系中,P、V 操作是在一个进程中成对出现的。而在同步关系中,P、V 则一定会是在两个进程甚至多个进程中成对出现的。

另外,值得一提的时,操作系统还提供了一些高级通信原语,如 Write/Read ,Send/Receive 可以实现相同的功能,他们能更好的补充P、V操作的不足,完成个更多的功能。

进程死锁和银行家算法

进程管理是操作系统的核心,但如果设计不当,就会出现死锁的问题。如果一个进程在等待一个不可能发生的事,则进程就被死锁了。而如果一个或者多个进程产生死锁,就会造成系统死锁。

下面是造成系统死锁的四个必要条件:

互斥条件:即一个资源每次只能被一个进程使用,在操作系统中这是真实存在的情况。

保持和等待条件:有一个进程已获得了一些资源。但因请求其他资源被阻塞时,对已获得的资源保持不放。

不可剥夺条件:有些系统资源时不可剥夺的,当某个进程已获得这种资源后,系统不能强制回收,只能由进程使用完时自己释放。

环路等待条件:若干个进程形成环形链,每个都占用对方要申请的下一个资源。

银行家算法即为在分配资源之前,先看清楚,如果资源分配下去之后,是否会导致系统死锁,如果会死锁,则不分配,否则就分配。

银行家算法求最少不发生死锁的资源数:

最少不发生死锁的资源数 >= 进程数 * (需求得资源数 - 1) +1

例如,若在系统中由若干个互斥资源 R ,6和并发进程中每一个都需要两个资源 R,那么为了使系统不发生死锁 R 的最少资源数目为多少个?

解:根据题意得:

∵ 6  * (2 -1)+ 1 = 7

∴ 为了使系统不发生死锁 R 的最少资源数目应该为 7 个。

解决进程死锁的四个策略:

死锁预防:“解铃还须系铃人”,随便破坏导致死锁的任意一个必要条件就可以预防死锁。例如,要求用户申请资源是一次性申请完所需要的全部资源,这样就破坏了保持和等待条件。将资源分层,道道上一层资源后,才能够申请下一层资源,它破坏了环路等待条件,预防通常降低系统的效率。

死锁避免:避免使指进程在每次申请资源时判断这些操作是否安全,典型的算法是银行家算法,但这种算法会增加系统的开销。

死锁检测:前两者是事前措施。而死锁的检测则是判断系统是否处于死锁状态,如果是,则执行死锁解除的策略。

死锁解除:这是与死锁检测结合使用的,它使用的方式就是剥夺。即将某进程所拥有的资源强制回收,分配给其他的进程。

文件管理

文件控制块的集合称为文件目录,文件目录也被组织成文件,常称为文件目录。文件管理器的一个重要方面是对文件目录的进行组织和管理。文件系统一班采用一级目录结果、二级目录结构或者多级目录结构。例如 DOS、UNIX 和 Windows 系统都采用多级树型目录结构。

在多级树型目录结构种,整个文件系统有一个根,然后根上分枝,任何一个分枝上都可以再分枝,枝上也可以长出树叶。根和枝称为目录或者文件夹,而树叶则是一个个的文件。实践证明,这种结构的文件系统效率比较高。一般在纸面上表达的时候。方框代表目录,圆形代表的则是文件。

在树型目录结构种,树的根结点为根目录,数据文件作为树叶,其他所有目录均作为树的结点。系统在建立每一个目录时,都会为它自动设定两个目录文件,一个是 “.”,它代表该目录本身,另一个是 “..” ,代表该目录得父目录。对于根目录而言,“.” 和 “..” 都代表其本身。值得注意的是,路径分为相对路径和绝对路径。绝对路径是指从根目录开始的路径,也称完全路径;相对路径是指从用户工作目录开始的路径。

另外,在 Windows 系统中,有两种格式的文件,分别是 FAT32(FAT16)文件和 NTFS文件。 NTFS 文件在使用中产生的磁盘碎片要比 FAT32少,安全性也更高,而且支持单个文件的容量更大,超过了 4GB,特别适合现在的大容量存储。NTFS可以支持的分区(如果采用动态磁盘则称为卷)大小可以达到 2TB。


回复列表



回复操作

正在加载验证码......

请先拖动验证码到相应位置

发布时间:2020-06-19 12:04:59

修改时间:2020-06-20 10:43:31

查看次数:40

评论次数:0