精华内容
下载资源
问答
  • 实验二:多道程序设计 2.1实现文件系统调用 1.题目要求 实现文件系统调用(create、open、read、write、close和unlink,记录在syscall.h中)。您将在UserProcess.java中看到halt的代码;最好也在这里放置新的系统...

    实验二:多道程序设计

    2.1实现文件系统调用

    1.题目要求

    实现文件系统调用(create、open、read、write、close和unlink,记录在syscall.h中)。您将在UserProcess.java中看到halt的代码;最好也在这里放置新的系统调用。请注意,您没有实现文件系统;相反,您只是让用户进程能够访问我们为您实现的文件系统。

    2.问题分析与解决方案

    基于对问题要求文档的阅读理解,本次任务是要实现一些列系统调用方法。其中一些系统调用需要与文件操作相关联,所以要理解我们这个nachos系统的文件管理机制。按照要求文档的说明,文件系统是已经实现了的,我们只需要理解这个文件系统并且学会利用它。

    在实现几种系统调用的时候,涉及到多个对文件的处理,需要考虑以下细节问题:

    • 一个文件不能多次创建
    • 已经打开的文件是不能直接删除的
    • 一个文件可以被打开多次 打开不存在的文件时先创建再打开

    为了解决以上问题,我们创建了两个哈希表来管理文件的状态和打开次数,分别是processfiles和files。在执行相关的操作时需要根据这两个表进行判断,条件允许再进行对文件的下一步操作。
    ①create系统调用:
    1.根据形参fileAddress, 从虚拟内存读取文件名,长度不能超过256。
    2.在file表判断文件名是否存在,不存在的话存入,状态记为1
    3.如果文件不存在,就直接创建该文件。首先寻找是否还有可以存放的位置,如果超出了数量限制就会退出,创建失败。如果仍有空间可以创建,调用 fileSystem.open(filename, true)。同时在processfiles表中记录。
    4.将fileAddress对应的openfile数组的位置放入刚刚创建的文件描述符
    ②open系统调用:
    1.根据形参fileAddress, 从虚拟内存读取文件名,长度不能超过256。
    2.在file表判断文件名是否存在,不存在的话存入,状态记为1,如果存在则状态加1,表示打开一次。
    3.如果文件不存在,就直接创建该文件。首先寻找是否还有可以存放的位置,如果超出了数量限制就会退出,创建失败。如果仍有空间可以创建,调用 fileSystem.open(filename, false)打开文件即可。同时在processfiles表中记录。
    4.将fileAddress对应的openfile数组的位置放入刚刚创建的文件描述符

    ③read系统调用:
    该系统调用涉及三个输入参数: 文件描述符, 写入的内存地址, 读取的字节数。
    1.首先判断打开条件,如果打开文件大于16个或者小于0个,或者打开文件列表为空,即出错,返回。
    2.创建临时数组temp,将文件的内容保存在temp中,并返回写入的字节数。
    3.如果返回的字节数小于0即为出错,返回。
    4.将读到的内容写入虚拟内存相应地址。
    5.返回写入内存的字节数。

    ④write系统调用:
    该系统调用涉及三个输入参数: 文件描述符, 读取内存的地址, 写入的字节数。
    1.首先判断打开条件,如果打开文件大于16个或者小于0个,或者打开文件列表为空,即出错,返回。
    2.创建临时数组 temp,将虚拟内存中的内容保存在temp中,并返回读出的字节数
    3.如果返回的字节数小于0即为出错,返回。
    4.将读到的内容写入磁盘。
    5.如果写入的数据长度小于读出的数据长度,则错误,返回。

    ⑤close系统调用:
    1.首先判断打开条件,如果打开文件大于16个或者小于0个,或者打开文件列表为空,即出错,返回。
    2.如果文件已经打开一次,修改processfiles和files状态,同时关闭文件
    3.把 openfile 数组中 fileDescriptor 中的位置置为null

    ⑥unlink 系统调用:
    1.根据形参fileAddress, 从虚拟内存读取文件名,长度不能超过256。
    2.如果文件不存在则不用删除
    3.如果文件处于打开状态,则不能删除
    4.否则删除文件。

    2.2完成对多道程序的支持

    1.题目要求

    实现对多道程序设计的支持。我们提供给您的代码仅限于一次运行一个用户进程;您的工作是使它对多个用户进程有效。

    2.问题分析与解决方案

    ①loadSections
    该方法为每个进程分配内存,将coff块导入进内存,如果成功,进程就会执行(进程初始化会失败的最后一步)
    1.首先判断需要的页的数量是否多于剩余物理页数量,如果物理页数量少于需要的页的数量,则内存分配失败,并提示缺少物理地址
    2.得到需要的物理页号后,实例化TranslationEntry类型的页表pageTable数组,从空闲物理页表号链表(memoryLinkedList)中取出一个空闲物理页号。在页表数组中实例化一个TranslationEntry对象,并为其赋上相应的虚拟页号和物理页号等信息。
    3.对于coffSection的每个section对象,通过for循环得到每一页页号,修改其权限为readonly,然后根据物理地址装入页。
    ②readVirtualMemory
    该方法涉及四个参数:要读的虚拟内存的首字节、数据存放的数组、写入数组的首字节、从虚拟内存转换到数组的字节数。从进程的虚拟内存中将数据复制到指定的数组,这个方法处理地址转换的细节。这个方法在发生错误时不能损坏当前进程,但是应该返回成功复制的字节的数量,如果没有数据复制返回0。
    1.计算页号并判断页号的合法性。
    2.计算页偏移量。
    3.根据页偏移量计算该页剩余容量。
    4.比较页剩余量和剩余传输量,取其中的较小值作为将要复制的数据长度。
    5.计算相应物理内存地址,虚拟页号对应的物理页号*页大小+页偏移量
    ③writeVirtualMemory
    与read类似,要先利用页表将逻辑地址转换为物理地址然后再将数组数据复制到内存中,并注意取页面时要检查页面是否为只读。

    2.3实现系统调用

    1.题目要求

    实现系统调用(exec, join, and exit, also documented in syscall.h)

    2.问题分析与解决方案

    ①exce系统调用
    该系统调用涉及三个参数:文件名地址,参数个数,参数地址。
    1.首先从虚拟内存中读取文件名,且文件名长度不能超过256,之后判断文件名的合法性:文件名不能为空,参数个数不能小于0,地址不能小于0,地址不能超过numPages*pageSize
    2.将文件内容读入虚拟内存
    3.创建子进程
    4.设置当前线程为该子进程的父进程,再将子进程加入子进程列表,并返回子进程的进程号

    ②join系统调用
    该系统调用涉及两个参数: join线程的进程号,子进程的返回值
    1.先通过pid确定进程,再检查其子进程表,遍历子进程链表,确定join的进程是子进程。如果子进程编号不在其中,则出错返回
    2.获得join的锁,使该进程睡眠直到被子进程唤醒
    3.子进程唤醒后释放锁,将子进程的运行状态存入父进程的内存中。
    4.判断进程是否正常结束,然后返回

    ③exit系统调用
    1.首先关闭coff文件。
    2.关闭该子进程openfile中所有打开的文件,并且把位置内容置为null。
    3.如果该进程有父进程,就将其唤醒。并从父进程的子进程表中删除这个子进程。
    3.判断当前正在运行的进程数量是否为1,如果只剩最后一个进程,执行停机指令

    2.4实现彩票调度

    1.题目要求

    实现彩票调度程序(将其放在threads/lottery scheduler.java中)。注意,这个类扩展了PriorityScheduler,您应该能够重用该类的大部分功能;彩票调度器不应该是大量的额外代码。唯一的主要区别是用于从队列中挑选线程的机制:举行抽签,而不是仅仅挑选优先级最高的线程。您的彩票计划程序应该实现优先捐赠。(注意,由于这是一个彩票调度程序,优先级反转实际上不会导致饥饿!但是,无论如何,您的调度程序必须进行优先级捐赠。)

    2.问题分析与解决方案

    彩票调度中持有彩票的获取方式是进程自己的彩票数加上自己等待队列中所有进程的彩票数,系统会在0至彩票总数之间随机生成一个数字表示抽取的彩票。彩票越多,下次得到的运行机会就越大。

    3.变量说明:

    UserProcess类:用户进程载入等方法
    LotteryScheduler类:实现彩票调度程序

    源代码:

    2.1相关代码

    
    private int handleCreate(int fileAddress) {
    		String filename = readVirtualMemoryString(fileAddress, 256);
    		//从虚拟内存读取文件名,长度不能超过256
    		if (filename == null)
    			return -1;		
    		int fileDescriptor=-1;
    		if(files.contains(filename)) {
        		int i=files.get(filename)+1;
        		files.put(filename, i);
        	}
        	else {
        		files.put(filename, 1);
        	}
    		if(processfiles.containsKey(filename))
        		return processfiles.get(filename);
    		fileDescriptor = findEmpty();
    		if (fileDescriptor==-1)
    			return -1;		
    		else{
    			openfile[fileDescriptor]=ThreadedKernel.fileSystem.open(filename, true);
    			//true代表如果不存在就创建
    			processfiles.put(filename, fileDescriptor);
    		}
    System.out.println("create success");
    		return fileDescriptor;
    	}
    private int handleOpen(int fileAddress){
    	String filename=readVirtualMemoryString(fileAddress,256);
    		if (filename == null)
    			return -1;	
    		int fileDescriptor=-1;
    		if(files.contains(filename)) {
        		int i=files.get(filename)+1;
        		files.put(filename, i);
        	}
        	else {
        		files.put(filename, 1);
        	}
        	if(processfiles.containsKey(filename))
        		return processfiles.get(filename);
    	    fileDescriptor = findEmpty();
    		if (fileDescriptor == -1)
    			return -1;		
    		else {
    			openfile[fileDescriptor] = ThreadedKernel.fileSystem.open(filename,false);
    			System.out.println("open success");
    			processfiles.put(filename, fileDescriptor);
    			return fileDescriptor;
    		}
    	}
    	private int handleRead(int fileDescriptor,int bufferAddress,int length){
    			if(fileDescriptor>15||fileDescriptor<0||openfile[fileDescriptor]==null)
    			return -1;		
    		byte temp[]=new byte[length];
    		int readNumber=openfile[fileDescriptor].read(temp, 0, length);
    		if(readNumber<=0)
    			return 0;	
    		int writeNumber=writeVirtualMemory(bufferAddress,temp);
    		//把读到的内容写到虚拟内存
    		return writeNumber;
    		//返回写入的字节数
    	}
    	private int handleWrite(int fileDescriptor,int bufferAddress,int length){
    		if(fileDescriptor>15||fileDescriptor<0||openfile[fileDescriptor]==null)
    			return -1;		
    		byte temp[]=new byte[length];
    			int readNumber=readVirtualMemory(bufferAddress,temp);
    		//从虚拟内存里面读出来,然后写到内存
    		if(readNumber<=0)
    			return 0;	
    		int writeNumber=openfile[fileDescriptor].write(temp, 0, length);
    		if(writeNumber<length)
    			return -1;
    		return writeNumber;
    	}
    	private int handleClose(int fileDescriptor){
    		if(fileDescriptor>15||fileDescriptor<0||openfile[fileDescriptor]==null)
    			return -1;			
    		else {
    		String filename=hashbl(processfiles,fileDescriptor);
    		if(processfiles.containsKey(filename))
    			processfiles.remove(filename);
    		if(files.containsKey(filename)) {
    			int i=files.get(filename)-1;
    			files.put(filename, i);}
    		openfile[fileDescriptor].close();
    		openfile[fileDescriptor]=null;
    		System.out.println("close success");
    		return 0;
    		}
    	}
    private int handleUnlink(int fileAddress){
    		String filename=readVirtualMemoryString(fileAddress,256);
    		if(filename==null)
    			return 0;		
    		if(files.get(filename)>0)
    			return -1;
    		else {
    		if(ThreadedKernel.fileSystem.remove(filename))
    			return 0;
    		else
    			return -1;
    	}
    	}
    
    

    2.2相关代码

    protected boolean loadSections() {
    			UserKernel.allocateMemoryLock.acquire();
    		if (numPages > Machine.processor().getNumPhysPages()) {
    			coff.close();
    				Lib.debug(dbgProcess, "\t insufficient(缺少物理地址) physical memory");
    			UserKernel.allocateMemoryLock.release();
    			return false;
    		}
    		pageTable=new TranslationEntry[numPages];
    		for(int i=0;i<numPages;i++){
    			
    int	nextPage=UserKernel.memoryLinkedList.remove();
    			pageTable[i]=new TranslationEntry(i,nextPage,true,false,false,false);
    		}
    		UserKernel.allocateMemoryLock.release();
    		
    for (int s = 0; s < coff.getNumSections(); s++) {
    			CoffSection section = coff.getSection(s);		
    			Lib.debug(dbgProcess,
    					"\tinitializing " + section.getName() + " section (" + section.getLength() + " pages)");
    			for (int i = 0; i < section.getLength(); i++) {
    				int vpn = section.getFirstVPN() + i;
    				pageTable[vpn].readOnly=section.isReadOnly();
    					section.loadPage(i,pageTable[vpn].ppn);
    			}
    		}
    		return true;
    	}
    public int readVirtualMemory(int vaddr, byte[] data, int offset, int length) {
    			Lib.assertTrue(offset >= 0 && length >= 0 && offset + length <= data.length);
    			byte[] memory = Machine.processor().getMemory();		
    			if(length>(pageSize*numPages-vaddr))
    			length=pageSize*numPages-vaddr;
    			if(data.length-offset<length)
    			length=data.length-offset;
    			int transferredbyte=0;
    		do{
    			
    int pageNum=Processor.pageFromAddress(vaddr+transferredbyte);
    				if(pageNum<0||pageNum>=pageTable.length)
    				return 0;
    				int pageOffset=Processor.offsetFromAddress(vaddr+transferredbyte);
    			
    			int leftByte=pageSize-pageOffset;
    			
    			int amount=Math.min(leftByte, length-transferredbyte);
    			
    			int realAddress=pageTable[pageNum].ppn*pageSize+pageOffset;
    			
    			System.arraycopy(memory, realAddress, data,offset+transferredbyte, amount);
    			
    			transferredbyte=transferredbyte+amount;
    		}while(transferredbyte<length);
    		return transferredbyte;
    }
    public int writeVirtualMemory(int vaddr, byte[] data, int offset, int length) {
    		Lib.assertTrue(offset >= 0 && length >= 0 && offset + length <= data.length);
    		
    		byte[] memory = Machine.processor().getMemory();
    		
    		if(length>(pageSize*numPages-vaddr))
    			length=pageSize*numPages-vaddr;
    		
    		if(data.length-offset<length)
    			length=data.length-offset;
    		int	transferredbyte=0;
    		do{
    			
    			int pageNum=Processor.pageFromAddress(vaddr+transferredbyte);
    			if(pageNum<0||pageNum>=pageTable.length)
    				return 0;
    			
    			int pageOffset=Processor.offsetFromAddress(vaddr+transferredbyte);
    			
    			int leftByte=pageSize-pageOffset;
    			
    			int	amount=Math.min(leftByte, length-transferredbyte);
    			int realAddress=pageTable[pageNum].ppn*pageSize+pageOffset;
    			
    			System.arraycopy(data, offset+transferredbyte, memory, realAddress, amount);
    			
    			transferredbyte=transferredbyte+amount;
    		}while(transferredbyte<length);
    		return transferredbyte;
    }
    

    2.3.相关代码

    private int handleExec(int fileAddress,int argc,int argvAddress){
    		
    		String filename=readVirtualMemoryString(fileAddress, 256);
    		if(filename==null||argc<0||argvAddress<0||argvAddress>numPages*pageSize)
    			return -1;
    		String[] args=new String[argc];
    		for(int i=0;i<argc;i++)
    		{
    			byte[] argsAddress=new byte[4];
    			if(readVirtualMemory(argvAddress+i*4,argsAddress)>0)
    				args[i]=readVirtualMemoryString(Lib.bytesToInt(argsAddress, 0), 256);//?
    		}
    		
    		UserProcess process=UserProcess.newUserProcess();
    		process.parentProcess=this;
    		childProcess.add(process);
    		if(!process.execute(filename, args))
    				return -1;
    		for(int i=0;i<process.parentProcess.childProcess.size();i++) {
    			System.out.print(process.parentProcess.childProcess.get(i).pid+" ");
    		}
    		System.out.println();
    		return process.pid;
    	}
    	private int handleJoin(int pid,int statusAddress)
    	{
    		UserProcess process=null;
    		
    		for(int i=0;i<childProcess.size();i++){
    			if(pid==childProcess.get(i).pid)
    			{
    				process=childProcess.get(i);
    				break;
    			}
    		}
    		if(process==null)
    			return -1;
    		
    		process.joinLock.acquire();
    		process.joinCondition.sleep();
    		process.joinLock.release();
    		byte[] childstat = new byte[4];
    		for(int i=0;i<childProcess.size();i++) {
    			System.out.print(childProcess.get(i).pid+" ");
    		}
    		childstat=Lib.bytesFromInt(process.status);
    		int numWriteByte=writeVirtualMemory(statusAddress,childstat);
    		if(process.normalExit&&numWriteByte==4) {
    			System.out.println("join success");
    			return 1;}
    		return 0;
    	}
    private int handleExit(int status){
    		coff.close();
    		for(int i=0;i<16;i++){
    			if(openfile[i]!=null)	
    			{
    				openfile[i].close();
    				openfile[i]=null;
    			}
    		}
    		this.status=status;
    		normalExit=true;
    		if(parentProcess!=null){
    			joinLock.acquire();
    			joinCondition.wake();
    			joinLock.release();
    			parentProcess.childProcess.remove(this);
    		}
    		unloadSections();
    		if(numOfRunningProcess==1)
    			Machine.halt();
    		numOfRunningProcess--;
    		KThread.currentThread().finish();
    		System.out.println("exit success");
    		return 0;
    	}
    

    2.4.相关代码

    public int getEffectivePriority() {
    			
    		    // implement me
    					effectivepriority=priority;
    			for(int i=0;i<waitQueue.waitQueue.size();i++)
    			{
    					if(waitQueue.waitQueue.get(i).getEffectivePriority()>effectivepriority) {
    						effectivepriority=effectivepriority+waitQueue.waitQueue.get(i).getEffectivePriority();
    						}
    			}
    		    return effectivepriority;
    		    }
    		public void setPriority(int priority) {
    			
    		    if(this.priority == priority)
    			return;
    		    this.priority = priority;
    		}
    public KThread nextThread() {
    		    Lib.assertTrue(Machine.interrupt().disabled());
    		    // implement me 
    		    index=0;
    		    int max=0;
    		    int nownumber=0;
    		    ThreadState temp=null;
    		    KThread thread=null;
    		    while((temp=pickNextThread())!=null){	
    		    	max=max+temp.getEffectivePriority();
    //		    	System.out.println("现在是");
    		    }
    		    Random ran=new Random();
    
    		    int select=ran.nextInt(max+1);
    //		    
    		    select=select-1;
    //		    System.out.println("随机数是"+select);
    		    for(int i=0;i<waitQueue.size();i++) {
    		    	nownumber=nownumber+waitQueue.get(i).getEffectivePriority();
    		    	if(nownumber>=select) {
    		    		thread=waitQueue.get(i).thread;
    		    		break;
    		    	}
    		    }
    		    if(thread==null)
    		    	return null;
    		    else {
    		    	waitQueue.remove(thread.schedulingState);
    		    	return thread;
    		    }
    		}
    
    展开全文
  • 操作系统实验:模拟多道程序设计的运行,并且比较顺序执行和多道程序执行的所需要的时间。 程序的生命周期为:计算->IO操作->计算->结束 下面为C语言实现版本,模拟的三个程序单通道模式 /* * 多道程序设计...

    操作系统实验:模拟多道程序设计的运行,并且比较顺序执行和多道程序执行的所需要的时间。
    程序的生命周期为:计算->IO操作->计算->结束

    下面为C语言实现版本,模拟的三个程序单通道模式

    /*
    *   多道程序设计模拟
    *   作者:hjz
    *   时间:2020/11/8
    *
    *   本次为操作系统的实验,模拟了A,B,C三个程序的多道程序的执行,比较顺序执行和多道程序设计
    *                       程序执行的顺序为:计算->IO操作->计算->结束,分为三段
    *	例如:
    *	A先计算30ms,再io操作40ms,再计算10ms。
    *   B先计算60ms,再io操作30ms,再计算10ms。
    *   A先计算20ms,再io操作40ms,再计算20ms。
    *
    *   本次实验只模拟了三个程序和单通道模式
    */
    #include<stdio.h>
    #include<stdlib.h>
    #define true 1
    #define false 0
    #define CPU 2
    #define IO -1
    
    typedef struct {
    	char id;//任务名称
    	int cpu_time1;//第一次计算时间
    	int cpu_time2;//第二次计算时间
    	int io_time;//io操作时间
    	short flag;//第一次是否已计算完,计算完为1
    }pro;//程序结构体
    
    typedef struct{
    	pro* arr[3];//队列
    	int first;//队头
    	int last;//队尾
    	int n;//元素数量
    }queue;//队列
    
    queue cpu_q;//cpu队列
    queue io_q;//io队列
    
    void init(pro*,pro*,pro*);
    void input(pro*);
    void run_seq();
    void run_par();
    int enqueue(pro*,int);
    pro* dequeue(int);
    int empty(int);
    int full(int);
    int back(int,pro*);
    
    int main(){
    	pro* pro_a;
    	pro* pro_b;
    	pro* pro_c;
    	init(pro_a,pro_b,pro_c);
    	run_seq();
    	run_par();
    	return 0;
    }
    
    /*
    *   判定队列是否是空
    *
    *   参数:
    *       i:为1判定cpu队列,否则为io队列
    *   返回值:如果为空返回正数,否则返回0
    */
    int empty(int i){
    	if(i == CPU){
    		return cpu_q.n == 0;
    	}else{
    		return io_q.n == 0;
    	}
    }
    
    /*
    *   判定队列是否满
    *
    *   参数:
    *       i:为CPU判定cpu队列,否则为io队列
    *   返回值:如果满返回正数,否则返回0
    */
    int full(int i){
    	if(i == CPU){
    		return cpu_q.n == 3;
    	}else{
    		return io_q.n == 3;
    	}
    }
    
    /*
    *   入队操作
    *
    *   参数:
    *       p:要入队的程序
    *       i:为CPU入cpu队列,否则为io队列
    *   返回值:如果正常入队返回1,否则返回0
    */
    int enqueue(pro* p,int i){
    	if(full(i)) return false;
    	if(i == CPU){
    		cpu_q.arr[cpu_q.last] = p;
    		cpu_q.last = (cpu_q.last + 1) % 3;
    		cpu_q.n++;
    	}else{
    		io_q.arr[io_q.last] = p;
    		io_q.last = (io_q.last + 1) % 3;
    		io_q.n++;
    	}
    	return true;
    }
    
    /*
    *   出队操作
    *
    *   参数:
    *       i:为1出cpu队列,否则为io队列
    *   返回值:返回队头元素或NULL
    */
    pro* dequeue(int i){
    	if(empty(i)) return NULL;
    	pro* temp;
    	if(i == CPU){
    	 	temp = cpu_q.arr[cpu_q.first];
    	 	cpu_q.arr[cpu_q.first] = NULL;
    	 	cpu_q.first = (cpu_q.first + 1) % 3;
    	 	cpu_q.n--;
    	}else{
    		temp = io_q.arr[io_q.first];
    	 	io_q.arr[io_q.first] = NULL;
    	 	io_q.first = (io_q.first + 1) % 3;
    	 	io_q.n--;
    	}
    	return temp;
    }
    
    /*
    *   将元素添加到队列头
    *
    *   参数:
    *       i:为CPU则添加到cpu队列,否则添加到io队列
    *       p:要添加的任务
    *   返回值:添加成功返回1
    */
    int back(int i,pro* p){
    	if(full(i)) return false;
    	if(i == CPU){
    		cpu_q.first = (cpu_q.first - 1) % 3;
    		cpu_q.arr[cpu_q.first] = p;
    		cpu_q.n++;
    		return true;
    	}else{
    		io_q.first = (io_q.first - 1) % 3;
    		io_q.arr[io_q.first] = p;
    		io_q.n++;
    		return true;
    	}
    	return false;
    }
    
    /*
    *   程序计算时间和io时间初始化
    *
    *   参数:
    *       p:要被初始化的程序
    */
    void input(pro* p){
    	printf("请输入程序%c第一次计算的时间:",p->id);
    	scanf("%d",&(p->cpu_time1));
    	printf("请输入程序%c所需要的io时间:",p->id);
    	scanf("%d",&(p->io_time));
    	printf("请输入程序%c第二次计算的时间:",p->id);
    	scanf("%d",&(p->cpu_time2));
    	p->flag = 0;
    	putchar('\n');
    }
    
    /*
    *   队列和多道程序初始化
    *
    *   参数:
    *       a:被初始化程序1
    *       b:被初始化程序2
    *       c:被初始化程序3
    */
    void init(pro* a,pro* b,pro* c){
    	printf("---------程序初始化---------\n");
    	a = (pro*)malloc(sizeof(pro));
    	b = (pro*)malloc(sizeof(pro));
    	c = (pro*)malloc(sizeof(pro));
    	a->id = 'A';
    	b->id = 'B';
    	c->id = 'C';
    	input(a);
    	input(b);
    	input(c);
    	cpu_q.arr[0] = a;
    	cpu_q.arr[1] = b;
    	cpu_q.arr[2] = c;
    	cpu_q.first = 0;
    	cpu_q.last = 0;
    	cpu_q.n = 3;
    	io_q.first = 0;
    	io_q.last = 0;
    	io_q.n = 0;
    }
    
    /*
    *   顺序执行模式
    */
    void run_seq(){
    	printf("---------顺序执行模式---------\n");
    	int i,sum = 0;
    	for(i = 0;i < 3;i++){
    		printf("程序%c计算%dms,io%dms,计算%dms\n",
    			cpu_q.arr[i]->id,cpu_q.arr[i]->cpu_time1,cpu_q.arr[i]->io_time,cpu_q.arr[i]->cpu_time2);
    		sum = sum + cpu_q.arr[i]->cpu_time1 + cpu_q.arr[i]->io_time + cpu_q.arr[i]->cpu_time2;
    	}
    	putchar('\n');
    	printf("总耗时%dms\n",sum);
    }
    
    /*
    *   多道执行模式
    */
    void run_par(){
    	printf("---------多道程序模式---------\n");
    	pro* temp,*temp1;
    	int time,sum = 0;
    	
    	while(!empty(CPU)||!empty(IO)){
    		//如果io队列为空,则进行计算
    		if(empty(IO)){
    			temp = dequeue(CPU);
    			if(temp != NULL){
    				time = (temp->flag == 0) ? (temp->cpu_time1) : (temp->cpu_time2);
    				printf("程序%c计算%dms\n",temp->id,time);
    				sum += time;
    				if(temp->flag == 0) {//如果是第一次计算,放入io队列,否则该程序结束
    					temp->flag = 1;
    					enqueue(temp,IO);
    				}
    				else free(temp);
    				continue;
    			}
    			exit(0);
    		}
    		//如果cpu队列为空,则进行io调度,io调度完成后继续完成计算至程序结束
    		if(empty(CPU)){
    			temp = dequeue(IO);
    			if(temp != NULL){
    				printf("程序%c进行io%dms\n",temp->id,temp->io_time);
    				printf("程序%c计算%dms\n",temp->id,temp->cpu_time2);
    				sum = sum + temp->io_time + temp->cpu_time2;
    				free(temp);
    				continue;
    			}
    			exit(0);
    		}
    		
    		//如果io队列和cpu队列都不为空,则io操作和计算同时进行
    		temp = dequeue(CPU);
    		temp1 = dequeue(IO);
    		if(temp->flag == 0) time = temp->cpu_time1 - temp1->io_time;
    		else time = temp->cpu_time2 - temp1->io_time;
    		
    		if(time >= 0){
    			if(temp->flag == 0){
    				printf("程序%c计算%dms的同时,程序%c进行io%dms",temp->id,temp->cpu_time1,temp1->id,temp1->io_time);
    				sum += temp->cpu_time1;
    			}else{
    				printf("程序%c计算%dms的同时,程序%c进行io%dms",temp->id,temp->cpu_time2,temp1->id,temp1->io_time);
    				sum += temp->cpu_time2;
    			}
    			while(time > 0){//如果在io操作完成后,正在计算的程序还没完成计算,继续调度io队列中的下一个
    				int temp_time;
    				if(!empty(IO)){
    					pro* temp2 = dequeue(IO);
    					temp_time = temp2->io_time;
    					if(temp_time > time){//如果下一个io操作所需的时间过长,则先进行一段io操作,再放回队首,下次再调度
    						printf(",程序%c进行io%dms",temp2->id,time);
    						temp2->io_time = temp2->io_time - time;
    						back(IO,temp2);
    						break;
    					}
    					else{
    						printf(",程序%c进行io%dms",temp2->id,temp_time);
    						time -= temp_time;
    						enqueue(temp2,CPU);
    					}
    				}
    				break;
    			}
    			enqueue(temp1,CPU);
    			if(temp->flag == 0){
    				temp->flag = 1;
    				enqueue(temp,IO);//如果是第一次计算,则进入io队列
    			}
    			else free(temp);
    			putchar('\n');
    		}
    		else{
    			sum += temp1->io_time;
    			if(temp->flag == 0){
    				printf("程序%c计算%dms的同时,程序%c进行io%dms",temp->id,temp->cpu_time1,temp1->id,temp1->io_time);
    			}else{
    				printf("程序%c计算%dms的同时,程序%c进行io%dms",temp->id,temp->cpu_time2,temp1->id,temp1->io_time);
    			}
    			time = -time;
    			while(time > 0){//如果计算完成后,io操作还在继续,则继续调度cpu队列
    				int temp_time;
    				if(!empty(CPU)){
    					pro* temp2 = dequeue(CPU);
    					temp_time = (temp2->flag == 0) ? (temp2->cpu_time1) : (temp2->cpu_time2);
    					if(temp_time > time){
    						printf(",程序%c计算%dms\n",temp2->id,time);
    						if(temp2->flag == 0) temp2->cpu_time1 = temp2->cpu_time1 - time;
    						else temp2->cpu_time2 = temp2->cpu_time2 - time;
    						back(CPU,temp2);
    						break;
    					}
    					else{
    						printf(",程序%c计算%dms",temp2->id,temp_time);
    						time -= temp_time;
    						if(temp2->flag == 0){
    							temp2->flag = 1;
    							enqueue(temp2,CPU);
    						}
    						else free(temp2);
    					}
    				}
    				break;
    			}
    			enqueue(temp1,CPU);//完成io操作后调入cpu队列
    			if(temp->flag == 0){
    				temp->flag = 1;
    				enqueue(temp,IO);
    			}
    			else free(temp);
    			putchar('\n');
    		}
    	}
    	printf("总耗时%dms\n",sum);
    }
    
    

    注:该多道程序设计的时间并不是最优解,还可以进一步改进。

    展开全文
  • 本章内容分为三个部分:1和2、实验操作(以及实验中遇见的问题)3、源码分析。4、总结一、实验操作(part1)该项实验听着好像挺难的,但实际操作起来还是比较简单的,因为孟宁老师已经提供了相应的源码。第一部分的...

    383 + 原创作品转载请注明出处 + 中科大孟宁老师的linux操作系统分析:https://github.com/mengning/linuxkernel。

    本章内容分为三个部分:1和2、实验操作(以及实验中遇见的问题)3、源码分析。4、总结

    一、实验操作(part1)

    该项实验听着好像挺难的,但实际操作起来还是比较简单的,因为孟宁老师已经提供了相应的源码。

    第一部分的实验操作主要是讲述如何部署kernel内核。

    1)准备虚拟机和ubuntu操作系统(本人的是ubuntu16.04)。

    2)为了便于理解和管理,首先自己先创建一个文件夹:

    mkdir MyKernel

    3)做好事前准备,kernel内核linux-3.9.4:

    wget https://www.kernel.org/pub/linux/kernel/v3.x/linux-3.9.4.tar.xz

    以及孟宁老师的kernel补丁包mykernel_for_linux3.9.4sc.patch:

    wget https://raw.github.com/mengning/mykernel/master/mykernel_for_linux3.9.4sc.patch

    c22afcd6515b03c24fd6a0d13fd6554f.png

    (PS:先不管5.0版本,本文中不涉及该版本。)

    4)将内核解压并打上孟宁老师的补丁包(PS:上图可知,我已经进行了初步的解压,源文件为linux-3.9.4.tar.xz。解压指令为:xz -d linux-3.9.4.tar.xz):

    tar xvf linux-3.9.4.tar

    df4d4b4e95f74ceb71f17b63103ab013.png

    (PS:如果没在同一个文件夹下,需要移动到同一个文件夹下面,如下图所示)

    90d9ed3ce464eefd26d41ee9052a548d.png

    进入linux3.9.4文件夹下,开始打补丁包:

    patch -p1 > mykernel_for_linux3.9.4sc.patch

    4cd0246b690cddd025d53100c095db2b.png

    (PS:补丁就不详细说明了,patch文件中看源码可以看明白)

    5)编译:

    (复位)make allnoconfig

    95f3010d52bc293f639fd65181230031.png

    (PS:此处warning和note的提示先不管他)

    {

    此处可能会出现的问题:如果没有安装过bison(语法分析器)和flex(词法分析器)可能会报错。

    解决方案:sudo apt-get install flex bison

    }

    (编译)make

    {

    489bb8c2aaa43840d5ff023409cc0d0e.png

    此处的问题:因为linux-3.9.4是老版本的内核,没有compiler-gcc5.h。

    解决方案:将complier-gcc4.h拷贝给complier-gcc5.h。

    cd include/linux/

    cp compiler-gcc4.h compiler-gcc5.h

    然后再回到linux-3.9.4路径下进行编译

    }

    a584564bf07d55e6adbaf1e3d091c55a.png

    好了编译已经完成。

    6)安装qemu

    sudo apt-get install qemu

    安装完成qemu后可以测试之前的内核是否能够正常运行了。

    qemu -kernel arch/x86/boot/bzImage

    {

    此处可能出现的问题:No command ‘qemu’ found, did you mean...

    解决方案:将qemu-system添加链接到usr/bin目录下。

    sudo ln –s /usr/bin/qemu-system-i386 /usr/bin/qemu

    }

    54a93723e295bf129b22e111bf36d2d3.png

    弹窗显示上图,说明linux-3.9.4布置成功。

    补充、patch中到底做了些什么?

    从之前的图片中可以看出patch补丁主要修改了原kernel中的几个文件:time.c、timer.h、start_kernel.h、main.c、Makefile。

    以及添加了mykernel文件夹和几个文件:mymain.c、myinterrupt.c、Makefile。

    patch中主要修改的内容(均在linux-3.9.4文件夹下):

    1)arch/x86/kernel/time.c

    f3b4ba63565aa365ef87637fa114778a.png

    主要是在时钟终端函数中添加了自己的函数my_timer_handler()。(irq:Interrupt Request中断请求)

    2)申明外部函数:my_start_kernel(void)、my_timer_handler(void)

    915ec16955eeeb526a2a774ed7759758.png

    3)init/main.c

    794986610dace33a619987f8bd1f7786.png

    在原kernel内核初始化的时候同时添加自己的内核启动函数。

    4)原kernel中的Makefile

    94f203e9632722c011614dcada72a23e.png

    主要添加了mykernel文件夹,将自己的内核文件与原内核绑定在一起。

    5)mykernel文件夹中的内容

    89c5253d9cc5d1521d6001f2fdb5e720.png

    mykernel中的Makefile添加mymain.o和myinterrupt.o两个目标文件。

    5a884f1ad0f8017097b7cad7e807e7e6.png

    60bfd454f268077a13804264fa9ebfc3.png

    在myinterrupt.c中实现my_timer_handler函数。

    14f074c272b5dd8355bdaa19c2eab70d.png

    63c7c49f806e71b70d6e87f3ccdee97b.png

    在mymain.c中实现my_start_kernel函数。

    总结:这部分的补丁的目的就是在原kernel内核总添加自己的mykernel内核程序,以及自己的中断处理程序。

    二、实验操作(part2)

    第二部分的实验操作主要为时间转轮片的实现。

    此处因为孟宁老师已经提供了源码,直接拷贝替换到linux-3.9.4/mykernel/内编译运行就好了,此处不多做赘述(将会在第三部分进行具体的源码分析),下面展示运行结果。

    {

    此处会出现一个错误:

    409ad8d3016df2a54392e641f7372d9a.png

    主要原因就是孟宁老师的代码mypcb.h中的一个问题,编译会报错,稍微改下代码就行了。

    解决方案:

    31cf1e233896555c8361524697f6de09.png

    将上图的代码改成下图模式

    2758ff9d75fc8bf77db762c1d649bdd6.png

    }

    27a489a2f1b40ca2fdf6b11047963872.png

    91ab5c9a6a70a816362fa0c3868073f8.png

    总共有4个状态,process0-3,系统开始在process 0中运行,在出现my_timer_handler后跳转到process 1,之后在process 1中运行,在出现my_timer_handler后跳转到process 2,之后在process 2中运行,在出现my_timer_handler后跳转到process 3,之后在process 3中运行,在出现my_timer_handler后跳转到process 0,依次循环。

    三、源码分析

    此部分主要对第二部分的源码进行分析,为了更好地理解操作系统是如何工作的。(PS:直接上代码。)

    1)mypcb.h

    06c6f0c7164b8b069d56fa46f508a9fd.png

    mypcb.h中主要实现了进程的主体类(pcb:进程管理块)。

    2)mymain.c

    736e6a6406830d4e6f02e80661b9a0db.png

    此处定义了进程数量MAX_TASK_NUM=4的进程组以及当前进程my_current_task。

    c69823d132d4ccd01775c1f2e7b855ba.png

    (PS:这张图有点糊,将就下)

    首先定义初始化了第一个任务进程,这里可以看到thread.ip为进程函数,thread.sp为进程分配的栈顶指针,栈大小为2*1024。

    之后再初始化剩下三个任务进程,并将所有任务进程按照链表的方式进行链接(1->next=2,2->next=3...)。

    主要操作为最后一段的汇编代码(PS:C语言看的懂吧?我把内联汇编翻译成C语言来表示):

    {

    首先明确一些基本的内联汇编常识:

    内敛汇编中用%0,%1来标识变量,要在内敛汇编中使用寄存器%eax就必须再加一个%,即%%eax。

    }

    另外,在解释前先明确一点,每个task都具有一个进程的栈,此处标记第i个进程为stki,stki初始时栈顶指针为task[i].thread.sp,为了方便说明,此处从stki[0]开始,即栈顶指针指向stki[0]开始。

    {

    解释:

    "movl %1 %%espnt" ----> %esp=task[i].thread.sp(%esp = &stki[0])

    "pushl %1nt" ----> stki[1] = task[i].thread.sp(%esp = &stki[1])

    "pushl %0nt" ----> stki[2] = my_process(%esp = &stki[2])

    "retnt" ----> eip = stki[2] = my_process(%esp = &stki[1],补充说明:eip寄存器中存放的下一个CPU指令存放的内存地址,当CPU执行完当前的指令后,从EIP寄存器中读取下一条指令的内存地址,然后继续执行)

    总结:汇编实现的目的就是实现进程的操作。

    补充:此处汇编好像少了一条代码"popl %%ebp"---->%ebp=task[i].thread.sp(%ebp=&stki[0],%esp=&stki[0])进行堆栈的复位。虽然不进行复位也不会出什么问题。

    }

    439956ea0e72d20f18078e64195b4906.png

    这个是进程函数,即该函数地址赋值给了进程的thread.ip,可以通过调用thread.ip执行此函数操作。该函数的操作为,在没有中断的情况下打印“XXX... process i -”,在出现中断的时候执行中断处理my_schedule()并打印“XXX... process i +”。

    3)my_interrupt.c

    baa2410f8b3b090ce888e31a34fbf984.png

    申明外部变量task数组和my_current_task,时钟中断处理标志位my_need_sched,每当发生时钟中断的时候就把my_need_sched值置为1,并使当前的task执行my_schedule()。

    83246411b2570eb7e67fcdb56188415e.png

    my_schedule()函数操作,主要实现了时间片轮转。非汇编部分主要是初始化定义了next和prev两个进程。汇编部分内容主要是实现prev进程和next进程的调度工作。

    主要内容为汇编代码:

    "pushl %%ebpnt" ----> 将当前的prev的%ebp保存,保存现场操作

    "movl %%esp, %0nt" ----> prev->thread.sp=%esp,将prev的%esp保存到prev的栈顶中,保存现场操作。

    "movl %2, %%espnt" ----> %esp=next->thread.sp,使%esp指向next栈的栈顶,切换进程。

    "movl $1f, %1nt" ----> 向前找标签1的地址,就是prev进程的开始执行的地址,并将其赋值给prev->thread.ip,即重置当前的prev的指令地址。

    "pushl %3nt" ----> 将next->thread.ip入栈,即将下一个进程的函数地址入栈,切换进程。

    "retnt" ----> eip = next->thread.ip,即接下来执行next进程。

    "1:t" ----> 此句的目的是为next进程的指令地址打上标签,为之后切换进程做准备。

    "popl %%ebpnt" ----> %ebp=task[i].thread.sp,即进行栈复位,准备开始next进程。

    四、总结

    对这次实验进行一次总结,我本身稍微懂一点汇编,但是因为对内联汇编的不熟悉所以刚开始看代码的时候经常理解错。本门课程对我来说还是有很多学习的意义的。本次实验的重点就是理解时间转轮片中断和my_schedule()函数中进程的调度机制,即如何利用时间转轮片的中断机制以及寄存器和堆栈的使用进行保存现场和恢复,最终实现操作系统进程的切换。

    展开全文
  • 程序设计思维实验 week2 整体感受 感觉实验题目难度挺合适,有点挑战性却又不是特别困难。三题整体用时大约5个小时,其中有很大部分卡在了B题疯狂报PE上。 三题都是小模拟题,感觉个人解题的时候关键在于如何...

    程序设计思维实验 week2

    整体感受

    感觉实验题目难度挺合适,有点挑战性却又不是特别困难。三道题整体用时大约5个多小时,其中有很大部分卡在了B题疯狂报PE上。
    三道题都是小模拟题,感觉个人解题的时候关键在于如何区分出不同的情况以便进行不同的后续操作(输出)。区分的时候需要仔细观察题目sample输入的特征。

    Problem A

    1.题目概述

    假设如下图,这个烷烃基有6个原子和5个化学键,6个原子分别标号1~6,然后用一对数字 a,b 表示原子a和原子b间有一个化学键。这样通过5行a,b可以描述一个烷烃基。
    烷烃及其类别
    你的任务是甄别烷烃的类别。

    2.Input

    输入第一行为数据的组数T(1≤T≤200000)。每组数据有5行,每行是两个整数a, b(1≤a,b≤6,a ≤b)

    数据保证,输入的烷烃基是以上5种之一。

    3.Output

    每组数据,输出一行,代表烷烃基的英文名。

    4.Example

    Input
    2
    1 2
    2 3
    3 4
    4 5
    5 6
    1 4
    2 3
    3 4
    4 5
    5 6

    Output
    n-hexane
    3-methylpentane

    5.整体解题思路

    分辨不同烷烃的主要依据是每个原子上接的化学键个数。例n-hexane有四个接了两个化学键的原子,两个接了一个化学键的原子。同理,2,3 和2,2 型烷烃也有唯一标示特征。如果是methylpentane,首先找到接了三个化学键的原子,然后判断与该原子相连的原子所接的化学键个数,若有两个只接了一个化学键的原子则为2-methylpentane,否则为3-methylpentane。

    6.代码

    #include <iostream>
    using namespace std;
    //设置point 类储存原子
    class point
    {
    public:
        point()
        {
            num=0;
            nlink=0;
            p=new int[4];
        }
        void link(point* n)
        {
            p[nlink]=n->num;
            nlink++;
        }
    public:
        int num=0;//原子序号
        int nlink=0;//原子接的化学键个数
        int *p;//相连原子的序号
    };
    int main()
    {
        int n;
        cin>>n;
        for(int i=0;i<n;i++)
        {
            point* q;
            q=new point[6];
            for(int j=0;j<6;j++)
            {
                q[j].num=j+1;
            }
            
            //原子与原子之间进行连接
            for(int j=0;j<5;j++)
            {
                int m1,m2;
                cin>>m1;
                cin>>m2;
                point* p1=&q[m1-1];
                point* p2=&q[m2-1];
                q[m1-1].link(p2);
                q[m2-1].link(p1);
            }
            
            //分别计算含有2,3,4个化学键的原子个数
            int tw=0,th=0,fo=0;
            int pth=0;
            for(int j=0;j<6;j++)
            {
                if(q[j].nlink==2)
                    tw++;
                else if(q[j].nlink==3)
                {
                    th++;
                    pth=j;
                }
                else if(q[j].nlink==4)
                    fo++;
            }
            //有唯一标示的情况可以直接判定输出
            if(tw==4)
                cout<<"n-hexane"<<endl;
            else if(th==2)
                cout<<"2,3-dimethylbutane"<<endl;
            else if(fo==1)
                cout<<"2,2-dimethylbutane"<<endl;
            //如果为3
            else if(th==1)
            {
                int tmp=0;
                for(int j=0;j<3;j++)
                {
                    int t=q[pth].p[j]-1;
                    if(q[t].nlink==1)
                        tmp++;
                }
                if(tmp==1)
                    cout<<"3-methylpentane"<<endl;
                else
                    cout<<"2-methylpentane"<<endl;
            }
        }
        return 0;
    }
    

    Problem B

    1.题目概述

    模拟题目评测系统。例如某次考试一共八道题(A,B,C,D,E,F,G,H),每个人做的题都在对应的题号下有个数量标记,负数表示该学生在该题上有过的错误提交次数但到现在还没有AC,正数表示AC所耗的时间,如果正数a跟上了一对括号,里面有个正数b,则表示该学生AC了这道题,耗去了时间a,同时曾经错误提交了b次。例子可见下方的样例输入与输出部分。

    2. Input

    输入数据包含多行,第一行是共有的题数n(1≤n≤12)以及单位罚时m(10≤m≤20),之后的每行数据描述一个学生的信息,首先是学生的用户名(不多于10个字符的字串)其次是所有n道题的得分现状,其描述采用问题描述中的数量标记的格式,见上面的表格。

    3.Output

    根据这些学生的得分现状,输出一个实时排名。实时排名显然先按AC题数的多少排,多的在前,再按时间分的多少排,少的在前,如果凑巧前两者都相等,则按名字的字典序排,小的在前。每个学生占一行,输出名字(10个字符宽),做出的题数(2个字符宽,右对齐)和时间分(4个字符宽,右对齐)。名字、题数和时间分相互之间有一个空格。数据保证可按要求的输出格式进行输出

    4.Example

    Input

    8 20
    GuGuDong 96 -3 40(3) 0 0 1 -8 0
    hrz 107 67 -3 0 0 82 0 0
    TT 120(3) 30 10(1) -3 0 47 21(2) -2
    OMRailgun 0 -99 -8 0 -666 -10086 0 -9999996
    yjq -2 37(2) 13 -1 0 113(2) 79(1) -1
    Zjm 0 0 57(5) 0 0 99(3) -7 0

    Output

    TT 5 348
    yjq 4 342
    GuGuDong 3 197
    hrz 3 256
    Zjm 2 316
    OMRailgun 0 0

    5.整体思路

    首先观察输入信息,每个题的做题情况如果第一个字符是‘-’或‘0‘可以不用管,继续读取下一道题的做题情况。其他情况的话首先做出题数+1,再判断是否有’(‘,如果没有直接将字符转化为数值存进time,如果有再找到’)‘,将中间的字符转化为数值加进time。多值排序时才用冒泡法。

    6.代码

    #include<iostream>
    #include<string>
    #include<vector>
    #include<cmath>
    #include<algorithm>
    #include<iomanip>
    using namespace std;
    
    //将字符变为数值
    int change(string s)
    {
        int size=s.size();
        int result=0;
        for(int i=0;i<size;i++)
        {
            int m=s[i]-48;
            result+=(m*pow(10,size-i-1));
        }
        return result;
    }
    
    //member记录每位参赛者
    
    class member
    {
    public:
        member()
        {}
        member(string name,int n,int penalty)
        {
            _n=n;
            _penalty=penalty;
            _name.append(name);
        }
        void addscore()
        {
            for(int i=0;i<_n;i++) {
                int target1 = 0, target2 = 0;
                string s;
                cin >> s;
                if (s[0] == '-' || s[0] == '0') continue;
                else {
                    score++;
                    for (int j = 0; j < s.size(); j++)
                    {
                        if (s[j] == '(') target1 = j;
                    }
                    if (target1 == 0) {
                        time += change(s);
                    }
                    else {
                        string s1(s, 0, target1);
                        string s2(s, target1 + 1);
                        s2.pop_back();
                        time += change(s1);
                        time += _penalty * change(s2);
                    }
                }
            }
        }
        inline bool operator < (const member &x) const
        {
            if((score>x.score)
               ||((score==x.score)&&(time<x.time))
               ||((score==x.score)&&(time==x.time)&&(_name[0]<x._name[0])))
                return true;
            else
                return false;
        }
    public:
        int _n;
        int _penalty;
        string _name;
        int score=0;
        int time=0;
    };
    
    int main() {
        int n, penalty;
        cin >> n;
        cin >> penalty;
        vector<member> MemberList;
        string name;
        int tmp=0;
        while (cin >> name) {
            if(cin.get()=='\n') break;
            member P(name, n, penalty);
            P.addscore();
            MemberList.push_back(P);
            tmp++;
        }
        sort(&MemberList,&MemberList+tmp);
        for(int i=0;i<MemberList.size();i++)
        {
            cout<<left<<setw(10)<<MemberList[i]._name<<' '<<right<<setw(2)<<MemberList[i].score<<' '<<right<<setw(4)<<MemberList[i].time<<endl;
        }
        return 0;
    }
    

    Problem C

    写了4800+length的题…(我也很无奈啊

    1.问题描述

    模拟四个人打扑克摸牌并排序的过程。
    游戏一共由一副扑克,也就是52张构成。开始,我们指定一位发牌员(东南西北中的一个,用英文首字母标识)开始发牌,发牌顺序为顺时针,发牌员第一个不发自己,而是发他的下一个人(顺时针的下一个人)。这样,每个人都会拿到13张牌。
    定义牌的顺序,首先,花色是(梅花)<(方片)<(黑桃)<(红桃),(输入时,我们用C,D,S,H分别表示梅花,方片,黑桃,红桃,即其单词首字母)。对于牌面的值,我们规定2 < 3 < 4 < 5 < 6 < 7 < 8 < 9 < T < J < Q < K < A。
    要求从小到大排序每个人手中的牌,并按照给定格式输出。

    2.Input

    输入包含多组数据
    每组数据的第一行包含一个大写字符,表示发牌员是谁。如果该字符为‘#’则表示输入结束。
    接下来有两行,每行有52个字符,表示了26张牌,两行加起来一共52张牌。每张牌都由两个字符组成,第一个字符表示花色,第二个字符表示数值。

    3.Output

    每组数据应该由24行的组成,输出按照顺时针方向,始终先输出South Player的结果,每位玩家先输出一行即玩家名称(东南西北),接下来五行,第一行和第五行输出固定格式(见样例),第二行和第四行按顺序和格式输出数值(见样例),第三行按顺序和格式输出花色(见样例)。

    4.Example

    Input

    N
    CTCAH8CJD4C6D9SQC7S5HAD2HJH9CKD3H6D6D7H3HQH4C5DKHKS9
    SJDTS3S7S4C4CQHTSAH2D8DJSTSKS2H5D5DQDAH7C9S8C8S6C2C3

    Output

    South player:
    ±–±--±–±--±–±--±–±--±–±--±–±--±–+
    |6 6|A A|6 6|J J|5 5|6 6|7 7|9 9|4 4|5 5|7 7|9 9|T T|
    | C | C | D | D | S | S | S | S | H | H | H | H | H |
    |6 6|A A|6 6|J J|5 5|6 6|7 7|9 9|4 4|5 5|7 7|9 9|T T|
    ±–±--±–±--±–±--±–±--±–±--±–±--±–+
    West player:
    ±–±--±–±--±–±--±–±--±–±--±–±--±–+
    |2 2|5 5|9 9|K K|5 5|7 7|9 9|4 4|T T|J J|A A|8 8|A A|
    | C | C | C | C | D | D | D | S | S | S | S | H | H |
    |2 2|5 5|9 9|K K|5 5|7 7|9 9|4 4|T T|J J|A A|8 8|A A|
    ±–±--±–±--±–±--±–±--±–±--±–±--±–+
    North player:
    ±–±--±–±--±–±--±–±--±–±--±–±--±–+
    |3 3|4 4|J J|2 2|3 3|T T|Q Q|K K|8 8|Q Q|K K|2 2|3 3|
    | C | C | C | D | D | D | D | D | S | S | S | H | H |
    |3 3|4 4|J J|2 2|3 3|T T|Q Q|K K|8 8|Q Q|K K|2 2|3 3|
    ±–±--±–±--±–±--±–±--±–±--±–±--±–+
    East player:
    ±–±--±–±--±–±--±–±--±–±--±–±--±–+
    |7 7|8 8|T T|Q Q|4 4|8 8|A A|2 2|3 3|6 6|J J|Q Q|K K|
    | C | C | C | C | D | D | D | S | S | H | H | H | H |
    |7 7|8 8|T T|Q Q|4 4|8 8|A A|2 2|3 3|6 6|J J|Q Q|K K|
    ±–±--±–±--±–±--±–±--±–±--±–±--±–+

    5.整体思路

    首先对每个玩家的牌进行录入,为了区分不同的花色,对C D S H四种花色分别设置0,100,200,300的附加值,加在卡牌本身数值上,用于排序时候比较大小。
    在指定一名玩家后,计算与south的偏差值(weight),南西北东分别设置为3 2 1 0;进行输出时,第i次输出的是第(i+weight)%4 卡牌组。

    6.代码

    #include<iostream>
    #include<vector>
    #include<string>
    #include<cstring>
    #include<algorithm>
    using namespace std;
    class cards
    {
    public:
        cards()
        {
            _Pval='C';
            _val=0;
            _addition=0;
            _variety='C';
            waterfall=0;//记录用于排序时的权值
        }
        cards(char addition,char val)
        {
            //设置数值
            _Pval=val;
            //设置花色
            _variety=addition;
            //根据花色设置附加值
            switch(addition) {
                case 'C': {
                    _addition = 0;
                    break;
                }
                case 'D': {
                    _addition = 100;
                    break;
                }
                case 'S': {
                    _addition = 200;
                    break;
                }
                case 'H': {
                    _addition = 300;
                    break;
                }
                default : break;
            }
            //将字符转换成数值
            if(val>=50&&val<=57)//2-9
            {
                _val=val-48;
            }
            else
            {
                switch(val) {
                    case 'T': {
                        _val = 10;
                        break;
                    }
                    case 'J': {
                        _val = 11;
                        break;
                    }
                    case 'Q': {
                        _val = 12;
                        break;
                    }
                    case 'K': {
                        _val = 13;
                        break;
                    }
                    case 'A': {
                        _val = 14;
                        break;
                    }
                    default : break;
                }
            }
            //计算waterfall用于排序计算
            waterfall=_val+_addition;
        }
        inline bool operator < (const cards &x) const 
        {
            return waterfall>x.waterfall;
        }
    public:
    
        int _val;
        int _addition;
        int waterfall;
        char _variety;
        char _Pval;
    };
    void Vsort(int k,vector<cards> &List)
    {
        sort(&List,&List+13);
        switch(k)
        {
            case 0:
            {
                cout << "South player:" << endl;
                break;
            }
            case 1:
            {
                cout << "West player:" << endl;
                break;
            }
            case 2:
            {
                cout << "North player:" << endl;
                break;
            }
            case 3:
            {
                cout << "East player:" << endl;
                break;
            }
            default: break;
    
        }
        cout << "+---+---+---+---+---+---+---+---+---+---+---+---+---+" << endl;
        for (int j = 0; j < 13; j++)
        {
            cout << "|" << List[j]._Pval << ' ' << List[j]._Pval;
        }
        cout << '|' << endl;
        for (int j = 0; j < 13; j++) {
            cout << "|" << ' ' << List[j]._variety << ' ';
        }
        cout << '|' << endl;
        for (int j = 0; j < 13; j++) {
            cout << "|" << List[j]._Pval << ' ' << List[j]._Pval;
        }
        cout << '|' << endl;
        cout << "+---+---+---+---+---+---+---+---+---+---+---+---+---+" << endl;
    
    }
    int main()
    {
        char position;
        while(cin>>position)
        {
            if(position=='#') break;
            vector<vector<cards>> handsin(4);
            int weight;
            switch(position) {
                case 'S': {
                    weight = 3;
                    break;
                }
                case 'W': {
                    weight = 2;
                    break;
                }
                case 'N': {
                    weight = 1;
                    break;
                }
                case 'E': {
                    weight = 0;
                    break;
                }
                default : {
                    weight=-1;
                    break;
                }
            }
            string str1;
            string str2;
            cin>>str1;
            cin>>str2;
            //发牌
            for(int i=0,j=1;i<str1.size()&&j<str1.size();i=i+2,j=j+2)
            {
                int tmp=((i%8)/2);
                cards newcard(str1[i],str1[j]);
                handsin[tmp].push_back(newcard);
            }
            for(int i=0,j=1;i<str2.size()&&j<str2.size();i=i+2,j=j+2)
            {
                int tmp=(((i%8)/2)+2)%4;
                cards newcard(str2[i],str2[j]);
                handsin[tmp].push_back(newcard);
            }
            //排序
            for(int i=0;i<4;i++)
            {
                int ch=(i+weight)%4;
                Vsort(i,handsin[ch]);
            }
            cout<<endl;
        }
        return 0;
    }
    
    展开全文
  • 掌握在程序中创建新进程的方法, 观察并理解多道程序并发执行的现象。 三、实验原理 fork():建立子进程。子进程得到父进程地址空间的一个复制。 返回值:成功时,该函数被调用一次,但返回两次,fork()对子进程...
  • 华师 PTA 2020程序设计基础实验作业题目集 编程题 #10 AC 不同的是加了许多的要求 要求漏斗的组成不再只是“*”,而是由用户输入决定的 要求的n个符号,并不一定能正好组成一个沙漏 要求打印出的沙漏能用掉尽可能...
  • 题是一个隐形的BFS题目,有其他解法,但是为了配合实验要求,我还是选用 BFS,代码看起来很长,但是只是将八种情况一一分类. 每回我们对当前状态有八种选择: 1往x灌水 2.往y灌水 3.x倒空 4. y倒空 5 y未满 , x->y ...
  • 陈巧然 原创作品 转载请注明出处 《Linux内核分析...一、使用实验楼的虚拟机, 观察只有一个死循环的mykernel与时钟中断的关系 步骤:cd LinuxKernel/linux-3.9.4 qemu -kernel arch/x86/boot/bzImage 执行效果如...
  • (2)进行程序设计的训练。 2.实验要求 用高级语言编写一个或个作业调度的模拟程序。 单批处理系统的作业调度程序。作业一投入运行,它就占有计算机的一切资源直到作业完成为止,因此调度作业时不必考虑它所...
  • (2)进行程序设计的训练。 二、 实验内容和要求 用高级语言编写一个或个作业调度的模拟程序。 单批处理系统的作业调度程序。作业一投入运行,它就占有计算机的一切资源直到作业完成为止,因此调度作业时...
  • (2)进行程序设计的训练。 二、 实验内容和要求 用高级语言编写一个或个作业调度的模拟程序。 单批处理系统的作业调度程序。作业一投入运行,它就占有计算机的一切资源直到作业完成为止,...
  • (2)进行程序设计的训练。 二、实验内容和要求 用高级语言编写一个或个作业调度的模拟程序。 单批处理系统的作业调度程序。作业一投入运行,它就占有计算机的一切资源直到作业完成为止,因此调度作业时不....
  • (2)进行程序设计的训练。 二、实验内容和要求 实验内容 根据指定的实验课题,完成设计、编码和调试工作,完成实验报告。 实验要求 用高级语言编写一个或个作业调度的模拟程序。 单批处理系统的作业调度...
  • (2)进行程序设计的训练。 2.实验要求 用高级语言编写一个或个作业调度的模拟程序。 单批处理系统的作业调度程序。作业一投入运行,它就占有计算机的一切资源直到作业完成为止,因此调度作业时不必考虑它所...
  • 不断更新左右区间,直到无法更新为止,在 51Nod 上见过一道类似的问题,不过那题只需要一遍(update() + update_())即可解决,而这个问题涉及到两个更新函数可能会互相影响彼此,所以需要次更新,直到无法更新...
  • (2)进行程序设计的训练。 2.实验要求 用高级语言编写一个或个作业调度的模拟程序。 单批处理系统的作业调度程序。作业一投入运行,它就占有计算机的一切资源直到作业完成为止,因此调度作业时不必考虑它所...
  • (2)进行程序设计的训练。 二、 实验内容和要求 实验内容 根据指定的实验课题,完成设计、编码和调试工作,完成实验报告。 实验要求 用高级语言编写一个或个作业调度的模拟程序。 单批处理系统的作业调度...

空空如也

空空如也

1 2 3 4 5 ... 15
收藏数 299
精华内容 119
关键字:

多道程序设计实验