进程调度存储器管理 银行家算法 磁盘调度操作系统实验报告

1、江苏科技大学操作系统实验报告（2015/2016学年第2学期） 课程名称： 操作系统 指导教师： 实验地点： 西校区图书馆计算机机房 学生姓名： 学生学号： 院 系： 计算机科学与工程学院 专 业： 计算机科学与技术 2016年 5 月 15 日实验一 进程调度一、实验目的多道程序设计中，经常是若干个进程同时处于就绪状态，必须依照某种策略来决定那个进程优先占有处理机。因而引起进程调度。本实验模拟在单处理机情况下的处理机调度问题，加深对进程调度的理解。二、实验内容1优先权法、轮转法简化假设1）进程为计算型的（无I/O）2）进程状态：ready、running、finish3）进程需要的CPU时间

2、以时间片为单位确定2算法描述1）优先权法动态优先权当前运行进程用完时间片后，其优先权减去一个常数。2）轮转法三、实验要求1产生的各种随机数的取值范围加以限制，如所需的CPU时间限制在120之间。2进程数n不要太大通常取48个3使用动态数据结构4独立编程5二种调度算法四、实验过程/秦魏编写 要拷贝使用 无（fa）偿(ge)使(hong)用(bao)#ifndef Maxpriority_H#define Maxpriority_H#define arrayLenth 100;template<class T>class MaxheapT *heap;int heapsize, len

3、th;public:Maxheap(int n) lenth = 0;heapsize = n;heap = new Theapsize;Maxheap(T *maxheap, int n)if (n < 0)return;lenth = n;heapsize = n;heap = new Theapsize;int i;for (i = 0; i < heapsize; i+)heapi = maxheapi;create();Maxheap() deleteheap; int Parent(int i)return (i+1)/ 2-1;/注意地址的转换，最后还要减去1int

4、Lchild(int i) return 2 * (i+1)-1; int Rchild(int i) return 2 * i + 2; void Maxheapify(int i)int l, r;l = Lchild(i);r = Rchild(i);int largest;if (l < lenth&&heapl.priority>heapi.priority)/第一个条件，起到一个判断是否为叶子节点的作用largest = l;else largest = i;if (r <lenth&&heapr.priority > hea

5、plargest.priority)largest = r;if (largest != i) swap(heaplargest, heapi),Maxheapify(largest);void swap(T &a, T &b)T store;store = a;a = b;b = store;void create()int i;for (i = lenth / 2-1; i >= 0; i-)Maxheapify(i);void insert(T &element) lenth+; heaplenth-1 = element;create();void pri

6、nt()int i;for (i = 0; i < lenth; i+)cout << heapi.priority;int heapextractmax()if (lenth=0) return -1;T max;max = heap0;heap0 = heaplenth - 1;lenth-;Maxheapify(0);return max.task;int empty() if (lenth = 0) return 1;return 0;#endif#ifndef Quene_H#define Quene_H#define size 1000/队列先进先出，从队尾进，从

7、对头出template<class T>class CirqueneT asize;int front,rear;public:Cirquene()front=rear=size-1;Cirquene() void Enquene(T &e)if(rear+1)%size=front) throw"上溢"rear=(rear+1)%size;arear=e;int Dequene()if(rear=size) throw"下溢"if (Empty() return -1;elsefront = (front + 1) % size;r

8、eturn afront.task;int Getfront()return front;int Empty()if (front = rear) return 1;return 0;void print()datatype e = arear;int i;doi = e.pre;cout << e.x << 't' << e.y << endl;e = ai; while (i!=-1);/注意这边i的取值;#endif#include<iostream>#include "Maxheap.h"#

9、include"Quene.h"using namespace std;enum State/enum变量后用逗号隔开！ready,exe,blo,fin,;/任务状态struct PCB/优先级队列通过堆排序实现int task;/任务int priority;/优先级int AexeTime;/已经运行时间int SexeTime;/剩余运行时间int blocktime;/阻塞时间State state;/任务状态;int checkstate(PCB *program) int i;/检查是否所有程序都已运行结束for (i = 0; i < 5; i+)if

10、 (programi.state != fin) return 0;return 1;void PSA(Maxheap<PCB> Test,PCB *program,int Arrtime,int quantum )/1个单位时间检查一次 用堆排序实现优先级队列int m = 0, alltime = 0,num=0,k,time=0;while (!checkstate(program)if (num < 5)for (m = 0; m < 5; m+)if (alltime = Arrtimem) Test.insert(programm),cout <<

11、; "进程" << m + 1 << "到达 " << endl,num+, programm.state = ready;/到达到达时间 进入就绪队列if(alltime=0|k=-1)k= Test.heapextractmax();/在无进程运行 后序有进程进入时应该抛出！alltime+, time+;if (k = -1) cout << "从" << alltime -1<< "到" << alltime <<

12、; "单位时间无进程运行" << endl;if (k != -1)programk.state = exe,programk.AexeTime+,programk.SexeTime-,programk.priority-=3,/优先级减3cout << "从" << alltime-1 << "到" << alltime << "单位时间" << k + 1 << "进程运行" << e

13、ndl;if (programk.SexeTime = 0) programk.state = fin, time = 0,cout << "进程" <<k + 1 << "在" << alltime<< "单位时间运行结束" << endl,k = Test.heapextractmax();if (programk.SexeTime != 0&&time=quantum) programk.state = ready,Test.insert(p

14、rogramk), time = 0, k = Test.heapextractmax();void RR(PCB *program, int i, int Arrtime, int quantum)/优先级列表用队列实现int m, k, num=0, alltime=0,time=0;Cirquene<PCB> priority;while (!checkstate(program)if(alltime=0)for (m = 0; m < i; m+)if (alltime = Arrtimem) priority.Enquene(programm),cout <&

15、lt; "进程" << m + 1 << "到达 " << endl,num+, programm.state = ready;/找到第一个到达的进程if(alltime=0|k=-1) k = priority.Dequene();/开始调度alltime+, time+;if (alltime != 0 && num<i)for (m = 0; m < i; m+)/先判断下一个时刻是否有进程到达 原因是在一个进程运行结束 同时另外一个进程到达 到达的那个进程应该首先进入就绪队列if (

16、alltime = Arrtimem) priority.Enquene(programm),cout << "进程" << m + 1 << "到达 " << endl,num+, programm.state = ready;if (k = -1) cout << "从" << alltime-1<< "到" << alltime << "单位时间无进程运行" << end

17、l;else programk.state = exe,programk.AexeTime+,programk.SexeTime-;cout << "从" << alltime -1<< "到" << alltime << "单位时间" << k + 1 << "进程运行" << endl;if (programk.SexeTime = 0)programk.state = fin,time = 0,cout <&

18、lt; "进程" << k + 1 << "在" << alltime << "单位时间运行结束" << endl, k = priority.Dequene();if (time = quantum)if (programk.SexeTime != 0) programk.state = ready, priority.Enquene(programk),k = priority.Dequene(),time=0;int main()int task5 = 0,1,2,3,

19、4 ;/任务int ExeTime5 = 5, 5, 3, 1, 3;/运行时间int priority5 = 2,5,2,4,3 ;/优先级int ArrTime5 = 4, 3, 2,0,4 ;/到达时间PCB program5,program25;int i;for (i = 0; i<5; i+)programi.task = taski,program2i.task = taski ;programi.priority = priorityi,program2i.priority = priorityi; programi.AexeTime = 0, program2i.Aex

20、eTime = 0;programi.SexeTime = ExeTimei, program2i.SexeTime = ExeTimei;programi.blocktime = 0, program2i.blocktime = 0;programi.state = blo,program2i.state = blo ;/初始化pcb*/Maxheap<PCB> Test(5);int quantum=2;/时间片为2cout << "优先权法:" << endl;PSA(Test, program, ArrTime,quantum);

21、cout << "轮转调度法:" << endl;RR(program2, 5, ArrTime, quantum);system("pause");return 0;五、实验分析与实现1.轮转法调度，具有先进先出的特点，所以利用队列实现2.优先级调度算法具有优先级动态变化的特点，每一次进行优先级要排序。所以优先级队列通过堆来实现六、实验过程中的问题及对应思考动态优先级调度算法：这种调度算法根据进程的资源需求来动态地分配进程的优先级，其目的就是在资源分配和调度时有更大的灵活性.在实时系统中，最早期限优先算法(EDF)算法是使用最多

22、的一种动态优先级调度算法，该算法给就绪队列中的各个进程根据它们的截止期限(Deadline)来分配优先级，具有最近的截止期限的进程具有最高的优先级.轮转法：系统将所有就绪进程按FIFO规则排队，按一定的时间间隔把处理机分配给队列中的进程。这样，就绪队列中所有进程均可获得一个时间片的处理机而运行。 虽然实验原理比较简单，但是在编写代码的过程中遇到了不少的问题，在两个小时之内已经完成 的大体代码的编写，但是之中存在不少的问题，导致了用了差不多四个小时的时间去调试才把它弄好，这主要归咎于在开始设计代码的不太合理，在后期使得代码结构有些混乱，使得调试更加的麻烦，以及对编程的不熟悉。通过这个实验不仅使我

23、对进程的调度算法有了更深的认识，使得理论知识得到的实践，也使我的编程能力得到了进一步提高。实验二 银行家算法一、实验目的死锁会引起计算机工作僵死，因此操作系统中必须防止。本实验的目的在于让学生独立的使用高级语言编写和调试一个系统动态分配资源的简单模拟程序，了解死锁产生的条件和原因，并采用银行家算法有效地防止死锁的发生，以加深对课堂上所讲授的知识的理解。二、实验内容银行家算法三、实验要求设计有n个进程共享m个系统资源的系统，进程可动态的申请和释放资源，系统按各进程的申请动态的分配资源。系统能显示各个进程申请和释放资源，以及系统动态分配资源的过程，便于用户观察和分析；四、实验过程#include&

24、lt;iostream>using namespace std;void Matrixminus(int a10,int b10,int c10,int m,int n)int i, k;for (i = 0; i < m; i+)for (k = 0; k < n; k+)cik = aik - bik;void Initialize(int a10, int m, int n)int c, b;for (c = 0; c < m; c+)for (b = 0; b < n; b+)cin>>acb;void Add(int a, int b10,

25、int m, int n)int i;for (i = 0; i < n; i+)ai = ai + bmi;void Matrixprint(int a10, int m, int n)int i, k;for (k = 0; k < m; k+)for (i = 0; i < n; i+)cout << aki;int Compare(int work,int need10,int m,int n)int i;for (i = 0; i < n; i+)if (needmi>worki) return 0;return 1;int Compare2

26、(int request10, int available, int m, int n)int i;for (i = 0; i < n; i+)if (availablei<requestmi) return 0;return 1; int Check(int m, int n, int Available10,int Max1010,int Allocation1010, int Need1010)int *Work;int *Finish;Finish = new intm;Work = new intn;int i,k;for (i = 0; i < m; i+)Fin

27、ishi = 0;for (i = 0; i < n; i+)Worki = Availablei;for (k = 0; k < m;k+)for (i = 0; i < m; i+)if (Compare(Work, Need, i, n) && Finishi = 0) Add(Work, Allocation, i, n), Finishi = 1;for (k = 0; k < m; k+)if (Finishk = 0) return 0;return 1;void Bankeralgorithm(int n,int m, int Avail

28、able, int Max10, int Allocation10, int Need10,int request1010,int k)int a;for (a = 0; a < n; a+)if (requestka>Needka) return;while (!Compare2(request,Available , k, n)for (a = 0; a < n;a+)Availablea = Availablea - requestka;Allocationka = Allocationka + requestka;Needka = Needka - requestka

29、;if (!Check(m, n, Available, Max, Allocation, Need)cout << "分配失败" << endl;for (a = 0; a < n; a+)Availablea = Availablea +requestka;Allocationka = Allocationka - requestka;Needka = Needka + requestka;else cout << "分配成功" << endl; int main()int Available10

30、,Max1010,Allocation1010,Need1010,request1010;int m, n;cout << "请输入进程个数和资源种类的个数" << endl;cin >> m >> n;cout << "请输入可分配资源" << endl;int i;for (i = 0; i < n; i+)cin >> Availablei;cout << "请输入进程最大所需资源" << endl;Initiali

31、ze(Max, m, n);cout << "请输入已分配资源" << endl;Initialize(Allocation, m, n);int k;cout << "请输入要申请资源的进程" << endl;cin >> k;cout << "请输入要分配的资源的数量"<<endl;for (i = 0; i < n; i+)cin >> requestki;Matrixminus(Max, Allocation, Need, m

32、, n);Bankeralgorithm(n, m, Available, Max, Allocation, Need,request,k);system("pause");return 0; 五、实验分析与实现实验数据来自书上例题6、 实验过程中的问题及对应思考通过本次实验，我知道了可以把操作系统看作是银行家，操作系统管理的资源相当于银行家管理的资金，进程向操作系统请求分配资源相当于用户向银行家贷款。 为保证资金的安全，银行家规定： (1) 当一个顾客对资金的最大需求量不超过银行家现有的资金时就可接纳该顾客； (2) 顾客可以分期贷款，但贷款的总数不能超过最大需求量； (

33、3) 当银行家现有的资金不能满足顾客尚需的贷款数额时，对顾客的贷款可推迟支付，但总能使顾客在有限的时间里得到贷款； (4) 当顾客得到所需的全部资金后，一定能在有限的时间里归还所有的资金. 操作系统按照银行家制定的规则为进程分配资源，当进程首次申请资源时，要测试该进程对资源的最大需求量，如果系统现存的资源可以满足它的最大需求量则按当前的申请量分配资源，否则就推迟分配。当进程在执行中继续申请资源时，先测试该进程本次申请的资源数是否超过了该资源所剩余的总量。若超过则拒绝分配资源，若能满足则按当前的申请量分配资源，否则也要推迟分配。 这次的实验中还遇到一些问题，在同学的帮助下一一解决了实验三 存储管

34、理一、实验目的存储管理的主要功能之一是合理地分配空间。请求页式管理是一种常用的虚拟存储管理技术。本实验的目的是通过请求页式管理中页面置换算法模拟设计，了解虚拟存储技术的特点，掌握请求页式存储管理的页面置换算法。二、实验内容（1） 通过计算不同算法的命中率比较算法的优劣。同时也考虑了用户内存容量对命中率的影响。页面失效次数为每次访问相应指令时，该指令所对应的页不在内存中的次数。在本实验中，假定页面大小为1k，用户虚存容量为32k，用户内存容量为4页到32页。（2） produce_addstream通过随机数产生一个指令序列，共320条指令。A、 指令的地址按下述原则生成：1） 50%的指令是顺

35、序执行的2） 25%的指令是均匀分布在前地址部分3） 25%的指令是均匀分布在后地址部分B、 具体的实施方法是：1） 在0，319的指令地址之间随机选取一起点m；2） 顺序执行一条指令，即执行地址为m+1的指令；3） 在前地址0，m+1中随机选取一条指令并执行，该指令的地址为m；4） 顺序执行一条指令，地址为m+1的指令5） 在后地址m+2，319中随机选取一条指令并执行；6） 重复上述步骤1）5），直到执行320次指令C、 将指令序列变换称为页地址流在用户虚存中，按每k存放10条指令排列虚存地址，即320条指令在虚存中的存放方式为：第0条第9条指令为第0页（对应虚存地址为0，9）；第10条第

36、19条指令为第1页（对应虚存地址为10，19）；。第310条第319条指令为第31页（对应虚存地址为310，319）；按以上方式，用户指令可组成32页。（3） 计算并输出下属算法在不同内存容量下的命中率。1） 先进先出的算法（FIFO）；2） 最近最少使用算法（LRU）；3） 最佳淘汰算法（OPT）；4） 最少访问页面算法（LFR）；其中3）和4）为选做内容当前运行进程用完时间片后，其优先权减去一个常数。2）轮转法三、实验要求1产生的各种随机数的取值范围加以限制，如所需的CPU时间限制在120之间。2进程数n不要太大通常取48个3使用动态数据结构4独立编程5二种调度算法四、实验过程#ifnde

37、f Linklist_H#define Linklist_Htemplate<class T> struct NodeT data; Node *next; template<class T> class Linklist Node<T> *first; public: Linklist() first = new Node<T> first->data = 0; first->next = 0; Linklist(T *a, int b) first = new Node<T> first->data=0; fir

38、st->next = 0; Node<T> *p, *r; p = first; int m; for (m = 0; m < b; m+) r = new Node<T> r->data = am; r->next = 0; p->next = r; p = r; p->next = 0; T Get(int i) Node<T> *p; p = first; int m; for (m = 0; m < i; m+) p=p->next; return p->data; int Locate(T a)

39、int count = 0; Node<T> *p; p = first; while (p->next!= 0) p = p->next; count+; if (p->data = a) return count; return 0; int Len() int count=0; Node<T> *p; p = first; while (p->next!= 0) p = p->next; count+; return count; void Delete(int i) Node<T> *p, *q; p = first;i

40、nt m;q=first;if (i != 1) for(m = 0; m < i - 1; m+)q=q->next;p = q->next;q->next=p->next;delete p; void Print() Node<T> *p; p = first; if (p->next= 0) cout << "链表为空"<<endl; while (p->next != 0) p = p->next;if(p!=0) cout << p->data <<

41、endl; void Insert(int i, T a) Node<T> *p, *q; p = first; int m = 0; while (m!=i-1) p = p->next; m+; q = new Node<T> q->data = a; q->next = p->next; p->next = q; Linklist() Node<T> *p; p = new Node<T> while (first != 0) p = first;/保留前面一个节点 同时将first后移 first = fir

42、st->next; delete p; int Empty() if (first->next = 0) return 1; return 0; ;#endif#ifndef Stack_H#define Stack_H#define Stacksize 1000/栈的最大特点是先进后出;template<class T>class StackT data1000;T top;public:Stack()top = -1;void Push(T a1)if (top = Stacksize - 1) throw"下溢"data+top = a1;T

43、pop()if (top = -1) throw"下溢"return datatop-;void Popfirst()int i;for (i = 0; i < top; i+)datai = datai + 1;top-;void print()int i;for (i = 0; i <= top; i+)cout << datai<< endl;int Locate(T a)int i;for (i = 0; i <= top; i+)if (datai = a) return i;return -1;void GoTop(T

44、a)/将栈中某一特定的值压倒栈顶int m = Locate(a);int i;for (i = m; i < top; i+)datai = datai + 1;top-;Push(a);Stack();#endif#ifndef Quene_H#define Quene_H#define size 5template<class T>class CirqueneT asize;int front,rear;public:Cirquene()front=rear=size-1;Cirquene()void Enquene(T e)/if(rear+1)%size=front

45、) throw"上溢"rear=(rear+1)%size;arear=e;T Dequene()if(rear=size) throw"下溢"front=(front+1)%size;return afront;int Getfront()return front;int Empty()if (front = rear) return 1;return 0;int Full() if (front - rear = 1) return 1;return 0;int check(T c)int b=front; while (b != rear)b=(b

46、+ 1) % size;if (ab = c) return 1;if (arear = c) return 1;return 0;#endif#include<iostream>#include<time.h>#include<stdlib.h>#include"Quene.h"#include"List.H"#include"Stack.h"using namespace std;#define ZoneNum 4/物理块为四struct pageadressint pNum;int fNum;

47、struct zoneint pNum;int fNum;zone *next;void Aexchange(pageadress *a,int b)a->pNum = b/ 10;a->fNum = b % 10;void produce_addstream(pageadress *test)srand(time(0);int i,m;for (i = 0; i < 80; i+)m =(rand()+1) % 320;Aexchange(test + 4 * i, m);m = rand() % (m + 1);Aexchange(test + 4 * i+1, m);m

48、 = (m + 1) % 320;Aexchange(test + 4 * i + 2, m);m = rand() % (319 - m) + m + 1;Aexchange(test + 4 * i + 3, m);void FIFO(pageadress *a,int k)Cirquene<int> test;int Num=0,i;test.Enquene(a0.pNum), Num+;for (i = 1; i < k; i+)if (!test.Full()if (!test.check(ai.pNum) Num+, test.Enquene(ai.pNum);i

49、f (test.Full() if (!test.check(ai.pNum) Num+, test.Dequene(), test.Enquene(ai.pNum);cout << "FIFO算法命中率：" << 1 - Num / 320.0 << endl;int Minvisitnumber(pageadress *a, int k,int *m)/k为目前的位置，m为物理块中的值int num,i,n;int store4;for (n = 0; n < 4; n+)for (i = 0,num=0; i < k -

50、 1; i+)if (ai.pNum = mn) num+;storen = num;int min = store0,Min=0;for (n = 1; n < 4; n+)if (storen < min) min = storen,Min=n;return mMin;void LFU(pageadress *a, int k)Linklist<int> test;int num=0,Num=0,storeZoneNum,m,min;test.Insert(1, a0.pNum),num+,Num+;for (int i = 1; i < k; i+)if (

51、!test.Locate(ai.pNum)if (num != 4)test.Insert(1, ai.pNum);num+;if (num = 4)for (m = 0; m < 4; m+)storem = test.Get(m + 1);min = Minvisitnumber(a, i, store);test.Delete(test.Locate(min);test.Insert(1, ai.pNum);Num+;cout << "LFU算法命中率：" << 1 - Num / 320.0 << endl;void LRU

52、(pageadress *a, int k)Stack<int> test;int num = 0, Num = 0, storeZoneNum, m, min;test.Push( a0.pNum), num+, Num+;/test.Push(a1.pNum);test.Push(a2.pNum);/test.GoTop(a0.pNum);/cout << a0.pNum << 't' << a1.pNum << 't' << a2.pNum << endl;/test.pr

53、int();for (int i = 1; i < k; i+)if (test.Locate(ai.pNum)=-1)if (num != 4)test.Push( ai.pNum);num+;if (num = 4)test.Popfirst();test.Push( ai.pNum);Num+;else test.GoTop(ai.pNum);cout << "LRU算法命中率：" << 1 - Num / 320.0 << endl;int Maxvisitnumber(pageadress *a, int k, int *m)/k为目前的位置，m为物理块中的值int i, n;int store4;for (n = 0; n < 4; n+)for (storen = 319, i = k + 1; i < 320; i+)if (ai.pNum = mn) storen = i;br