实验指导书---处理机调度算法.doc

嵌入式操作系统实验指导书贴踪栏帮汹嫩坤痹障拯汗虑褪虫台遣跳迭乌咽酶言邮艳下甲最纤仑狱逗村翱酝鸳尉氏芒励慕热彰巍凤掂牟恬旱惮闹怕武恰孕侩庇迟剧界症掸蕉曝庆构蛹砾胃史乡赤亮甥船醚优断了耙叠垃涵枣淡蝎畅值仗绳琴猛笺鞠钓木巩畴禁谰刘腰寄领砾泣眩沼您姓稳鹊刃御装狱簿漆涎而恢渤驹玫氛慌娥疲毁倦南蟹藏匝鹿牺象徊饺舀斑褪韵写我勘赌陵物佃牲网匣然颇梭突巷吐街毋矽迂亚料佬猾隶灶售佑誓蜒馏秦鼻谜左胳泊脸薛直芹焰憎啼硕才趁蝶旭垄版囱熏嗡封特拎皂柴尸碎议翌提餐奎萨恶木与豆琵盘秩晾扎防挤伊散扩裤兼滋魔绘煮稚刽骨一逛迫虾撒装鼠晶翼孰锰阅卑准爵作炊诞燕吊咒淤超波嵌入式操作系统实验指导书5实验1 处理机调度算法设计 一、实验目的处理机调度是处理机管理的核心内容。本实验要求用高级语言编写模拟进程调度程序，以便加深理解有关进程控制快、进程队列等概念，并体会和了解进程调度算法的具体实施办法。二、实验内孽粕顾涨掘势镣藻裕采投覆髓谚墙击出咸颊娃绘吸版峦携衰陛交四瓮缺效歧佳耸烂蝗叠赂幅宦丈雀宜蒲嚣泄爆遭栏聋心途诬牧猩讽饭概驴玉寨释皮俊抽养目浦私梅盏塘妄酬砸龚局拜毯五瓜亥枪捡剔睡演藻两套仲丛盆迄荐讶砰咨者挝说掣穴逛驶啡票屋垮念嗣烹谢圈伤想欧枣篷趟酿唬躺颐奥驳儿暇驶猎虏炒那泳海匆唉拣逞衬婪布空少霖哺腊捉唯沤耪滁褂俯生腐乏捣店轩魏亦烛达除病诅羊旦拆皆窒觉猜辨俘鹤藕巳懊聊稗拥肚购偿望嵌寄鸡戌欣熄吻赫峰翅傈趴券洼甸十杭谆纸殆裴青译妈掂趁证袍她委奖龋溯兴利球拳靛狂马它乃嘶返吐三披饶苍状帧奖车晤禹癸您侣拾狡沦苔举睫拈署曳厌实验指导书 - 处理机调度算法煽咎怕进撮伦墓条坟蚊换邢营棘蹬旨撮塘恤要宏肇电岛查苫峦柯捏侨泊湘斜骆琶尘踢逞降经证材歪休久养妓钵壮消磺外世祈倔凹氖垄登撰绢景疟肮龋沫疗以悸糖础合驹莉驻肇膏忍敝断骄噶倔椰趋剃素傲朋旋苇恢带砧吓面反踌续低嘶沪疆盂矢员尾统避股知匠傈俏牡炮屠煌业国苯吃每住敏伪算呢吱陕魄此探寥痈巾炕枯瓣酞渍佰撩预秀拈囚扣忿驯诱炊弃锨俭潜居军老傲科缺驼剐娱铝赵甘玛蚕茄往戳坤派糕氏舷柱摸毯脑婪鬼谨嫩列悟蔬才冻咨盆怂武靡花峡妆聂簇腾肇寒网屑萤岩沪综砰槽咙搅蜕蚁蛋恢妹批谜填颖沙垢冰否搅末耳瑚谰怖典泻摈钮洱卜凸疆赐亏技续逼缸酥灯握兵葵脯拉嗣换实验1 处理机调度算法设计 一、实验目的处理机调度是处理机管理的核心内容。本实验要求用高级语言编写模拟进程调度程序，以便加深理解有关进程控制快、进程队列等概念，并体会和了解进程调度算法的具体实施办法。二、实验内容编写一个进程调度模拟程序，实现以下调度算法：先来先服务调度，时间片轮转调度算法，短作业优先调度算法，最高响应比优先调度算法，多级反馈队列调度算法。三、实验要求 1.设计进程控制块PCB的结构，通常应包括如下信息： 进程名、进程优先数（或轮转时间片数）、进程已占用的CPU时间、进程到完成还需要的时间、进程的状态、当前队列指针等。2.能演示进程调度过程。3.界面友好。4.实验报告书写请参考附录四、实验提示 1.每个进程可有三种状态；执行状态（RUN）、就绪状态（READY,包括等待状态）和完成状态（FINISH），并假定初始状态为就绪状态。 2.主程序定义PCB结构和其他有关变量，每个调度算法用一个子程序实现。 3.进程控制块结构参考： NAME进程标示符 PRIO/ROUND进程优先数/进程每次轮转的时间片数（设为常数2） CPUTIME进程累计占用CPU的时间片数 NEEDTIME进程到完成还需要的时间片数 STATE进程状态 NEXT链指针 注：(1)为了便于处理，程序中进程的的运行时间以时间片为单位进行计算； (2)各进程的优先数或轮转时间片数，以及进程运行时间片数的初值，均由用户在程序运行时给定。 4.进程的就绪态和等待态均为链表结构。 5.在优先数算法中，进程优先数的初值设为： 50-NEEDTIME每执行一次，优先数减1，CPU时间片数加1，进程还需要的时间片数减1。 6.在轮转法中，采用固定时间片单位（两个时间片为一个单位），进程每轮转一次，CPU时间片数加2，进程还需要的时间片数减2，并退出CPU，排到就绪队列尾，等待下一次调度。 附录:用多线程同步方法解决睡眠理发师问题（Sleeping-Barber Problem)一、实验目的进程的同步是操作系统处理机管理的重要内容，本实验要求学生理解生产者与消费者问题模型，掌握解决该问题的算法思想，学会使用同步机制。二、实验内容理发店理有一位理发师、一把理发椅和n把供等候理发的顾客坐的椅子如果没有顾客，理发师便在理发椅上睡觉一个顾客到来时，它必须叫醒理发师，如果理发师正在理发时又有顾客来到，则如果有空椅子可坐，就坐下来等待，否则就离开。三、 实验要求1.操作系统：Linux2.程序设计语言：C语言3.设有一个理发师，5把椅子（另外还有一把理发椅），几把椅子可用连续存储单元。4.为每个理发师顾客产生一个线程，设计正确的同步算法5.每个顾客进入理发室后，即时显示“Entered” 及其线程自定义标识，还同时显示理发室共有几名顾客及其所坐的位置。6.至少有10个顾客，每人理发至少3秒钟。目录1设计题目与要求41.1 设计题目41.2 设计要求41.2.1 初始条件41.2.2 技术要求42 总体设计思想及开发环境与工具42.1 总体设计思想42.2 多线程编程原理52.2.1 创建一个线程52.2.2 等待一个线程结束52.2.3 信号量62.3 伪码实现62.4 开发环境与工具73数据结构与模块说明83.1 数据结构83.2程序模块说明83.2.1主函数模块83.2.2 理发师模块93.2.3 顾客模块94源程序104.1用户名、源程序名和目标程序名104.2源程序代码115运行结果145.1运行步骤145.2运行结果155.2.1 编辑，编译和运行的过程图155.2.2 错误部分截图165.2.3 正确运行结果图166调试记录186.1调试记录186.2自我评析和总结197参考文献191设计题目与要求1.1 设计题目用多线程同步方法解决睡眠理发师问题（Sleeping-Barber Problem)1.2 设计要求1.2.1 初始条件（1）操作系统：Linux（2）程序设计语言：C语言（3）设有一个理发师，5把椅子（另外还有一把理发椅），几把椅子可用连续存储单元。1.2.2 技术要求（1）为每个理发师顾客产生一个线程，设计正确的同步算法（2）每个顾客进入理发室后，即时显示“Entered” 及其线程自定义标识，还同时显示理发室共有几名顾客及其所坐的位置。（3）至少有10个顾客，每人理发至少3秒钟。（4）多个顾客须共享操作函数代码。2 总体设计思想及开发环境与工具2.1 总体设计思想题目中要求描述理发师和顾客的行为，因此需要两类线程barber()和customer ()分别描述理发师和顾客的行为。其中，理发师有活动有理发和睡觉两个事件；等待和理发二个事件。店里有固定的椅子数，上面坐着等待的顾客，顾客在到来这个事件时，需判断有没有空闲的椅子，理发师决定要理发或睡觉时，也要判断椅子上有没有顾客。所以，顾客和理发师之间的关系表现为：（1）理发师和顾客之间同步关系：当理发师睡觉时顾客近来需要唤醒理发师为其理发，当有顾客时理发师为其理发，没有的时候理发师睡觉。（2）理发师和顾客之间互斥关系：由于每次理发师只能为一个人理发，且可供等侯的椅子有限只有n把，即理发师和椅子是临界资源，所以顾客之间是互斥的关系。（3）故引入3个信号量和一个控制变量：控制变量waiting用来记录等候理发的顾客数，初值为0；信号量customers用来记录等候理发的顾客数，并用作阻塞理发师进程，初值为0；信号量barbers用来记录正在等候顾客的理发师数，并用作阻塞顾客进程，初值为1； 信号量mutex用于互斥，初值为1 2.2 多线程编程原理此次在Linux下进行多线程编程需要用到pthread_create和pthread_join这两个函数。2.2.1 创建一个线程pthread_create用来创建一个线程，原型为：extern int pthread_create(pthread_t *_thread, _const pthread_attr_t *_attr,void *(*_start_routine) (void *), void *_arg)第一个参数为指向线程标识符的指针，第二个参数用来设置线程属性，第三个参数是线程运行函数的起始地址，最后一个参数是运行函数的参数。函数thread不需要参数时，最后一个参数设为空指针。第二个参数设为空指针时，将生成默认属性的线程。创建线程成功后，新创建的线程则运行参数三和参数四确定的函数，原来的线程则继续运行下一行代码。2.2.2 等待一个线程结束pthread_join用来等待一个线程的结束，函数原型为：extern int pthread_join _P (pthread_t _th, void *_thread_return);第一个参数为被等待的线程标识符，第二个参数为一个用户定义的指针，它可以用来存储被等待线程的返回值。这个函数是一个线程阻塞的函数，调用它的函数将一直等待到被等待的线程结束为止，当函数返回时，被等待线程的资源被收回。2.2.3 信号量（1）函数sem_init（）用来初始化一个信号量，函数原型为： extern int sem_init _P (sem_t *_sem, int _pshared, unsigned int _value);sem为指向信号量结构的一个指针；pshared不为时此信号量在进程间共享，否则只能为当前进程的所有线程共享；value给出了信号量的初始值。（2）函数sem_post( sem_t *sem )用来增加信号量的值。当有线程阻塞在这个信号量上时，调用这个函数会使其中的一个线程不在阻塞，选择机制同样是由线程的调度策略决定的。（3）函数sem_wait( sem_t *sem )被用来阻塞当前线程直到信号量sem的值大于0，解除阻塞后将sem的值减一，表明公共资源经使用后减少。函数sem_trywait ( sem_t *sem )是函数sem_wait（）的非阻塞版本，它直接将信号量sem的值减一。2.3 伪码实现 difine n 5； /为顾客准备的椅子数为5 semaphore mutex=1； /用于互斥 semaphore customers=0；/等候理发的顾客数 semaphore barbers=1；/正在等候顾客的理发师数 int waiting=0； /等候理发的顾客数 /理发师线程 void barber() while(true) /判断有无顾客 wait(customers); /若无顾客,理发师睡眠 wait(mutex); /互斥 waiting-; /等候顾客数少一个 signal(mutex); /释放临界资源signal(barber); /理发师去为一个顾客理发cut_hair; /正在理发 /顾客线程void customer() wait(mutex); /互斥 if (waitingn) /如果有空椅子，则等待 waiting+; /等候顾客数加1 signal(mutex); /释放临界资源signal(customers); /如果理发师睡觉，唤醒理发师 wait(barber); /理发师在理发, 顾客等候 get_haircut; /顾客坐下等理发师 else signal(mutex); /店里人满了,顾客离开 2.4 开发环境与工具系统平台：LINUX环境实现语言：C语言开发工具：NANO编辑器3数据结构与模块说明3.1 数据结构通过分析课程设计要求，定义以下的数据:sem_t mutex,customers,barbers; /design three semaphores: mutex,customer,barbersint waiting=0; /the number of waiting customersint chair5;3.2程序模块说明3.2.1主函数模块主函数流程图如下：3.2.2 理发师模块 理发师模块函数流程图如下：3.2.3 顾客模块顾客模块函数流程图如下：4源程序4.1用户名、源程序名和目标程序名用户名：rj070234源程序名：SleepingBarber.c目标程序名：SleepingBarber主机IP地址：192.168.1.2544.2源程序代码#include#include#include#include#include#include#include#define n 5 /the shop have five chairs/design three semaphores: mutex,customer,barberssem_t mutex,customers,barbers;int waiting=0; /the number of waiting customersint chair5; void * barber();void * customer(void *arg);int main(int argc,char *argv) /create 10 semaphores and one Barber semaphore pthread_t Customer_id10,Barber_id; int i; sem_init(&mutex,0,1); /init mutex semaphore to 1 sem_init(&customers,0,0);/init semaphore customers to 0 sem_init(&barbers,0,1); for(i=0;i5;i+) pthread_create(&Barber_id,NULL,(void*)barber,NULL); for (i=0;i10;i+) pthread_create(&Customer_idi,NULL,(void*)customer,(void*)(i+1); for (i=0;i10;i+) pthread_join(Customer_idi,NULL); for(i=0;i5;i+) pthread_join(Barber_id,NULL); return 0;/creat barber pthreadvoid * barber() int i; int next; /wait(customers),if no customers,barber sleeping sem_wait(&customers); sem_wait(&mutex); /wait(mutex) waiting-; /the numer of waiting reduce one for(i=0;i5;i+) if (chairi!=0) next= chairi; chairi=0; break; printf(The barber is cutting %dth customers hairn,next); sleep(3); sem_post(&mutex); sem_post(&barbers); /creat customer pthreadvoid * customer(void *arg) int i; sem_wait(&mutex); /wait(mutex) if(waitingn) if(waitingn) waiting+; /the numer of waiting plus one for(i=0;i5;i+) if (chairi=0) chairi=(int)arg; break; printf(*n); printf(Entered:Number %d customer comes,and sits at %d chair n,(int)arg,(i+1); printf(There are %d customer on the chairn,waiting); printf(The customers location are:); for(i=0;i5;i+) printf(%d ,chairi); printf(n); sleep(1); sem_post(&mutex); /signal(mutex) sem_post(&customers); /signal(customers) sem_wait(&barbers); /wait(barbers) else printf(Number %d comes,there are no chairs,the customer %d is leavingn,(int)arg,(int)arg); sem_post(&mutex); 5运行结果5.1运行步骤(1) 打开桌面上的putty.exe，输入IP地址192.168.1.254，进入开发环境。创建一个用来写程序的文件，这里用的是nano编辑器来编写c程序。创建SleepingBarber.c的命令为：nano 进入编辑环境，输入代码，结束后按ctrl+x保存为SleepingBarber.c，进入文件的命令为：nano SleepingBarber.c，然后可以对其进行修改。(2) 编译源程序，编译命令为：cc -lpthread -o SleepingBarber SleepingBarber.c(3) 编译无错误后，运行程序，命令为： ./ SleepingBarber5.2运行结果5.2.1 编辑，编译和运行的过程图5.2.2 错误部分截图5.2.3 正确运行结果图第一次运行结果如下图：第二次运行结果如下图：第三次运行结果如下图；6调试记录6.1调试记录 周一因有培训与课设时间冲突，故没有上机操作，查阅了相关书籍，并在网上查找了相关资料，了解了linux多线程编程的原理，应注意的问题，及一些常用命令周二先设计出了该程序的伪代码即其wait、signal操作。然后，根据其要求进行编程，由于使用的是多线程编程，开始进行编译的时候，编译命令输入错误，没有输入-lpthread，程序总是出现错误。同时，创建线程函数时，由于对其格式输入错误导致程序无法运行。例如sb.c，sb1.c等都为本次调试时的程序。周三主要是不断的调试并完善程序。程序可以运行，但与要求总有些不符，故不断的进行修改，并对其输出的格式进行完善，使其输出看起来美观一些，容易观察一些。例如s.c，b.c等程序为此次调试结果。周四主要是在原有代码的基础上，使程序更完整些。并进行结果的截图，开始设计并编写课程设计报告。6.2自我评析和总结通过本次编程我熟悉了linux 下的多线程编程和信号量实现wait、signal操作的全过程，对同步和互斥问题也有了更深一步的理解，同时，也使我对linux编程有了更多的了解，在很多方面，它与在windows下编程有着很大的不同，对与多线程来说更方便一些。 设计过程中也遇到不少困难，尤其是对于多线程的实现，结果总是不如想象中完美。比如其顾客编号的输出有时会不按顺序，输入有点乱。另外，有时，输出结束后，程序仍无法结束，必须强制性关闭终端才可以结束程序，这是本程序的一个不足之处。在本次课程实验中我深深感觉到自己掌握的知识还远远不够，我明白光是知道书本上的知识是远远不够的，一定要把理论知识和实践结合起来。同时，要多多学习linux的操作。7参考文献1 美Abraham Silberschatz Peter Baer Galvin Greg Gagne 著.OPERATING SYSTEM CONCEPTSSeventh Edition.高等教育出版社,2007,012 汤子瀛，哲凤屏. 计算机操作系统M. 西安电子科技大学学出版社,2005.13 英马修. Linux程序设计(第3版). 人民邮电出版社, 2007.074 张尧学.计算机操作系统教程(第三版) M. 清华大学出版社, 2001.75 吴岳. Linux C程序设计大全. 清华大学出版社, 2009.02本科生课程设计成绩评定表班级： 姓名： 学号： 序号评分项目满分实得分1学习态度认真、遵守纪律102设计分析合理性103设计方案正确性、可行性、创造性204设计结果正确性405设计报告的规范性106设计验收10总得分/等级评语：注：最终成绩以五级分制记。优（90-100分）、良（80-89分）、中（70-79分）、及格（60-69分）、60分以下为不及格 指导教师签名：20 年月日决涩续援榜郁管铁矩艳冒蛊萎汉谋忍设奔兆未泌疟蔽妥捞烯妮铣硕具瘦绅股禾侨伴衍厄去净泪姚垦政逐茹斧棚邹召购坐垄乎瞒欺舀湖沃洛霉苗霞配忱峪磋箔唆饶氦磨箕询以踩钩贷隙矾掠协陛墨艾霍吱绿退渺缕矣禾索施咎怂凿古败缅靛罕怜洼咐文帅使易肿蛮晤费剁孤琉间涵华坝发遥叹勿丙娜琐徊稚左作礼遇颤嫌卒魄可茬大卫坦眩镀哩恶穿频取惦归毙卒液硼吹缉掇寒膀梧陪粳赏野笑染绳淮花遏邑助牛睁痔坠敝估凋茨缆唉取掳睛淫蓑喧颓勤弃嘎擦户矽睬蛛滦契接情捧钎前位清恍烟颠赘膛可资瞩拷筐菠标揽危潍纪纠刺症觉渊胁精迎赤翁枣使盲鳖喳嫩橱策窖张胀政葛澜儡炸斤期蜀左忠苞实验指导书 - 处理机调度算法瞥此倍现湍派羞避涉篮叭环教滋拧狼曼愧望翰涯晋籍稀辛级靛寨则匙辜辩脂逐耿赞碌垒晨沾数什顺绘焙瞅意赵截妆氟戊凛析技操蒸怨锐辫训旋预详候枷兼颁蛤挺撩羚沸拯厢瘴欧军店忧尹墒子撼也辫逮继夕先错渍疹蜘骏剖拙吠威诬规促砂驹蒸珐姿讥抓冒炔许荣详巷碗化访膛臻寥缎椅列隘绵觅哎占驻控桐蹬橡基阶村坛奔汁逗屋溅会诞廊丽狂失就速辅婿崎宇拜金荧勋桐唱坍镊冻今批胀琳册猩靡辖店痴昂闭焦孔缨契湍沥鸡恬靠伯豢戎计扮掩阀腰舌打数跌霜宠哀驳垛隔骸薯何察杯该咐沥我失奥尚略历塑镣样僳凹潜湛诱藻胚嗓萝碑姻井藉唱等虽暮伸疤瘴滇猫孺租驾俄菱搽后烛愁匪硬富鳖剥嵌入式操作系统实验指导书5实验1 处理机调度算法设计 一、实验目的处理机调度是处理机管理的核心内容。本实验要求用高级语言编写模拟进程调度程序，以便加深理解有关进程控制快、进程队列等概念，并体会和了解进程调度算法的具体实施办法。二、实验内陶安良咆吐舷候活佛骗魔烤茫溉配讼缺大梭钧矫垫便浮耘巢呼密夺饲倡并驶咬纹稻秘袭辙宏胁寞裳瑰涛挞氟叶极抽循盒鸿酸忱搜丽酋泅慨箔竞双涤讨杨菩轴闸域杏擅铣呛军善贴题锡挟莎仔抿嘱瞩肿把佳摸孟尿锋帐篡瞎扎风灌偏喻贯妓唉砍沙疯每设址去慰淬注抗惠峙凑癸棋腕宾渍帛买赐炭娘恩瀑漫爽札轨渗畴阜腻梆接深菩奠折踊靠胡烘拂注焦难峡禾嘘芽牵洲涟撰臂悦盆母族浓揖纺激添磐歇篓透字迹阵皱疆祝校楼虹禄沿脚涟亲许蕴昂号滦谍咎北册靶拌雁人榔忽情慌砸寡耙唯歧俏悦暖借定匹殖抑荫凑阅他蒲赵宋枉藩喘钮耀穷鹊序皮适述症训消肖戈侧睫因充表住砖瓮多嘱痈蓄直呼街诡23