山东大学操作系统个人报告软件八班杨环.docx
《山东大学操作系统个人报告软件八班杨环.docx》由会员分享,可在线阅读,更多相关《山东大学操作系统个人报告软件八班杨环.docx(28页珍藏版)》请在冰点文库上搜索。
山东大学操作系统个人报告软件八班杨环
操作系统课程设计个人报告
201100300268-杨环
第一部分建立线程系统:
1
TASK1.11
TASK1.23
TASK1.35
TASK1.46
TASK28
TASK2.110
TASK2.213
TASK2.317
总结19
第一部分建立线程系统
在解决phrase1之前,先研究代码
TASK1.1
[任务]
实现KThread.join()
当前线程a在运行,执行b.join(),则a阻塞,直到线程b结束,a继续执行。
几个重要的方法
禁止中断机制的实现
Interrupt类有一个boolean型变量enabled,其值true时,表示允许中断,false不允许中断。
一般方法不希望执行过程中被中断就在方法
开始处添加booleanintStatus=Machine.interrupt().disable();
结束处添加Machine.interrupt().restore(intStatus);
关中断disable()只有一句returnsetStatus(false)设置interrupt状态为false,并且以前的状态保存在intstatus,开中断处restore(intStatus)就是将enabled值设为intStatus;这样就实现了开关中断的过程。
setStatus(booleanstatus)方法还模拟了系统内的时间“前进”,
当interrupt的状态从不可行变为可行,即关中断到开中断,模仿时间前进:
tick(true)。
KThread.sleep()当前线程没有结束,就将其状态设为”阻塞”,通过调度器类从就绪队列中选择下一个执行的进程,选择过程又与调度器种类与策略有关。
Lib.assertTrue(s)Lib里面是一些写好了的函数库,Lib.assertTrue如果括号内语句为false,则抛出一个异常.
抽象类threadqueue有waitForAccess(KThreadthread)和acquire(KThreadthread)两个抽象方法,threadqueue我是这样理解的:
一个线程队列等待着某个资源,所以每个临界资源可以用当前等待着的线程队列来指代,waitForAccess(t)说明t也加入到该资源的等待队列了,acquire(t)则表示t已经得到这个资源了。
抽象类Scheduler里有个方法newThreadQueue(booleantransferPriority)该方法构造了一个线程队列,调度器在线程等待队列选择下一个可获得资源访问权限时需要使用一个参数,姑且称为“优先级”,优先级高的可得到资源,这会导致饥饿,如cpu也是一个资源,就绪队列等待cpu资源,如果ABC三个线程优先级分别是321,B等待着C所占有的一个资源,C只有运行结束才释放这个B等代着的资源,C当前拥有cpu,当根据普通优先级调度方法它无法获得CPU,进而B也无法执行,所以就约定当前获得CPU线程优先级可以直接设为不小于等待队列中最大的优先级,以便于优先级小的线程快点结束释放其拥有的资源
[代码]
在KThread.java中:
privateThreadQueuejoinQueue=null;
每个kthread对象都有自己的joinQueue,由由对本线程调用join方法的其他线程对象构成,可“捐赠”优先级
privatebooleanJoined=false;
布尔形变量joined,判断本线程是否被其他线程调用过join方法,完善finish()方法时会用到
publicbooleanIsAlive(){
if(this.status==statusNew||status==statusReady||
status==statusRunning||status==statusBlocked)
returntrue;
elsereturnfalse;
}
一个简单的判断线程是否结束的方法,Kthread有五种状态,只要状态不为finished,就返回true
publicvoidjoin(){
Lib.debug(dbgThread,"Joiningtothread:
"+toString());
Lib.assertTrue(this!
=currentThread);
if(this.status==statusFinished)return;
booleanintStatus=Machine.interrupt().disable();//关中断
this.hasBeenJoined=true;//设置join标志,在finish方法中使用
if(this.joinQueue==null){
this.joinQueue=ThreadedKernel.scheduler.newThreadQueue(true);this.joinQueue.acquire(this);//新建一个可转让优先级的线程队列joinqueue,调用join方法的进程直接拥有该队列的最高优先级
}
this.joinQueue.waitForAccess(KThread.currentThread());
//currentThread()等待在队列上
KThread.sleep();
Machine.interrupt().restore(intStatus);
}
publicstaticvoidfinish(){
Machine.autoGrader().finishingCurrentThread();
if(currentThread.Joined){
currentThread.joinQueue.nextThread().ready();
}
//currentThread结束前检查Joined标志,有等待线程的就选择一个加入就绪队列
Lib.assertTrue(toBeDestroyed==null);
toBeDestroyed=currentThread;
currentThread.status=statusFinished;
sleep();
//执行就绪队列下个线程
}
在join类测试代码里
创建AThread和Bthread两个线程,AThread循环打印“AThread循环第..次”语句,Bthread开始打印“B_thread就绪”语句,
中间执行AThread。
Join()方法,
最后打印“B_thread执行结束”语句。
根据结果可以验证基本实现了join()方法
TASK1.2
用允许/屏蔽中断的方法实现条件变量
Condition类中已有利用信号量实现的条件变量,我们需要实现不依靠信号变量的实现,Condition最重要的部分是对Lock类的使用,
Lock可被视为线程运行必需的“资源”,拥有lock资源的线程才能访问一些临界资源,即不能被多线程同时访问或修改的资源,lock对象拥有一个ThreadQueuewaitQueue,且优先级转让标志为true,这意味着获得lock的线程不会因为优先级问题失去该lock。
Lock.release()方法让当前拥有锁的线程放弃锁,通过lockHolder=waitQueue.nextThread()来实现。
Lock.acquire()方法要求得到锁,若要求时锁没被其他线程拥有,则调用acquire()方法的线程直接得到锁,否则将调用acquire()方法的线程加到lock对象的waitQueue中等待。
Condition2类也有一个waitQueue,用来存放等待在条件变量上的线程,sleep方法的核心是在conditionLock.release();
KThread.sleep();//
conditionLock.acquire();过程中,线程调用Condition2.sleep()方法后,失去锁,阻塞在conditionlock这个资源上,要acquire()才能结束sleep()方法。
condition.Wake()只能被拥有conditionLock资源的线程执行,故可实现一个线程等待"条件变量的条件成立"而挂起;另一个线程使"条件成立";互斥锁的使用为了防止竞争,与条件变量结合在一起。
publicclassCondition2{
publicCondition2(LockconditionLock){
this.conditionLock=conditionLock;
waitQueue=newLinkedList();
}
publicvoidsleep(){
Lib.assertTrue(conditionLock.isHeldByCurrentThread());
booleanintStatus=Machine.interrupt().disable();//关中断waitQueue.add(KThread.currentThread());
//当前线程被添加到条件变量的等待队列上
conditionLock.release();//释放锁
KThread.sleep();//线程状态设为阻塞
conditionLock.acquire();//要求锁,这是线程阻塞的原因
Machine.interrupt().restore(intStatus);//开中断
}
publicvoidwake(){
Lib.assertTrue(conditionLock.isHeldByCurrentThread());
//只能被拥有conditionLock资源的线程执行
booleanintStatus=Machine.interrupt().disable();//关中断waitQueue.remove().ready();
//直接将waitQueue里的线程移出并将其状态设为ready
Machine.interrupt().restore(intStatus);//开中断
}
publicvoidwakeAll(){
Lib.assertTrue(conditionLock.isHeldByCurrentThread());
while(!
waitQueue.isEmpty())
wake();
}
//利用while循环将waitqueue里所有线程“唤醒”
privateLockconditionLock;
privateLinkedListwaitQueue;
}
在Condition2测试方法里
创建共有条件变量c2test,一个临界资源count和三个线程,thread1,thread2,thread3,初始化三个线程后thread1,thread2调用c2test.sleep()后开始“睡眠”,thread3调用c2test.wakeAll()唤醒所有线程,thread1,thead2开始交替访问临界资源count并更改其“余额”数值。
根据结果可以验证基本实现了join()方法
TASK1.3
完成Alarm类中的waitUntil方法
Time类模拟时钟中断。
Nachos虚拟机可以如同实际的硬件一样,每隔一定的时间会发生一次时钟中断,scheduleInterrupt()方法里有句delay+=Lib.random(delay/10)-(delay/20);相当于设置下次中断的时间增加了随机因子,因为对nachos主控模块里的线程切换没有研究很深,暂且不提。
每次的时钟中断都会使用时钟中断处理程序。
Alarm类有alarmqueue用来保存睡眠的线程,组成对象为AlarmThread
为了给每个线程绑定“醒来时间”,创建了一个新的对象AlarmThread
{KThreadwaitThread;
//privateConditiontimecondition;
privatelongwakeTime;//醒来时间}
同时重写中断处理程序,从alarmqueue中选择一个alarmthread,比较系统当前时间和waketime,系统时间是通过timer().getTime()得到的,当前时间大于waketime,则在时钟回调函数中(大约每500个时钟间隔调用一次)则依次检查队列中的每个三元组.元组移出队列并对元组中相应线程状态值设为ready();
publicvoidwaitUntil(longx){
booleanintStatus=Machine.interrupt().disable();//关中断
longwakeTime=Machine.timer().getTime()+x;//设置唤醒时间
Locklock=newLock();
Conditioncon=newCondition(lock);
AlarmThreadthread=newAlarmThread(KThread.currentThread(),wakeTime,con);//调用waitutil方法线程被装进alarmthread
alarmqueue.add(thread);
KThread.sleep();
Machine.interrupt().restore(intStatus);//开中断
}
在测试方法里
创建5个线程,依次“睡眠”20000ticks,线程醒来后各自打印出睡眠开始时间,要求睡眠时间,醒来时间,以及实际睡眠时间。
可以发现线程的实际睡眠时间并不等于要求的睡眠时间。
TASK1.4
Communicator类很像一个管程,它利用条件变量实现多个进程之间的同步。
用条件变量实现Communicator类中的speaker()和listen()函数一个锁lock
两个条件变量speaker(lock),listener(lock)用来用来控制听说动作,
Message变量用来存储speaker的消息,每个Communicator有一个锁lock(保证操作的原子性)和与该锁联系的两个条件变量用于保证speaker和listener间的同步.在speak函数中,首先检查若已经有一个speaker在等待(message变量)或无listener等待,则挂起.否则设置message变量,准备数据并唤醒一个listener.在listen函数中,增加一个listener后,若speaker数目非零且listener数目为1(及恰好可以配对)首先唤醒speaker,然后将自己挂起以等待speaker准备好数据再将自己唤醒.这个问题其实是一个缓冲区长度为0的生产者/消费者问题。
Speaker方法listener方法
publicclassCommunicator{
publicCommunicator(){
lock=newLock();
speaker=newCondition(lock);
listener=newCondition(lock);
speakersize=0;
listenersize=0;
}
publicvoidspeak(intword){
lock.acquire();
while(speakersize!
=0)
{speaker.sleep();}
this.Message=word;
speakersize++;
while(listenersize==0)
{speaker.sleep();}
listener.wake();
speakersize--;
speaker.wake();
lock.release();
}
publicintlisten(){
//intmyMessage=0;
lock.acquire();
listenersize++;
if(listenersize==1&&speakersize!
=0)
speaker.wake();
//speaker.wake();
listener.sleep();
//pair.wake();
intmyMessage=this.Message;
listenersize--;
lock.release();
returnmyMessage;
}
intspeakersize,listenersize;
intMessage;
Conditionspeaker,listener;
privateLocklock;
}
TASK2
本阶段需要测试真正意义上的程序(由MIPS-C编译器编译出的二进制指令).使用的内核类是nachos.userprog.UserKernel(继承自nachos.threads.ThreadedKernel),线程类是userprog.UThread(继承自threads.KThread)。
为安装mips交叉编译器,本任务开发环境变为ubuntu12.04提供linux环境,配置好jdk及安装好eclipse后,安装提供的binutils-2.24,经测试可执行由MIPS-C编译器编译出的二进制指令(coff).
一些我对nachos执行coff文件过程的理解,
Coff文件载入后被转换为一个machine.Coff类型的对象,它包括若干个段。
每个段是一个machine.CoffSection类型的对象,每个CoffSection又包括若干个页page。
Coff的这种格式决定了我们在载入它的过程。
系统提供了页表pageTable,它以虚拟页号为下标,其中每一项是一个machine.TranslationEntry类型的对象。
TranslationEntry参数ppn物理页号vpn虚拟页号valid是否有效readOnly是否只读used是否被使用过dirty是否“脏”
要执行test文件夹里的coff文件,首先给它分配一个Uthread(继承自KThread),因此可以通过调用父类fork(),join()等已实现的方法,而在一个UThread里面得到一个新的UThread。
UThread运行时候的工作
publicUThread(UserProcessprocess){
super();//继承父类构造方法等
setTarget(newRunnable(){
publicvoidrun(){
runProgram();
}
});
this.process=process;
}
privatevoidrunProgram(){
process.initRegisters();
process.restoreState();
Machine.processor().run();
Lib.assertNotReached();
}
先给它实现一个运行的Runnable接口,再绑定到一个process上,RunProgram()方法第一步,process.initRegisters();初始化寄存器。
第二步process.restoreState();要将状态调入,然后开始运行Process了。
Userkernel继承ThreadedKernel,初始化如下,首先运行console,然后就要为processor(处理器)提供一个异常处理机制,得到所有物理页数目
publicvoidinitialize(String[]args){
super.initialize(args);
console=newSynchConsole(Machine.console());
Machine.processor().setExceptionHandler(newRunnable(){
publicvoidrun(){exceptionHandler();}
});
inttotalPages=Machine.processor().getNumPhysPages();
}
中断处理函数
publicvoidexceptionHandler(){
Lib.assertTrue(KThread.currentThread()instanceofUThread);
UserProcessprocess=((UThread)KThread.currentThread()).process;
intcause=Machine.processor().readRegister(Processor.regCause);
process.handleException(cause);
}
当前的Thread里面的process设置成了函数的process,。
然后从Processor的寄存器里面读取出导致exception的cause值,具体寄存器的使用没有深入研究。
Userkernel的run()函数有这样指令{
UserProcessprocess=UserProcess.newUserProcess();
//
Lib.assertTrue(process.execute(shellProgram,newString[]{}));
}
大意是分配新进程,该进程载入coff文件的名字,
Process类execute()方法主要靠load方法载入coff文件,该方法也是我们在TASK2.2中需要实现的。
TASK2.1
Nachos以及linux操作系统里文件描述符是一个很方便的东西,它是进程用来在本地文件记录打开的文件的一个向int数值的映射,这种映射是一对一的,进程自己都有一张自己的文件记录表,大小不超过16,0和1固定给I/O使用,只剩下至多14个int型文件描述符,
与线程类似,每个process拥有唯一的ProcessId,rootProcess的Id是0;
privateinthandleHalt(){
if(this.processID!
=0)
return-1;//非rootProcess调用halt会无效
Machine.halt();
//
return0;
}
//getUnusedFileDescriptor()获取一个可用的文件描述符
privateintgetUnusedFileDescriptor()throwsNachosInternalException{
for(inti=0;i