“操作系统课程设计”总结报告
学期 20##-2013学年第2学期
学院 软件学院
学号
姓名
20## 年7月3日
本学期开设了操作系统课程,主要学习了计算机操作系统方面的知识(进程控制、进程调度、请求分页存储管理、设备管理、文件管理),了解了操作系统的相关应用,并通过“操作系统课程设计”实现了一套模拟的单用户多任务操作系统,掌握了操作系统包括进程管理、存储管理、设备管理和文件管理四部分。更深刻地领会操作系统工作原理和操作系统实现方法,并提高程序设计能力。以下是课程设计五个设计内容的总结。
一、 进程控制
1.1目的
通过简单的结构和控制方法,完成模拟进程结构、进程状态和进程控制,掌握进程控制的实现。
1.2完成的内容
1、用PCB表示整个进程实体,利用随机数方法或键盘控制方法模拟进程执行中产生的事件操作控制进程管理内容。
2、定义PCB:包括理论PCB中的基本内容,如内部ID、外部ID、进程状态、队列指针。由于无法实现真正的进程创建功能,在实验中只需建立PCB,用它代表完整的进程。
3、定义进程状态转换方式:进程的状态转换是由进程内部操作或操作系统的控制引起,由于无法实现这些功能,采用随机数方法或键盘控制方法模拟,并实现对应的控制程序。随机方法指产生1-6的随机数,分别代表创建进程(c)、结束进程(e)、进程阻塞(b)、激活进程(w)、调度进程(p)、时间片到(t)等事件;键盘模拟方法指定义6种按键代表以上6种事件。
4、根据事件处理就绪队列、阻塞队列和当前执行进程的状态。每次事件处理后应形象地显示出当前系统中的执行进程是哪一个,就绪队列和阻塞队列分别包含哪些进程。
1.3主要数据结构
void create(){ //新建
struct PCB *temp;
char name[10];
printf("process name:");
scanf("%s",name);
temp=(struct PCB *)malloc(sizeof(struct PCB));
strcpy(temp->name,name); //拷贝
temp->next=NULL;
add(ready,temp);
if(running==NULL){
running=removeFirst(ready);
}
}
void interupt(){//中断
if(running!=NULL){
add(ready,running);
running=removeFirst(ready);
}
}
void block(){//阻塞
if(running!=NULL){
add(blocked,running);
running=removeFirst(ready);
}
}
void wakeup(){//唤醒
if(blocked->next!=NULL){
add(ready,removeFirst(blocked));
}
if(running==NULL){
running=removeFirst(ready);
}
}
void finished(){//终止
if(running!=NULL){
free(running);
running=removeFirst(ready);
}
}
1.4算法设计及流程图
建立三个链表分别表示就绪队列、执行队列、阻塞队列;
根据不同的命令对相应的队列进行增删改;
1.5小结
(如何实现的?可以以关键部分流程图、主要数据结构、程序整体框架等内容表示。)
二、 请求分页存储器管理
2.1目的
通过在第1部分实验基础上实现进程的分页式内存分配和地址转换过程,完成请求分页式存储分配和地址转换过程,掌握页面置换算法:先进先出(FIFO)、最近最久未使用(LRU)等算法。
2.2完成的内容
1、建立一个位示图,用来模拟内存的分配情况,位示图的位数与设定的物理块个数相同。程序启动时可利用一组随机0和1填充位示图,表示内存已被占用情况。
2、创建进程时输入进程大小,并根据程序中设定的物理块大小为进程分配物理块,同时建立页表。
3、输入当前执行进程所要访问的逻辑地址,并将其转换成相应的物理地址。
4、进程退出时,根据其页表内容向位示图反向回填“1”。
5、扩充页表,将其变成支持请求和置换功能的二维页表(增加存在位等)。创建进程时可装入固定的前三页(或键盘输入初始装入页数,不同进程的装入个数可以不同),其余页装入到置换空间内。
6、分别采用FIFO和LRU置换算法对地址转换过程中遇到的缺页现象进行页面置换,可将多次地址转换过程中所涉及到的页号视为进程的页面访问序列,从而计算置换次数和缺页率.
2.3主要数据结构
struct page_table_item
{
int pagenum;
int blocknum;
int exist; //存在位
int modify; //修改位
int swap_add;
};
2.4算法设计及流程图
void terminate()
{
int i,j,p,q;
if(running==NULL)
{
printf("已结束所有进程!!!");
}
if(running!=NULL)
{
j=ceil(running->size,PAGE_SIZE);
if(j>3)
{
for(i=0;i<3;i++)
{
//printf("aaaaa\n");
p=(*(running->pagetable+i)).blocknum/8;
q=(*(running->pagetable+i)).blocknum%8;
//printf("%d",p);
setbit(&bitmap[p],q,0);
}
for(i=3;i<j;i++)
{
//printf("bbbb\n");
p=(*(running->pagetable+i)).blocknum/8;
q=(*(running->pagetable+i)).blocknum%8;
// printf("%d %d\n",p,q);
//printf("%d",p);
setbit(&changemap[p],q,0);
}
}
else
{
for(i=0;i<j;i++)
{
p=(*(running->pagetable+i)).blocknum/8;
q=(*(running->pagetable+i)).blocknum%8;
setbit(&bitmap[p],q,0);
}
}
free(running);
}
if(ready!=NULL)
{
running=removeFirst(ready);
}
}
void translate(){//逻辑地址转换成物理地址
if(running==NULL)
{
printf("没有执行进程");
}
else
{
int logical;
int pagenum,offset;
int blocknum;
printf("请输入逻辑地址:\n");
scanf("%d",&logical);
pagenum=(int)(logical/PAGE_SIZE);
offset=logical%PAGE_SIZE;
blocknum=(running->pagetable+pagenum)->blocknum;
//blocknum=*(running->pagetable+pagenum);
printf("物理地址:%d",blocknum*PAGE_SIZE+offset);
printf("\n");
}//blockno=*(running->pagetable + pageno);
}
void dispagetable()//显示执行进程页表
{
int i;
if(running==NULL)
{ printf("没有执行进程");
return;
}
for(i=0;i<ceil(running->size,BLOCK_SIZE);i++)
printf(" %d %d %d %d %d \n",(*(running->pagetable+i)).pagenum,(*(running->pagetable+i)).blocknum,(*(running->pagetable+i)).exist,(*(running->pagetable+i)).modify,(*(running->pagetable+i)).swap_add);
}
2.5小结
三、 设备管理
3.1目的
通过在前面的实验基础上,完成设备管理功能的模拟,掌握包括通道和控制器的添加和删除,设备的添加、删除,设备的分配和回收 。
3.2完成的内容
1、设备管理子系统涉及到系统设备表(SDT)、通道控制表(CHCT)、控制器控制表(COCT)和设备控制表(DCT)来体现输入输出系统的四级结构和三级控制。
2、实现上述设备、控制器以及通道的层次关系,同时能够添加或删除新的设备、控制器或通道。
3、通过键盘命令模拟进程执行过程中提出的设备分配或释放请求,并为此请求分配或释放设备。分配设备成功后可将进程状态调整为阻塞,释放设备后变为就绪状态。
4、分配设备时应如果该设备已被其它进程占用,则设备分配失败,请求进程进入阻塞状态,同时等待该设备的释放。如果设备空闲,进程占用设备的同时还应提出申请控制器请求,直到与设备相关的通道都已申请成功为止。
5、设备、控制器或通道的释放应引起对应节点的等待队列中的第一个阻塞进程被唤醒。如果被唤醒的进程还未完成申请操作,应继续执行上级节点的申请操作。
3.3主要数据结构
struct Node *DCTs,*COCTs,*CHCTs;//添加头结点,设备,控制器,通道
struct Node *addNode(char *name,struct Node *parent,struct Node *head){//在以head为头结点队列中添加名为name的节点
struct Node *tmp=head;//查找最末位节点
while(tmp->next!=NULL)
tmp=tmp->next;
tmp->next=(struct Node *)malloc(sizeof(struct Node));
strcpy(tmp->next->name,name);
tmp->next->next=NULL;
tmp->next->parent=parent;
tmp->next->process=NULL;
tmp->next->ready=(struct PCB *)malloc(sizeof(struct PCB));
tmp->next->ready->next=NULL;
return tmp->next;
}
3.4算法设计及流程图
int get_child_count(struct Node *node,struct Node *childs_head){//获取一个节点的所有子节点
int count=0;
struct Node *tmp=childs_head->next;
while(tmp!=NULL){
if(tmp->parent==node)
count++;
tmp=tmp->next;
}
return count;
}
struct Node *findByName(char *name,struct Node *head){
struct Node *tmp=head->next;
while(tmp!=NULL){
if(strcmp(tmp->name,name)==0)//比较当前节点,相等就返回这个节点,否则查看下一个节点
return tmp;
tmp=tmp->next;
}
printf("%cError:can't find %s!\n",BEEP,name);//名为name的节点未找到
return NULL;
}
void removeNode(char *name,struct Node *head){
struct Node *tmp1=head;
struct Node *tmp2=head->next;
while(tmp2!=NULL){//节点实际存在
if(strcmp(tmp2->name,name)==0){//比较
if(tmp2->process==NULL && tmp2->ready->next==NULL){
tmp1->next=tmp2->next;
free(tmp2);
}
else
printf("%cError:can't remove %s!\n",BEEP,name);
return;
}
tmp1=tmp2;
tmp2=tmp2->next;
}
printf("%cError:can't find %s!\n",BEEP,name);
}
//struct Node *addNode(char *name,struct Node *parent,struct Node *queue)
/*void remove Node(char *name,struct Node*queue){
}*/
void add_devices(){//添加设备
int i;
char name[10],parent[10];
while(1){
printf("1:add device\n");//设备
printf("2:add controller\n");//控制器
printf("3:add channel\n");//通道
printf("0:return\n");//返回主程序
scanf("%d",&i);//i变量读菜单
if(i!=0){
printf("name:");
scanf("%s",name);
}
if(i==1 || i==2){
printf("parent name:");
scanf("%s",parent);
}
switch(i){
case 1:
addNode(name,findByName(parent,COCTs),DCTs);//所添加的设备名在name里,通过parent名在COCT队列中找到父节点,之后以这个节点,这个名称为参数在DCT队列中添加一个新结点
break;
case 2:
addNode(name,findByName(parent,CHCTs),COCTs);
break;
case 3:
addNode(name,NULL,CHCTs);//通道没有父节点
break;
case 0:
return ;
}
}
}
void remove_devices(){
int i;
char name[10];
struct Node *tmp;
while(1){
printf("1:remove device\n");
printf("2:remove controller\n");
printf("3:remove channel\n");
printf("0:return\n");
scanf("%d",&i);
if(i!=0){
printf("name:");
scanf("%s",name);
}
switch(i){
case 1:
removeNode(name,DCTs);
break;
case 2:
tmp=findByName(name,COCTs);
if(tmp==NULL)
printf("%cError:can't find %s!\n",BEEP,name);
else if(get_child_count(tmp,DCTs)>0) //子节点个数
printf("%cError:can't remove %s!\n",BEEP,name);
else
removeNode(name,COCTs);
break;
case 3:
tmp=findByName(name,CHCTs);
if(tmp==NULL)
printf("%cError:can't find %s!\n",BEEP,name);
else if(get_child_count(tmp,COCTs)>0)
printf("%cError:can't remove %s!\n",BEEP,name);
else
removeNode(name,CHCTs);
break;
case 0:
return;
}
}}
void allocate_channel(struct Node *node,struct PCB *p){
if(p==NULL)
return;
if(node->process==NULL){
node->process=p;
block(blocked,p);
}
else
block(node->ready,p);
}
void allocate_controller(struct Node *node,struct PCB *p){
if(p==NULL)
return;
if(node->process==NULL){
node->process=p;
allocate_channel(node->parent,p);
}
else
block(node->ready,p);
}
void allocate_device(struct Node *node,struct PCB *p){
if(p==NULL)
return;
if(node->process==NULL){
node->process=p;
allocate_controller(node->parent,p);
}
else
block(node->ready,p);
}
void allocate(){
char name[10];
struct Node *node;
if(running==NULL)
return;
printf("device name:");
scanf("%s",name);
node=findByName(name,DCTs);
if(node==NULL){
printf("Can't find %s!\n",name);
return;
}
allocate_device(node,running);
}
void release_channel(struct Node *node,struct PCB *p){
if(node->process==p){
node->process=NULL;
allocate_channel(node,removeFirst(node->ready));
add(ready,remove_process(blocked,p));
if(running==NULL)
running=removeFirst(ready);
}
else{
add(ready,remove_process(node->ready,p));
if(running==NULL)
running=removeFirst(ready);
}
}
void release_controller(struct Node *node,struct PCB *p){
if(node->process==p){
node->process=NULL;
allocate_controller(node,removeFirst(node->ready));
release_channel(node->parent,p);
}
else{
add(ready,remove_process(node->ready,p));
if(running==NULL)
running=removeFirst(ready);
}
}
void release(){
char name[10];
struct Node *node;
struct PCB *p;
printf("device name:");
scanf("%s",name);
node=findByName(name,DCTs);
if(node==NULL || node->process==NULL)
return;
p=node->process;
node->process=NULL;
allocate_device(node,removeFirst(node->ready));
release_controller(node->parent,p);
}
void display_process_status(struct Node *node){//显示节点的占用进程以及等待进程信息
struct PCB *p=node->ready->next;
if(node->process!=NULL)
printf("<--%s",node->process->name);
while(p!=NULL){
printf("<--%s",p->name);
p=p->next;
}
printf("\n");
}
void display_status(){//显示设备状态
struct Node *chct=CHCTs->next,*coct,*dct;
while(chct!=NULL){
printf("%s",chct->name);
display_process_status(chct);
coct=COCTs->next;
while(coct!=NULL){
if(coct->parent==chct){
printf("\t%s",coct->name);
display_process_status(coct);
dct=DCTs->next;
while(dct!=NULL){
if(dct->parent==coct){
printf("\t\t%s",dct->name);
display_process_status(dct);
}
dct=dct->next;
}
}
coct=coct->next;
}
chct=chct->next;
}
}
3.5小结
四、 文件管理
4.1目的
通过利用磁盘文件,完成操作系统的文件管理功能,掌握包括目录结构的管理、外存空间的分配与释放以及空闲空间管理三部分 。
4.2完成的内容
1、通过初始化操作建立一个模拟外存空间的虚拟磁盘文件,在该文件中保存目录和文件内容。创建该文件时应创建初始的根目录内容、文件分配表。
2、文件目录项(可以采用FCB格式)应包括类型(目录 or文件)、创建日期、大小、第一个磁盘块块号。
3、显示命令提示符“$”,并根据输入命令完成相应的文件操作:
n MD(创建子目录):创建目录文件,并在父目录文件中增加目录项。
n CD(切换工作目录):根据当前目录切换到指定目录。
n RD(删除子目录):搜索所要删除的目录是否为空目录,若是则删除。
n MK(创建空文件):创建指定大小的文件(如输入命令 “mk test 2000”,表示创建大小为2000字节的test文件),并在父目录中添加文件名称;还应对FAT表进行适当修改。
n DEL(删除文件):如果所要删除的文件存在,则删除,同时修改父目录内容;还应对FAT表进行适当修改。
n DIR:列出当前目录的所有目录项。
n FORMAT:根据进一步的虚拟磁盘文件名和块个数信息创建出虚拟磁盘文件。
4.3主要数据结构
struct FCB{
char name[8];
int size;
int first_block;
char datetime[15];
char type;
};
char current_directory[256]="";//当前目录
char formated_file_name[32];//虚拟磁盘文件名
int current_directory_block_no=0;//当前目录块号
4.4算法设计及流程图
void md(char *name){
if(!is_valid_name(name))
return;
struct FCB *directory_content=(struct FCB *)malloc(BLOCK_SIZE);
read_block(current_directory_block_no,(char *)directory_content);
if(get_directory_item(directory_content,1,name)!=NULL || get_directory_item(directory_content,2,name)!=NULL){
alert("所要创建的目录名已被占用");
free(directory_content);
return;
}
int block_no=get_empty_block_number(0);
if(block_no<0){
alert("虚拟磁盘空间已耗尽");
free(directory_content);
return;
}
struct FCB *tmp=directory_content;
for(int i=0;i<BLOCK_SIZE/sizeof(struct FCB);i++,tmp++){
if(tmp->type==0){
char datetime[15];
get_datetime(datetime);
strcpy(tmp->datetime,datetime);
tmp->size=BLOCK_SIZE;
tmp->type=(char)2;
tmp->first_block=block_no;
strcpy(tmp->name,name);
write_block(current_directory_block_no,(char *)directory_content);
set_fat_item(block_no,LAST_BLOCK);
free(directory_content);
write_directory_content(block_no,current_directory_block_no,datetime);
return;
}
}
}
void dir(){
struct FCB *directory_content=(struct FCB *)malloc(BLOCK_SIZE);
read_block(current_directory_block_no,(char *)directory_content);
struct FCB *tmp=directory_content;
for(int i=0;i<BLOCK_SIZE/sizeof(struct FCB);i++,tmp++){
if(tmp->type==1 || tmp->type==2){
int type=tmp->type;
if(tmp->first_block>=0)
printf("%d\t",tmp->first_block);
else
printf("\t");
*(tmp->datetime+15)=0;
printf("%s\t",tmp->datetime);
if(tmp->type==2)
printf("<DIR>\t");
else
printf("%d\t",tmp->size);
printf("%s\n",tmp->name);
}
}
free(directory_content);
}
void cd(char *name){
if(name==NULL)
printf("%s\n",strlen(current_directory)==0?"\\":current_directory);
else if(strcmp(name,".")==0)
return;
else if(strcmp(name,"\\")==0){
current_directory_block_no=0;
strcpy(current_directory,"");
}
else{
struct FCB *directory_content=(struct FCB *)malloc(BLOCK_SIZE);
read_block(current_directory_block_no,(char *)directory_content);
struct FCB *tmp=get_directory_item(directory_content,2,name);
if(tmp==NULL)
alert("没有找到子目录项!");
else if(strcmp(tmp->name,"..")==0){
char *sub_name=strcat(current_directory,"\\");
current_directory_block_no=tmp->first_block;
substr(current_directory,current_directory,0,sub_name-current_directory);//\test\sub--->\tets
}
else{
current_directory_block_no=tmp->first_block;
strcat(current_directory,"\\");
strcat(current_directory,name);
}
free(directory_content);
}
}
void rd(char *name){//rd test
}
void mk(char *name,int size,char *content){
if(!is_valid_name(name))
return;
struct FCB *directory_content=(struct FCB *)malloc(BLOCK_SIZE);
read_block(current_directory_block_no,(char *)directory_content);
if(get_directory_item(directory_content,1,name)!=NULL || get_directory_item(directory_content,2,name)!=NULL){
alert("所要创建的目录名已被占用");
free(directory_content);
return;
}
int block_no=get_empty_block_number(0);
if(block_no<0){
alert("虚拟磁盘空间已耗尽");
free(directory_content);
return;
}
struct FCB *tmp=directory_content;
for(int i=0;i<BLOCK_SIZE/sizeof(struct FCB);i++,tmp++){
if(tmp->type==0){
char datetime[15];
get_datetime(datetime);
strcpy(tmp->name,name);
strcpy(tmp->datetime,datetime);
tmp->size=size;
tmp->type=(char)1;
tmp->first_block=block_no;
if(size>0){
tmp->first_block=block_no;
int block_count=(int)ceil(size/(double)BLOCK_SIZE);
int *block_numbers=(int *)malloc(sizeof(int)*block_count);
*block_numbers=block_no;
for(int j=1;j<block_count;j++){
*(block_numbers+j)=get_empty_block_number(*(block_numbers+j-1)+1);//ffff 0000 ffff 0000
if(*(block_numbers+j)==-1){
alert("没有足够空间!");
free(block_numbers);
free(directory_content);
return;
}
}
for(j=0;j<block_count;j++){
if((j+1)==block_count)
set_fat_item(*(block_numbers+j),LAST_BLOCK);
else
write_block(*(block_numbers+j),(char *)(content+BLOCK_SIZE*j));
}
free(block_numbers);
}
else
tmp->first_block=-1;
write_block(current_directory_block_no,(char *)directory_content);
free(directory_content);
return;
}
}
alert("父目录已满");
free(directory_content);
}
void put(char *src,char *dest){
FILE *fp=fopen(src,"rb");
if(fp==NULL)
alert("没有找到本地文件!");
else{
int size=get_file_size(src);
char *content=(char *)malloc((int)(ceil(size/(double)BLOCK_SIZE))*BLOCK_SIZE);
memset(content,0,(int)(ceil(size/(double)BLOCK_SIZE))*BLOCK_SIZE);
fread(content,size,1,fp);
mk(dest==NULL?src:dest,size,content);
free(content);
fclose(fp);
}
}
void my_open(char *name){
FILE *fp=my_fopen(name,"rb");
if(fp==NULL)
alert("无法打开文件,请先格式化!");
else{
strcpy(formated_file_name,name);
fclose(fp);
}
}
4.5小结
五、 进程调度算法的实现
5.1目的
通过在1、2、3阶段实验基础上完成先来先服务FCFS、短作业优先SJF以及时间片轮转算法调度进程的模拟过程,掌握进程调度算法。
5.2完成的内容
1、程序开始运行时选择调度算法,创建进程时输入进程所需服务时间以及到达时间。
2、根据当前所设定调度算法,连续调度所有进程,并计算每个进程的周转时间和带权周转时间、所有进程的平均周转时间和平均带权周转时间。
3、调度时应适当输出调度过程中各进程状态队列的变化情况以及进程的已执行时间、还需服务时间(针对时间片轮转算法)。
5.3主要数据结构
struct PCB{
char name[10];
int size;
int arrival_time,burst_time;//到达时间,服务时间
int finished_time;//终止时间
int runned_time;//在时间片中使用
int *pagetable;
struct Access_Queue *fifo,*lru;
struct PCB *next;
};
5.4算法设计及流程图
void FCFS(){//先来先服务
int i,systime=0;
struct PCB *p;
sort_ready();
p=removeFirst(ready);
while(p!=NULL){
if(p->arrival_time>systime)
systime=p->arrival_time;
for(i=0;i<p->burst_time;i++)
printf("%s",p->name);
printf(" ");
p->finished_time=systime+p->burst_time;
systime=p->finished_time;
add(finished,p);
p=removeFirst(ready);
}
printf("\n");
display_scheduled_message();
}
void RR(){//时间片
int systime=0;
struct PCB *p;
sort_ready();
p=removeFirst(ready);
while(p!=NULL){
if(p->arrival_time>systime)
systime=p->arrival_time;
printf("%s ",p->name);
p->runned_time++;//当前取出的进程被调度了一次
systime++;//已执行一个时间片
if(p->runned_time==p->burst_time){
p->finished_time=systime;
add(finished,p);
}
else
add(ready,p);
p=removeFirst(ready);
}
printf("\n");
display_scheduled_message();
}
void SJF(){//短作业优先
int i,systime=0;
struct PCB *p;
sort_ready();
p=get_shortest(&systime);
while(p!=NULL){
for(i=0;i<p->burst_time;i++)
printf("%s",p->name);
printf(" ");
p->finished_time=systime+p->burst_time;
systime=p->finished_time;
add(finished,p);
p=get_shortest(&systime);
}
printf("\n");
display_scheduled_message();
}
5.5小结
六、 课程总结
回顾紧张但又充实的学习和编码过程,我从青巴图老师身上学到了很多东西。他认真负责的工作态度,严谨的治学精神和深厚的理论水平都使我收益匪浅。他无论在理论上还是在实践中,都给与我很大的帮助,使我得到很大的提高,这对于我以后的工作和学习都有一种巨大的帮助,在此感谢他耐心的辅导。