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

嵌入式操作系统实验指导书实验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把供等候理发的顾客坐的椅子如果没有顾客，理发师便在理发椅上睡觉一个顾客到来时，它必须叫醒理发师，如果理发师正在理发时又有顾客来到，则如果有空椅子可坐，就坐下来等待，否则就离开。3、 实验要求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 下的多线程