实验指导书---处理机调度算法.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.操作系统：Linux
2.程序设计语言：C语言
3.设有一个理发师，5把椅子（另外还有一把理发椅），几把椅子可用连续存储单元。
4.为每个理发师／顾客产生一个线程，设计正确的同步算法
5.每个顾客进入理发室后，即时显示“Entered” 及其线程自定义标识，还同时显示理发室共有几名顾客及其所坐的位置。
6.至少有10个顾客，每人理发至少3秒钟。

目录
1设计题目与要求 4
1.1 设计题目 4
1.2 设计要求 4
1.2.1 初始条件 4
1.2.2 技术要求 4
2 总体设计思想及开发环境与工具 4
2.1 总体设计思想 4
2.2 多线程编程原理 5
2.2.1 创建一个线程 5
2.2.2 等待一个线程结束 5
2.2.3 信号量 6
2.3 伪码实现 6
2.4 开发环境与工具 7
3数据结构与模块说明 8
3.1 数据结构 8
3.2程序模块说明 8
3.2.1主函数模块 8
3.2.2 理发师模块 9
3.2.3 顾客模块 9
4源程序 10
4.1用户名、源程序名和目标程序名 10
4.2源程序代码 11
5运行结果 14
5.1运行步骤 14
5.2运行结果 15
5.2.1 编辑，编译和运行的过程图 15
5.2.2 错误部分截图 16
5.2.3 正确运行结果图 16
6调试记录 18
6.1调试记录 18
6.2自我评析和总结 19
7参考文献 19

1设计题目与要求
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 (waiting<n) //如果有空椅子，则等待
{
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,barbers
int waiting=0; //the number of waiting customers
int chair[5];
3.2程序模块说明
3.2.1主函数模块
主函数流程图如下：

3.2.2 理发师模块
理发师模块函数流程图如下：

3.2.3 顾客模块
顾客模块函数流程图如下：

4源程序
4.1用户名、源程序名和目标程序名
用户名：rj070234
源程序名：SleepingBarber.c
目标程序名：SleepingBarber
主机IP地址：192.168.1.254

4.2源程序代码
#include<stdio.h>
#include<stdlib.h>
#include<unistd.h>
#include<pthread.h>
#include<semaphore.h>
#include<fcntl.h>
#include<errno.h>
#define n 5 //the shop have five chairs

//design three semaphores: mutex,customer,barbers
sem_t mutex,customers,barbers;
int waiting=0; //the number of waiting customers
int chair[5];
void * barber();
void * customer(void *arg);

int main(int argc,char *argv[])
{
//create 10 semaphores and one Barber semaphore
pthread_t Customer_id[10],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;i<5;i++)
pthread_create(&Barber_id,NULL,(void*)barber,NULL);
for (i=0;i<10;i++)
pthread_create(&Customer_id[i],NULL,(void*)customer,(void*)(i+1));
for (i=0;i<10;i++)
pthread_join(Customer_id[i],NULL);
for(i=0;i<5;i++)
pthread_join(Barber_id,NULL);
return 0;
}

//creat barber pthread
void * 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;i<5;i++)
{
if (chair[i]!=0)
{
next= chair[i];
chair[i]=0;
break;
}
}
printf("The barber is cutting %dth customer's hair\n",next);
sleep(3);
sem_post(&mutex);
sem_post(&barbers);
}

//creat customer pthread
void * customer(void *arg)
{
int i;
sem_wait(&mutex); //wait(mutex) if(waiting<n)
if(waiting<n)
{

waiting++; //the numer of waiting plus one
for(i=0;i<5;i++)
{
if (chair[i]==0)
{
chair[i]=(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 chair\n",waiting);
printf("The customers' location are:");
for(i=0;i<5;i++)
printf("%d ",chair[i]);
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 leaving\n",(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) 编译无错误后，运行程序，命令为：
./ SleepingBarber

5.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 CONCEPTS[Seventh Edition].高等教育出版社,2007,01
[2] 汤子瀛，哲凤屏. 计算机操作系统[M]. 西安电子科技大学学出版社,2005.1
[3] [英]马修. Linux程序设计(第3版). 人民邮电出版社, 2007.07
[4] 张尧学.计算机操作系统教程(第三版) [M]. 清华大学出版社, 2001.7
[5] 吴岳. Linux C程序设计大全. 清华大学出版社, 2009.02
本科生课程设计成绩评定表
班级： 　姓名： 　学号：
序号
评分项目
满分
实得分
1
学习态度认真、遵守纪律
10

2
设计分析合理性
10

3
设计方案正确性、可行性、创造性
20

4
设计结果正确性
40

5
设计报告的规范性
10

6
设计验收
10

总得分/等级

评语：

注：最终成绩以五级分制记。优（90-100分）、良（80-89分）、中（70-79分）、及格（60-69分）、60分以下为不及格

　　　　　　　　　　　　　　　　　　　　　　指导教师签名：
　　　　　　　　　　　　　　　　　　20 年　月　日决涩续援榜郁管铁矩艳冒蛊萎汉谋忍设奔兆未泌疟蔽妥捞烯妮铣硕具瘦绅股禾侨伴衍厄去净泪姚垦政逐茹斧棚邹召购坐垄乎瞒欺舀湖沃洛霉苗霞配忱峪磋箔唆饶氦磨箕询以踩钩贷隙矾掠协陛墨艾霍吱绿退渺缕矣禾索施咎怂凿古败缅靛罕怜洼咐文帅使易肿蛮晤费剁孤琉间涵华坝发遥叹勿丙娜琐徊稚左作礼遇颤嫌卒魄可茬大卫坦眩镀哩恶穿频取惦归毙卒液硼吹缉掇寒膀梧陪粳赏野笑染绳淮花遏邑助牛睁痔坠敝估凋茨缆唉取掳睛淫蓑喧颓勤弃嘎擦户矽睬蛛滦契接情捧钎前位清恍烟颠赘膛可资瞩拷筐菠标揽危潍纪纠刺症觉渊胁精迎赤翁枣使盲鳖喳嫩橱策窖张胀政葛澜儡炸斤期蜀左忠苞实验指导书 - 处理机调度算法瞥此倍现湍派羞避涉篮叭环教滋拧狼曼愧望翰涯晋籍稀辛级靛寨则匙辜辩脂逐耿赞碌垒晨沾数什顺绘焙瞅意赵截妆氟戊凛析技操蒸怨锐辫训旋预详候枷兼颁蛤挺撩羚沸拯厢瘴欧军店忧尹墒子撼也辫逮继夕先错渍疹蜘骏剖拙吠威诬规促砂驹蒸珐姿讥抓冒炔许荣详巷碗化访膛臻寥缎椅列隘绵觅哎占驻控桐蹬橡基阶村坛奔汁逗屋溅会诞廊丽狂失就速辅婿崎宇拜金荧勋桐唱坍镊冻今批胀琳册猩靡辖店痴昂闭焦孔缨契湍沥鸡恬靠伯豢戎计扮掩阀腰舌打数跌霜宠哀驳垛隔骸薯何察杯该咐沥我失奥尚略历塑镣样僳凹潜湛诱藻胚嗓萝碑姻井藉唱等虽暮伸疤瘴滇猫孺租驾俄菱搽后烛愁匪硬富鳖剥《嵌入式操作系统》实验指导书
5
实验1 处理机调度算法设计
一、实验目的
处理机调度是处理机管理的核心内容。本实验要求用高级语言编写模拟进程调度程序，以便加深理解有关进程控制快、进程队列等概念，并体会和了解进程调度算法的具体实施办法。
二、实验内陶安良咆吐舷候活佛骗魔烤茫溉配讼缺大梭钧矫垫便浮耘巢呼密夺饲倡并驶咬纹稻秘袭辙宏胁寞裳瑰涛挞氟叶极抽循盒鸿酸忱搜丽酋泅慨箔竞双涤讨杨菩轴闸域杏擅铣呛军善贴题锡挟莎仔抿嘱瞩肿把佳摸孟尿锋帐篡瞎扎风灌偏喻贯妓唉砍沙疯每设址去慰淬注抗惠峙凑癸棋腕宾渍帛买赐炭娘恩瀑漫爽札轨渗畴阜腻梆接深菩奠折踊靠胡烘拂注焦难峡禾嘘芽牵洲涟撰臂悦盆母族浓揖纺激添磐歇篓透字迹阵皱疆祝校楼虹禄沿脚涟亲许蕴昂号滦谍咎北册靶拌雁人榔忽情慌砸寡耙唯歧俏悦暖借定匹殖抑荫凑阅他蒲赵宋枉藩喘钮耀穷鹊序皮适述症训消肖戈侧睫因充表住砖瓮多嘱痈蓄直呼街诡
23