做网站需要什么资金,新泰市住房和城乡建设局网站,杭州营销型网站怎么做,网络营销发展历程ppt目录第二章 2.1_1进程的定义、组成、组成形式、特征 2.1_2进程的状态与转换 2.1_3进程的控制 2.1_4进程通信 2.1_5线程概念和多线程模型 2.2_1处理机调度的概念层次 2.2_2处理机调度的时机、切换与过程、方式 2.2_3调度算法的评价指标 2.2_4FCFS、SJF、HRRN调度算法 2.2_5时间片…目录第二章 2.1_1进程的定义、组成、组成形式、特征 2.1_2进程的状态与转换 2.1_3进程的控制 2.1_4进程通信 2.1_5线程概念和多线程模型 2.2_1处理机调度的概念层次 2.2_2处理机调度的时机、切换与过程、方式 2.2_3调度算法的评价指标 2.2_4FCFS、SJF、HRRN调度算法 2.2_5时间片轮转、优先级调度多级反馈队列调度算法 2.3_1进程同步、进程互斥 2.3_2进程互斥软件的实现方法 2.3_3进程互斥的硬件实现方法 2.3_4信号量机制 2.3_5用信号量机制实现进程互斥、同步、前驱关系 2.3_6生产者-消费者问题 2.3_7多生产者-多消费者问题 2.3_8读者-写者问题 2.3_9哲学家进餐问题 2.3_10管程 2.4_1死锁的概念 2.4_2死锁的处理策略-预防死锁 2.4_3死锁的处理策略-避免死锁 2.4_4死锁的处理策略-检测和解除
第二章
2.1_1进程的定义、组成、组成形式、特征 重点
1 PCBPCB是进程存在的唯一标志每个进程都有且仅有一个PCB其内存放着进程描述信息、进程控制和管理信息、资源分配清单、处理机相关信息。 2进程与程序的区别 程序是静态的进程是动态的程序是存储在某种介质上的二进制代码进程对应了程序的执行过程系统不需要为一个不执行的程序创建进程一旦进程被创建就处于不断变化的动态过程中对应了一个不断变化的上下文环境。 程序是永久的进程是暂时存在的。程序的永久性是相对于进程而言的只要不去删除它它可以永久的存储在介质当中。
2.1_2进程的状态与转换 重点
**1三个重要状态 ①运行态占用CPU其他信息资源具备 ②就绪态不占用CPU但是其他资源具备等待CPU ③阻塞态不占用CPU其他资源不具备 2进程状态间的转换重点阻塞态不能直接转化为运行态 ①就绪态-运行态当有空闲的CPU时处于就绪态的进程将转换为运行态 ②运行态-就绪态时间片到或者CPU被其他高优先级的进程抢占 ③运行态-阻塞态等待系统资源分配或者等待某事件发生如i\o中断等待输入 ④阻塞态-就绪态资源分配到位或等待的事件发生 **
2.1_3进程的控制 重点
1原语原语是只能一气呵成的特殊的程序任何中断都不能使之暂停实现方式是关/开中断。 相关的原语有进程的切换、创建、终止、阻塞、唤醒
2.1_4进程通信 重点
1共享存储同一时间只能允许一个进程访问 2管道通信只能单向传输且个进程要互斥的访问管道 3消息传递有消息头和消息体
2.1_5线程概念和多线程模型 重点
1什么是线程 2引入线程后的系统开销 3线程的属性 3线程的实现方式用户级线程和内核级线程重点内核级线程才是处理机分配的单元
2.2_1处理机调度的概念层次 2.2_2处理机调度的时机、切换与过程、方式
重点
1进程在操作系统内核临界区中不能进行调度与切换但在普通临界区中能进行调度补充临界区
2.2_3调度算法的评价指标 2.2_4FCFS、SJF、HRRN调度算法 重点
1先来先服务FCFS/First Come First Serve **规则**顾名思义先来先服务 2短作业优先SJF/Shortest Job First ①非抢占式的短作业优先算法 **规则**每次调度时选择当前已到达且运行时间最短的作业/进程 ②抢占式的短作业优先算法 **规则**每当有进程加入就绪队列改变时就需要调度,如果新到达的进程剩余时间比当前运行的进程剩余时间更短,则由新进程抢占处理机,当前运行进程重新回到就绪队列。另外,当一个进程完成时也需要调度 3高响应比优先算法HRRN/Highest Response Ratio Next **规则**非抢占式的调度算法只有当前运行的进 程主动放弃CPU时正常/异常完成或主动阻塞才需要进 行调度调度时计算所有就绪进程的响应比选响应比最高的 进程上处理机。
2.2_5时间片轮转、优先级调度多级反馈队列调度算法 重点
1时间片轮转 **规则**轮流让就绪队列中的进程依次执行一个时间片每次选择的都是排在就绪队列队头的进程 2优先级调度 **补充优先级**静态优先级创建进程时确定之后一直不变。 动态优先级创建进程时会有一个初始值之后会根据情况动态的调整优先级。 **通常**系统进程优先级高于用户进程、前台进程优先级高于后台进程优先级、操作系统更偏好I/O型设备 优先级越大或者越小时优先级越高具体根据题目判断 **①非抢占式的优先级调度算法 规则**每次调度时选择当前已达到且优先级最高的进程。当前进程主动放弃处理机时发生调度 **②抢占式的优先级调度算法 规则**每次调度时选择当前已达到且优先级最高的进程。当前进程主动放弃处理机时发生调度另外当就绪队列发生改变时也需要检查是否会发生抢占。 3多级反馈队列调度算法 规则
2019 王道考研 操作系统2.3_1进程同步、进程互斥 重点
1进程互斥 2进程互斥遵循的四个原则空闲让进、忙则等待、有限等待、让权等待。
2.3_2进程互斥的软件实现方法 重点
1单标志法 缺点 2双标志先检查法 缺点 3双编制后检查法 缺点 4Peterson算法
后客气的等待2.3_3进程互斥的硬件实现方法 重点中断屏蔽过程
**原理**在某进程开始访问临界区到访问结束都不允许被中断也就不能发生过程切换因此也不可能发生两个同事访问临界区的情况但是不适用于多处理机因为在另一个处理机中临界区并没有中断因此可以访问临界区 2TestAndSetLock指令适用于多处理机 3Swap指令
2.3_4信号量机制 重点
1P、V原语 wait、signal原语常简称为P、V原语 C语言描述 2整形信号量 **概念**用一个整型变量作为信号量数值便是某种资源的数量当变量为零时表明所有资源都已被占用。 **实现过程**若S的初始值为1若第一个进程要占用打印机则执行wait原语将S–此时S0之后去占用打印机此时若另一个进程2请求使用打印机则进程2会先执行wait原语检查S是否等于0若等于0则说明打印机正在占用进程2会循环执行whileS 0直到进程1使用结束并调用signal原语将S、 **缺点**会忙等而且有一点bug因为进程2在循环执行wait原语中的whileS 0语句那么是不是一直没法中断没法切换到其他程序呢 3记录型信号量 **概念**与整形信号量不同记录型信号量的wait原语不仅将信号量减一而且还会检查信号量减一后是否小于零若小于零则说明在减一之前临界区已经被占用完然后会将当前请求访问临界区的进程挂到等待队列并将此进程从运行态转为阻塞态。 2.3_5用信号量机制实现进程互斥、同步、前驱关系 重点
**1进程互斥**设置互斥信号mutex例semaphore mutex nsemaphore信号量 **2进程同步**设置同步信号量S初始为0如果需要实现a代码在b代码之前执行则在a代码后加V(S),使得S 1 在b代码前加P(S),这样就会使得当a未执行时S为0b代码被阻塞当a执行完Sb可以运行。 3前驱关系
2.3_6生产者-消费者问题
1问题描述 ①系统中有一组生产者进程和一组消费者进程 ②生产者进程每次生产一个产品放入缓冲区即货架消费者进程每次从缓冲区货架中取出一个产品并使用。(注: 这里的“产品”理解为某种数据) ③生产者、消费者共享一个初始为空、大小为n的缓冲区即初始货架上现有产品为0容量为n。 ④**两个同步关系只有缓冲区没满时生产者才能把产品放入缓冲区否则必须等待。只有缓冲区不空时消费者才能从中取出产品否则必须等待。 ⑤一个互斥关系**缓冲区货架是临界资源各进程互斥使用 2问题解决步骤 3解决问题 4易错问题能否改变相邻P或者V的顺序
将此代码中的相邻的P语句互换的话
producer() { consumer() {while(1) { while (1) {P (empty); P (full) ;P (mutex) ; P (mutex) ;V (mutex) ; V (mutex) ;V (full) ; V (empty) ;} }
} }
得到如下代码
producer() { consumer() {while(1) { while (1) {P (mutex) ; P (mutex) ;P (empty); P (full) ;V (mutex) ; V (mutex) ;V (full) ; V (empty) ;} }
} }
分析换完之后若当缓冲区货架已满且临界缓冲区无人占用此时生产进程执行P(mutex)进入缓冲区执行P(empty)由于缓冲区已满生产者进程阻塞。只有等待消费者进程消费一个产品但是消费者进程执行P(mutex)发现临界缓冲区已经被占用同样进入阻塞状态这样就会发生死锁可知P不可以互换同样可以证明V可以互换
2.3_7多生产者-多消费者问题
本章重要内容 ①其核心思想在于设置了一个计数器count用来记录当前正在访问共享文件的读进程数。我们可以用count的值来判断当前进入的进程是否是第一个/最后一个读进程从而做出不同的处理。 ②另外对count变量的检查和赋值不能一气呵成导致了一些错误如果需要实现“一气呵成”自然应该想到用互斥信号量。 ③最后还要认真体会我们是如何解决“写进程饥饿”问题的。
1问题描述 桌子上有一一只盘子每次只能向其中放入一-个水果。爸爸专向盘子中放苹果妈妈专向盘子中放橘子儿子专等着吃盘子中的橘子女儿专等着吃盘子中的苹果。只有盘子空时爸爸或妈妈才可向盘子中放-一个水果。仅当盘子中有自己需要的水果时儿子或女儿可以从盘子中取出水果。 用PV操作实现上述过程。 2解决问题 思路 dad代码首先要看plate是否为一若为一则将plate减一互斥信号量减一并进行放苹果操作然后互斥信号量加一Apple加一唤醒女儿进程女儿进程首先看Apple数量若Apple为一则先Apple–然后互斥信号量减为0进行取出苹果操作再讲互斥信号量将plate 3拓展问题 当plate初值为一的时候可以通过分析发现不用设置互斥信号量。 但是大于一的时候必须设置以免两个生产者同时访问临界区进而发生数据覆盖的问题。
2.3_7读者-写者问题
1问题描述 有读者和写者两组并发进程共享一个文件当两个或两个以上的读进程同时访问共享数据时不会产生副作用但若某个写进程和其他进程(读进程或写进程)同时访问共享数据时则可能导致数据不一致的错误。因此要求: ①允许多个读者可以同时对文件执行读操作; ②只允许一个写者往文件中写信息; ③任一 写者在完成写操作之前不允许其他读者或写者工作; ④写者执行写操作前应让已有的读者和写者全部退出。 2一步步解决问题 第一步代码
semaphore rw1;//用于实现对文件的互斥访问。表示当前是否有进程在访问共享文件
int count 0;//记录当前有几个读进程在访问文件
writer() {while (1) {P (rw) ;//写之前“加锁写文件.V (rw) ;//写之后“解锁”}
}
reader() {while(1) {if (count0)P(rw); //第一个读进程负责“加锁”count;//访问文件的读进程数1读文件....count- - - ;//访问文件的读进程数-1if (count0)V(rw);//最后一个读进程负责“解锁”}
}**此代码缺陷**可能前一个瞬间一个读者操作执行到了if (count 0)P(rw);后一个瞬间切换到了另一个读者进程同样执行了if (count0)这样就会出现第二个进程执行P(rw);的时候阻塞进而不能实现这两个读进程同时或者共同读文件的操作因此需要作出如下改进
semaphore rw1;//用于实现对文件的互斥访问。表示当前是否有进程在访问共享文件
int count 0;//记录当前有几个读进程在访问文件
semaphore mutex 1//用于将if (count0)P(rw);语句“一气呵成”
writer() {while (1) {P (rw) ;//写之前“加锁写文件.V (rw) ;//写之后“解锁”}
}
reader() {while(1) {P(mutex);/ /改动之处用于将if (count0)P(rw);语句“一气呵成”if (count0)P(rw); //第一个读进程负责“加锁”V(mutex);count;//访问文件的读进程数1读文件....count- - - ;//访问文件的读进程数-1if (count0)V(rw);//最后一个读进程负责“解锁”}
}**此代码缺陷**改动之后仍有缺陷那就是很有可能读者源源不断使得写者饿死所以需要进一步改进
semaphore rw1;//用于实现对文件的互斥访问。表示当前是否有进程在访问共享文件
int count 0;//记录当前有几个读进程在访问文件
semaphore mutex 1//用于将if (count0)P(rw);语句“一气呵成”
semaphore w 1;//用于解决写者饿死现象
writer() {while (1) {P(w);/ /P (rw) ;//写之前“加锁写文件.V (rw) ;//写之后“解锁”V(w);/ /}
}
reader() {while(1) {P(w);/ /P(mutex);if (count0)P(rw); //第一个读进程负责“加锁”V(mutex);V(w);/ /count;//访问文件的读进程数1读文件....count- - - ;//访问文件的读进程数-1if (count0)V(rw);//最后一个读进程负责“解锁”}
}**分析**这样就解决了写者饿死问题我们来分析一下当有读者读文件的时候写者执行P(w); 然后执行P(rw);发生堵塞一直等待读者进程执行V(rw);若此时有其他读者进程将要执行则执行P(w);会发生堵塞 不过我认为这个w信号量用mutex替代就行所以进行了如下改进:
semaphore rw1;//用于实现对文件的互斥访问。表示当前是否有进程在访问共享文件
int count 0;//记录当前有几个读进程在访问文件
semaphore mutex 1//用于将if (count0)P(rw);语句“一气呵成”以及解决写者饿死现象
writer() {while (1) {P(mutex );/ /P (rw) ;//写之前“加锁写文件.V (rw) ;//写之后“解锁”V(mutex );/ /}
}
reader() {while(1) {P(mutex);if (count0)P(rw); //第一个读进程负责“加锁”V(mutex);count;//访问文件的读进程数1读文件....count- - - ;//访问文件的读进程数-1if (count0)V(rw);//最后一个读进程负责“解锁”}
}2.3_9哲学家进餐问题
1问题描述 一张圆桌上坐着5名哲学家每两个哲学家之间的桌.上摆一根筷子 桌子的中间是一碗米饭。哲学家们倾注毕生的精力用于思考和进餐哲学家在思考时并不影响他人。只有当哲学家饥饿时才试图拿起左、右两根筷子(一根一根地拿起)。如果筷子已在他人手上则需等待。饥饿的哲学家只有同时拿起两根筷子才可以开始进餐当进餐完毕后放下筷子继续思考。 2三种解决方案 ①可以对哲学家进程施加一些限制条件比如最多允许四个哲学家同时进餐。这样可以保证至少有一个哲学家是可以拿到左右两只筷子的 ②要求奇数号哲学家先拿左边的筷子然后再拿右边的筷子而偶数号哲学家刚好相反。用这种方法可以保证如果相邻的两个奇偶号哲学家都想吃饭那么只会有其中一个可以拿起第一只筷 子另一个会直接阻塞。 这就避免了占有一支后再等待另一只的情况。 ③将拿左边筷子和拿右边筷子使用互斥信号量一气呵成
semaphore chopstick[5]{1,1,1,1,1} ;
semaphore mutex 1; / /互斥地取筷子
Pi(){//i号哲学家的进程while(1) {P (mutex) ;P (chopstick[i]) ;//拿左P (chopstick[ (i1)85]) ;//拿右V (mutex) ;吃饭...V (chopstick[i]) ;//放左V (chopstick[ (i1)号5]) ;//放右思考..}
}
2.3_10管程 2.4_1死锁的概念
本节大纲什么是死锁、死锁产生的必要条件、死锁的处理策略 1什么是死锁 在并发环境下各进程因竞争资源而造成的一种 互相等 待对方手里的资源导致各进程都阻塞都无法向前推进的现象就是死锁。发生死锁后若无外力干涉、这些进程都将无法向前推进一步。 2死锁产生的必要条件 产生死锁必须同时满足一下四个条件只要其中任一条件不成立死锁就不会发生。 ①互斥条件:只有对必须互斥使用的资源临界资源) 的争抢才会导致死锁(如哲学家的筷子、打印机设备)像内存、扬声器这样可以同时让多个进程使用的资源是不会导致死锁的(因为进程不用阻塞等待这种资源) ②不剥夺条件:进程所获得的资源在未使用完之前不能由其他进程强行夺走只能主动释放。不可抢占其他进程的资源 ③请求和保持条件:进程已经保持了至少一个资源但又提出了新的资源请求而该资源又被其他进程占有此时请求进程被阻塞但又对自己已有的资源保持不放。 ④循环等待条件:存在一种进程资源的循环等待链你等我、我等他、他等你链中的每一个进程已获得的资源同时被下一个进程所请求。 3死锁的处理政策 ①预防死锁静态策略。破坏死锁产生的四个必要条件中的一个或几个。 ②避免死锁动态策略。用某种方法防止系统进入不安全状态从而避免死锁(银行家算法) ③死锁的检测和解除。允许死锁的发生不过操作系统会负责检测出死锁的发生然后采取某种措 施解除死锁。
2.4_2死锁的处理策略-预防死锁
本节大纲预防死锁的四个方式破坏互斥条件、破坏不剥夺条件、破坏请求和保持条件、破坏循环等待条件此法为静态策略即只需改变某些起始条件后续无需改动 ①破坏互斥条件 **破坏互斥条件**如果把只能互斥使用的资源改造为允许共享使用则系统不会进入死锁状态。比如: SPOOLing技术。操作系统可以采用SPOOLing技术把独占设备在逻辑上改造成共享设备。比如用SPOOLing技 术将打印机改造为共享设备 缺点: 并不是所有的资源都可以改造成可共享使用的资源。并且为了系统安全很多地方还必须保护这种互斥性。因此很多时候都无法破坏互斥条件。
②破坏不剥夺条件 破坏不剥夺条件: 方案一自行释放所有资源:当某个进程请求新的资源得不到满足时它必须立即释放保持的所有资源待以后需要时再重新申请。也就是说即使某些资源尚未使用完也需要主动释放从而破坏了不可剥夺条件。 方案二抢占其他进程资源:当某个进程需要的资源被其他进程所占有的时候可以由操作系统协助将想要的资源强行剥夺。这种方式一般需要考虑各进程的优先级(比如:剥夺调度方式就是将处理机资源强行剥夺给优先级更高的进程使用) 缺点: 1.实现起来比较复杂。 2.释放已获得的资源可能造成前一阶段工作的失效。因此这种方法一般只适用于易保存和恢复状态的资源如CPU。 ③破坏请求和保持条件 破坏请求和保持条件 可以采用静态分配方法即原子分配即进程在运行前一次申请完它所需要的全部资源在它的资源未满足前不让它投入运行。一旦投入运行后这些资源就一直归它所有该进程就不会再请求别的任何资源了。 缺点: 有些资源可能只需要用很短的时间因此如果进程的整个运行期间都一直保持着所有资源就会造成严重的资源浪费资源利用率极低。另外该策略也有可能导致某些进程饥饿。
④破坏循环等待条件 可采用顺序资源分配法。首先给系统中的资源编号规定每个进程必须按编号递增的顺序请求资源同类资源(即编号相同的资源)一次申请完。 原理分析:一个进程只有已占有小编号的资源时才有资格申请更大编号的资源。按此规则已持有大编号资源的进程不可能逆向地回来申请小编号的资源从而就不会产生循环等待的现象。 缺点: 1.不方便增加新的设备因为可能需要重新分配所有的编号; 2.进程实际使用资源的顺序可能和编号递增顺序不一-致 会导致资源 浪费;
2.4_3死锁的处理策略-避免死锁
本节大纲什么是安全序列和安全状态、银行家算法此法为动态策略即一步一检测 1安全序列和安全状态 安全序列就是指如果系统按照这种序列分配资源则每个进程都能顺利完成。只要能找出一个安全序列系统就是安全状态。当然安全序列可能有多个。 2银行家算法 **“银行家算法”的核心思想**在资源分配之前预先判断这次分配是否会导致系统进入不安全状态以此决定是否答应资源分配请求。 银行家算法步骤: ①检查此次申请是否超过了之前声明的最大需求数 ②检查此时系统剩余的可用资源是否还能满足这次请求 ③试探着分配更改各数据结构 ④用安全性算法检查此次分配是否会导致系统进入不安全状态 安全性算法步骤: 检查当前的剩余可用资源是否能满足某个进程的最大需求如果可以就把该进程加入安全序列并把该进程持有的资源全部回收。 不断重复上述过程看最终是否能让所有进程都加入安全序列。
2.4_4死锁的处理策略-检测和解除
本节大纲资源分配数据结构、如何根据数据结构进行检测和解除 1数据结构 2死锁的检测 检测死锁的算法: 1)在资源分配图中找出既不阻塞又不是孤点的进程Pi (即找出一条有向边与它相连且该有向边对应资源的申请数量小于等于系统中已有空闲资源数量。如下图中R1没有空闲资源R2有一个空闲资源。若所有的连接该进程的边均满足上述条件则这个进程能继续运行直至完成然后释放它所占有的所有资源)。消去它所有的请求边和分配边使之称为孤立的结点。在下图中P1是满足这一条件的进程结点于是将P1的所有边消去。 2)进程Pi所释放的资源可以唤醒某些因等待这些资源而阻塞的进程原来的阻塞进程可能变为非阻塞进程。在下图中P2 就满足这样的条件。根据1)中的方法进行一系列简化后若能消去途中所有的边则称该图是可完全简化的。.
可完全简化 不可完全简化 3死锁的解除 ① 资源剥夺法。挂起(暂时放到外存上)某些死锁进程并抢占它的资源将这些资源分配给 其他的死锁进程。但是应防止被挂起的进程长时间得不到资源而饥饿。 ②撤销进程法(或称终止进程法)。强制撤销部分、甚至全部死锁进程并剥夺这些进程的资 源。这种方式的优点是实现简单但所付出的代价可能会很大。因为有些进程可能已经运行 了很长时间已经接近结束了一旦被终止可谓功亏一篑 以后还得从头再来。 ③进程回退法。 让一个或多个死锁进程回退到足以避免死锁的地步。这就要求系统要记录进程 的历史信息设置还原点。
