아 날로 그 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    :
",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
",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
",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  
",replaceIndex+1,old,p);
91 　　　　}
92 　　　　printf("————————————
");
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<<"
result:
";
87 　　handle(end_time);
88 　　return 0;
89 }