操作系统课程设计个人心得

时间:2024.3.27

课程设计心得体会


第二篇:关于操作系统课程设计


操作系统课程设计报告

文件组织:

实验1位于nachos-3.4.1项目

实验2位于nachos-3.4.2项目

实验3位于nachos-3.4.3项目

实验4位于nachos-3.4.4项目

以上代码位于code文件夹

输出位于output文件夹。

目录

一、内核线程调度策略设计......................................................................................... 3

设计目标:..................................................................................................................... 3

设计背景:..................................................................................................................... 3

1.1为Nachos添加按动态优先数调度策略................................................................. 3

设计算法说明:............................................................................................................. 4

设计内容和步骤:......................................................................................................... 4

新的设计的实验内容和步骤:..................................................................................... 7

以上设计实验输出结果的分析:................................................................................. 8

二、Hoare条件变量的设计与实现.............................................................................. 8

设计目标:..................................................................................................................... 8

设计背景:..................................................................................................................... 8

1.1实现Hoare样式的管程......................................................................................... 10

设计算法说明:........................................................................................................... 10

设计内容和步骤:....................................................................................................... 10

新的设计的实验内容和步骤:................................................................................... 17

以上设计实验输出结果的分析:............................................................................... 18

三、实现系统调用与内存管理................................................................................... 18

设计目标:................................................................................................................... 18

设计背景:................................................................................................................... 18

1.1 实现fork,exec,exit与join系统调用.............................................................. 19

设计算法说明:........................................................................................................... 19

设计内容和步骤:....................................................................................................... 19

1.2 实现内存管理........................................................................................................ 23

设计算法说明:........................................................................................................... 23

设计内容和步骤:....................................................................................................... 24

以上设计实验输出结果的分析:............................................................................... 38

四、文件系统............................................................................................................... 39

设计目标:................................................................................................................... 39

设计背景:................................................................................................................... 39

1.1实现二级索引......................................................................................................... 39

设计算法说明:........................................................................................................... 39

设计内容和步骤:....................................................................................................... 39

新的设计的实验内容和步骤:................................................................................... 41

以上设计实验输出结果的分析:............................................................................... 41

本设计的创新点:....................................................................................................... 42

本设计存在的问题和没达到的功能:....................................................................... 42

设计的体会、收获和总结........................................................................................... 42

一、内核线程调度策略设计

设计目标:

在Nachos系统中实现按优先数调度线程

研究各种调度策略算法的实现,

分析各种调度算法的性能。

设计背景:

从Nachos系统的基本内核./threads/scheduler.cc文件中可以看出Nachos系统的基本内核实现了先进先出的调度策略。

调度类Scheduler管理着一个就绪队列list。它的成员函数ReadyToRun (current Thread)将当前线程挂入该队列的队尾:

Scheduler::ReadyToRun (Thread *thread)

{

DEBUG('t', "Putting thread %s on ready list.\n", thread->getName());

thread->setStatus(READY);

readyList->Append((void *)thread);

}

它的另一成员函数FindNextToRun()则从list队首摘出一个就绪线程准备运行:

Thread *

Scheduler::FindNextToRun ()

{

return (Thread *)readyList->Remove();

}

这从基本内核执行的输出中可以得到验证:

*** thread 0 looped 0 times

*** thread 1 looped 0 times

*** thread 0 looped 1 times

*** thread 1 looped 1 times

*** thread 0 looped 2 times

*** thread 1 looped 2 times

*** thread 0 looped 3 times

*** thread 1 looped 4 times

1.1为Nachos添加按动态优先数调度策略

设计算法说明:

采用静态优先数先给定一个线程的基本优先级,该优先数可以在创建一个线程的时候指定,范围在0到100之间,数值越小优先级越低。

动态优先数计算方法为:

初始值 = 静态优先数

执行线程每Tick + 10

就绪线程每Tick - 1

唤醒线程 - 5

当执行线程动态优先数为0时重新计算就绪队列动态优先数:

按降序调整就绪队列优先级,从就绪队列首选择新的执行线程。

设计内容和步骤:

1、

2、 将thread目录下的所有文件拷贝到lab2中,并修改其Makefile.local文件。 INCPATH += -I../lab2 -I../machine 在Thread类中增加一个变量用于记录优先级并增加相应的构造函数与访问函数。

void setPriority(int p){this->priority = p;}

void increPriority(int in){

if(this->priority + in < Max && this->priority + in > Min){

}

else{

}

}

int getPriority(){return priority;}

private:

int priority;

Thread::Thread(char* threadName,int p)

{

name = threadName;

stackTop = NULL;

stack = NULL;

status = JUST_CREATED;

priority = 0;

priority = p;

#ifdef USER_PROGRAM if(in > 0){ } else{ } this->priority = Min; this->priority = Max; this->priority += in;

space = NULL;

#endif

}

3、

在Scheduler类中增加一个方法用于为整个就绪队列中的所有线程改变优先级 void ThreadLowPri(_int arg){ Thread *t = (Thread *)arg; t->increPriority(-1);}

Scheduler::AddAll(){

readyList->Mapcar((VoidFunctionPtr) ThreadLowPri);

}

4、 在interrupt::OneTick中改变优先级

scheduler->AddAll();

currentThread->increPriority(10);

if(currentThread->getPriority() == Max){

yieldOnReturn = TRUE;

}

5、 更改相应的加入就绪队列与从就绪队列中取一个线程运行的方法s

void

Scheduler::ReadyToRun (Thread *thread)

{

DEBUG('t', "Putting thread %s on ready list.\n", thread->getName());

thread->setStatus(READY);

readyList->SortedInsert((void *)thread,thread->getPriority());

}

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

// Scheduler::FindNextToRun

//

// Return the next thread to be scheduled onto the CPU. If there are no ready threads, return NULL.

// Side effect:

//

Thread *

Scheduler::FindNextToRun ()

{

Thread* thread = (Thread *)readyList->Remove();

if(thread){

}

return thread;

} thread->increPriority(-5); Thread is removed from the ready list. //----------------------------------------------------------------------

6、 修改Thread::Yield()方法,使得在选取下一个线程运行的时候包括当前线程

void

Thread::Yield ()

{

Thread *nextThread;

IntStatus oldLevel = interrupt->SetLevel(IntOff);

ASSERT(this == currentThread);

DEBUG('t', "Yielding thread \"%s\"\n", getName());

scheduler->ReadyToRun(this);

nextThread = scheduler->FindNextToRun(); if (nextThread != NULL) {

scheduler->Run(nextThread);

}

(void) interrupt->SetLevel(oldLevel);

}

7、 修改测试类

void

SimpleThread(_int which)

{

int num;

for (num = 0; num < 5; num++) {

interrupt->SetLevel(IntOff);

printf("*** thread %d looped %d times\n", (int) which, num);

interrupt->SetLevel(IntOn);

}

printf("thread %d exit---------------------------------\n",(int) which);

}

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

// ThreadTest

// Set up a ping-pong between two threads, by forking a thread

// to call SimpleThread, and then calling SimpleThread ourselves.

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

void

ThreadTest()

{

DEBUG('t', "Entering SimpleTest");

Thread *t1 = new Thread("forked thread1",10);

Thread *t2 = new Thread("forked thread2",20);

Thread *t3 = new Thread("forked thread3",30);

Thread *t4 = new Thread("forked thread4",40);

Thread *t5 = new Thread("forked thread5",50);

t1->Fork(SimpleThread, 1);

t2->Fork(SimpleThread, 2);

t3->Fork(SimpleThread, 3);

t4->Fork(SimpleThread, 4);

t5->Fork(SimpleThread, 5);

}

新的设计的实验内容和步骤:

重新执行../lab2中的make然后运行,运行结果如下:

*** thread 1 looped 0 times

*** thread 1 looped 1 times

*** thread 1 looped 2 times

*** thread 2 looped 0 times

*** thread 2 looped 1 times

*** thread 2 looped 2 times

*** thread 2 looped 3 times

*** thread 2 looped 4 times

thread 2 exit--------------------------------- *** thread 3 looped 0 times

*** thread 3 looped 1 times

*** thread 3 looped 2 times

*** thread 4 looped 0 times

*** thread 4 looped 1 times

*** thread 4 looped 2 times

*** thread 4 looped 3 times

*** thread 4 looped 4 times

thread 4 exit--------------------------------- *** thread 1 looped 3 times

*** thread 1 looped 4 times

thread 1 exit--------------------------------- *** thread 3 looped 3 times

*** thread 3 looped 4 times

thread 3 exit--------------------------------- *** thread 5 looped 0 times

*** thread 5 looped 1 times

*** thread 5 looped 2 times

*** thread 5 looped 3 times

*** thread 5 looped 4 times

thread 5 exit---------------------------------

No threads ready or runnable, and no pending interrupts.

Assuming the program completed.

Machine halting!

Ticks: total 400, idle 10, system 390, user 0

Disk I/O: reads 0, writes 0

Console I/O: reads 0, writes 0

Paging: faults 0

Network I/O: packets received 0, sent 0

Cleaning up...

以上设计实验输出结果的分析:

主线程首先执行后放弃CPU,T1优先级最低排在队首先被选中。主线程由于优先级最高被排在队列尾。T1线程放弃CPU,当前T2在队首先被选中。这样依次进行,直到所有的线程招待结束。

二、Hoare条件变量的设计与实现

设计目标:

在nachos中实现Hoare样式的条件变量

使用Hoare样式的条件变量,实现生产者、消费者问题

使用Hoare样式的条件变量,实现哲学家就餐问题,要求避免死锁与饥饿

设计背景:

在nachos,已经实现了Mesa样式的管程,其类声明如下:

class Condition {

public:

Condition(char* debugName);

// initialize condition to // "no one waiting"

// deallocate the condition ~Condition();

char* getName() { return (name); }

void Wait(Lock *conditionLock);

// these are the 3 operations on // condition variables; releasing the

// lock and going to sleep are // *atomic* in Wait()

void Signal(Lock *conditionLock); // conditionLock must be held by

void Broadcast(Lock *conditionLock);// the currentThread for all of

private:

char* name;

List* queue; // threads waiting on the condition

Lock* lock; // debugging aid: used to check correctness of

// arguments to Wait, Signal and Broacast

}; // these operations

其中最主要两个方法是wait与signal,其代码如下:

void Condition::Wait(Lock* conditionLock)

{

IntStatus oldLevel = interrupt->SetLevel(IntOff);

ASSERT(conditionLock->isHeldByCurrentThread()); // check pre-condition

if(queue->IsEmpty()) {

}

ASSERT(lock == conditionLock); // another pre-condition

queue->Append(currentThread); // add this thread to the waiting list

conditionLock->Release(); // release the lock

currentThread->Sleep(); // goto sleep

conditionLock->Acquire(); // awaken: re-acquire the lock

(void) interrupt->SetLevel(oldLevel);

}

void Condition::Signal(Lock* conditionLock)

{

Thread *nextThread;

IntStatus oldLevel = interrupt->SetLevel(IntOff);

ASSERT(conditionLock->isHeldByCurrentThread());

if(!queue->IsEmpty()) {

}

(void) interrupt->SetLevel(oldLevel);

} ASSERT(lock == conditionLock); nextThread = (Thread *)queue->Remove(); scheduler->ReadyToRun(nextThread); // wake up the thread lock = conditionLock; // helps to enforce pre-condition

从其中可以看出,在signal中,一个队列把另一个队列唤醒,只是把被唤醒的队列放在了就绪队列中,而从wait中也可以看出,一个线程被唤醒之后,轮到它运行时,它还得去获得锁,

而唤醒它的线程在离开管程之前,并没有释放锁,因此只有当唤醒线程运行完之后,被唤醒的线程才能去运行。

但是,当一个线程被唤醒之后,这时候它运行的条件是一定满足的,而随着唤醒线程的运行,并且在重新获得锁的过程中,被唤醒线程运行的条件可能就已经失去了。因此,最好可以在一个线程被唤醒之后,就立刻让它运行,而让唤醒线程去等待。这就是Hoare样式的管程。

1.1实现Hoare样式的管程

设计算法说明:

首先,要增加一个队列,用于唤醒进程去等待。当线程1把线程2唤醒之后 ,线程1立刻去等待。

其次,在设计的过程中,把原来用于互斥进入管程的锁换成了信号量。这是因为当线程1去唤醒线程2时,此时一定是线程1在运行,如果要让线程2去运行,就必须要让线程2获得锁。但是,锁必须由获得它的线程进行释放,因此线程1必须释放锁,但此时线程2会与别的线程进行竞争,最后不一定是线程2能获得锁。而使用信号量,可以让线程1去等待的时候并不去执行V操作,而是直接让线程2运行,此时别的进程或阻塞在条件变量中,或在唤醒等待队列中,或在管程外,最后运行的一定是线程2。可以由线程2与唤醒等待队列中最后退出管程的那个线程负责执行V操作。

使用一个信号量next来实现唤醒等待队列,当一个线程在一个条件变量上wait时或当其退出管程时,优先去唤醒唤醒等待队列的线程,如果没有的话,就让一个等待在管程外的线程运行。

对于生产者消费者问题,采用两个条件变量full与empty来实现。

对于哲学家就餐问题,采用的策略是让每次进入的哲学家数量比筷子数量少1,并且只有两边的筷子能同时拿起来的时候才可以去就餐,这样就可以避免死锁与饥饿。

设计内容和步骤:

修改threads/synch.h与threads/synch.cc,增加Hoare样式的条件变量的声明与定义。

class HCondition {

public:

HCondition(char* debugName);

// initialize condition to // "no one waiting"

// deallocate the condition

~HCondition(); char* getName() { return (name); } void Wait(Semaphore *conditionLock,Semaphore* nextSema,int& count);

void Signal(Semaphore *conditionLock,Semaphore* nextSema,int& count);

private:

char* name;

List* queue; // threads waiting on the condition

Semaphore* lock; // debugging aid: used to check correctness of

// arguments to Wait, Signal and Broacast

Semaphore* next;

};

void HCondition::Wait(Semaphore* conditionLock,Semaphore* nextSema,int& nextCount) {

IntStatus oldLevel = interrupt->SetLevel(IntOff);

ASSERT(nextCount >= 0);

printf("%s waiting!\n",currentThread->getName());

if(queue->IsEmpty()) {

}

ASSERT(lock == conditionLock); // another pre-condition

ASSERT(next == nextSema);

queue->Append(currentThread); // add this thread to the waiting list

printf("now now now next count = %d\n",nextCount);

if(nextCount > 0) {

}

else {

}

(void) interrupt->SetLevel(oldLevel);

}

void HCondition::Signal(Semaphore* conditionLock,Semaphore* nextSema,int& nextCount) {

Thread *nextThread;

IntStatus oldLevel = interrupt->SetLevel(IntOff);

ASSERT(nextCount >= 0);

if(!queue->IsEmpty()) {

}

(void) interrupt->SetLevel(oldLevel);

} ASSERT(lock == conditionLock); ASSERT(next == nextSema); nextThread = (Thread *)queue->Remove(); printf("%s was waked\n",nextThread->getName()); scheduler->ReadyToRun(nextThread); // wake up the thread nextCount++; next->P(); nextCount--; conditionLock->V(); currentThread->Sleep(); // goto sleep next->V(); currentThread->Sleep(); // goto sleep lock = conditionLock; // helps to enforce pre-condition next = nextSema;

2、在lab3中,增加生产者消费者问题的管程的实现,代码位于lab3/Ring.cc

3、在lab3中,增加生产者消费者问题的测试类,代码位于lab3/myprocon.cc

4、 增加哲学家就餐问题的管程与测试的实现。 其主要代码如下:

// ring.cc

//实现了一个生产者消费者的管程 extern "C" {

#include <stdio.h>

}

#include "ring.h"

slot::slot(int id, int number) {

}

Ring::Ring(int sz)

{

}

Ring::~Ring() {

} delete[] buffer; delete conditionLock; delete next; delete full; delete empty; // Initialize the data members of the ring object. size = sz; cs = 0; nextCount = 0; in = 0; out = 0; buffer = new slot[size]; //allocate an array of slots. conditionLock = new Semaphore("Condition Lock",1); next = new Semaphore("Next semaphore",0); full = new HCondition("full"); empty = new HCondition("empty"); if (sz < 1) { } fprintf(stderr, "Error: Ring: size %d too small\n", sz); exit(1); thread_id = id; value = number; extern int exit(int st);

void

Ring::Put(slot *message,_int which)

{

conditionLock->P(); while(Full()){ } printf(" >>>>>>>>>>>>>>>>>>>>>>>>>>>>>..inner Prodcuer %i is going to put a slot whose number printf("full!\n"); full->Wait(conditionLock,next,nextCount); is %i\n",which,message->value);

}

void

Ring::Get(slot *message,_int which)

{

conditionLock->P(); while(Empty()){ } printf("inner Consumer %i is going to get a slot\n",which); message->thread_id = buffer[out].thread_id; message->value = buffer[out].value; out = (out + 1) % size; cs--; printf("<<<<<<<<M<<<<<<<<<<<<<<<<<<<<<<. inner Consumer %i get a printf("empty!\n"); empty->Wait(conditionLock,next,nextCount); buffer[in].thread_id = message->thread_id; buffer[in].value = message->value; in = (in + 1) % size; cs++; empty->Signal(conditionLock,next,nextCount); if(nextCount > 0){ } else{ } conditionLock->V(); printf("nextCOunt = %d",nextCount); next->V();

slot %i\n",which,message->value);

full->Signal(conditionLock,next,nextCount); if(nextCount> 0) { printf("nextCOunt = %d",nextCount); next->V();

}

} else { } conditionLock->V();

int Ring::Empty() {

}

int Ring::Full() {

}

#include <stdio.h>

#include "copyright.h"

#include "system.h"

#include "ring.h"

#define MAX_LENGTH 1

#define PRO_COUNT 3

#define CON_COUNT 3

#define TIME 20

Ring* myRing = new Ring(MAX_LENGTH); int slotId[] = {0,0,0,0,0};

void producer(_int which){

}

void consumer(_int which){

for(int i = 0;i < TIME;i++){ slot* s = new slot(0,0); for(int i = 0;i < TIME;i++){ } printf("Prodcuer %i exit---------------------------------------------------",which); slot* s = new slot(which,slotId[which]++); printf("Prodcuer %i is going to put a slot whose number is %i\n",which,s->value); myRing->Put(s,which); printf("Prodcuer %i put a slot whose number is %i\n\n",which,s->value); printf("test for full in = %i,out = %i,currentSize = %i\n",in,out,cs); return (cs >= size); printf(" test for empty in = %i,out = %i,currentSize = %i\n",in,out,cs); return (cs == 0);

}

} printf("Consumer %i is going to get a slot\n",which); myRing->Get(s,which); printf("Consumer %i get a slot whose number is %i\n\n",which,s->value); printf("Consumer %i exit---------------------------------------------------",which);

void procon(){

}

#ifndef DP_H_ #define DP_H_

#include "synch.h"

class DP{ public:

DP(int _number); ~DP(); void pickup(int i); void putdown(int i); void test(int i); void eat(int i); typedef enum state{eating,waiting,hungry,thinking} State; State* state; HCondition** condition; int number; Semaphore* lock; Semaphore* next; printf("All create^^^^\n"); t = new Thread("consumer1"); t->Fork(consumer, 1); t = new Thread("consumer2"); t->Fork(consumer, 2); DEBUG('t', "producer and consumer problem start!"); printf("producer and consumer problem start!\n"); Thread *t = new Thread("producer1"); t->Fork(producer, 1); t = new Thread("producer2"); t->Fork(producer, 2); private:

};

int nextCount;

#endif /* DP_H_ */

#include "dp.h"

DP::DP(int _number):number(_number),nextCount(0){

}

DP::~DP(){

}

void DP::pickup(int i){

}

void DP::putdown(int i){

ASSERT(i >= 0 && i < number); lock->V(); state[i] = thinking; printf(">>>>>>>>>>>>>>>phi %i has put down the forks\n",i); test((i+number-1)%number); test((i+1)%number); if(nextCount > 0){ ASSERT(i >= 0 && i < number); state[i] = hungry; lock->P(); test(i); while(state[i] != eating){ } printf(">>>>>>>>>>>>>>>phi %i has pickup the forks\n",i); condition[i]->Wait(lock,next,nextCount); test(i); for(int i = 0;i < number;i++){ } delete[] condition; delete lock; delete next; delete condition[i]; state = new State[number]; condition = new HCondition*[number]; for(int i = 0;i < number;++i){ } lock = new Semaphore("lock",number - 1); next = new Semaphore("next",0); condition[i] = new HCondition("dp condition"); state[i] = thinking;

} } next->V();

void DP::test(int i){

}

void DP::eat(int i){

} printf(">>>>>>>>>>>>>>phi %i is eating...\n",i); if(state[(i+number-1)%number] != eating && state[(i+1)%number] != eating && state[i] == hungry){ } state[i] = eating; condition[i]->Signal(lock,next,nextCount);

#include "dp.h"

DP* dp = new DP(5);

void phi(_int which){

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

}

printf("dp %i exit-----------------------------\n",which);

}

void dpTest() {

Thread* t = new Thread("phi_0");

t->Fork(phi, 0);

Thread* t1 = new Thread("phi_1");

t1->Fork(phi, 1);

Thread* t2 = new Thread("phi_2");

t2->Fork(phi, 2);

Thread* t3 = new Thread("phi_3");

t3->Fork(phi, 3);

Thread* t4 = new Thread("phi_4");

t4->Fork(phi, 4);

} dp->pickup(which); dp->eat(which); dp->putdown(which); printf("phi_%i success for %i\n",which,i);

新的设计的实验内容和步骤:

1、在lab3下的makefile.local文件去掉关于prodcons++.cc的编译定义,并增加对procon.cc的

编译定义

2、进入lab3下,进行make

3、增加#define DP 定义,利用条件编译,对DP问题进行测试。

4、由于输出太多,所以不再帖出。生产者消费者问题的输出在output/procon.txt中,哲学家

就餐问题输出在dp.txt中。

以上设计实验输出结果的分析:

从上而两个测试的输出,我们可以看出,当一个线程被唤醒之后,它立刻就能运行。而且所有的线程都可以正常退出,没有发生死锁。

三、实现系统调用与内存管理

设计目标:

实现fork,exec,exit与join系统调用。

实现多道程序驻留内存

实现虚拟内存

实现写时复制

设计背景:

在nachos中,Thread类是来模拟一个线程的。在Thread类中,模拟了一个系统栈,并

且在这个栈中保存系统寄存器的值。这里所说的系是指nachos运行的环境,对我们来说,就是所在的Linux系统。因为nachos要模拟线程的切换,因此必须要有能保存真实机器的CPU中的寄存器内容的地方。这就是说nachos自己实现了一个线程库。

在一个线程刚创建时,其处在JUST_CREATE状态,并且未分配系统栈。Thread类中,还有一个很重要的函数是fork,这个函数接收一个函数指针作为参数。在这个函数中,nachos会初始化这个线程的系统栈空间,并且会把所传入的函数的首址放在栈顶,这样,当这个线程被第一次运行的时候,就会从传入的这个函数处开始运行。

在线程还维护了一个AddrSpace类型的指针。当调用exec时,就会从文件中装载并初始化进程的用户空间。在nachos上,可执行文件是noff格式的。这种格式的文件中,包括一个文本段与三个数据段,并且在文件头中记录了其在虚拟空间的起始位置、在文件中的起始位置,以及大小,这样可以分别来初始化其用户空间的代码段、初始化数据段与未初始化数据段。这时候可以认为这个线程已经变成了一个进程。

在nachos中,对机器原模拟是在machine类中。在这个类中,用两个整型数组分别来模拟寄存器与内存。在machine中,有一个Run函数,这个是用来模拟机器的运行的。这个函数是一个死循环,在每一次循环的时候,首先从用户空间中取一条指令,然后在一个大的switch语句中解释执行指令。 在userpro目录下,有一个system.h的头文件,在这个头文件中,声明了与系统调用有关的函数头。对于test下的测试程序,就可以通过调用这个头文件中声明的函数来实现系统调用。

在用户程序被编译完成后,在函数调用的时候,首先会把参数放到r4-r7这几个寄存器中去,然后会把相应的系统调用编译成下而的指令:

addiu $2,$0,SC_Halt

syscall j $31 .end Halt

即首先是把系统调用的类型放入r2,然后再执行系统调用指令。在nachos内部,是用RaiseException来模拟系统调用的,这个函数会调用ExceptionHandle,依靠分支来处理各种系统调用。

1.1 实现fork,exec,exit与join系统调用

设计算法说明:

在nachos中,原本一个线程的释放是由它自己来进行的,但是有了这四个系统调用之后就不一样了。首先,是一个程序调用fork来开辟一个新线程,然后根据调用返回值来确定其是父线程还是子线程。在一个线程要退出的时候,会执行exit系统调用(如果不自己调用的话,隐式执行exit(0)),释放用户空间,如果有父进程的话则进入僵尸态并加入到父进程的僵尸队列中去,等待父进程join时或退出时将其释放,而一个父进程如果要等待子进程执行完毕的话,就会执行join系统调用。

为了实现这四个系统调用,首先要建立起进程的父子结构。为此,在thread类中,增加线程的zombie状态,并增加以下声明:

int pid; Thread* parent; List* activeChild; List* zombieChild;

Semaphore* exit;

int exitStatus;

pid作为一个线程惟一的编号,在本程序中是从0一直向上增长的。在一个进程中,维护了其父进程,并且维护了两个子进程队列,分别是活动子进程队列与僵尸子进程队列。exit是用来使执行join的父进程阻塞的,exitStatus是用来保存其退出状态而等待父进程收集。

在建立起来这些结构之后,就可以实现这四个系统调用了。

设计内容和步骤:

1、

为了测试方便,增加write系统调用如下: int buffer = machine->ReadRegister(4); int size = machine->ReadRegister(5); int fileId = machine->ReadRegister(6); int next; char ch; for(int i = 0;i < size;i++){ } machine->ReadMem(buffer+i,1,&next); ch = (char)next; WriteFile(fileId, &ch, sizeof(char)); else if (type == SC_Write) {

} machine->advancedPC();

在实现write的时候,有一点就是如何取得字符串参数。首先,字符串被放到了machine类用于模拟内存的整型的数组中,而传入寄存器r4的是其在虚拟地址。由于在实现了分页之后,其内存页不一定连续,因此采用的方法是逐字节的从内存中读,直到读到足够字节为止。然后调用nachos封装的linux系统调用将其写入相应文件。之后增加PC值去执行下一条入出指令。 2、 增加fork系统调用 代码如下: else if(type == SC_Fork){ } printf("fork\n"); int id = interrupt->fork(); machine->WriteRegister(2,id); machine->advancedPC(); Interrupt::fork(); int Interrupt::fork(){ //save the currentThread; Thread* t = new Thread("new Thread"); t->parent = currentThread; currentThread->activeChild->SortedInsert(t,t->pid); t->space = new AddrSpace(t->parent->space); t->exit = new Semaphore("Exit",0); for (int i = 0; i < NumTotalRegs; i++) { t->userRegisters[i] = machine->ReadRegister(i); } t->userRegisters[2] = 0; t->Fork(setupRegister,t->pid); return t->pid;

}

//setupRegister

void setupRegister(_int which) {

} printf("who am i %d pc = %d? \n",which,currentThread->userRegisters[PCReg]); if (currentThread->space != NULL) { // if there is an address space } machine->advancedPC(); machine->Run(); currentThread->RestoreUserState(); // to restore, do it. currentThread->space->RestoreState();

在interrupt->fork中,首先是初始化一个新线程,设置其父进程并且将其插入其父进程的活动子进程队列中去,并用其父进程的地址空间来实现其初始化其地址空间。之后调用

Thread::Fork()并传入setupRegister函数来初始化子进程的寄存器。在创建一个子进程的时候,要把当前父进程执行的寄存器保存到其系统栈空间,在setupRegister的时候,要恢复寄存器的值,并调用machine->run(),从而使子进程可以从fork的下一条指令处开始执行与父进程相同的代码。通过将子进程的r2人为设成0从而可以实现对子进程返回0而对父进程返回新生成子进程的id。

3、实现exec系统调用

else if(type == SC_Exec) {

} space->InitRegisters(); // set the initial register values space->RestoreState(); // load page table register machine->Run(); // jump to the user progam ASSERT(FALSE); // machine->Run never returns; // the address space exits // by doing the syscall "exit" if (executable == NULL) { } space = new AddrSpace(executable); currentThread->space = space; //delete executable; // close file printf("Unable to open file %s\n", fileName); return; OpenFile *executable = fileSystem->Open(fileName); AddrSpace *space; printf("Exec\n"); char fileName[128]; int next; int i; int buffer = machine->ReadRegister(4); // Assume the file name lt 128 chars for(i = 0;i < 127;i++) { } fileName[i] = 0; printf("fileName = %s\n",fileName); machine->ReadMem(buffer+i,1,&next); if(next == 0) { } fileName[i] = (char)next; break;

在exec中,首先是要从模拟内存中读出可执行文件的文件名。然后打开文件并用exec初始化进程的地址空间。但是在初始化完成后,就不能立刻delete executable,而是要将其保存下来,这是因为在虚拟内存中还要去文件中读取。

4、实现exit系统调用

else if (type == SC_Exit) {

int code = machine->ReadRegister(4);

printf("Current thread %d is exit for code %d\n", currentThread->pid,code); currentThread->RealExit(code);

}

Thread::RealExit

void Thread::RealExit(int code) {

}

Thread::ReleaseSpace

void Thread::ReleaseSpace() {

if(space != NULL) { delete space; space = NULL; } //delete the zomibe child; Thread *t; while((t = (Thread*)zombieChild->Remove()) != NULL) { ASSERT(this == currentThread); scheduler->Print(); printf("\nhehe\n"); scheduler->Print(); printf("\n"); if(!parent) { } else { } //return the exit code; exitStatus = code; Thread* t; while((t = (Thread*)activeChild->Remove()) != NULL) { } ReleaseSpace(); (void) interrupt->SetLevel(IntOff); //set the currentThread to zombie thread; Zombie(); parent->activeChild->SortedInsert(t,t->pid); Thread* t; while((t = (Thread*)activeChild->Remove()) != NULL) { } ReleaseSpace(); Finish(); //now we just make it's parent to null to be easy; t->parent = NULL;

} delete t; } //Wake up parent if parent is waiting currentThread->exit->V(); //release the semphore; delete currentThread->exit;

在一个进程退出时,首先看它有没有父进程。如果没有的话,刚要向以前一样,自己负责把自己释放掉。首先,所自己活动子队列中的所有进程的父进程设成空,然后释放空间,这包括释放用户空间以及释放僵尸子进程。如果有父进程的化,则把自己的活动子进程交给自己的父进程,然后填写自己的退出状态,释放空间,唤醒可能等待的父进程,然后把自己插入父进程的僵尸子进程中去,然后进入僵尸状态,并把自己人就绪队列中删除,从此便不会再活动。

5、 实现join系统调用

else if(type == SC_Join){

} int cid = machine->ReadRegister(4); Thread* child = (Thread*)currentThread->activeChild->Remove(cid); if(child){ } else{ } machine->advancedPC(); child = (Thread*)currentThread->zombieChild->Remove(cid); if(child){ } int code = child->exitStatus; delete child; machine->WriteRegister(2,code); child->exit->P();//to wait the child to exit; //remove it from the zombie list; currentThread->zombieChild->Remove(child->pid); int code = child->exitStatus; delete child; machine->WriteRegister(2,code);

在一个父进程要去join一个子进程的时候,根据当前子进程的不同状态会采取不同的行动。首先,如果子进程在其活动子进程队列中的话,则执行P操作阻塞在子进程中的exit信号量上,然后等到子进程将自己唤醒子后,子进程一定已经成为了僵尸,所以从僵尸子进程队列中找到相应子进程,将其取下,收集其退出状态,删除子进程并返回。否则如果其子进程在其僵尸队列中,则直接收集其退出状态,删除子进程并返回。

1.2 实现内存管理

设计算法说明:

在nachos中,最基本的内存管理制度就是分页。把物理内存划分成一定大小的帧,然后把进程的逻辑内存空间划分成同样大小的页。这里为了方便,就把一页的大小设成与硬盘的一个扇区的大小相同,都是512B。 在一个进程用户空间中,有这个进程的页表,如下所示: TranslationEntry *pageTable;

unsigned int numPages;

而在每一个TranslationEntry中,如下所示:

class TranslationEntry {

public:

int virtualPage;

int physicalPage;

bool valid;

bool readOnly;

bool use;

bool dirty;

};

分别代表了页表中的虚拟地址、物理地址,以及其是否有效,是否可读,而use与dirty是用来处理页面调度的,dirty是用来表示内存已写的。

在machine中还有一个系统页表的指针。当一个进程被切换到CPU上执行时,会把其指向这个进程的页表。

当执行exec系统调用时,会从文件中装入内存映象。但是,在nachos中,每一次为一个进程装入映象,都会装入到内存的起始位置开始的一段连续的空间。这样会使以前装入内存的数据被覆盖,所以不能实现多道程序的并发,而且在装入内存映象的时候,会依赖于其物理内存空间是连续的。因此必须进行修改。

在nachos中,开始的时候会把整个进程的整个内存空间装入物理内存。为了实现虚拟内存,开始时给每个进程一个最大的页的限定,把其它页valid设成无效,待以后从文件中或交换区中读入。

为了实现写时拷贝,在一个新进程实现的时候,让其与其父进程共享其数据段与代码段,直到有人向数据区里写数据的时候,才给要写入的进程重新分配一个新的页,并把原来的页的内容复制进去。为了区分一个页是真的只读还是写时拷贝,因此将其各段起始与大小存起来,如果其所有段不是只读,但其所在页是只读,这就说明这一页是写时拷贝页。而为了知道一个帧的物理信息(在这里主要是一个帧在被多少个进程共享),需要有一个数据结构存储其每个页的大小。

设计内容和步骤:

1、

#ifndef MEMMANAGER_H_

#define MEMMANAGER_H_

#include "machine.h"

#include "thread.h"

实现其本的内存管理类:

#define SWAP "SWAP"

class Page{

public:

};

class MemManager{

public:

private:

};

#endif /* MEMMANAGER_H_ */ Page* map; Page* swapMap; int swapId; int lru(); int doNoPage(); int swapOut(int vpn); void swapIn(int page,int sa); int getNextSwapFreePage(); void returnSwapPage(int sp); void increaseSwapRef(int sp); MemManager(); ~MemManager(); int getNextFreePage(); void returnPage(int phyPage); void increaseRef(int pp); int getCount(int pp); unsigned int count;

include "MemManager.h" extern Machine* machine;

extern Thread* currentThread;

MemManager::MemManager() {

map = new Page[NumPhysPages]; swapMap = new Page[NumPhysPages*2]; for(int i = 0;i < NumPhysPages;i++){ map[i].count = 0;

} } for(int i = 0;i < NumPhysPages*2;i++){ } swapId = OpenForWrite(SWAP); printf("%d\n",swapId); char foo = '0'; for(int i = 0;i < MemorySize*2;i++) { } WriteFile(swapId,&foo,1); swapMap[i].count = 0;

MemManager::~MemManager(){

}

int MemManager::getNextFreePage(){

}

void MemManager::returnPage(int phyPage){

}

void MemManager::increaseRef(int pp){

}

int MemManager::getCount(int pp){

}

int MemManager::getNextSwapFreePage() {

for (int i = 0; i < NumPhysPages*2; i++) { return map[pp].count; map[pp].count++; printf("page = %d\n",phyPage); ASSERT(phyPage < NumPhysPages); if(map[phyPage].count > 0){ } map[phyPage].count--; for(int i = 0;i < NumPhysPages;i++){ } return -1; if(map[i].count == 0){ } map[i].count = 1; return i; delete[] swapMap; printf("map= %x\n",map); delete[] this->map; Close(swapId);

} } if (swapMap[i].count == 0) { } swapMap[i].count++; return i; return -1;

void MemManager::returnSwapPage(int sp) {

}

void MemManager::increaseSwapRef(int sp){

}

int MemManager::doNoPage() {

}

int MemManager::swapOut(int vpn){

int sa = this->getNextSwapFreePage(); int page = machine->pageTable[vpn].physicalPage; int fa = page*PageSize; printf("swap from %d\n",fa); Lseek(swapId,sa*PageSize,0); WriteFile(swapId,&machine->mainMemory[fa],PageSize); swapMap[sa].count = map[page].count; return sa; //select a page to the SWAP; int out = lru(); printf("out = %d\n", out); int page = machine->pageTable[out].physicalPage; //do swap; if (machine->pageTable[out].dirty) { } machine->pageTable[out].valid = FALSE; return page; int swapPage = swapOut(out); printf("swapPage = %d\n",swapPage); machine->pageTable[out].physicalPage = swapPage; machine -> pageTable[out].physicalPage = -1; swapMap[sp].count++; if(swapMap[sp].count> 0) { } swapMap[sp].count--; } else {

}

void MemManager::swapIn(int page,int sa){

}

int MemManager::lru()

{

printf("lru\n"); currentThread->space->print(); int start = currentThread->space->lastLru; printf("start = %d\n",start); int length = machine->pageTableSize; int count = 0; int index = -1 , index_dirty = -1 , index_use = -1 ,index_last = -1; bool flag = FALSE , dirty_flag = FALSE , use_flag,dirty_used_flag = FALSE; int i = 0; for(int j=1;j<length;j++) { i = (start+j)%length; bool use_i = machine->pageTable[i].use; bool dirty_i = machine->pageTable[i].dirty; int page = machine->pageTable[i].physicalPage; if(!machine->pageTable[i].valid){ } else{ } if(use_i==FALSE&&dirty_i==FALSE) { } else if(use_i==FALSE&&dirty_i==TRUE) flag=TRUE; index=i; break; printf("i = %d,map[page].count = %d\n",i,map[page].count); if(map[page].count != 1){ } continue; continue; printf("sa = %d,page = %d\n",sa,page); Lseek(swapId,sa*PageSize,0); Read(swapId,&machine->mainMemory[page*PageSize],PageSize); map[page].count = 1; swapMap[sa].count--;

} } { } else if(use_i==TRUE&&dirty_i==FALSE) { } else { } machine->pageTable[i].use =FALSE; if(index_last == -1) index_last = i; machine->pageTable[i].use = FALSE; if(index==-1) index_use = i; if(index_dirty==-1) index_dirty = i; dirty_flag = TRUE; use_flag = TRUE; dirty_used_flag = TRUE; if(flag) { } else if(dirty_flag) { } else if(use_flag) { } else{ } currentThread->space->lastLru = count; return machine->pageTable[count].virtualPage; count = index_last; count = index_use; count = index_dirty; count = index;

这个类主要用来管理物理内存与交换区。在这里,交换区是用一个硬盘文件SWAP来模拟的,其大小是物理内存的2倍,也分成与页大小的部分进行管理。Page是一个用来管理物理帧的数据结构,在这里比较简单,只有一个int型的变量来记录对应的物理帧被多少个进程共享。这个类中,给出了寻找与管理物理帧与空闲交换区的方法,以及换入、换出一页与

处理缺页的方法,以及其所用的的lru换页的方法(在下面讲述)。在nachos中增加了一个该类的全局实例,并且在系统退出的时候析构。

2、增加Addrspace的类变量

SegTable* st;

OpenFile* file; int lastLru; 首先,SegTable是用于存储各段的信息,其定义如下:

class MSegment{

public:

};

class SegTable{

public:

};

bool SegTable::getReadOnly(int va) {

}

if((va >= code.startAddr)&&(code.startAddr+code.size> va)) { } if((va >= initData.startAddr)&&(initData.startAddr+initData.size> va)) { } if((va >= uninitData.startAddr)&&(uninitData.startAddr+uninitData.size> va)) { } if((va >= stack.startAddr)&&(stack.startAddr+stack.size> va)) { } ASSERT(FALSE); return FALSE;//This will never execute; return stack.readOnly; return uninitData.readOnly; return initData.readOnly; return code.readOnly; bool getReadOnly(int va); int getInFileAddr(int va,int size,int* realSize); MSegment code; MSegment initData; MSegment uninitData; MSegment stack; int startAddr; int size; int inFileAddr; bool readOnly;

int SegTable::getInFileAddr(int va,int size,int* realSize) {

//Here we assume that the code,data are continue in the file,and here it is; if((va >= code.startAddr)&&(va < uninitData.startAddr)) {

*realSize = (initData.startAddr + initData.size - va > size) ? size : s

} } *realSize = 0; return -1; initData.startAddr+initData.size - va; return code.inFileAddr+(va - code.startAddr);

在MSegment中,startAddr是用来存储其起始虚地址,size是用来存储其大小,inFileAddr用来存储其在文件中的起始位置,readOnly是用来存储其读写信息从而用于写时拷贝。其中有两个方法,getReadOnly用为获取一个虚拟地址所有段的可读写信息,而getInFileAddr则返回一个虚拟地址所在文件中的位置以及从这里开始共可以读出多少个字节,用于缺页的时候从文件中读取内容。

file变量是用来存储其所对应的可执行文件,lastLru存储了上一次换页时的结束虚页号,用于下一次换页时确定其起始考查页。

3、修改Addrspace类的构造函数:

AddrSpace::AddrSpace(OpenFile *executable)

{

//GY:: /* * As the nachos has no hardware support for the segment memory control * we didn't use it any more; * */ // how big is address space? size = noffH.code.size + noffH.initData.size + noffH.uninitData.size + UserStackSize; // we need to increase the size // to leave room for the stack numPages = divRoundUp(size, PageSize); //int codePages = noffH.code.size/PageSize; noffHeader noffH; unsigned int i, size; file = executable; executable->ReadAt((char *)&noffH, sizeof(noffH), 0); if ((noffH.noffMagic != NOFFMAGIC) && (WordToHost(noffH.noffMagic) == NOFFMAGIC)) SwapHeader(&noffH); ASSERT(noffH.noffMagic == NOFFMAGIC);

size = numPages * PageSize; st = new SegTable(); st->code.startAddr = noffH.code.virtualAddr; st->code.size = noffH.code.size; st->code.inFileAddr = noffH.code.inFileAddr; st->code.readOnly = TRUE; st->initData.size = noffH.initData.size; st->initData.startAddr = noffH.initData.virtualAddr; st->initData.inFileAddr = noffH.initData.inFileAddr; st->initData.readOnly = FALSE; st->uninitData.size = noffH.uninitData.size; st->uninitData.startAddr = noffH.uninitData.virtualAddr; st->uninitData.inFileAddr = noffH.uninitData.inFileAddr; st->uninitData.readOnly = FALSE; st->stack.size = UserStackSize; st->stack.startAddr = noffH.uninitData.size+noffH.uninitData.size; st->stack.readOnly = FALSE; DEBUG('a', "Initializing address space, num pages %d, size %d\n", numPages, size); printf("initial page table\n"); // first, set up the translation pageTable = new TranslationEntry[numPages]; for (i = 0; i < numPages; i++) { pageTable[i].virtualPage = i; // for now, virtual page # = phys page # if(i < IniPages){ } else { } pageTable[i].use = FALSE; pageTable[i].dirty = FALSE; pageTable[i].readOnly = FALSE; } int left; int start; for(int i = 0;i < numPages;i++) { start = pageTable[i].physicalPage*PageSize; pageTable[i].physicalPage = -1; pageTable[i].valid = FALSE; pageTable[i].physicalPage = mm->getNextFreePage(); pageTable[i].valid = TRUE;

}

if(start > 0){ } } printf("copy files\n"); // then, copy in the code and data segments into memory char tmp; if (noffH.code.size> 0) { DEBUG('a', "Initializing code segment, at 0x%x, size %d\n", noffH.code.virtualAddr, noffH.code.size); bzero(&machine->mainMemory[start],PageSize); //copy the head to align; copyPhy(noffH.code.virtualAddr,noffH.code.inFileAddr,noffH.code.size,TRUE); } if (noffH.initData.size> 0) { DEBUG('a', "Initializing data segment, at 0x%x, size %d\n", noffH.initData.virtualAddr, noffH.initData.size); copyPhy(noffH.initData.virtualAddr,noffH.initData.inFileAddr,noffH.initData.size,FALSE); /*executable->ReadAt(&(machine->mainMemory[noffH.initData.virtualAddr]), noffH.initData.size, noffH.initData.inFileAddr);*/ } lastLru = 0; print();s

void AddrSpace::copyPhy(int va,int fa,int size,bool code) {

ASSERT(file != NULL); int i; bool finish = FALSE; int vStart = va/PageSize; int offset = va%PageSize; int left = PageSize - offset; int ifStart = fa; printf("vStart = %d\n",vStart); int start = pageTable[vStart].physicalPage*PageSize+offset; printf("start = %d\n",start); //if already not vaild,then exit; if(pageTable[vStart].valid) { if(left> size) { } else { printf("read\n"); file->ReadAt(&machine->mainMemory[start],PageSize-offset, ifStart); file->ReadAt(&machine->mainMemory[start],size, ifStart);

} } } printf("end first read\n"); //if all is code; if(offset == 0&&code) { } ifStart+=left; start = vStart+1; int pages = (size - left)/PageSize; printf("pages = %d\n",pages); int end = start+pages; for(i = start;i < end;i++) { } int tLeft = size - pages*PageSize -left; if(tLeft != 0 && pageTable[end].valid) { } start = pageTable[end].physicalPage*PageSize; file->ReadAt(&machine->mainMemory[start],tLeft, ifStart); if(pageTable[i].valid) { } else{ } if(code) { } pageTable[i].readOnly = TRUE; // if the code segment was entirely on // a separate page, we could set its // pages to be read-only if(!code){ } break; start = pageTable[i].physicalPage*PageSize; //printf("start = %d",start); //printf("i = %d,start = %d\n",i,start); file->ReadAt(&machine->mainMemory[start],PageSize, ifStart); ifStart+=PageSize; pageTable[vStart].readOnly = TRUE;

在这里,我们不再连续分配物理帧,而是向内存管理器请求空闲帧,内存管理器会遍历其帧表,查找一个count == 0的页并将其返回。对于一个进程,其初始分配的帧不会走超过一个定值,对于不在物理内存中的页,其vaild位为false,如果其在可执行文件中,则其物理帧号为-1,否则为其在交换区中的块号(刚开始当然都为-1)。并且要把所有的页的readOnly位设好。在这里的copyPhy文件用于将文件中的各段以页为单位拷入内存,设置各个标记位,并且处理段开始与结尾不在帧边界的情况。

2、 处理缺页错误:

else if(which == PageFaultException){

s } } else{ } machine->pageTable[vpn].physicalPage = page; machine->pageTable[vpn].valid = TRUE; machine->pageTable[vpn].use = FALSE; currentThread->space->print(); mm->swapIn(page,machine->pageTable[vpn].physicalPage); if(size < PageSize){ } ASSERT(page*PageSize+PageSize <= MemorySize); bzero(&machine->mainMemory[page*PageSize+size],PageSize - size); int type = machine->ReadRegister(BadVAddrReg); int vpn = type/PageSize; int page = mm->getNextFreePage(); if(page == -1) { } printf("page = %d\n",page); if(machine->pageTable[vpn].physicalPage == -1){ int size; int ifa = machine->st->getInFileAddr(vpn*PageSize,PageSize,&size); sif(size != 0){ } ASSERT(page * PageSize+size <= MemorySize);page = mm->doNoPage(); currentThread->space->file->ReadAt(&machine->mainMemory[page*PageSize],size, ifa);

在这里首先向内存管理器申请一个新页,如果没有新页的话,由调用MemoryManager类的doNoPage方法来处理换页。这个算法会首先选定一牺牲页。这里使用的是增强型二次机会算法,其优先级是未用未写>未用已写>已用未写>已用已写,每次接着上一次的开始遍历,将各页使用信息清零,并且跳过共享页,具体算法在内存管理器的lru()方法中。在找到一个牺牲页之后,根据其从读入内存后是否修改过来决定将其换出到交换区或直接覆盖,并将其物理帧号设成-1或其相应的交换区的块号。然后将这一页返回。

根据物理帧号到相应位置将这一页读入。若其在文件中,则可以通过进程的SegTable获取其在文件中的起始位置与可读长度,并把剩余内容置0。若在交换区,则能过内存管理器将其从交换区中换出。然后设置页标识位。之后,进程从缺页处重新执行,由于此时该页已经被换入内存,因此不会再发生错误,程序会继续执行。

3、 实现子进程创建时共享父进程内存

首先是在一个子进程创建的时候,子进程会有子进程会与父进程共享代码区与数据区,但是要有自己的栈空间。因此,开始的时候,首先要复制父进程的段表与可执行文件指针,然后对于代码段与数据段,如果其在物理内存或交换区中,则直接设置子进程对应页的物

理帧,否则的话也将其物理帧设成-1。另外,每一个进程都要有自己的栈空间,并复制其父进程的栈空间。

AddrSpace::AddrSpace(AddrSpace* parent) {

st = new SegTable(); memcpy(st,parent->st,sizeof(SegTable)); lastLru = parent->lastLru; file = parent->file; int shareSize = st->code.size + st->initData.size + st->uninitData.size; int size = shareSize + UserStackSize; int sharePages = shareSize/PageSize; numPages = parent->numPages; printf("numberPages = %d,in fact is %d,shared size = %d,sharePages is %d\n",numPages,divRoundUp(size, PageSize),shareSize,sharePages); pageTable = new TranslationEntry[numPages]; int i; TranslationEntry* ppt = parent->pageTable; for (i = 0; i < sharePages; i++) { pageTable[i].virtualPage = i; pageTable[i].valid = ppt[i].valid; pageTable[i].use = ppt[i].use; pageTable[i].dirty = ppt[i].dirty; pageTable[i].physicalPage = ppt[i].physicalPage; if(!ppt[i].valid){ } else{ } } for (i = sharePages; i < numPages; i++) { pageTable[i].virtualPage = i; pageTable[i].valid = ppt[i].valid; pageTable[i].use = ppt[i].use; pageTable[i].dirty = ppt[i].dirty; pageTable[i].readOnly = ppt[i].readOnly; if(ppt[i].valid){ pageTable[i].physicalPage = mm->getNextFreePage(); //@TODO if no page now;

memcpy(&machine->mainMemory[pageTable[i].physicalPage*PageSize],&machine->mainMemory[ppt[i].physicalPage*PageSize],PageSize); pageTable[i].readOnly = TRUE; mm->increaseRef(ppt[i].physicalPage); pageTable[i].readOnly = ppt[i].readOnly; if(ppt[i].physicalPage != -1){ } mm->increaseSwapRef(ppt[i].physicalPage);

} } else{ } } print(); if(ppt[i].physicalPage == -1){ } else{ } pageTable[i].physicalPage = ppt[i].physicalPage; pageTable[i].physicalPage = -1;

4、

处理ReadOnly异常 else if(which == ReadOnlyException){

;

} } } machine->pageTable[vp].physicalPage = newPage; machine->pageTable[vp].readOnly = FALSE; machine->pageTable[vp].valid = TRUE; machine->pageTable[vp].use = FALSE; machine->pageTable[vp].dirty = machine->pageTable[page].dirty;sss mm->returnPage(page); int va = machine->ReadRegister(BadVAddrReg); int vp = va/PageSize; if(machine->st->getReadOnly(va)){ } else{ memcpy(&machine->mainMemory[newPage*PageSize],&machine->mainMemory[page*PageSize],PageSize)int page = machine->pageTable[vp].physicalPage; if(mm->getCount(page) == 1){ } else { } //physical page; int newPage = mm->getNextFreePage(); if(newPage == -1) { newPage = mm->doNoPage(); machine->pageTable[vp].readOnly = FALSE; currentThread->RealExit(2);

如前所述,当要去写一个只读的页时,首先到段表获取其段readOnly属性,并由此决定其是否是写时拷贝。如果不是的话,则杀死进程,否则,如果该帧只有这一个进程在使用的话,

则直接将其readOnly属性设成false,如果有多个进程共享的话,则为该进程重新分配一帧并将原来的内容复制进新帧中,将其设为可读写,并把原来页的count减1。然后从该指令处重新执行,此时就不会再陷入内核了。

以上设计实验输出结果的分析:

执行以下测试程序test/sort.c,其中包括了对系统调用与内存管理的测试:

#include "syscall.h"

/* size of physical memory; with code, we'll run out of space!*/

#define ARRAYSIZE 100

int A[ARRAYSIZE];

int

main()

{

int i, j, tmp;

//Write("nihao\n",7,1);

SpaceId id = Fork();

if(id == 0) {

}

else {

int status; //then sort! for (i = 0; i < (ARRAYSIZE - 1); i++) for (j = 0; j < ((ARRAYSIZE - 1) - i); j++) if (A[j]> A[j + 1]) {//out of order -> need to swap ! } tmp = A[j]; A[j] = A[j + 1]; A[j + 1] = tmp; for (i = 0; i < ARRAYSIZE; i++) A[i] = ARRAYSIZE - i - 1; Exit(1); /*and then we're done -- should be 0!*/ status = Join(id); /*if(status == 0) { } else if(status == 1) { }*/ Write("exit status = 1\n",sizeof("exit status = 1\n"),1); Write("exit without any thing\n",25,1);

}

Exit(0);

/* first initialize the array, in reverse sorted order */

}

实验输出分别位于output/sort12与output/sort128.txt中,分别对应于12帧与128时的情况。可以看出,在12帧时,其执行时间与换页数比128帧要多。另外,父线程是在子线程退出之后才退出的。这说明了系统调用的有效性。

四、文件系统

设计目标:

为文件增加二级索引

实现文件的append功能

设计背景:

在nachos中,已经实现了基本的文件系统结构。最底层的是Disk类,使用一个名叫DISK的文件来模拟最底层的硬盘。在此之上的是Synchdisk,在nachos中,硬盘也是一个异步设备,并且同一时刻只能有一个线程访问磁盘。当一个线程要读磁盘时,会在SynchDisk::ReadSector()中阻塞,直到有一个读中断到来。在向上一层是FileHdr,用来实现FCB,再向上就是FileSystem、OpenFile与Directory类,分别用来实现文件系统、打开文件与目录(只有一级)。除此之外,在nachos文件系统中,使用一个位图来管理空闲块。

在使用nachos –f来初始化一个文件系统的时候,nachos会生成一个新的位图与一个新的空白目录。然后把位图与目录写入0号与1号扇区。

在nachos中,文件索引只能占一个扇区,这就限制了文件的最大长度。通过增加二级索引,就可以增加文件的长度。

1.1实现二级索引

设计算法说明:

能过在FileHeader类中增加一个指向二级索引的指针(即记录二级索引所在的扇区号)来实现二级索引。

设计内容和步骤:

1、增加Second类代表二级索引,在其中数据变量只有一个int型的数组。

class Second{

public:

int dataSectors[NumSecondDirect]; // Disk sector numbers for each data

bool WriteBack(int sn);

bool FetchFrom(int sn);

};

2、在文件头中增加记录二级索引扇区的变量 int second; 由于增加了一个int型的变量,所以有一级索引中可以记录的扇区号必须减少1 #define NumDirect ((SectorSize - 3 * sizeof(int)) / sizeof(int))

3、 在创建一个文件头的时候,考虑二级索引

bool

FileHeader::Allocate(BitMap *freeMap, int fileSize)

{

second = -1;

numBytes = fileSize;

if(fileSize> MaxFileSize) {

printf("map = %x\n",freeMap);

second = freeMap->Find();

printf("second = %d\n",second);

if(second == -1) {

}

}

numSectors = divRoundUp(fileSize, SectorSize);

if (freeMap->NumClear() < numSectors){

printf("full!\n");

return FALSE; // not enough space

}

for (int i = 0; i < numSectors&& i < NumDirect; i++) {

dataSectors[i] = freeMap->Find();

}

if(numSectors > NumDirect){

Second* sec = new Second;

for(int i = NumDirect;i < numSectors;i++){

}

if(!sec->WriteBack(second)){

}

}

return TRUE;

} printf("write failed second = %d\n",second); return FALSE; sec->dataSectors[i-NumDirect] = freeMap->Find(); return FALSE;

假如文件已经超过了一级索引表示的最大长度,就为其分配二级索引。

4、更改ByteToSector方法,从而使在读写磁盘的时候,如果读写的数据位置记录在二级

索引上,则考虑这种情况。

int

FileHeader::ByteToSector(int offset)

{

if(offset>MaxFileSize){

Second* sec = new Second;

sec->FetchFrom(second);

return (sec->dataSectors[(offset-MaxFileSize)/SectorSize]); }

else

return(dataSectors[offset / SectorSize]);

}

5、当删除一个文件的时候,也要考虑二级索引。

void

FileHeader::Deallocate(BitMap *freeMap)

{

} if(second > 0){ Second* sec = new Second(); sec->FetchFrom(second); for(int j=NumDirect;j<numSectors;j++) { } } for (int i = 0; i < NumDirect; i++) { ASSERT(freeMap->Test((int) dataSectors[i])); // ought to be marked! freeMap->Clear((int) dataSectors[i]); ASSERT(freeMap->Test((int) sec->dataSectors[j-NumDirect])); freeMap->Clear((int) sec->dataSectors[j-NumDirect]); }

新的设计的实验内容和步骤:

s

在filesys文件夹下,执行make,然后执行如下命令: ./nachos –f //格式化一个新的磁盘 ./nachos –cp test/vb vb //将一个必须使用2级索引的文件拷入nachos的文件系统。 ./nachos –l //列出已有文件

以上设计实验输出结果的分析:

vb

No threads ready or runnable, and no pending interrupts. Assuming the program completed.

Machine halting!

Ticks: total 2600, idle 2330, system 270, user 0

Disk I/O: reads 4, writes 0

Console I/O: reads 0, writes 0

Paging: faults 0

Network I/O: packets received 0, sent 0

Cleaning up...

可以看出vb已经拷入。

本设计的创新点:

在本设计中,首先是比较完整的实现了一个简单的内存管理与系统调用,完成了实验的要求。 本设计存在的问题和没达到的功能:

1、 由于对C++的项组织与make工具不熟悉,使得如果把所有的实验放在一个项目中,

各个项目会相互影响,导致编译失败。因此,不得不把每个实验放在一个单独的项

目中。

调度算法只实现了一个,而文件系统没有实现变长文件。 2、

设计的体会、收获和总结

通过本次实验,使我对操作系统原理中提到的各种算法更加清晰,进一步加深了对操作

系统结构的理解。比如对于管程,以前一直不是很清楚,通过本次实验,才明白了其原理与实现。另外,以前对线程与进程的关系也很模糊,也是通过这次实验才有了清晰的认识。

只有通过实践,才能把理论真正理解清楚。

在这次实验中,也体现出了对CPP项目组织上的不足,以后需要加强。

更多相关推荐:
操作系统课程设计总结报告(白雪娇20xx3823)

操作系统课程设计总结报告学期20##-20##学年第二学期学院软件学院学号姓名20##年7月1日

操作系统课程设计报告

枣庄学院计算机科学系课程设计任务书题目学号20xx12230360姓名专业课程操作系统指导教师职称讲师完成时间20xx年06月20xx年06月枣庄学院计算机科学系制20xx年月日正文1课程设计简介11课程设...

操作系统SPOOLing系统实现课程设计心得

操作系统课程设计心得体会

操作系统课程设计报告

南通大学操作系统课程设计实验报告一设计内容利用C语言实现操作系统模拟算法和windows的系统调用编程分别设计进程调度的时间片轮转算法银行家算法信号量模拟超市购物算法信号量模拟停车场算法调试运行成功后将它们整合...

13级操作系统课程设计指导书

操作系统课程设计指导书李海霞编信息工程学院基础教学部二0一五年七月目录实验一Windows中线程与线程同步3实验二进程调度6实验三银行家算法8实验四请求页式存储管理中常用页面置换算法模拟14实验一Windows...

操作系统课程设计报告

目录一课程设计目标3二课题内容3三设计思路3四源代码5五运行与测试9六心得体会10一课程设计目标学习多线程编程使用线程的同步机制实现哲学家进餐问题具体要求1创建POSIX线程实现多线程的并发执行验证多线程共享进...

操作系统课程设计报告

一实验目的在该部分中根据设计题目的要求充分地分析和理解问题叙述系统的功能要求明确问题要求做什么以及限制条件是什么1输入的形式和输入值的范围2输出的形式3程序所能达到的功能二实验原理算法思想银行家算法是避免死锁的...

操作系统课程设计报告

操作系统课程设计报告专业学号姓名提交日期操作系统课程设计报告设计目的1本实验的目的是通过一个简单多用户文件系统的设计加深理解文件系统的内部功能和内部实现2结合数据结构程序设计计算机原理等课程的知识设计一个二级文...

20xx年操作系统课程设计题目与要求

操作系统课程设计题目与要求课程设计要求1可以依据教材中的算法自行选题也可以从下面给出的题目中选题要求每两名同学之间课程设计内容应该不同如果有选择相同题目的小组则设计方案不同否则视为抄袭可以两人一组也可以一人一题...

操作系统课程设计报告

课程设计说明书设计题目操作系统课程设计班级信管学号姓名山东科技大学20xx年12月15日课程设计任务书学院信息学院专业信息管理与信息系统班级112姓名胡晓迪一课程设计题目设计1死锁相关算法设计2CPU调度算法设...

操作系统课程设计题目

操作系统课程设计题目与要求一课程设计要求1根据每道题的人数选定题目2分析设计要求给出解决方案建立必要的数据结构然后设计总体流程包括界面详细设计必要的算法并最终显示结果基于WINDOWS或LINUX操作系统都可以...

操作系统课程设计-莫黎

课程设计报告课程名称操作系统课题名称进程调度算法的设计专业通信工程班级1101学号20xx03020xx5姓名莫黎指导教师20xx年6月29日湖南工程学院课程设计任务书课程名称课题专业班级通信1101学生姓名莫...

操作系统课程设计心得体会(31篇)