操作系统实习

2019-03-28 16:46:58 qq_40172319 阅读数 4741

操作系统实验

hello,我是橘子
最近突然发现我以前写的操作系统实验,然后分享给大家吧,就是自己写的代码也不是很好,希望大家见谅哈
实验目的
一、进程控制
●基本要求:利用简单的结构和控制方法模拟进程结构、进程状态和进程控制。
●参考学时:9学时
●实验提示:
1、用PCB表示整个进程实体,利用随机数方法或键盘控制方法模拟进程执行中产生的事件,或者利用基于图形界面的鼠标或者键盘操作控制进程管理内容。
2、定义PCB:包括理论PCB中的基本内容,如内部ID、外部ID、队列指针。由于很难实现真正的进程创建功能,在实验中只需建立PCB节点,并用它代表一个完整的进程。每创建一个进程时,可动态分配PCB节点,对相应内容赋值,并链接到适当的队列上。
可参考如下数据结构(动态形式):
struct PCB{
char name[10];
struct PCB*next;
};
struct PCB *ready,*blocked,running;
创建进程时:
struct PCB p=(struct PCB )malloc(sizeof(struct PCB));
并将此进程添加到就绪队列末尾:
add(ready,p);
其中,ready为就绪队列头节点,并在开始处分配了空间;add函数是链表中添加节点函数,代码可以为:
void add(struct PCB head,struct PCBprocess){
struct PCB
tmp=head;
while(tmp->next!=NULL)
tmp=tmp->next;
tmp->next=process;
process->next=NULL;
}
3、定义进程状态转换方式:真实的进程状态转换是由进程内部操作或操作系统的控制引起的。由于模拟程序中无法实现这些功能,我们可以采用随机数方法或键盘控制方法模拟,并实现对应的控制程序。随机方法指产生1-5的随机数,分别代表创建进程(1)、时间片到(2)、进程阻塞(3)、唤醒进程(4)、结束进程(5)等事件;键盘模拟方法指定义5个选项菜单代表以上五种事件。
4、根据随机数或键盘操作处理就绪队列、阻塞队列和当前执行进程的状态。每次事件处理后应显示出当前系统中的执行进程是哪一个,就绪队列和阻塞队列分别包含哪些进程。
5、
(带
部分为试验班和特长班需要完成的内容,普通班选作)完成可变分区的分配与回收,创建进程的同时申请一块连续的内存空间,结束进程同时回收分配的内存空间。分配采用最佳适应算法,碎片大小为2Kb,最后回收所有进程的空间。可以查看进程所占的空间和系统空闲空间。
●评分标准:满分15分
要求必须完成以下几个方面的内容:
能够模拟进程的创建与撤销过程;5分
可对进程的状态进行全面的控制;5分
按先进先出方式管理就绪和阻塞队列,能够按队列形式输出进程状态。5分

#include<iostream>
#include<stdlib.h>
using namespace std;
typedef struct PCB
{
	char data;
	struct PCB *next;
}PCB,*PCBlist;
void show(PCBlist rear)//就绪状态和堵塞状态展示
{
	PCBlist P=rear;
	while(P->next)
	{
		cout<<P->next->data<<" ";
		P=P->next;
	}
}
void runshow(char running)//执行状态展示
{
	if(running=='\0')
		cout<<"没有正在执行的进程"<<endl;
	else
		cout<<running<<endl;
}
void add(PCBlist rear,char ch)//尾插法插入
{
	PCBlist P=rear;//队列头
	PCBlist s=new PCB;//新建节点
	s->data=ch;
	s->next=NULL;
	if(P->next==NULL)//进程链为空添加节点
	{
		P->next=s;
	}
	else
	{
		while(P->next!=NULL)//进程链不为空添加节点
		{
			P=P->next;
		}
		P->next=s;
	}
}
void menu()//进程选择菜单
{
	//cout<<"请选择执行的操作:"<<endl;
	cout<<"1.创建进程"<<endl;
	cout<<"2.时间片到"<<endl;
	cout<<"3.进程阻塞"<<endl;
	cout<<"4.唤醒进程"<<endl;
	cout<<"5.结束进程"<<endl;
}
void showall(PCBlist ready,PCBlist block,char running)//进程状态显示
{
	cout<<"----------------------------------"<<endl;
	cout<<"就绪状态为:";
	show(ready);
	cout<<endl;
	cout<<"执行状态为:";
	runshow(running);
	cout<<"阻塞状态为:";
	show(block);
	cout<<endl;
	cout<<"----------------------------------"<<endl;
}
void main()
{
	PCBlist S;//释放空间
	int n;
	char running ='\0';
	char ch,temp;// ch为输入进程的名字
	PCBlist ready=new PCB;
	PCBlist block=new PCB;
	ready->next=NULL;
	block->next=NULL;
	PCBlist rear1=block;
//	PCBlist pc=ready;

//	PCBlist pd=block;
	showall(ready,block,running);
log:{
	menu();
	cout<<"请选择执行的操作:"<<endl;
	}
	cin>>n;
	while(true)
	{	
		system("cls");
		menu();
		switch(n)
		{
		case 1://创建进程
			{
				cout<<"请输入进程名";
				cin>>ch;
				add(ready,ch);
				//显示:
				if(running=='\0')//如果还没有正在执行的进程
				{
					if(ready->next!=NULL)//就绪队列不为空
					{
						temp=ready->next->data;//获取队头进程(就绪队列第一个元素)
						S=ready->next;
						ready->next=ready->next->next;//出队头
						delete S;
						running=temp;//将就绪状态变为执行状态
					}
					showall(ready,block,running);
				}
				else
				{
					showall(ready,block,running);
				}
				break;
			}
		case 2://时间片到
			{
				if(running!='\0')
				{
					add(ready,running);//将正在执行的进程添加到就绪状态中
					
					if(ready->next!=NULL)
					{
						temp=ready->next->data;
						S=ready->next;
						ready->next=ready->next->next;
						delete S;
						running=temp;
					}//将此时就绪队列的队头变为执行状态
					else
					{
						running='\0';
					}
					showall(ready,block,running);
				}
				else
				{
					cout<<"没有正在进行的进程"<<endl;
				}
				break;
			}
		case 3://进程阻塞
			{
				if(running=='\0')
					cout<<"没有正在进行的进程"<<endl;
				else
				{
					add(block,running);//将阻塞的进程添加到阻塞队列
				
					if(ready->next!=NULL)
					{
						temp=ready->next->data;
						S=ready->next;
						ready->next=ready->next->next;
						delete S;
						running=temp;
					}//将此时就绪队列的队头变为执行状态
					else
					{
						running='\0';
					}
					showall(ready,block,running);
				}
				break;
			}
		case 4://唤醒进程
			{
				if(block->next==NULL)
					cout<<"没有正在阻塞的进程"<<endl;
				else
				{
					cout<<"请输入要唤醒的进程"<<endl;
					cin>>ch;
					
					while(rear1->next->data!=ch)//找到要唤醒的进程
					{
						if(rear1->next->next!=NULL)
						{
							rear1=rear1->next;
						}
						else
						{
							cout<<"未查询到该进程"<<endl;
                            showall(ready,block,running);
							goto log;
						}

					}
					add(ready,rear1->next->data);//将要唤醒的进程添加到就绪队列中
					if(rear1->next->next!=NULL)//判断此节点后面是否还存在节点
					{
					    S=rear1->next ;
					    rear1->next=rear1->next->next;//删除刚才节点
						delete S;
					}
					else
					{
                        rear1->next=NULL;
					}
					if(running=='\0')//如果没有正在执行的进程
				    {
						if(ready->next!=NULL)
						{
							temp=ready->next->data;
							running=temp;
							S=ready->next;
							ready->next=ready->next->next;
							delete S;
						}
					   showall(ready,block,running);
					}
					else
					{
						 showall(ready,block,running);
					}
					
				}
				
				break;
			}
		case 5://结束进程
			{
				//ws/cout<<"请输入要结束的进程号";
				//cin>>q;
				//while(pc->next!=NULL)//在就绪队列中找要结束的进程
				//{
				//	if(pc->next->data==q)
				//	{
				//		pc->next=pc->next->next;
				//		showall(ready,block,running);
				//		break;
				//	}
				//	else
				//		pc=pc->next;
				//}
				//while(pd->next!=NULL)//在阻塞队列中找要结束的进程
				//{
				//	if(pd->next->data==q)
				//	{
				//		pd->next=pd->next->next;
				//		showall(ready,block,running);
				//		break;
				//	}
				//	else
				//		pd=pd->next;
				//}
				//if(running==q)//如果要结束的进程正在执行
				//{
					running='\0';
					if(ready->next!=NULL)
					{
						
						temp=ready->next->data;
						S=ready->next;
						ready->next=ready->next->next;
						running=temp;
						delete S;
					}
					showall(ready,block,running);
				/*}*/
			}
		}
		cout<<"请选择执行的操作:"<<endl;
		cin>>n;
	}
}


2019-03-31 07:16:36 qq_41063141 阅读数 705

一:以硬盘方式启动bochs

1.准备工作:安装计算机硬件模拟器:

   1.1 安装bochs编译环境(即bochs运行所需要的环境):

安装C/C++的编译环境【gcc以及g++】,

sudo apt-get install build-essential

安装图形化的bochs【模拟显卡等硬件】

sudo apt-get install xorg-dev

安装依赖库

sudo apt-get install libgtk2.0-dev

 1.2安装bochs和bochs-x软件

apt install bochs

sudo apt-get install bochs-x

sudo apt-get install bochs-sdl

  终端输入bochs,弹出bochs的启动配置文件。按6便可直接启动bochs,启动成功会弹出bochs x86-64 emulator 的窗口

bochs的官网:http://bochs.sourceforge.net/

 

   1.3 创建映像文件:

(我是在根目录home/lmj下创建的映像文件dimos.img)

   

dd if=你的镜像路径(即编译得到的boot.bin的路径) of=dimos.img          

1.4编写系统启动的驱动程序(一般都是用汇编语言来写的,这里也不例外)

 

找个目录新建:  touch boot.asm        编辑boot.asm

org		07c00h		;告诉编译器程序加载到7c00处
	mov		ax, cs
	mov		ds, ax
	mov		es, ax
	call	DispStr			;调用显示字符串例程
	jmp		$		;无限循环
DispStr:
	mov		ax, BootMessage
	mov		bp, ax		;ES:BP = 串地址
	mov		cx, 16		;CX = 串长度
	mov		ax, 01301h	;AH = 13h, AL = 01h
	mov		bx, 000ch	 ;页号为0(BH= 0)黑底红字(BL = 0Ch,高亮)
	mov		dl, 0
	int		10h		;10h号中断
	ret
BootMessage:		db		"Hello, OS world!"
times	510-($-$$)	db		0	;填充剩下的空间,使生成的二进制代码恰好为512字节
dw		0xaa55				;结束标志

代码解释:

这是一个简单的引导扇区程序。

可能有些同学会有疑问——为什么第一句要用org指令将我们的代码定位到7C00H处。这是因为,当计算机电源被打开时,它会先进行加电自检(POST),然后寻找启动盘,如果是选择从软盘启动(我们的设置就是从软盘启动),计算机就会检查软盘的0面0磁道1扇区,如果它以0xAA55结束(正是我们上面代码的结束标志),则BIOS认为它是一个引导扇区。一旦BIOS发现了引导扇区,就会将这512字节的内容装载到内存地址0000:7C00处,然后跳转到0000:7C00处将控制权彻底交给这段引导代码(这就是原因)。到此,计算机不再由BIOS中固有的程序来控制,而变成有操作系统的一部分来控制。
--------------------- 
作者:尚书左仆射 
来源:CSDN 
原文:https://blog.csdn.net/wzxq123/article/details/53009730 
版权声明:本文为博主原创文章,转载请附上博文链接!

 

这是汇编语言:需要编译成机器语言(即可执行程序),这里我们使用nasm编译工具

我们把这段代码用NASM编译一下:

?

1

$nasm boot.asm -o boot.bin

如果没有安装NASM,可以用如下命令进行安装:

?

1

$sudo apt-get install nasm

编译完成后,会在当前目录生成一个512字节的boot.bin文件。

 

1.5将驱动程序放入刚才创建的硬盘里:

     使用dd命令将它写进刚刚创建的软盘映像a.img的第一个扇区:

1

$dd if=boot.bin of=a.img bs=512 count=1 conv=notrunc

 

我的代码:dd if=boot.bin of=dimos.img

启动:

将boot.bin  ,dimos.img移动到bochs的安装目录:

bochs -f /usr/share/bochs/bochsrc.bxrc

 

其中bochsrc.bxrc的配置文件如下:

###############################################################
# Configuration file for Bochs
###############################################################

# how much memory the emulated machine will have
megs: 32

# 对应真实机器的BIOS和VGA BIOS
romimage: file=/usr/share/bochs/BIOS-bochs-latest
vgaromimage: file=/usr/share/bochs/VGABIOS-lgpl-latest

# 设置bochs使用的磁盘,软盘使用关键字floppya,硬盘使用disk
# 若有多个软盘,可写floppya,floppyb
#floppya: 1_44=a.img, status=inserted

# choose the boot disk.
# 默认是软盘,注释掉,改为disk
#boot: floppy
boot: disk

# where do we send log messages?
log: /tmp/bochsout.txt
# disable the mouse
mouse: enabled=0

# enable key mapping, using US layout as default.
#keyboard_mapping: enabled=1, map=/usr/share/bochs/keymaps/x11-pc-us.map
keyboard:keymap=/usr/share/bochs/keymaps/sdl-pc-us.map
#keyboard_mapping: enabled=1, map=/usr/share/bochs/keymaps/sdl-pc-us.map
display_library: sdl
ata0: enabled=1, ioaddr1=0x1f0, ioaddr2=0x3f0, irq=14

#这一句是根据bximage生成的,后面会解释。
ata0-master: type=disk, path=/usr/share/bochs/dimos.img, mode=flat, cylinders=121, heads=16, spt=63
#ata0-master: type=disk, path="/usr/share/bochs/dimos.img", mode=flat, cylinders=121, heads=16, spt=63

下面谈谈以上过程中遇到的问题:

1.Message: ata0-0: specified geometry doesn't fit on disk image

2.00000000000e[     ] /usr/share/bochs/bochsrc.bxrc:29: 'keyboard_mapping' will be replaced by new 'keyboard' option.

解决:

请参考文章:=================如何配置并启动bochs

https://blog.csdn.net/ByChen623/article/details/53619084

 

bochs启动原理:(如何突破512字节):

https://blog.csdn.net/cielozhang/article/details/6171783

 

备注:如果硬盘方式启动失败,可尝试第二节的软盘方式启动。

 

二:以软盘方式启动bochs:

              2.1  在bochs的安装目录下:创建   a.asm   : 编辑代码:

org             07c00h          ;告诉编译器程序加载到7c00处
        mov             ax, cs
        mov             ds, ax
        mov             es, ax
        call    DispStr                 ;调用显示字符串例程
        jmp             $               ;无限循环
DispStr:
        mov             ax, BootMessage
        mov             bp, ax          ;ES:BP = 串地址
        mov             cx, 16          ;CX = 串长度
        mov             ax, 01301h      ;AH = 13h, AL = 01h
        mov             bx, 000ch        ;页号为0(BH= 0)黑底红字(BL = 0Ch,高
亮)
        mov             dl, 0
        int             10h             ;10h号中断
        ret
BootMessage:            db              "Hello, OS world!"
times   510-($-$$)      db              0       ;填充剩下的空间,使生成的二进制>代码恰好为512字节
dw              0xaa55                          ;结束标志

            2.2 编译成二进制文件:  sudo nasm a.asm -o a.bin

     2.3 创建操作系统的软盘:bximage                  (将hd改为fd,软盘名称设为a.img,其他的默认即可)

     2.4 创建bochs的启动配置文件:  vi .bochsrc                            文件内容如下:    

megs: 32
romimage: file=$BXSHARE/BIOS-bochs-latest
vgaromimage: file=$BXSHARE/VGABIOS-lgpl-latest
#floppya: 1_44=a.img, status=inserted  1_44   image="/home/lmj/文档/dimos/a.img"
floppya: 1_44="a.img", status=inserted
boot: floppy
log: bochsout.txt
mouse: enabled=0
keyboard: keymap=$BXSHARE/keymaps/x11-pc-us.map

    2.5 将驱动程序写入软盘中:sudo dd if=a.bin of=a.img

   2.6.下面是我的完整运行过程图:

 

 

备注:输入完   bochs -f .bochsrc   后并不会马上弹出hello world,因为我们是用调试模式打开的,所以需要接着输入c,让程序继续往下运行

三:常见错误及解决方案:

     3.1  参考这篇博文:总结的很全面。

        https://blog.csdn.net/zhaodedong/article/details/51082128

    3.2  我出现的问题是:启动后出现无启动设备的错误。

Boot failed: not a bootable device. 
FATAL:No bootable device.

     我把编译文件a.asm的代码删除之后,在网上又找了一份bochs启动的代码。复制编译,重新dd进软盘就ok了

  3.3最后再说一下:bochs的配置文件.bochsrc要注意的问题

megs: 32                            #虚拟一个32的计算机
romimage: file=$BXSHARE/BIOS-bochs-latest             #要加上file=  (该文件在bochs的安装目录下,这里是文件的相对路径,$BXSHARE他会自动找到你的安装目录,不需要你去配置)
vgaromimage: file=$BXSHARE/VGABIOS-lgpl-latest          #同上
#floppya: 1_44=a.img, status=inserted  1_44   image="/home/lmj/文档/dimos/a.img"
floppya: 1_44="a.img", status=inserted             #这是配置软盘的映像文件的位置,这是相对路径,a.img的位置相对与.bochsrc文件而言,因为我的a.img与.bochsrc位于统一目录,所以这里配成a.img,我的bochs版本是2.6,所以要用1_44="a.img",不能用image=“”
boot: floppy          #操作系统的启动方式:这里是软盘驱动的方式启动
log: bochsout.txt
mouse: enabled=0
keyboard: keymap=$BXSHARE/keymaps/x11-pc-us.map       #固定配置,不用改,跟我的配置相同就可以了

今天就写到这里。

 

2008-01-13 11:20:00 Melody_1208 阅读数 2513

众所周知,CPU是整个计算机系统中运算速度最快的部分,而外部设备是最慢的部分,它们之间存在着很大的差别。然而,CPU却时时刻刻可能要求访问外设。如果CPU的每次操作都必须等待外设完成,那么CPU宝贵的运行时间就会大大浪费。随着现代计算机技术的发展,大多数现代操作系统都对这个问题进行了处理。下面就介绍Windows 2000中解决这个不匹配问题的方法:高速缓存和异步传输。

1.文件高速缓存

文件高速缓存是CPU访问外设的一个“中间设备”。说是设备,其实它不是真正的物理设备,而是一种核心级内存映像机制。由于它被设置在内存中,因此速度非常快,可以部分解决CPU与硬盘速度差异的问题。文件系统的驱动程序通过调用“高速缓存管理程序” 来使用文件高速缓存,然后高速缓存管理程序执行高速缓存的处理工作。

文件高速缓存的原理是:假设一个进程读了文件的第一个字节,它常常会按照顺序读第二个第三个字节,一直到读出所有的字节。利用这个原理可以进行“预取”,也就是说,在进程没请求读磁盘之前就先把文件读出来并放到高速缓存中。这样,当进程请求访问磁盘时,高速缓存可以快速地把已经取到内存中的文件内容直接送给进程使用,从而大大加速了访问磁盘的速度。另外,由于一个文件可能会被多次读入,因此可以在第一次读入后,将文件数据保存在高速缓存中。这样,下次再读时,就不必从硬盘而可以从缓存中读取。利用LRU(Least Recently Used)的原则,可以将不常使用的文件从缓存中删除以节省高速缓存空间。

2.异步传输

与文件高速缓存不同,文件的异步传输是一种改变指令执行顺序的机制。在以往的操作系统中,指令都是顺序执行的,下一条指令必须在上一条指令执行完毕后才能执行。因此,如果CPU遇到一条放盘指令,那么它就必须等待缓慢的磁盘访问结束以后才能进行后续工作。如果它后面遇到的指令并不依赖于访盘操作时,这个等待就很没有必要。Windows2000中使用了一种异步文件传输机制来解决这个问题。它通过设置打开文件时的一个标志位来使进程不等待读些文件操作而继续执行。当后续指令必须用到磁盘访问的结果数据时,它在通过一条Wait指令进行等待。这样,在访盘指令和等待指令之间的指令就可以与磁盘访问同时进行了,从而大大加快了系统的整体速度。

实习要求:

设计一个函数int filter(char source, char *sink, int f),其中:

source:源文件,即从哪个文件读。

sink:目标文件,即写到哪个文件。

f:一个对文件的操作(可以指定任何操作)

分别用3种方法实现一个对文件的操作:

1)无缓冲方式:表示用的标志位是FILE_FLAG_NO_BUFFERING。

2)缓冲方式:表示用的标志位是FILE_FLAG_SEQUENTIAL_SCAN。

3)异步方式:表示用的标志位是FILE_FLAG_OVERLAPPED。

源代码如下:

#include <iostream.h>
#include <windows.h>

// three partterns
void filter_nobuffer(char *source, char *sink, void (*func)(char *addr));
void filter_sequen(char *source, char *sink, void (*func)(char *addr));
void filter_overlp(char *source, char *sink, void (*func)(char *addr));

// five function operations
void f1(char *addr);
void f2(char *addr);
void f3(char *addr);
void f4(char *addr);
void f5(char *addr);

#define BUFFER_SIZE 1024
char *buffer;

void main()
{
 // allocate the buffer
 buffer = new char[BUFFER_SIZE];

 DWORD tick;

 DWORD nobuffer_average_time = 0;
 DWORD sequen_average_time = 0;
 DWORD overlp_average_time = 0;

 cout<<"无文件高速缓存模式正在运行..."<<endl;

 DWORD nobuffer_start_time = GetTickCount();

 tick = nobuffer_start_time;
 filter_nobuffer("source.txt", "nobuffer_1.txt", f1);
 cout<<"nobuffer 0-1: "<<GetTickCount() - tick<<" ms."<<endl;

 tick = GetTickCount();
 filter_nobuffer("nobuffer_1.txt", "nobuffer_2.txt", f2);
 cout<<"nobuffer 1-2: "<<GetTickCount() - tick<<" ms."<<endl;

 tick = GetTickCount();
 filter_nobuffer("nobuffer_2.txt", "nobuffer_3.txt", f3);
 cout<<"nobuffer 2-3: "<<GetTickCount() - tick<<" ms."<<endl;

 tick = GetTickCount();
 filter_nobuffer("nobuffer_3.txt", "nobuffer_4.txt", f4);
 cout<<"nobuffer 3-4: "<<GetTickCount() - tick<<" ms."<<endl;

 tick = GetTickCount();
 filter_nobuffer("nobuffer_4.txt", "nobuffer_5.txt", f5);
 cout<<"nobuffer 4-5: "<<GetTickCount() - tick<<" ms."<<endl;

 tick = GetTickCount();
 filter_nobuffer("nobuffer_5.txt", "nobuffer_6.txt", f1);
 cout<<"nobuffer 5-6: "<<GetTickCount() - tick<<" ms."<<endl;

 tick = GetTickCount();
 filter_nobuffer("nobuffer_6.txt", "nobuffer_7.txt", f2);
 cout<<"nobuffer 6-7: "<<GetTickCount() - tick<<" ms."<<endl;

 tick = GetTickCount();
 filter_nobuffer("nobuffer_7.txt", "nobuffer_8.txt", f3);
 cout<<"nobuffer 7-8: "<<GetTickCount() - tick<<" ms."<<endl;

 tick = GetTickCount();
 filter_nobuffer("nobuffer_8.txt", "nobuffer_9.txt", f4);
 cout<<"nobuffer 8-9: "<<GetTickCount() - tick<<" ms."<<endl;

 tick = GetTickCount();
 filter_nobuffer("nobuffer_9.txt", "nobuffer_10.txt", f5);
 DWORD nobuffer_end_time = GetTickCount();
 cout<<"nobuffer 9-10: "<<nobuffer_end_time - tick<<" ms."<<endl;

 cout<<"使用文件高速缓存模式正在运行..."<<endl;

 DWORD sequen_start_time = GetTickCount();
 
 tick = sequen_start_time;
 filter_sequen("source.txt", "sequen_1.txt", f1);
 cout<<"sequen 0-1: "<<GetTickCount() - tick<<" ms."<<endl;

 tick = GetTickCount();
 filter_sequen("sequen_1.txt", "sequen_2.txt", f2);
 cout<<"sequen 1-2: "<<GetTickCount() - tick<<" ms."<<endl;

 tick = GetTickCount();
 filter_sequen("sequen_2.txt", "sequen_3.txt", f3);
 cout<<"sequen 2-3: "<<GetTickCount() - tick<<" ms."<<endl;

 tick = GetTickCount();
 filter_sequen("sequen_3.txt", "sequen_4.txt", f4);
 cout<<"sequen 3-4: "<<GetTickCount() - tick<<" ms."<<endl;

 tick = GetTickCount();
 filter_sequen("sequen_4.txt", "sequen_5.txt", f5);
 cout<<"sequen 4-5: "<<GetTickCount() - tick<<" ms."<<endl;

 tick = GetTickCount();
 filter_sequen("sequen_5.txt", "sequen_6.txt", f1);
 cout<<"sequen 5-6: "<<GetTickCount() - tick<<" ms."<<endl;

 tick = GetTickCount();
 filter_sequen("sequen_6.txt", "sequen_7.txt", f2);
 cout<<"sequen 6-7: "<<GetTickCount() - tick<<" ms."<<endl;

 tick = GetTickCount();
 filter_sequen("sequen_7.txt", "sequen_8.txt", f3);
 cout<<"sequen 7-8: "<<GetTickCount() - tick<<" ms."<<endl;

 tick = GetTickCount();
 filter_sequen("sequen_8.txt", "sequen_9.txt", f4);
 cout<<"sequen 8-9: "<<GetTickCount() - tick<<" ms."<<endl;

 tick = GetTickCount();
 filter_sequen("sequen_9.txt", "sequen_10.txt", f5);
 DWORD sequen_end_time = GetTickCount();
 cout<<"sequen 9-10: "<<sequen_end_time - tick<<" ms."<<endl;

 cout<<"异步传输模式正在运行..."<<endl;

 DWORD overlp_start_time = GetTickCount();

 tick = overlp_start_time;
 filter_overlp("source.txt", "overlp_1.txt", f1);
 cout<<"overlp 0-1: "<<GetTickCount() - tick<<" ms."<<endl;

 tick = GetTickCount();
 filter_overlp("overlp_1.txt", "overlp_2.txt", f2);
 cout<<"overlp 1-2: "<<GetTickCount() - tick<<" ms."<<endl;

 tick = GetTickCount();
 filter_overlp("overlp_2.txt", "overlp_3.txt", f3);
 cout<<"overlp 2-3: "<<GetTickCount() - tick<<" ms."<<endl;

 tick = GetTickCount();
 filter_overlp("overlp_3.txt", "overlp_4.txt", f4);
 cout<<"overlp 3-4: "<<GetTickCount() - tick<<" ms."<<endl;

 tick = GetTickCount();
 filter_overlp("overlp_4.txt", "overlp_5.txt", f5);
 cout<<"overlp 4-5: "<<GetTickCount() - tick<<" ms."<<endl;

 tick = GetTickCount();
 filter_overlp("overlp_5.txt", "overlp_6.txt", f1);
 cout<<"overlp 5-6: "<<GetTickCount() - tick<<" ms."<<endl;

 tick = GetTickCount();
 filter_overlp("overlp_6.txt", "overlp_7.txt", f2);
 cout<<"overlp 6-7: "<<GetTickCount() - tick<<" ms."<<endl;

 tick = GetTickCount();
 filter_overlp("overlp_7.txt", "overlp_8.txt", f3);
 cout<<"overlp 7-8: "<<GetTickCount() - tick<<" ms."<<endl;

 tick = GetTickCount();
 filter_overlp("overlp_8.txt", "overlp_9.txt", f4);
 cout<<"overlp 8-9: "<<GetTickCount() - tick<<" ms."<<endl;

 tick = GetTickCount();
 filter_overlp("overlp_9.txt", "overlp_10.txt", f5);
 DWORD overlp_end_time = GetTickCount();
 cout<<"overlp 9-10: "<<overlp_end_time - tick<<" ms."<<endl;

 // 输出3种模式下的平均时间做对比
 cout<<"3种模式的平均用时如下:"<<endl;
 cout<<"1.无文件高速缓存模式平均用时:"
  <<(nobuffer_end_time - nobuffer_start_time)/10<<" ms."<<endl;
 cout<<"2.使用高速文件缓存模式平均用时:"
  <<(sequen_end_time - sequen_start_time)/10<<" ms."<<endl;
 cout<<"3.异步传输模式平均用时:"
  <<(overlp_end_time - overlp_start_time)/10<<" ms."<<endl;
 return;
}

// --------------------------------------------------------------
// 对文件内容进行的5种操作
// f1 +1
// f2 -1
// f3 *1
// f4 >>
// f5 <<
void f1(char *addr){ *addr = (unsigned char)*addr + 1;}
void f2(char *addr){ *addr = (unsigned char)*addr - 1;}
void f3(char *addr){ *addr = (unsigned char)*addr * 1;}
void f4(char *addr){ *addr = (unsigned char)*addr >> 1;}
void f5(char *addr){ *addr = (unsigned char)*addr << 1;}

// --------------------------------------------------------------

// 没有文件高速缓存的filter函数
void filter_nobuffer(char *source, char *sink, void (*func) (char *addr))
{
 HANDLE handle_src, handle_dst;  // handles of source file and destination file
 BOOL cycle;
 DWORD NumberOfBytesRead, NumberOfBytesWrite, index;

 // open the source file
 handle_src = CreateFile(source, GENERIC_READ, NULL, NULL,
  OPEN_EXISTING, FILE_FLAG_NO_BUFFERING, NULL);

 handle_dst = CreateFile(sink, GENERIC_WRITE, NULL, NULL,
  CREATE_ALWAYS, NULL, NULL);

 if(handle_src == INVALID_HANDLE_VALUE || handle_dst == INVALID_HANDLE_VALUE)
 {
  cout<<"CreateFile Invocation Error!"<<endl;
  exit(1);
 }

 cycle = TRUE;
 // use cycle to know when we finished reading the file
 while(cycle)
 {
  // read data and send them into buffer from the source file
  if(ReadFile(handle_src, buffer, BUFFER_SIZE, &NumberOfBytesRead, NULL) == FALSE)
  {
   cout<<"ReadFile Error!"<<endl;
   exit(1);
  }

  if(NumberOfBytesRead < BUFFER_SIZE)
   cycle = FALSE;

  // do the operation to the file
  for(index = 0; index < NumberOfBytesRead; index ++)
   func(&buffer[index]);

  // write the content of the buffer to the destination file
  if(WriteFile(handle_dst, buffer, NumberOfBytesRead, &NumberOfBytesWrite, NULL) == FALSE)
  {
   cout<<"WriteFile Error!"<<endl;
   exit(1);
  }
 }

 // close the file handle
 CloseHandle(handle_src);
 CloseHandle(handle_dst);
}

void filter_sequen(char *source, char *sink, void (*func) (char *addr))
{
 HANDLE handle_src, handle_dst;  // handles of source file and destination file
 BOOL cycle;
 DWORD NumberOfBytesRead, NumberOfBytesWrite, index;

 // open the source file
 handle_src = CreateFile(source, GENERIC_READ, NULL, NULL,
  OPEN_EXISTING, FILE_FLAG_SEQUENTIAL_SCAN, NULL);

 handle_dst = CreateFile(sink, GENERIC_WRITE, NULL, NULL,
  CREATE_ALWAYS, FILE_FLAG_SEQUENTIAL_SCAN, NULL);

 if(handle_src == INVALID_HANDLE_VALUE || handle_dst == INVALID_HANDLE_VALUE)
 {
  cout<<"CreateFile Invocation Error!"<<endl;
  exit(1);
 }

 cycle = TRUE;
 // use cycle to know when we finished reading the file
 while(cycle)
 {
  // read data and send them into buffer from the source file
  if(ReadFile(handle_src, buffer, BUFFER_SIZE, &NumberOfBytesRead, NULL) == FALSE)
  {
   cout<<"ReadFile Error!"<<endl;
   exit(1);
  }

  if(NumberOfBytesRead < BUFFER_SIZE)
   cycle = FALSE;

  // do the operation to the file
  for(index = 0; index < NumberOfBytesRead; index ++)
   func(&buffer[index]);

  // write the content of the buffer to the destination file
  if(WriteFile(handle_dst, buffer, NumberOfBytesRead, &NumberOfBytesWrite, NULL) == FALSE)
  {
   cout<<"WriteFile Error!"<<endl;
   exit(1);
  }
 }

 // close the file handle
 CloseHandle(handle_src);
 CloseHandle(handle_dst);
}

void filter_overlp(char *source, char *sink, void (*func) (char *addr))
{
 HANDLE handle_src, handle_dst;  // handles of source file and destination file
 BOOL cycle;
 DWORD NumberOfBytesRead, NumberOfBytesWrite, index, dwError;
 OVERLAPPED overlapped;    // overlapped 结构

 // open the source file
 handle_src = CreateFile(source, GENERIC_READ, NULL, NULL,
  OPEN_EXISTING, FILE_FLAG_NO_BUFFERING | FILE_FLAG_OVERLAPPED, NULL);

 handle_dst = CreateFile(sink, GENERIC_WRITE, NULL, NULL,
  CREATE_ALWAYS, NULL, NULL);

 if(handle_src == INVALID_HANDLE_VALUE || handle_dst == INVALID_HANDLE_VALUE)
 {
  cout<<"CreateFile Invocation Error!"<<endl;
  exit(1);
 }

 // initialize the overlapped struct
 overlapped.hEvent = NULL;
 overlapped.Offset = -BUFFER_SIZE;
 overlapped.OffsetHigh = 0;

 cycle = TRUE;
 // use cycle to know when we finished reading the file
 while(cycle)
 {
  // calculate the offset of the file
  overlapped.Offset = overlapped.Offset + BUFFER_SIZE;

  // read data and send them into buffer from the source file
  if(ReadFile(handle_src, buffer, BUFFER_SIZE, &NumberOfBytesRead, &overlapped) == FALSE)
  {
   switch(dwError = GetLastError())
   {
   case ERROR_HANDLE_EOF:
    cycle = FALSE;
    break;
   case ERROR_IO_PENDING:
    if(GetOverlappedResult(handle_src, &overlapped, &NumberOfBytesRead, TRUE) == FALSE)
    {
     cout<<"GetOverlappedResult Error!"<<endl;
     exit(1);
    }
    break;
   default:
    break;
   }
  }

  if(NumberOfBytesRead < BUFFER_SIZE)
   cycle = FALSE;

  // do the operation to the file
  for(index = 0; index < NumberOfBytesRead; index ++)
   func(&buffer[index]);

  // write the content of the buffer to the destination file
  if(WriteFile(handle_dst, buffer, NumberOfBytesRead, &NumberOfBytesWrite, NULL) == FALSE)
  {
   cout<<"WriteFile Error!"<<endl;
   exit(1);
  }
 }

 // close the file handle
 CloseHandle(handle_src);
 CloseHandle(handle_dst);
}

实际测试当中,采用一个37KB的文本文件,输出结果如下:

当然,这些数据还需要更多的测试才准确,但是整体看来还是使用高速缓存时速度最快啊。不过我们还是应该根据情况采用不同的文件操作模式。

2018-06-29 11:38:36 qq_41175905 阅读数 2527

前言:本程序从本人报告拷贝过来,格式可能稍有问题,但应该不影响阅读。

一、题目与要求

题目:实现银行家算法

要求:提交电子档报告

 

二、需求分析

思想:面向对象程序设计

数据结构:一维数组、二维数组等(注:该算法可以引进队列,但由于队列相关知识的遗忘,所以就没有用到队列,后面会加强这一方面的学习!)

三、银行家算法

3.1算法思想

       申请者事先说明对各类资源的最大需求量。在进程活动期间动态申请某类资源时,由系统审查系统现有的该类资源的数目是否满足当前进程的最大需求量,如能满足就给予分配,否则拒绝。

 

3.2数据结构

(1) 可利用资源向量available。这是一个含有m个元素的数组,其中的每一个元素代表一类可利用的资源数目,其初始值是系统中所配置的该类全部可用资源的数目,其数值随该类资源的分配和回收而动态地改变。

如果available[j]=K,则表示系统中现有Rj类资源K个。

 

(2) 最大需求矩阵max。这是一个m×n的矩阵,它定义了系统中m个进程中的每一个进程对n类资源的最大需求。如果max[i,j]=K,则表示进程i需要Rj类资源的最大数目为K。

 

(3) 分配矩阵allocation。这也是一个m×n的矩阵,它定义了系统中每一类资源当前已分配给每一进程的资源数。

    如果allocation[i,j]=K,则表示进程i当前已分得Rj类资源的数目为K。

 

(4) 需求矩阵need。这也是一个m×n的矩阵,用以表示每一个进程尚需的各类资源数。如果need[i,j]=K,则表示进程i还需要Rj类资源K个,方能完成其任务。

上述三个矩阵间存在下述关系:need[i, j]=max[i, j]-allocation[i,j]

 

3.3算法

在这里算法主要有两种:1、银行家算法 2、安全算法

3.3.1银行家算法:

 设request i是进程Pi的请求向量,如果request i[j]=K,表示进程P i需要K个R j类型的资源。当P i发出资源请求后,系统按下述步骤进行检查:

  (1) 如果requesti[j]>=need[i,j],便转向步骤(2);否则认为出错,因为它所需要的资源数已超过它所宣布的最大值。

  (2) 如果requesti[j]≤available[j],便转向步骤(3);否则,表示尚无足够资源,Pi须等待。

  (3) 系统试探着把资源分配给进程P i,并修改下面数据结构中的数值:

available[j]:= available[j]-request i[j]

allocation[i,j]:= allocation[i,j]+request i[j]

need[i,j]:= need[i,j]-request i[j]

  (4) 系统执行安全性算法,检查此次资源分配后系统是否处于安全状态。若安全,才正式将资源分配给进程Pi,以完成本次分配;否则,将本次的试探分配作废,恢复原来的资源分配状态,让进程Pi等待。

 

3.3.2安全算法

  系统所执行的安全性算法可描述如下:

  (1) 设置两个向量:

  ① 工作向量work,它表示系统可提供给进程继续运行所需的各类资源数目,它含有n个元素,在执行安全算法开始时,work:=available。

  ② finish,它表示系统是否有足够的资源分配给进程,使之运行完成。开始时先做finish[i]:=false;当有足够资源分配给进程时,再令finish[i]:=true。

  (2) 从进程集合中找到一个能满足下述条件的进程:

① finish[i]=false

  ② need[i,j]≤work[j];若找到,执行步骤(3),否则,执行步骤(4)。

(3) 当进程Pi获得资源后,可顺利执行,直至完成,并释放出分配给它的资源,故应执行:

work[j]:= work[j]+allocation[i,j]

finish[i]:=true

go to step (2);

(4) 如果所有进程的finish[i]=true都满足,则表示系统处于安全状态;否则,系统处于不安全状态。

 

3.4死锁的定义及死锁发生的条件

银行家算法是为了解决死锁问题而产生的一种算法:

 

3.4.1死锁的定义

死锁是指两个或两个以上的进程在执行过程中,由于竞争资源或者由于彼此通信而造成的一种阻塞的现象,若无外力作用,它们都将无法推进下去。此时称系统处于死锁状态或系统产生了死锁,这些永远在互相等待的进程称为死锁进程。

银行家算法是避免死锁的一种重要方法。 操作系统按照银行家制定的规则为进程分配资源,当进程首次申请资源时,要测试该进程对资源的最大需求量,如果系统现存的资源可以满足它的最大需求量则按当前的申请量分配资源,否则就推迟分配。当进程在执行中继续申请资源时,先测试该进程已占用的资源数与本次申请的资源数之和是否超过了该进程对资源的最大需求量。若超过则拒绝分配资源,若没有超过则再测试系统现存的资源能否满足该进程尚需的最大资源量,若能满足则按当前的申请量分配资源,否则也要推迟分配。

3.4.2死锁的发生条件

① 互斥条件:指进程对所分配到的资源进行排它性使用,即在一段时间内某资源只由一个进程占用。如果此时还有其它进程请求资源,则请求者只能等待,直至占有资源的进程用毕释放。

② 请求和保持条件:指进程已经保持至少一个资源,但又提出了新的资源请求,而该资源已被其它进程占有,此时请求进程阻塞,但又对自己已获得的其它资源保持不放。

③ 不剥夺条件:指进程已获得的资源,在未使用完之前,不能被剥夺,只能在使用完时由自己释放。

④ 环路等待条件:指在发生死锁时,必然存在一个进程——资源的环形链,即进程集合{P0,P1,P2,···,Pn}中的P0正在等待一个P1占用的资源;P1正在等待P2占用的资源,……,Pn正在等待已被P0占用的资源。

四、设计

4.1设计思想

(1)包含各头文件以及声明命名空间

(2)声明一个bank类,该类中有Init()Banker()Display()Safe()函数

(3)实现bank类中的各个函数

(4)主函数

 

4.2设计表示







                                                         

4.3 详细设计

(1)包含各头文件以及声明命名空间

#include<iostream>
using namespace std;
const int Max_process = 50;//最大进程数
const int Max_source = 50;//最大资源数

(2)声明一个bank类,该类中有Init()Banker()Display()Safe()函数

class bank 
{
private:
	int available[Max_source];//可用资源数
	int max[Max_process][Max_source];//最大需求
	int allocation[Max_process][Max_source];//已分配资源数
	int need[Max_process][Max_source];//还需资源数
	int request[Max_process][Max_source];//进程需要资源数
	bool finish[Max_process];//判断系统是否有足够的资源分配
	int p[Max_process];//记录序列
	int m;//用来表示进程
	int n;//表示资源
	
public:
	void Init();//完成对变量的初始化
	bool Safe();//安全检测算法
	void Banker();//银行家算法
	void Display(int ,int );//显示进程与资源状态

};
(3)实现bank类中的各个函数
void bank::Init()//实现对各个数组的初始化
void bank::Display(int n, int m)//实现对数组的输出
void bank::Banker()//实现银行家算法
bool bank::Safe()//实现安全性算法

五、调试分析

为了增加程序的鲁棒性,我后面对程序进行了改进,主要体现在对need数组的取值上,当need数组中有个值小于0时,程序会跳出本次循环,并且j--,即忽略本次need值的取值,同时提醒用户重新输入allocation数组的值

for (int i = 0; i < m;i++)
       for (int j = 0; j < n;j++)
       {
           cin >> allocation[i][j];
           need[i][j]= max[i][j] - allocation[i][j];//注意这里的need可能小于0;要进行报错并重新输入,可以用continue来跳出当前循环
           if (need[i][j] < 0)
           {
               cout <<"你输入的第"<<i+1<<"个进程的第"<<j+1<<"个资源数有问题!\n请重新输入!";
               j--;//忽略这个资源数
               continue;//跳出本次循环
           }
       }

此外,之前写的程序缺点在于进程和资源数比较固定(分别是5个进程和3个资源),后来干脆采用了定义两个全局常量,来使得进程数和资源数可以有更多的选择,而且方便后期对程序的调试(一次又一次的输入一个个5X3矩阵真的很麻烦,而当我们输入1个进程一个资源的时候可以测试程序的可行

六、用户手册

用户需要按照系统提示,进行相关输入操作,依次输入,

七、测试数据及检测结果


自动生成安全序列:


资源申请操作:(其中安全序列是随着资源申请操作动态变化的)



(至此资源分配完毕!)

八、源程序清单

#include<iostream>
using namespace std;
const int Max_process = 50;//最大进程数
const int Max_source = 50;//最大资源数


class bank 
{
private:
	int available[Max_source];//可用资源数
	int max[Max_process][Max_source];//最大需求
	int allocation[Max_process][Max_source];//已分配资源数
	int need[Max_process][Max_source];//还需资源数
	int request[Max_process][Max_source];//进程需要资源数
	bool finish[Max_process];//判断系统是否有足够的资源分配
	int p[Max_process];//记录序列
	int m;//用来表示进程
	int n;//表示资源
	
public:
	void Init();//完成对变量的初始化
	bool Safe();//安全检测算法
	void Banker();//银行家算法
	void Display(int ,int );//显示进程与资源状态

};

void bank::Init()
{
	cout << "请输入进程的数目:";
	cin >> m;

	cout << "请输入资源的数目:";
	cin >> n;

	cout << "请输入每个进程最多所需的各资源数,按照"<<m<<'X'<<n<<"矩阵格式输入"<<endl;
	for (int i = 0; i < m; i++)
		for (int j = 0; j < n; j++)
			cin >> max[i][j];

	cout << "请输入每个进程已分配的各资源数,按照" << m << 'X' << n << "矩阵格式输入" << endl;
	for (int i = 0; i < m; i++)
		for (int j = 0; j < n; j++)
		{
			cin >> allocation[i][j];
			need[i][j] = max[i][j] - allocation[i][j];//注意这里的need可能小于0;要进行报错并重新输入,可以用continue来跳出当前循环
			if (need[i][j] < 0)
			{
				cout << "你输入的第"<<i+1<<"个进程的第"<<j+1<<"个资源数有问题!\n请重新输入!";
				j--;//忽略这个资源数
				continue;//跳出本次循环
			}
		}

	cout << "请输入各个资源现有的数目"<<endl;
	for (int i = 0; i < n; i++)
	{
		cin >> available[i];
	}

}
//m表示进程,n表示资源
void bank::Display(int n, int m)
{
	cout << endl << "+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++" << endl;
	
	cout << "系统可用的资源数为:	";
	for (int i = 0; i < n; i++)
	{
		cout << available[i] << "	";
	}

	cout << endl << "各进程还需要的资源量:" << endl;
	for (int i = 0; i < m; i++)
	{
		cout << "	进程" << i << ":";
		for (int j = 0; j < n; j++)
			cout << "		" << need[i][j];
		cout << endl;
	}


	cout << endl << "各进程已经得到的资源:		" << endl;
	for (int i = 0; i < m; i++)
	{
		cout << "	进程" << i << ":";
		for (int j = 0; j < n; j++)
		{
			cout << "		" << allocation[i][j];
		}
		cout << endl;
	}

	cout << endl << endl;
}


void bank::Banker()
{
	int i, cusneed, flag = 0;//cusneed表示资源进程号
	char again;//键盘录入一个字符用于判断是否继续请求资源
	while (1)
	{
		Display(n,m);
		cout << endl;
		/*请求资源*/
		while (true)
		{
			cout << "请输入要申请的进程号"<<endl;
			cin >> cusneed;
			if (cusneed > m)
			{
				cout << "没有该进程,请重新输入"<<endl;
				continue;
			}
			cout << "请输入进程所请求的各资源数" << endl;
			for (int i = 0; i < n; i++)
				cin >> request[cusneed][i];
			for (int i = 0; i < n; i++)
			{
				if (request[cusneed][i] > need[cusneed][i])
				{
					cout << "你输入的资源请求数超过进程数需求量!请重新输入"<<endl;
					continue;
				}
				if (request[cusneed][i] > available[i])
				{
					cout << "你输入的资源请求数超过系统当前资源拥有数!" << endl;
					break;
				}
			}
			break;
		}

		/*上述是资源请求不合理的情况,下面是资源请求合理时则执行银行家算法*/
		for (int i = 0; i < n; i++)
		{
			available[i] -= request[cusneed][i];//可用资源减去成功申请的
			allocation[cusneed][i] += request[cusneed][i];//已分配资源加上成功申请的
			need[cusneed][i] -= request[cusneed][i];//进程还需要的减去成功申请的
		}

		/*判断分配申请资源后系统是否安全,如果不安全则将申请过的资源还给系统*/
		if (Safe())
			cout << "同意分配请求!";
		else
		{
			cout << "你的请求被拒绝! !!"<<endl;
			/*进行向系统还回资源操作*/
			for (int i = 0; i < n; i++)
			{
				available[i]+= request[cusneed][i];
				allocation[cusneed][i] -= request[cusneed][i];
				need[cusneed][i] += request[cusneed][i];
			}
		}

		/*对进程的需求资源进行判断,是否还需要资源,简言之就是判断need数组是否为0*/
		for (int i = 0; i < n; i++)
			if (need[cusneed][i] <= 0)
				flag++;
			if (flag == n)
			{
				for (int i = 0; i < n; i++)
				{
					available[i] += allocation[cusneed][i];
					allocation[cusneed][i] = 0;
					need[cusneed][i] = 0;
				}
				cout << "进程" << cusneed << "占有的资源已释放!!"<<endl;
				flag = 0;
			}
			for (int i = 0; i < m; i++)
				finish[i] = false;
			/*判断是否继续申请*/
			cout << "你还想再次请求分配吗?是请按Y/y,否请按其他键!" << endl;
			cin >> again;
			if (again == 'Y' || again == 'y')
				continue;
			break;
	}
}

bool bank::Safe()
{
	int l = 0, j, i;
	int work[Max_source];
	/*对work数组进行初始化,初始化时和avilable数组相同*/
	for (int i = 0; i < n; i++)
		work[i] = available[i];
	/*对finish数组初始化全为false*/
	for (int i = 0; i < m; i++)
		finish[i] = false;
	for (int i = 0; i < m; i++)
		{
			if (finish[i] == true)
				continue;
			else
			{
				for (j = 0; j < n; j++)
				{
					if (need[i][j] > work[j])
						break;
				}
				if (j ==n)
				{
					finish[i] = true;
					for (int k = 0; k < n; k++)
						work[k] += allocation[i][k];
					p[l++] = i;//记录进程号
					i = -1;
				}
				else
					continue;
			}
		}

		if (l == m)
		{
			cout << "系统是安全的" << endl;
			cout << "安全序列:" << endl;
			for (int i = 0; i < l; i++)
			{
				cout << p[i];
				if (i != l - 1)
					cout << "-->";
			}
			cout << endl << endl;
			return true;
		}
	
}


int main()
{
	bank peter;
	peter.Init();
	peter.Safe();
	peter.Banker();
	return 0;
}


2018-05-27 22:53:30 hml666888 阅读数 889

目录

一、 进程调度 2

1. 短作业优先调度算法 2

1.1题目内容 2

1.2题目要求 2

1.3设计思想 3

1.4算法分析 3

1.4.2程序结构 3

1.4.2数据结构 3

1.5核心代码 5

1.6程序流程图 6

1.7测试数据或截图 6

2. 时间片轮转调度算法 7

2.1题目内容 7

2.2题目要求 7

2.3设计思想 7

2.4算法分析 8

2.4.1程序结构 8

2.4.2数据结构 8

2.5核心代码 9

2.6程序流程图 11

2.7测试数据或截图 12

二、 磁盘调度管理 12

1. 题目内容 12

2. 题目要求 12

3.设计思想 13

4.算法分析 13

4.1程序结构 13

4.2数据结构 13

5.核心代码 15

7.测试数据或截图 17

三、 心得体会 18

 

 

 

一、进程调度

1. 短作业优先调度算法

1.1题目内容

设计程序模拟单处理机系统中的进程调度算法,在短作业优先调度算法、 时间片轮转调度、最高优先级优先算法三种算法中选择两种实现。

1.2题目要求

每个进程由一个进程控制块(PCB)表示。进程控制块可以包含如下信息: 进程名、优先数、到达时间、需要运行时间、已用CPU时间、进程状态等。进程的优先数及需要的运行时间可以事先人为地指定(也可以由随机数 产 生)。进程的到达时间为进程输入的时间。

进程的运行时间以时间片为单位进行计算。

每个进程的状态可以是就绪W(Wait)、运行R(Run)或完成F(Finish)3 中状态之一。

1.3设计思想

该算法先比较作业运行时间长短,运行时间短的作业先执行,如果运行 时间相同,则按照到到达时间执行,到达时间早的先执行。

1.4算法分析

1.4.1程序结构

①输入部分:

void input(PCB *p,int N)

{

int i;

printf("请输入进程的名称、到达时间和运行时间:\nfor example:a 0 100\n");

for(i=0;i<=N-1;i++)

{

printf("请输入第%d个进程的信息:\n",i+1); scanf("%s%f%f",&p[i].name,&p[i].arrivetime,&p[i].runtime);

}

}

②输出部分:

oid output(PCB *p,int N)

{

int k;

printf("优先运行顺序:");

printf("%s",p[0].name); for(k=1;k<N;k++)

{

printf("-->%s",p[k].name); }

printf("\n各个进程的信息:\n");

printf("\n名称\t到达\t运行\t开始\t完成\t周转\t带权周转 \n");

for(k=0;k<N;k++)

{

printf("%s\t%-.2f\t%-.2f\t%-.2f\t%-.2f\t%-.2f\t%-.2f\t\n",p[k]. name,p[k].arrivetime,p[k].runtime,p[k].starttime,p[k].finishtim e,p[k].zztime,p[k].dqzztime);

}

}

③排序部分:用冒泡排序法将到达时间降序排序

void sort(PCB *p,int N)

{

for(int i=0;i<N;i++)

for(int j=0;j<i;j++)

if(p[i].arrivetime<p[j].arrivetime) {

PCB t;

t=p[i];

p[i]=p[j];

p[j]=t;

}

}

④计算部分:为了得到每个进程的结束时间

void deal(PCB *p,int N)/{

int k;

 

for(k=0;k<N;k++)

{

if(k==0) {

p[k].starttime=p[k].arrivetime;

p[k].finishtime=p[k].starttime+p[k].runtime;

}

else

{

p[k].starttime=p[k-1].finishtime;

p[k].finishtime=p[k].starttime+p[k].runtime;

}

}

for(k=0;k<N;k++)

{

p[k].zztime=p[k].finishtime-p[k].arrivetime;

p[k].dqzztime=p[k].zztime/p[k].runtime;

}

}

1.4.2数据结构

struct PCB

{

char name[10];

float arrivetime;

float runtime;

float starttime;

float finishtime;

float zztime;

float dqzztime;

};

PCB a[100];

1.5核心代码

void sjff(PCB *p,int N)

{

float arrivetime=0,runtime=0,starttime=0,finishtime=0,zztime=0,dqzztime=0;

sort(p,N);

   for(int m=0;m<N-1;m++)

{

if(m==0)

        p[m].finishtime=p[m].arrivetime+p[m].runtime;         else

{

if(p[m-1].finishtime >=p[m].arrivetime )

{

p[m].starttime=p[m-1].finishtime;}/

else

{

p[m].starttime =p[m].arrivetime;}

   p[m].finishtime=p[m].starttime+p[m].runtime;

}

int i=0;

        for(int n=m+1;n<=N-1;n++)

{

if(p[n].arrivetime<=p[m].finishtime)

            i++;

}

        float min=p[m+1].runtime;

        int next=m+1;//m+1=n

        for(int k=m+1;k<m+i;k++)

{

          if(p[k+1].runtime<min)

          {

  min=p[k+1].runtime;

              next=k+1;

  }

}

            PCB temp;

            temp=p[m+1];

            p[m+1]=p[next];

            p[next]=temp;

}

   deal(p,N);

   output(p,N);

}

 


1.6程序流程图


    1.7测试数据或截图

 

 

2. 时间片轮转调度算法

2.1题目内容

      设计程序模拟单处理机系统中的进程调度算法,在短作业优先调度算法、时间片轮转调度、最高优先级优先算法三种算法中选择两种实现。    

2.2题目要求  

         每个进程由一个进程控制块(PCB)表示。进程控制块可以包含如下信息:进程名、优先数、到达时间、需要运行时间、已用CPU时间、进程状态等。

进程的优先数及需要的运行时间可以事先人为地指定(也可以由随机数产生)。进程的到达时间为进程输入的时间。

进程的运行时间以时间片为单位进行计算。

每个进程的状态可以是就绪W(Wait)、运行R(Run)或完成F(Finish)3中状态之一。

2.3设计思想

该算法按照先来先服务执行进程,用time()函数计算进程运行时间,先将 进程初始化信息进行备份,用while条件判断进程是否全部执行完毕,如果进 程执行完毕则跳出循环结束计算。

2.4算法分析:

  2.4.1程序结构

①输入函数:

int pinput() /*进程参数输入*/

{

    int i;

    printf("请输入进程个数:\n");

    scanf("%d",&counter);

    printf("请输入时间片长度:\n");

    scanf("%d",&timecounter);

    for(i=0; i<counter; i++)

    {

     printf("**************************************\n");

printf("请输入进程名称、到达时间、运行时间:(中间用 空格隔开)\n");

scanf("%s%f%f",tasks[i].name,&tasks[i].arrivetime,& tasks[i].runtime);

        tasks[i].starttime=0;

        tasks[i].finishtime=0;

        tasks[i].runflag=0;  //运行是否结束

        tasks[i].startflag=0;//是否首次被执行

    }

    return 0;

}

②输出函数:

int poutput()

{

    int i;

    float dqzztime=0,zztime=0,w=0;

    printf("进程名 到达时间 运行时间 开始时间 结束 时间 周转时间 带权周转时间\n");

    for(i=0; i<counter; i++)

    {

         zztime=tasks[i].finishtime-tasks[i].arrivetime;

        dqzztime=zztime/tasks[i].runtime;

     printf("%s\t%5.3f\t%5.3f\t%5.3f\t %5.3f\t%5.3f\t%5.3 f\n",tasks[i].name,tasks[i].arrivetime,tasks[i].run time,tasks[i].starttime,tasks[i].finishtime,zztime, dqzztime);

    }

    return 0;

}

③判断函数:判断进程是否全部执行完毕

int charge()

{

    int k;

    int superflag=0;

    for(k=0; k<counter; k++)

    {

        if(tasks[k].runflag==0)

        {

            superflag=1;

            return superflag;

            break;

        }

        else

        {

            superflag=0;

        }

    }

    return superflag;

}

2.4.2数据结构

struct task_struct

{

    char name[10];           /*进程名称*/

    float arrivetime;         /*到达时间*/

    float starttime;     /*开始运行时间*/

    float runtime;          /*运行时间*/

    float finishtime;      /*运行结束时间*/

    int runflag;          /*调度标志*/

    int startflag;     //是否为第一次开始调度

} tasks[MAX];

int counter; /*实际进程个数*/

int pinput();

int timecounter=0;

int poutput(); /*调度结果输出*/

int time();

int charge();//判断是否所有的进程都被执行过

2.5核心代码

int time()

{

    float temp=0;

    int i;

    int j=0;

    int k=0;

    struct task_struct  copy_task[MAX];//备份

    for(i=0; i<counter; i++)

    {

        copy_task[j++]=tasks[i];//对进程的初始化信息备份

    }

    temp=tasks[0].arrivetime;//temp=第一个进程的到达时间

    while(charge())

    {

        for(i=0; i<counter; i++)

        {

            if(tasks[i].arrivetime>temp)

            {

                temp=tasks[i].arrivetime;

            }

            if(tasks[i].runflag==0)//第i个进程还未结束

            {

                if(tasks[i].startflag==0)  

                {

                    tasks[i].starttime=temp;

                    tasks[i].startflag=1;

                }

                if(tasks[i].runtime/timecounter>1)

                {

                    tasks[i].runtime=tasks[i].runtime-timecounter;

                    temp=temp+timecounter;

                }

                else if(tasks[i].runtime-timecounter==0)

                {

                    temp=temp+timecounter;                     tasks[i].finishtime=temp;

                    tasks[i].runflag=1;//标记该进程已经执行完毕

                    tasks[i].runtime=copy_task[i].runtime;

                }

                else//仅剩下不足一倍的时间片,则剩余运行时间除以时间片长度<1

                {

                    temp=temp+tasks[i].runtime;

                    tasks[i].finishtime=temp;

                    tasks[i].runflag=1;//标记该进程已经运行完毕

                    tasks[i].runtime=copy_task[i].runtime;

                }

            }

        }

    }

return 0;

}

2.6程序流程图

 

 

 


2.7测试数据或截图

 

 

二、磁盘调度管理

1. 题目内容

设定开始磁道号寻道范围,依据起始扫描磁道号和最大磁道号数,随机产生要进行寻道的磁道号序列。选择磁盘调度算法,显示该算法的磁道访问顺序,计算出移动的磁道总数和平均寻道总数。

2. 题目要求

1. 最短寻道优先算法SSTF:该算法选择这样的进程:其要求访问的

道与当前磁头所在的磁道距离最近,以使每次的寻道时间最短。

2.扫描算法SCAN:该算法不仅考虑到欲访问的磁道与当前磁道间的距离,更优先考虑的是磁头当前的移动方向。例如,当磁头正在自里向外移动时,SCAN算法所考虑的下一个访问对象,应是其欲访问的磁道既在当前磁道之外,又是距离最近的。这样自里向外地访问,直至再无更外的磁道需要访问时,才将磁臂换向为自外向里移动。

3.循环扫描算法CSCAN:CSCAN算法规定磁头单向移动,例如,只是自里向外移动,当磁头移到最外的磁道并访问后,磁头立即返回到最里的欲访问的磁道,亦即将最小磁道号紧接着最大磁道号构成循环,进行循环扫描。

3.设计思想

该算法用vvector标准模板库模拟有许多扇区的磁盘,用srand()和rand()函数随机生成磁盘序列,存放到outfile文件流里面,设计一个选择函数,用switch选择需要调用的SSTF、SCAN、CSCAN算法,也用switch选择是否结束进程。

4.算法分析

4.1程序结构

随机生成序列函数,用srand和rand随机生成序列

void request(vector<int>&m_vec,ofstream &outfile){  

    cout<<"随机生成磁盘序列:"<<endl;  

    int n = 0;  

    srand(time(NULL));    

    n = rand() % 20 + 1; //rand()是一个产生随机数的函数,与srand一起 用,rand()%20+1:n的取值为1-20

    int temp = 0;  

    for(int i=0;i<n;i++){  

        temp = rand() % 100; //temp的取值为0-100

        m_vec.push_back(temp); // 将随机生成的temp数输入到vector里面

        cout<<temp<<" ";  

        outfile<<temp<<endl; //outfile输出数据文件流,输出到输出文件中

    }  

    cout<<endl;  

    position = rand() % 100; //当前磁道为随机生成的0-100之间的数

    cout<<"当前磁道:"<<position<<endl;  

}

②最短寻道算法:

void SSTF(vector<int>m_vec,int position){    

    dis = 0;  

    average_distance = 0;  

    sort(m_vec.begin(),m_vec.end());    //从小到大排序

    int i = 0;  

    for(vector<int>::iterator it=m_vec.begin();it!=m_vec.end();it++){  

        if(position >= *it) //找到position所在磁道

            i++;  

    }  

    int count = 0;  

    int left = i-1; //i为下标

    int right = i;  

    while(count<m_vec.size()){  //选择扫描方向,如果

        if((left >=0 && abs(m_vec[right]-position) > abs(m_vec[left]-position)) || right>=m_vec.size()){

            dis += abs(m_vec[left]-position);  

            Sleep(500);  

            cout<<"->"<<m_vec[left];  

            position = m_vec[left];  

            left--;  

        }  

        else{ //选择从右边开始扫描

            dis += abs(m_vec[right]-position);  

            Sleep(500);  

            cout<<"->"<<m_vec[right];  

            position = m_vec[right];  

            right++;  

        }  

        count++;  

    }  

    compute_dis(m_vec,dis,average_distance);  

}

③扫描算法:

void SCAN(vector<int>m_vec,int position){    

    dis = 0;  

    average_distance = 0;  

    sort(m_vec.begin(),m_vec.end());    //从小到大排序  

    int i = 0;  

    for(vector<int>::iterator it=m_vec.begin();it!=m_vec.end();it++){  

        if(position >= *it)  

            i++;      //找到position所在的磁道  

    }  

    int left = i - 1;   //先从外到内扫描  

    int right = i;  

    while(left >= 0){  

        dis += abs(position - m_vec[left]);  

        Sleep(500);  

        cout<<"->"<<m_vec[left];  

        position = m_vec[left];  

        left --;//当左边的序列走完之后跳出这个while循环  

    }  

    while(right < m_vec.size()){  

        dis += abs(position - m_vec[right]);  

        Sleep(500);  

        cout<<"->"<<m_vec[right];  

        position = m_vec[right];  

        right ++;  

    }  

    compute_dis(m_vec,dis,average_distance);  

}

④循环扫描算法:

void CSCAN(vector<int>m_vec,int position){   //循环扫描算法  

    dis = 0;  

    average_distance = 0;  

    sort(m_vec.begin(),m_vec.end());    //从小到大排序  

    int i = 0;  

    for(vector<int>::iterator it=m_vec.begin();it!=m_vec.end();it++){  

        if(position >= *it)  

            i++;      //找到position所在的磁道  

    }  

    int left = i - 1;   //先从外到内扫描  

    int right = i;  

    while(left >= 0){  

        dis += abs(position - m_vec[left]);  

        Sleep(500);  

        cout<<"->"<<m_vec[left];  

        position = m_vec[left];  

        left --;  

    }  

 

    int len = m_vec.size()-1;  

    while(len >= right){ //从最外侧在是扫描一遍,像梳头发一样

        dis += abs(position - m_vec[len]);

        Sleep(500);  

        cout<<"->"<<m_vec[len];  

        position = m_vec[len];  

        len --;  

    }  

    compute_dis(m_vec,dis,average_distance);  

}

⑤计算平均距离算法:

void compute_dis(vector<int>m_vec,int &dis,double &average_distance){  

    average_distance = (double)dis / (double)m_vec.size();  

}

5.核心代码

int choose_algorithm(vector<int>m_vec){  

    cout<<endl<<endl;  

    cout<<"本实验可用的调度算法有以下3种:"<<endl;  

    cout<<"1.SSTF  2.SCAN  3.CSCAN   4.结束本序列的调度  5.结束程序"<<endl;  

    int choice = 0;  

    cout<<"选择:"<<endl;  

    cin>>choice;  

    cout<<endl;  

    while(choice!=4 && choice!=5){  

        cout<<"磁盘请求的服务状况:"<<endl;  

        cout<<position;  

        switch(choice){  

            case 1:  

                SSTF(m_vec,position);break;  

            case 2:  

                SCAN(m_vec,position);break;  

            case 3:  

                CSCAN(m_vec,position);break;  

 

            default:  

                cout<<"******非法输入!******"<<endl<<endl;break;   

        }   

        if(choice<=5 && choice>=1)   

            print();  

        cout<<"选择:"<<endl;  

        cin>>choice;  

    }  

    if(choice == 5)  

        return 0;  

    else  

        cout<<endl<<endl; //清空输出缓冲区,相当于将vertor初始化

return 1;  

}

6.程序流程图

 

7.测试数据或截图

 

 

三、心得体会

每一次课程设计度让我学到了在平时课堂不可能学到的东西。不一定我的课程设计能够完成得有多么完美,但是我总是很投入的去研究去学习。但是每完成一个任务我都兴奋不已。总体而言我的课设算是达到了老师的基本要求。总结一下有以下体会。

1、网络真的很强大,用在学习上将是一个非常高效的助手。几乎所有的资料都能够在网上找到。也因为这样,整个课程设计下来,我浏览的相关网页已经超过了100个(不完全统计)。当然网上的东西很乱很杂,自己要能够学会筛选。

2、同学间的讨论,这是很重要的。老师毕竟比较忙。对于课程设计最大的讨论伴侣应该是同学了。能和学长学姐讨论当然再好不过了,没有这个机会的话,和自己班上同学讨论也是能够受益匪浅的。大家都在研究同样的问题,讨论起来,更能够把思路理清楚,相互帮助,可以大大提高效率。

3、敢于攻坚,越是难的问题,越是要有挑战的心理。这样就能够达到废寝忘食的境界。当然这也是不提倡熬夜的,毕竟有了精力才能够打持久战。但是做课设一定要有状态,能够在吃饭,睡觉,上厕所都想着要解决的问题,这样你不成功都难。