模拟LRU算法&通道处理算法
最近写了两个程序，模拟操作系统的算法，只是基本实现了课本上的基本功能，实际应该是很复杂的。
模拟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
作者： Leo_wl
出处： http://www.cnblogs.com/Leo_wl/
本文版权归作者和博客园共有，欢迎转载，但未经作者同意必须保留此段声明，且在文章页面明显位置给出原文连接，否则保留追究法律责任的权利。
版权信息声明：本文来自网络，不代表【好得很程序员自学网】立场，转载请注明出处：http://www.haodehen.cn/did49450