缓冲区管理

//假设系统中有两个分别名为P1、P2的进程
//两台均可进行输入、输出操作的设备d1、d2
//两个进程可以从两台设备中的任何一台输入数据，并可以向其中的任何一台设备输出数据。

#include
#include
#include
#include
#include


#define NUMOFBUFFER 10
#define SIZEOFBUFFER 100
#define NO -1
#define MAX 200


struct buffer{ //系统中的缓冲区
int count; //缓冲区中现在的字符个数
char databuffer[SIZEOFBUFFER]; //数据区
struct buffer *p; //用作队列指针
}buf[NUMOFBUFFER];


typedef struct queue{ //队列
int buf[NUMOFBUFFER]; //保存队列中的元素
int front; //头指针
int rear; //尾指针
int currentSize; //当前长度
int maxSize; //最大长度
}SqQueue;


SqQueue emptyBuffer;
SqQueue outputOfDevice1;
SqQueue outputOfDevice2;
SqQueue inputOfDevice1;
SqQueue inputOfDevice2;


int mutex = 1;
int od1,od2,id1,id2;

int mistake = 0;


//初始化空队列
void InitEmptyQueue(SqQueue &L){
int i;
for(i = 0;i <>
L.buf[i] = i;
L.front = 0;
L.rear = 9;
L.currentSize = 10;
L.maxSize = NUMOFBUFFER;
}


//初始化队列
void InitQueue(SqQueue &L){
int i;
for(i = 0;i <>
L.buf[i] = NO;
L.front = 0;
L.rear = L.front - 1;
L.currentSize = 0;
L.maxSize = NUMOFBUFFER;
}


//P操作
void Pprocess(int source){
source --;
if(source <>
printf("Sorry.There is no empty buffer.Please wait.:-(\n");
mistake = 1;
}
}


//V操作
void Vprocess(int source){
source ++;
if(source > 0)
mistake = 0;
}


//入队
void EnQueue(SqQueue &L,int buf){
Pprocess(mutex);

if(L.currentSize == 0){
L.front = 0;
L.rear = -1;
}

if(L.rear == 9) //队满的情况已经在主函数中做过处理
L.rear = fmod(L.rear + 1,10);
else
L.rear ++;
L.buf[L.rear] = buf;
L.currentSize ++;

Vprocess(mutex);
}


//出队
int DeQueue(SqQueue &L){ //队空的情况已经在主函数中做过处理
int e;

Pprocess(mutex);

e = L.buf[L.front];
L.buf[L.front] = NO;
L.front ++;
L.currentSize --;

Vprocess(mutex);

return e;
}


//完成缓冲区和各个队列的初始化操作
void init(){

//缓冲区初始化操作
int i,j;
for(i = 0;i <>
buf[i].count = 0;
for(j = 0;j <>
buf[i].databuffer[j] = ' ';
buf[i].p = &buf[i + 1];
}

//各个队列的初始化操作
InitEmptyQueue(emptyBuffer);
InitQueue(outputOfDevice1);
InitQueue(outputOfDevice2);
InitQueue(inputOfDevice1);
InitQueue(inputOfDevice2);
}


//从空队列中取出一个缓冲区
int getBuffer(){
int index;
int size = emptyBuffer.currentSize;

Pprocess(size);

if(mistake != 1){
Pprocess(mutex); //对空缓冲区队列进行互斥操作
index = DeQueue(emptyBuffer);
Vprocess(mutex);
}

return index;
}


//空队列中放入一个缓冲区
void putBuffer(int index){
int size = emptyBuffer.currentSize;

Pprocess(mutex); //对空缓冲区队列进行互斥操作
EnQueue(emptyBuffer,index);
Vprocess(mutex);

Vprocess(size);
}


//输出内容，格式控制函数
void print(){
int i = 0,k = 0,index;

printf("...........................................\n");
printf("...........................................\n");

//显示空缓冲区队列
printf("emptyBuffer : ");
if(emptyBuffer.currentSize == 0 || mistake == 1)
printf("NULL");
else{
i = emptyBuffer.front;
do{
index = fmod((i+k),10);
printf("%d ",emptyBuffer.buf[index]);
k ++;
}while(k <>
}
putchar('\n');

//显示设备一的输出队列
printf("outputOfDevice1 : ");
if(outputOfDevice1.currentSize == 0)
printf("NULL");
else{
i = outputOfDevice1.front;
k = 0;
do{
index = fmod((i+k),10);
printf("%d ",outputOfDevice1.buf[index]);
k ++;
}while(k <>
}
putchar('\n');

//显示设备二的输出队列
printf("outputOfDevice2 : ");
if(outputOfDevice2.currentSize == 0)
printf("NULL");
else{
i = outputOfDevice2.front;
k = 0;
do{
index = fmod((i+k),10);
printf("%d ",outputOfDevice2.buf[index]);
k ++;
}while(k <>
}
putchar('\n');

//显示设备一的输入队列
printf("inputOfDevice1 : ");
if(inputOfDevice1.currentSize == 0)
printf("NULL");
else{
i = inputOfDevice1.front;
k = 0;
do{
index = fmod((i+k),10);
printf("%d ",inputOfDevice1.buf[index]);
k ++;
}while(k <>
}
putchar('\n');

//显示设备二的输入队列
printf("inputOfDevice2 : ");
if(inputOfDevice2.currentSize == 0)
printf("NULL");
else{
i = inputOfDevice2.front;
k = 0;
do{
index = fmod((i+k),10);
printf("%d ",inputOfDevice2.buf[index]);
k ++;
}while(k <>
}
putchar('\n');

printf("...........................................\n");
}


//设备选择显示函数
int withTools(){
char dc = getch();
if(dc == '1')
printf("device1.");
else{
if(dc == '2')
printf("device2.");
else
printf("error.");
}
putchar('\n');
printf("...........................................\n");
int tool = (int)dc - 48;
return tool;
}


//线程选择显示函数
int withType(){
int dc = getch();
if(dc == '1')
printf("thread1.");
else{
if(dc == '2')
printf("thread2.");
else
printf("error.");
}
putchar('\n');
printf("...........................................\n");
int type = (int)dc - 48;
return type;
}


//完成进程的数据处理.
//按照inputdev指定的设备号从该设备的输入队列中取出一个缓冲区；
//按照procnum的序号对缓冲区中的数据进行指定的数据处理操作；
//按照outputdev指定的设备号将缓冲区放入该设备的输出队列。
void process(int procnum,int inputdev,int outputdev){
int index;

switch (inputdev){
case 1:
id1 = inputOfDevice1.currentSize;
Pprocess(id1);
index = DeQueue(inputOfDevice1);
break;
case 2:
id2 = inputOfDevice2.currentSize;
Pprocess(id2);
index = DeQueue(inputOfDevice2);
break;
}

strupr(buf[index].databuffer); //小写字母转换成大写字母

switch (outputdev){
case 1:
od1 = outputOfDevice1.currentSize;
EnQueue(outputOfDevice1,index);
Vprocess(od1);
break;
case 2:
od2 = outputOfDevice2.currentSize;
EnQueue(outputOfDevice2,index);
Vprocess(od2);
break;
}

printf("thread: %d---inputdevice: %d---outputdevice: %d\n",procnum,inputdev,outputdev);
print();
}


//完成设备的读写操作.其中参数devnum指出需要进行I/O操作的设备,flag为操作类型
void deviceReadAndWrite(int devnum,int flag){
int index;
char input[SIZEOFBUFFER];

if(flag == 1){ //读操作
index = getBuffer(); //从空队列中取出一个缓冲区
if(mistake == 1){
printf("You must make a full buffer empty.:-(\n");
goto lab;
}
else{
printf("Please input some letters : ");
scanf("%s",input);
strcpy(buf[index].databuffer,input); //从终端读入一行字符串，放入缓冲区的数据区
buf[index].count = strlen(input);
if(devnum == 1){ //按照指定的设备号将缓冲区放入相应的设备输入队列
id1 = inputOfDevice1.currentSize;
EnQueue(inputOfDevice1,index);
Vprocess(id1);
}
else{
id2 = inputOfDevice2.currentSize;
EnQueue(inputOfDevice2,index);
Vprocess(id2);
}
}
}
else{ //写操作
if(devnum == 1){
od1 = outputOfDevice1.currentSize;
Pprocess(od1); //p(od1)
index = DeQueue(outputOfDevice1); //按照指定的设备号，从设备的输出队列中取出一个装满数据的缓冲区
printf("The contents of this buffer is : ");
printf("%s\n",buf[index].databuffer); //将缓冲区中的数据在终端上显示
putBuffer(index); //将空缓冲区放入空缓冲区队列
}
if(devnum == 2){
od2 = outputOfDevice2.currentSize;
Pprocess(od2); //p(od2)
index = DeQueue(outputOfDevice2); //按照指定的设备号，从设备的输出队列中取出一个装满数据的缓冲区
printf("The contents of this buffer is : ");
printf("%s\n",buf[index].databuffer); //将缓冲区中的数据在终端上显示
putBuffer(index); //将空缓冲区放入空缓冲区队列
}
}

lab:
print();
}


//代码使用控制函数
void getIn(){
char password[7] = {'0','5','2','2','2','6'};
char input[10];
int i = 0;

printf("-------------------------------------------\n");
printf("-------------------------------------------\n");


printf("Password : ");
char c = getch();

while(c != '*'){
input[i] = c;
i ++;
putchar('*');
c = getch();
}
input[i] = '\0';
putchar('\n');

if(strcmp(password,input) != 0){
printf("You do not have the right to use this code. :-(\n");
exit(0);
}

printf("-------------------------------------------\n");
printf("-------------------------------------------\n");
}


//模式选择函数
int printTip(){
printf("This code support three work models : \n");
printf("A.input B.output C.deal D.exit \n");
printf("Please choose : ");
char c = getch();
int model;

switch(c){
case 'A':
printf("input.\n");
model = 1;
break;
case 'B':
printf("output.\n");
model = 2;
break;
case 'C':
printf("deal.\n");
model = 3;
break;
case 'D':
printf("exit.\n");
model = 4;
break;
}
printf("...........................................\n");
return model;
}


//判断输出队列是否为空
int judgeOutput(int tool){
int emp; //0非空1空

switch (tool){
case 1:
if(outputOfDevice1.currentSize == 0)
emp = 1;
else
emp = 0;
break;
case 2:
if(outputOfDevice2.currentSize == 0)
emp = 1;
else
emp = 0;
break;
}
return emp;
}


//判断输入队列是否为空
int judgeInput(int tool){
int emp; //0非空1空
switch (tool){
case 1:
if(inputOfDevice1.currentSize == 0)
emp = 1;
else
emp = 0;
break;
case 2:
if(inputOfDevice2.currentSize == 0)
emp = 1;
else
emp = 0;
break;
}
return emp;
}


//判断输入队列是否为满
int judgeInputFull(int tool){
int full; //0非满1满
switch (tool){
case 1:
if(inputOfDevice1.currentSize == 10)
full = 1;
else
full = 0;
break;
case 2:
if(inputOfDevice2.currentSize == 10)
full = 1;
else
full = 0;
break;
}
return full;
}


//判断输出队列是否为满
int judgeOutputFull(int tool){
int full; //0非满1满
switch (tool){
case 1:
if(outputOfDevice1.currentSize == 10)
full = 1;
else
full = 0;
break;
case 2:
if(outputOfDevice2.currentSize == 10)
full = 1;
else
full = 0;
break;
}
return full;
}


void main(){
void InitEmptyQueue(SqQueue &L);
void InitQueue(SqQueue &L);
void EnQueue(SqQueue &L,int buf);
int DeQueue(SqQueue &L);
void init();
int getBuffer();
void putBuffer(int index);
void print();
int withTools();
int withType();
void process(int procnum,int inputdev,int outputdev);
void Pprocess(int source);
void Vprocess(int source);
void deviceReadAndWrite(int devnum,int flag);
void getIn();
int printTip();
int judgeOutput(int tool);
int judgeInput(int tool);
int judgeInputFull(int tool);
int judgeOutputFull(int tool);

int tool,thrd,model,tools;

getIn();
printf("Initiate : \n");
init();
print();

do{
model = printTip();
switch(model){
case 1: //输入
do{
printf("1:device1 2:device2\nPlease choose : ");
tool = withTools();
if(judgeInputFull(tool) == 1){ //判断输入队列是否为满
printf("The list of inputDevice%d is full.:-(\n",tool);
printf("Please input again.\n");
}
}while(judgeInputFull(tool) == 1);
deviceReadAndWrite(tool,model);
break;
case 2: //输出
do{
printf("1:device1 2:device2\nPlease choose : ");
tool = withTools();
if(judgeOutput(tool) == 1){ //判断输出队列是否为空
printf("The list of outputOfDevice%d is empty.:-(\n",tool);
printf("Please input again.\n");
}
}while(judgeOutput(tool) == 1);
deviceReadAndWrite(tool,model);
break;
case 3: //数据处理
printf("1:thread1 2:thread2\nPlease choose : ");
thrd = withType();
do{
printf("1:device1 2:device2\nThe device of input : ");
tool = withTools();
if(judgeInput(tool) == 1){ //判断输入队列是否为空
printf("The list of input of device%d is empty.:-(\n",tool);
printf("Please input again.\n");
}
}while(judgeInput(tool) == 1);
do{
printf("1:device1 2:device2\nThe device of output : ");
tools = withTools();
if(judgeOutputFull(tool) == 1){ //判断输出队列是否为满
printf("The list of output of device%d is full.:-(\n",tool);
printf("Please input again.\n");
}
}while(judgeOutputFull(tool) == 1);
process(thrd,tool,tools);
break;
case 4: //退出
break;
}
}while(model != 4);

printf("...........................................\n");
printf("...........................................\n");
printf("Thank you for using by 052226.:-)\n");
}

UNIX磁盘空间管理算法

#include
#include
#include

#define NO -1

struct size{//每一个磁盘块都有一个数组,该数组包含10个元素,当该磁盘快成为当前组的第一个时,用于存放下一组的信息
int blocl[10];
};

struct blocd{//定义组,每组有10个磁盘块
struct size a[10];//用于在空闲磁盘块号链中存放磁盘块号
}block[40];

struct File{
int fileblocd[100];//用于记录分别分配给文件的磁盘块号,每个文件最多占有100个磁盘快
}file[5];

struct SqStack{ //定义一个记录磁盘块号的堆栈
int *base;
int *top; //指向栈顶元素
int stacksize;
int s_nfree; //记录栈中现有磁盘块数的变量
}s_free;

void InitStack(SqStack &S){
S.base = (int *)malloc(10 * sizeof(int));
if(!S.base)
exit(OVERFLOW);
S.top = S.base - 1;
S.stacksize = 10;
S.s_nfree = 0;
}

void Push(SqStack &S, int e){
S.top ++;
*S.top = e;
S.s_nfree ++;
}

int Pop(SqStack &S){
int e = *S.top;
S.top --;
S.s_nfree --;
return e;
}

int label;//用来记录当前磁盘块的绝对名字
int nextLabel;//用来记录下一个磁盘块的绝对名字

//完成空闲磁盘块号堆栈、空闲磁盘块号队列及记录文件占用磁盘块状态的file结构数组
void init(){
int i,j,k;

//初始化空闲磁盘块号队列
for(i = 0;i <>
for(j = 0;j <>
if(i == 0){ //第0组中每个磁盘块内的数组中的每个元素都是NO
for(k = 0;k <>
block[i].a[j].blocl[k] = NO;
}
else{ //其他组中,除第0个磁盘块外,其他磁盘块的数组中的每个元素都是NO
if(j == 0){
for(k = 9;k >= 0;k --){
block[i].a[j].blocl[k] = label;
label --;
}
}
else{
for(k = 0;k <>
block[i].a[j].blocl[k] = NO;
}
}
}
j = j - 1;
label = i * 10 + j;
}

//初始化空闲磁盘块号堆栈
int tmp[10];
InitStack(s_free);
for(i = 0;i <>
tmp[i] = label;
label --;
} //循环结束时,label为下一组的最后一个元素的绝对名字
for(i = 9;i >= 0;i --)
Push(s_free,tmp[i]);

//初始化文件占用磁盘块状态
for(i = 0;i <>
for(j = 0;j <>
file[i].fileblocd[j] = NO;
}
}

int getLine(int name){
int line = name/10;
return line;
}

int getCount(int name){
int count = fmod(name,10);
return count;
}

void keepStackFull(int name){
int line = getLine(name);
int count = getCount(name);
int temp[10],i;

for(i = 0;i <>
temp[i] = block[line].a[count].blocl[i];
Push(s_free,temp[i]);
}

}

void keepStackEmpty(int nextName){
int line = getLine(nextName);
int count = getCount(nextName);

int temp[10],i,j;
for(i = 0;i <>
temp[i] = Pop(s_free);
for(i = 0,j = 9;i <>
block[line].a[count].blocl[i] = temp[j];

}

//fileno为文件序号，用于指定需要分配的文件;blockd为所需要磁盘块数目
void alloc(int fileno,int blockd){
int i;
for(i = 0;i <>
if(s_free.s_nfree == 0)
keepStackFull(label);
label = Pop(s_free);
file[fileno].fileblocd[i] = label;
}
}

void free(int fileno){
int i = 0;
do{
label = file[fileno].fileblocd[i];

if(s_free.s_nfree == 10){
//if(fmod(label,10) != 0)
//keepStackEmpty(nextLabel);
//else
keepStackEmpty(label);
}

Push(s_free,label);
file[fileno].fileblocd[i] = NO;
nextLabel = file[fileno].fileblocd[i+1];
i ++;
}while(nextLabel != NO);
}

//设置打印格式
void print(){
int i = 0,j,k,num;
printf("............................................................................\n");
printf("Free block : \n");
int st[10];
int line,count;
if(s_free.s_nfree != 0){
while(s_free.s_nfree != 0){
st[i] = Pop(s_free);
i ++;
}
}
else{
j = 9;
line = getLine(label);
count = getCount(label);
while(j >= 0){
st[i] = block[line].a[count].blocl[j];
i ++;
j --;
}
}


num = i;
for(i = num - 1;i >= 0;i --)
Push(s_free,st[i]);
for(i = 0;i <>
printf(" %3d ",st[i]);
putchar('\n');

line = getLine(st[num-1]);
count = getCount(st[num-1]);
do{
for(i = 9;i >= 0;i --)
printf(" %3d ",block[line].a[count].blocl[i]);
putchar('\n');
st[num - 1] = block[line].a[count].blocl[0];
line = getLine(st[num-1]);
count = getCount(st[num-1]);
}while(block[line].a[count].blocl[0] != NO);
printf("............................................................................\n");
printf("File : \n");
for(i = 0;i <>
printf("file[%d] :",i);
j = 0;
k = 0;
do{
if(file[i].fileblocd[j] == NO){
printf(" NULL");
break;
}
else{
printf(" %3d ",file[i].fileblocd[j]);
nextLabel = file[i].fileblocd[j+1];
j ++;
k ++;
if(fmod(k,10) == 0){
putchar('\n');
printf(" ");
}
}
}while(nextLabel != NO);
putchar('\n');
}
printf("............................................................................\n");
}

void main(){
init();
printf("初始化 : \n");
print();

int i,s;
char c,null;
int count_f = 0,count_h = 0;
step:
do{
printf("请输入待分配的文件的序号 : \n");
scanf("%d",&i);
null = getchar();
printf("请输入待分配的文件的所需的磁盘块数目 : \n");
judge:
scanf("%d",&s);
null = getchar();
alloc(i,s);
print();
if(s > 100){
printf("请重新输入文件所需的磁盘块数目 : ");
goto judge;
}
count_f = count_f + 1;
if(count_h > 0)
count_h = count_h - 1;
if(count_f == 5){
printf("已经有5个文件存在，达到最大值 . :-(\n");
break;
}
printf("分配 ? y or n ?\n");
c = getchar();
}while(c == 'y');

do{
printf("请输入待回收的文件的序号 : \n");
scanf("%d",&i);
null = getchar();
free(i);
print();
count_h = count_h + 1;
count_f = count_f - 1;
if(count_h == 5 || count_f == 0){
printf("已经没有文件存在，无法删除. :-(\n");
break;
}
printf("回收 ? y or n ?\n");
c = getchar();
null = getchar();
}while(c == 'y');
printf("分配 ? y or n ?\n");
c = getchar();

if(c == 'y')
goto step;
printf("感谢使用 by 052226 .:-)\n");
}