最近写了两个程序，模拟操作系统的算法，只是基本实现了课本上的基本功能，实际应该是很复杂的。
模拟LRU页面置换算法：
1 #include <stdio.h>
2 #include <stdlib.h>
3 #include <string.h>
4
5 #define TN 3 //分配给该程序的主存页数
6 #define PN 10 //地址流
7
8 int page[TN],cnt[PN]; //主存页面表
9 typedef struct PAGE{
10 int kPage; //the kth line 分配给该程序的主存页数的索引
11 int aPage; //address page 程序页号
12 int cnt; //到当前页地址的距离计数器
13 }PAGE;
14
15 PAGE pg[PN]; //页地址流
16 int cmp(const void *a, const void *b){
17 return ((PAGE *)b)->cnt - ((PAGE *)a)->cnt;
18 }
19
20 /*页面命中和替换页面时都需要初始化调入的页面*/
21 void init(int k, int p){
22 for(int i=0;i<k;i++){
23 if(pg[i].aPage==p)
24 pg[i].cnt=1;
25 }
26 }
27
28 /*查找页面表中最大的计数器,返回对应的索引*/
29 int findMax(){
30 int ans=0, max_cnt=-1, cnt, index;
31 int i,j;
32 for(i=0;i<TN;i++) {
33 /*在主存页面表中查找与给定页地址流页面相等的页面*/
34 for(j=0;j<PN;j++){
35 if(page[i] == pg[j].aPage){
36 cnt = pg[j].cnt;
37 break;
38 }
39 }
40
41 if(max_cnt < cnt) {
42 max_cnt = cnt;
43 ans = i;
44 index = j;
45 }
46 }
47 return ans;
48 }
49
50 int main(){
51 int i,p,k=0; /*p：当前页面，k：页地址流全局索引*/
52 memset(page,0,sizeof(page));
53 memset(cnt,0,sizeof(cnt));
54 memset(pg,0,sizeof(pg));
55
56 while(~scanf("%d",&p)){
57 int inserted=0, hit=0;
58
59 pg[k].aPage=p;
60 for(i=0;i<=k;i++) {
61 pg[i].cnt+=1;
62 }
63 printf("第%d个页地址:\n",k+1);
64 for(i=0;i<TN;i++) {
65 if(p == page[i]) { //命中
66 pg[k].cnt=1;
67 inserted=1;
68 hit=1;
69 printf("命中该道程序第%d行存放的页面%d\n",i+1,p);
70 break;
71 }
72 if(!page[i]){ //有空余页
73 page[i]=p;
74 pg[k].kPage=i;
75 pg[k].cnt=1;
76 inserted=1;
77 printf("第%d行调进页面%d\n",i+1,p);
78 break;
79 }
80 }
81 if(hit == 1) init(k,p);
82
83 /*替换操作,调进页面设置*/
84 if(!inserted){
85 //qsort(page,N,sizeof(page[0]),cmp);
86 init(k,p);
87 int replaceIndex=findMax();
88 int old=page[replaceIndex];
89 page[replaceIndex]=p; //置换
90 printf("第%d行的页面%d将被页面%d替换\n",replaceIndex+1,old,p);
91 }
92 printf("————————————\n");
93 k++;
94 }
95 return 0;
96 }
字节多路通道响应和设备处理：
1 #include <iostream>
2 #include <algorithm>
3 using namespace std;
4
5 #define N 5 //设备数目
6 #define GAP 10 //通道处理时间
7
8 struct Device{
9 int cycle; //设备周期
10 int start; //起始时间
11 int priority; //优先级
12 bool applied; //是否提出申请
13 }d[N];
14
15 /*初始化各设备起始状态*/
16 void init() {
17 for(int i=0; i < N; i++) {
18 d[i].applied = false;
19 cin>>d[i].start>>d[i].cycle>>d[i].priority;
20 }
21 }
22
23 int cmp(const void *a, const void *b){
24 int c=((Device *)b)->priority - ((Device *)a)->priority; //按优先级排序
25 if(c == 0) return ((Device *)a)->start - ((Device *)b)->start;
26 else if(c > 0)
27 return 1;
28 else return -1;
29 }
30
31 void swap(Device **a, Device *b){
32 Device tmp;
33 tmp.cycle = (*a)->cycle;
34 tmp.priority = (*a)->priority;
35 tmp.start = (*a)->start;
36 tmp.applied = (*a)->applied;
37
38 (*a)->cycle = b->cycle;
39 (*a)->priority = b->priority;
40 (*a)->start = b->start;
41 (*a)->applied = b->applied;
42
43 b->cycle = tmp.cycle;
44 b->priority = tmp.priority;
45 b->start =tmp.start;
46 b->applied = tmp.applied;
47 }
48 void Quicksort(Device **p) {
49 for(int i=0; i<N; i++) {
50 if(d[i].applied == true) { //只对申请的设备排序
51 if(d[i].priority > (*p)->priority) {
52 swap(p, &d[i]);
53 }
54 else if(d[i].priority == (*p)->priority){
55 if(d[i].start < (*p)->start)
56 swap(p, &d[i]);
57 }
58 }
59 }
60 }
61 void handle(int end_time){
62 int i,jv;
63 Device *p; //选中的设备
64 for(i = 0; i<end_time; i+=GAP){
65 int k=0;
66 for(j = 0; j<N; j++) {
67 if(d[j].start <= i) {
68 d[j].applied=true; //申请
69 if(k==0) p=&d[j]; //保存第一个提交申请的设备
70 k++;
71 }
72 }
73 Quicksort(&p);
74
75 /*选中的设备处理*/
76 p->applied = false;
77 p->start+=p->cycle;
78 cout<<p->priority<<" "<<p->cycle<<endl;
79 }
80 }
81
82 int main(){
83 init();
84 int end_time;
85 cin>>end_time;
86 cout<<"\nresult:\n";
87 handle(end_time);
88 return 0;
89 }
分类: 数据结构&算法
当前标签: 算法
模拟LRU算法&通道处理算法 Seiyagoo 2012-04-07 23:25 阅读:544 评论:0
扩展的欧几里得&中国剩余定理 Seiyagoo 2012-03-21 19:05 阅读:969 评论:3