山大操作系统课程设计报告（全套）

计算机科学与技术学院实验报告：3

实验题目：信号量同步问题 日期：2010-11-10 姓名： 实验目的： 在本次实验中，通过使用信号量，在原有的程序框架的基础上添加关键代码实现生产者/消费者同步问题。从而深入理解Nachos的信号量的使用以及实现，生产者/消费者问题是如何用信号量实现的以及 在Nachos中是如何创建线程，实现多线程。 硬件环境： 软件环境： Linux 实验步骤： 1.首先初始化三个信号量，代码如下： mutex = new Semaphore(\信号量初始化为1，才能起到加锁功能 nfull = new Semaphore(\的大小在生产者没生产前为0 nempty = new Semaphore(\的大小应该为buffer的大小 2.首先考虑生产者进程，首先要查看buffer是否有空, nempty->P();if nempty>0,nempty=nempty -1，当对缓冲区操作时必须要加锁：mutex->P();加锁. 然后向ring中放入message信息，其次还要解锁mutex->V();解锁.最后通知消费者buffer有新信息, nfull->V();nfull=nfull+1；具体实现代码如下： 3. 考虑消费者进程，像生产者进程一样，查看buffer中是否有信息 nfull->P();if nfull>0,nfull-1；取消息时也要上锁，即：mutex->P();加锁. 然后从ring buffer中取出信息；其次mutex->V();解锁；最后通知生产者bufferr有空nempty->V();nempty=nempty+1，具体代码如下： 4. 创建线程生成一个生产者的代码： producers[i] = new Thread(prod_names[i]); producers[i] -> Fork(Producer,i); 4. 创建线程生成一个消费者的代码： producers[i] = new Thread(prod_names[i]); producers[i] -> Fork(Producer,i); 关键代码： void Producer(_int which) { int num; slot *message = new slot(0,0); for (num = 0; num < N_MESSG ; num++) { //这是消息创建的代码 message->thread_id=which; message->value=num; //p,v 操作 nempty->P(); mutex->P(); ring->Put(message); //p,v 操作 mutex->V(); nfull->V(); } } void Consumer(_int which) { char str[MAXLEN]; char fname[LINELEN]; int fd; slot *message = new slot(0,0); sprintf(fname, \ // create a file. Note that this is a UNIX system call. if ( (fd = creat(fname, 0600) ) == -1) { for (; ; ) { // p,v,操作 nfull->P(); mutex->P(); perror(\Exit(1); } ring->Get(message); // p,v,操作 mutex->V(); nempty->V(); // form a string to record the message sprintf(str,\ message->thread_id, message->value); //把信息写入文件 if ( write(fd, str, strlen(str)) == -1 ) { } //---------------------------------------------------------------------- // ProdCons // 初始化信号量以及需要的生产者消费者线程 //---------------------------------------------------------------------- void ProdCons() { int i; DEBUG('t', \ // 初始化信号量，包括一个访问互斥信号量，初值为1； //一个nempty信号量，初值为缓冲区的大小 //一个nfull的信号量，初值为0 mutex=new Semaphore(\ nempty=new Semaphore(\ nfull=new Semaphore(\ // 新建一个缓冲区 ring=new Ring(BUFF_SIZE+1); perror(\ Exit(1); } } // create and fork N_PROD of producer threads for (i=0; i < N_PROD; i++) { // this statemet is to form a string to be used as the name for // produder i. sprintf(prod_names[i], \ // 创建生产者线程 producers[i]=new Thread(prod_names[i]); producers[i]->Fork(Producer,i); }; // create and fork N_CONS of consumer threads for (i=0; i < N_CONS; i++) { // this statemet is to form a string to be used as the name for // consumer i. sprintf(cons_names[i], \ //创建消费者线程 consumers[i]=new Thread(cons_names[i]); consumers[i]->Fork(Consumer,i); }; } 调试记录： 在源代码中exit(0)没有大写，调试过程发现了这个问题改正， 在使用Linux系统调用写入文件时，有一个头文件没有引入，因而需要修改 #include #include \#include \#include #include 而且对于新添加的头文件的方法其中源文件使用的一个方法是废弃的，所以改成相应的方法write(fd, str, strlen(str))， 实验结果： 生成两个文件分别代表两个消费者取得的产品的记录。 文件tmp_0 producer id --> 0; Message number --> 3; 文件tmp_1 producer id --> 0; Message number --> 0; producer id --> 1; Message number --> 0; producer id --> 1; Message number --> 1; producer id --> 0; Message number --> 1; producer id --> 0; Message number --> 2; producer id --> 1; Message number --> 2; producer id --> 1; Message number --> 3; 分析结果： 从实验结果中可以看出，两个消费者取得的产品的顺序和生成者生产的顺序是一致的。结果正确。 （实验所在目录：home/lu/csc2404/nachos-3.4/code/lab3） 结论分析与体会： 在本次实验中，实现生产者/消费者同步问题，通过使用信号量，即Nachos 提供的系统调用，进一步理解Nachos的信号量的使用以及实现 同时，学会在Nachos中是如何创建线程，实现多线程，理解了多线程的问题。

计算机科学与技术学院实验报告：5

实验题目：扩展Nachos的文件系统 日期：2010-11-10 Email： 实验目的：

Nachos的文件系统的文件的大小是不可扩展的：文件被创建后，文件的大小就不能再改变。 本次实验的目的即是设计扩展Nachos的文件系统，使得文件的大小是可以被扩展的。 这样就可以实现在一个文件尾部或者中间追加文件。

硬件环境：

软件环境：

Linux操作系统，Nachos操作系统

实验步骤：

1， 了解Nachos文件系统的结构,为一级目录结构,

其中目录结构以及目录的使用记录保存在文件中。使用BitMap来获取空闲的扇区号。 class DirectoryEntry { public: bool inUse; int sector;

// Is this directory entry in use?

// Location on disk to find the

// FileHeader for this file

char name[FileNameMaxLen + 1]; // Text name for file, with +1 for };

这个是DirectoryEntry类，也就是目录项。 Directory::Directory(int size)

// the trailing '\\0'

{

table = new DirectoryEntry[size]; tableSize = size;

for (int i = 0; i < tableSize; i++) table[i].inUse = FALSE; }

这个是目录类，也就是一级目录结构的定义。 bool

Directory::Add(char *name, int newSector) {

if (FindIndex(name) != -1) return FALSE;

for (int i = 0; i < tableSize; i++) if (!table[i].inUse) { table[i].inUse = TRUE;

strncpy(table[i].name, name, FileNameMaxLen); table[i].sector = newSector; return TRUE; }

return FALSE; // no space. Fix when we have extensible files. }

这个是添加一个目录项的方法，当创建一个新文件的时候使用。 bool

FileSystem::Create(char *name, int initialSize)

这个是创建一个新的文件，其中主要工作是新建一个FileHeader， 作为一个目录项中保存的 int sector;

FileHeader，即文件头，中保存了这个文件的大小，所占的扇区的数目， 以及所占用的全部的扇区号。即：

int numBytes; // Number of bytes in the file

int numSectors; // Number of data sectors in the file

int dataSectors[NumDirect]; // Disk sector numbers for each data // block in the file

因此，为了实现对文件的追加工作，首先对FileHeader类里面加入新的方法

bool AppSectors(BitMap *freeMap, int fileSize);，为了改变一个文件的文件头的大小。

2， 实现在一个已有的文件尾部追加新的内容。首先写改变文件头中对文件所在扇区的描述，

由AppSectors来实现；该方法将在OpenFile类的对象执行Append File 时被调用。 对FileHeader类里面加入新的方法

bool AppSectors(BitMap *freeMap, int fileSize);

bool

FileHeader::AppSectors(BitMap *freeMap, int appFileSize) {

//如果要追加的文件大小小于等于0，则直接函数返回

if(appFileSize<=0)return true;

int restFileSize = SectorSize * numSectors - numBytes; /*如果要追加的文件的大小小于一个扇区的文件头可以表示的文件的大小， 则返回成功追加文件，即TRUE，否则返回FALSE*/ if(restFileSize >= appFileSize) {

numBytes += appFileSize; return true; } else {

int needFileSize = appFileSize - restFileSize;

if(freeMap->NumClear()< divRoundUp(needFileSize, SectorSize)) return false;

int i = numSectors;

numBytes += appFileSize;

numSectors += divRoundUp(needFileSize, SectorSize); for( ; i < numSectors; i++)

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

printf(\} 3，

在openfile.cc文件中，OpenFile类中加入方法，用于追加文件的AppFileSize（int numByte）。 这个方法首先从文件系统中获取空闲的扇区的位试图文件，构造BitMap对象， 传给FileHeader类的对象（也就是这个OpenFile的文件头），

执行AppSectors(BitMap *freeMap, int fileSize)方法，扩大文件的长度。

bool

OpenFile::AppFileSize(int numBytes) {

//fetch the bitmap

OpenFile *freeMapFile= new OpenFile(FreeMapSector); BitMap *freeMap = new BitMap(NumSectors); freeMap->FetchFrom(freeMapFile); //ask for new space

if(!(hdr->AppSectors(freeMap, numBytes)))return false;

printf(\ //write back the bitmap

freeMap->WriteBack(freeMapFile);

delete freeMapFile; delete freeMap; return true; } 4，

在fstest.cc文件中的修改Append方法，也就是在Nachos运行的时候执行命令， 例如：Nachos –x ap ../test/small small

这个方法是Nachos系统中本来就提供好的一个方法，只需要在局部修改一下语句， 就可以正确的运行。

void

Append(char *from, char *to, int half) {

/*fileLength 是计算出来的Linux文件中的文件的大小

fileLengthBefore是指追加之前的Nachos系统的文件的大小 start是文件开始追加的位置 */

FILE *fp;

OpenFile* openFile;

int amountRead, fileLength; char *buffer;

// start position for appending int start;

// Open UNIX file

if ((fp = fopen(from, \

printf(\ return; }

// Figure out length of UNIX file fseek(fp, 0, 2); fileLength = ftell(fp); fseek(fp, 0, 0);

if (fileLength == 0) {

printf(\ return; }

if ( (openFile = fileSystem->Open(to)) == NULL) {

// file \ if (!fileSystem->Create(to, 0)) {

printf(\ fclose(fp); return; }

openFile = fileSystem->Open(to); }

int fileLengthBefore=openFile->Length();

/*执行追加，并判断要追加文件的大小是否超过最大长度*/

if(!(openFile->AppFileSize(fileLength))) {

printf(\//too long file to append

return; }

3. Nachos原来实现AddressSpace分配的时候没有使用bitmap来寻找空闲页，而是直接的从0号内存空间 开始分配，因而需要修改成使用bitmap的find函数分配内存空间 其中，要声明一个位试图的是对象，在AddrSpace中 并且数据段代码段按页存储。 4. 计算加载一个程序需要的页表的数目 5. 实现Nachos的系统调用，采用的是触发异常中断的，在userprog/exception.cc，添加SC_Exec异常， 存放要执行的文件的路径的字符串的首地址存放在4号寄存器中，因此可以通过这个方式找到文件的路径， 从而使用文件系统提供的方法打开这个文件： 6. 结果分析： 编译成功之后，输入命令 ./nachos –x ../test/Exec.noff 运行结果： lu@ubuntu:~/csc2404/nachos-3.4/code/userprog$ ./nachos -x ../test/exec.noff page table dump: 12 pages in total ========================================================= VirtPage, PhysPage 0, 0 1, 1 2, 2 3, 3 4, 4 5, 5 6, 6 7, 7 8, 8 9, 9 10, 10 11, 11 =========================================================== the allocated physical Address:0 he address in the executable file :40 copy size 128 the allocated physical Address:128 he address in the executable file :168 copy size 128 the allocated physical Address:256 he address in the executable file :296 copy size 128 SC_Exec in exceptionHandler The value of the register 4 is, .i.e. the address of the String 272 add content of fn is now: 742f2e2e the char view is . . / t add content of fn is now: 2f747365 the char view is e s t / add content of fn is now: 746c6168 the char view is h a l t add content of fn is now: 666f6e2e the char view is . n o f add content of fn is now: 66 the char view is f add content of fn is now: 0 the char view is add content of fn is now: 0 the char view is add content of fn is now: 0 the char view is add content of fn is now: 0 the char view is add content of fn is now: 0 the char view is Exec file is ../test/halt.noff page table dump: 11 pages in total ========================================================= VirtPage, PhysPage 0, 12 1, 13 2, 14 3, 15 4, 16 5, 17 6, 18 7, 19 8, 20 9, 21 10, 22 =========================================================== the allocated physical Address:1536 he address in the executable file :40 copy size 128 the allocated physical Address:1664 he address in the executable file :168 copy size 128 the allocated physical Address:1792 he address in the executable file :296 copy size 128 Machine halting! Ticks: total 50, idle 0, system 10, user 40 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... lu@ubuntu:~/csc2404/nachos-3.4/code/userprog$ 加载进来的程序的地址空间没有覆盖原来那个程序的地址空间,使用新的地址空间去执行关机操作 Machine halting! 实现了一个程序加载另一个程序运行。 (实验所在路径： csc2404/nachos-3.4/code/ multiProcess 主要修改的文件，addrspace.cc exception.cc ) 结论分析与体会： Nachos之前没有实现按页分配地址空间，物理页和逻辑页地址一致，而且数据段代码段连续分配 每当一个新的用户程序建立的时候，虚拟地址和物理地址都是从0开始分配，这样新的用户程序 将会冲掉原来在物理0开始的程序。 因而使用位示图分配物理地址。使用bitmap的find函数分配虚存对应的物理地址，在为数据段和 代码段写入数据的时候是以扇区为单位的，而不是原有的连续一个文件的读入连续的内存。 Nachos操作系统通过中断的方式实现系统调用。需要增加userprog/exception.cc中的内容，即 必须在此类中添加处理Exec的方法。 返回

计算机科学与技术学院实验报告：9

实验题目：设计并实现具有优先级的线程调度策略 日期：2010-11-13 Email： 实验目的：

Nachos系统采用基本的FCFS的线程调度策略，修改成为具有优先级的线程调度策略

硬件环境：

软件环境：

linux操作系统，Nachos操作系统

实验步骤：

1．修改Thread类的构造函数，加入优先级priority属性，并且加入getPrioty方法。以便在线程的 等待队列中找到优先级最高的线程。其中，线程优先级的范围从1到7，默认为7，即最低优先级。 修改代码如下：（thread.cc,thread.h） class Thread {

…………………………………… public:

Thread(char* debugName, int priority=7);// initialize a Thread ………………………………………………… int getPriority(){return this->priority; }

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

if(p<1) priority = 1;

else if(p>7) priority = 7; else priority = p; name = threadName; stackTop = NULL; stack = NULL;

status = JUST_CREATED; #ifdef USER_PROGRAM space = NULL; #endif }

2，首先，了解Nachos系统原来的线程调度方式。通过读threadtest.cc,thread.cc,scheduler.cc文件 中的内容了解线程调度的方式。

首先，修改threadtest.cc 文件中的ThreadTest方法，创建有优先级的Thread，代码如下：

然后，从Thread类中找到Fork方法，代码如下：

这说明ThreadTest方法的目的是，实例化新的线程，调用Fork方法，也就是让新产生的线程去执行SimpleThread方法，并且把 当前执行的线程加入到等待队列。

从SimpleThread的定义中可以知道，新生产的线程就是打印一条信息然后去执行Yield（）；

通过查看yield，可知，先从等待队列中找到一个线程保留在nextThread中，并将当前线程加到等待队列，然后使nextThread运行 void

Thread::Yield () {

Thread *nextThread;

IntStatus oldLevel = interrupt->SetLevel(IntOff);

ASSERT(this == currentThread);

DEBUG('t', \

nextThread = scheduler->FindNextToRun(); if (nextThread != NULL) { scheduler->ReadyToRun(this); scheduler->Run(nextThread); }

(void) interrupt->SetLevel(oldLevel); }

3， 为了实现按优先级调度，需要按优先级选择等待队列中的，即状态为ready的线程，因而，在线程插入，移除等待队列的时候使用List类中提供好的SortedInsert(void *item, int sortKey) SortedRemove(int *keyPtr)

方法，而不是原来使用的Append，Remove方法；

void

Scheduler::ReadyToRun (Thread *thread) {

DEBUG('t', \

thread->setStatus(READY);

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

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

Thread *

Scheduler::FindNextToRun () {

int p;

return (Thread *)readyList->SortedRemove(&p); }

4， 结果显示：

lu@ubuntu:~/csc2404/nachos-3.4/code/threadsWithPrioty$ ./nachos ******* thread 2 looped 0 times ******* thread 4 looped 0 times ******* thread 2 looped 1 times ******* thread 2 looped 2 times ******* thread 4 looped 1 times ******* thread 2 looped 3 times ******* thread 4 looped 2 times ******* thread 2 looped 4 times ******* thread 4 looped 3 times ******* thread 4 looped 4 times ******* thread 5 looped 0 times ******* thread 5 looped 1 times ******* thread 5 looped 2 times ******* thread 3 looped 0 times ******* thread 5 looped 3 times ******* thread 3 looped 1 times ******* thread 5 looped 4 times ******* thread 3 looped 2 times ******* thread 1 looped 0 times ******* thread 3 looped 3 times ******* thread 1 looped 1 times ******* thread 3 looped 4 times ******* thread 1 looped 2 times ******* thread 1 looped 3 times ******* thread 1 looped 4 times

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...

5， 结果分析：

可以看出，线程执行的顺序不是在ThreadTest中的生成Thread（1,2,3,4,5）的顺序，而是按照优先级的顺序 调度的。首先从等待队列中找一个优先级最高的线程，然后把当前运行的线程加入到等待队列中，然后再运行

（本次实验所在所在位置：csc2404/nachos-3.4/code/threadsWithPrioty） 结论分析与体会：

通过这个实验，为了实现线程优先级的调度，细致分析了Thread目录下的各个文件的内容，尤其是thread.cc， Scheduler.cc，文件中对于线程的状态，以及调度函数的实现等问题上面有了更深一步的了解。从而，知道如何 修改可以实现线程的优先级调度问题，也就是管理一个SortedList，其内容是状态为Ready的线程。 由概念到实践，了解了简单的线程调度的实现。

返回

计算机科学与技术学院实验报告：10

实验题目：具有二级索引的文件系统 日期：2010-11-18 Email： 实验目的：

Nachos的文件系统中保存文件内容所在扇区索引的“文件头“目前只占用一个扇区，

为了可以使Nachos文件系统创建较大的文件，将”文件头”扩大到两个扇区，也就是实现二级索引。

硬件环境：

软件环境：

Linux操作系统，Nachos操作系统

实验步骤：

1， 通过实验5的扩展文件大小的实验，了解了nachos 系统的对文件系统的管理。本次实验的目的主要是 扩大Nachos系统可以创建的文件的大小，使用两个扇区来保存文件头的信息。 为了达到这个目的，首先了解nachos 自带的文件系统的文件头的结构： 保存在一个扇区中，第一个int保存了文件的字节数（numBytes），第二个int保存了使用的扇区数 （numSectors），第三个数据结构是文件所在的各个扇区号（dataSectors[NumDiresct]）。 也就是说，Nachos系统采用的是索引式的文件管理方式。

因而，要实现nachos文件系统的二级索引，可以使第一个索引节点（也就是原有的文件头那个扇区）的 dataSectors数组的最后一个元素保留第二个索引节点（也就是第二个扇区）的引用（也就是扇区号）。 如果文件大小不超过一个索引节点可以保留的内容，则这个最后一个元素的值为-1。

2， 通过分析可知，需要修改filehdr.cc中的内容。 代码如下： bool

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

numBytes = fileSize;

numSectors = divRoundUp(fileSize, SectorSize); if (freeMap->NumClear() < numSectors)

return FALSE; // not enough space

/*如果文件大小超过索引节点中保存扇区号的数目，则返回false*/ else if(NumDirect + NumDirect2 <= numSectors)

return FALSE;//the filesys cannot support such big file

/*toNextNode 是保留第二个索引节点的扇区号*/

int toNextNode=NumDirect-1; //toNextNode is the Sector number of the second node of the filehd

//if the second node is not needed, then dataSector[toNextNode]=-1 if(numSectors < toNextNode) {

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

dataSectors[i] = freeMap->Find();//为文件分配扇区

dataSectors[toNextNode] = -1; }

//If the numSectors excends the rage of dataSectors,

else{

for (int i = 0; i < toNextNode; i++) dataSectors[i] = freeMap->Find();

dataSectors[toNextNode] = freeMap->Find();//找一个空闲的扇区，作为第二个扇区，索引节点

//this is the content,i.e.filehdr of the allocated sectors, of the second node

int dataSectors2[NumDirect2];

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

dataSectors2[i] = freeMap->Find();//为文件分配扇区

//the fefault synchDisk->WriteSector do not include the second node //so write back the new build node

synchDisk->WriteSector(dataSectors[toNextNode], (char *)dataSectors2); }

return TRUE;

/*revised*/ }

void

FileHeader::Deallocate(BitMap *freeMap) {

/*toNextNode 是保留第二个索引节点的扇区号*/

int toNextNode= NumDirect - 1;

// test if has the second node if(dataSectors[toNextNode]==-1) {

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

ASSERT(freeMap->Test((int) dataSectors[i])); // ought to be marked! freeMap->Clear((int) dataSectors[i]); } }

//has a second node, then find it, then clean the bitmap, then else {

//clear the first n-1 bit,remain the toNextNode int i=0;

for ( ; i < toNextNode; i++) {

ASSERT(freeMap->Test((int) dataSectors[i])); // ought to be marked! freeMap->Clear((int) dataSectors[i]); }

int dataSectors2[NumDirect2];

synchDisk->ReadSector(dataSectors[toNextNode], (char *)dataSectors2); freeMap->Clear((int) dataSectors[toNextNode]);//clear the toNextNode

for( ; i < numSectors; i++)

freeMap->Clear((int) dataSectors2[i-toNextNode]);//toNextNode==the number of filehdr item} } int

FileHeader::ByteToSector(int offset) {

ASSERT(offset<=numBytes);

/*toNextNode 是保留第二个索引节点的扇区号*/

int toNextNode = NumDirect - 1; //test if offset excedes the first node if(offset / SectorSize < toNextNode)

return(dataSectors[offset / SectorSize]); else {

int dataSectors2[NumDirect2];

synchDisk->ReadSector(dataSectors[toNextNode], (char *)dataSectors2); return (dataSectors2[offset / SectorSize - toNextNode]); } }

void

FileHeader::Print() {

/*revised*/ int i, j, k;

/*toNextNode 是保留第二个索引节点的扇区号*/

int toNextNode = NumDirect - 1;

char *data = new char[SectorSize];

//test if there is a second node if(dataSectors[toNextNode] == -1) {

printf(\ for (i = 0; i < numSectors; i++) printf(\ printf(\

for (i = k = 0; i < numSectors; i++) { synchDisk->ReadSector(dataSectors[i], data);

for (j = 0; (j < SectorSize) && (k < numBytes); j++, k++) { if ('\\040' <= data[j] && data[j] <= '\\176') // isprint(data[j])

printf(\ else

printf(\}

printf(\ } }

// If there is a secondary index,

// first read in the dataSectors2 from the Disk. // Then, deallocate the data blocks for this file.

// At last, deallocate the block that dataSector2 locates. else {

int dataSectors2[NumDirect2];

synchDisk->ReadSector(dataSectors[toNextNode], (char *)dataSectors2); //1, print the filedre items

printf(\ for (i = 0; i < toNextNode; i++) printf(\for(; i < numSectors; i++)

printf(\ printf(\

//2,print the content of the first node pointed for (i = k = 0; i < toNextNode; i++) { synchDisk->ReadSector(dataSectors[i], data);

for (j = 0; (j < SectorSize) && (k < numBytes); j++, k++) { if ('\\040' <= data[j] && data[j] <= '\\176') // isprint(data[j]) printf(\ else

printf(\}

printf(\ }

//3,print the content of the second node pointed for( ; i < numSectors; i++) {

synchDisk->ReadSector(dataSectors2[i - toNextNode], data);

for (j = 0; (j < SectorSize) && (k < numBytes); j++, k++) { if ('\\040' <= data[j] && data[j] <= '\\176') // isprint(data[j]) printf(\ else

printf(\}

printf(\

} }

delete [] data; /*revised*/ } bool

FileHeader::AppSectors(BitMap *freeMap, int appFileSize) {

/*revised*/

if(appFileSize <= 0)return false;

int restFileSize = SectorSize * numSectors - numBytes;

if(restFileSize >= appFileSize) {

numBytes += appFileSize; return true; } else {

int moreFileSize = appFileSize - restFileSize;

if(freeMap->NumClear()< divRoundUp(moreFileSize, SectorSize)) return FALSE;

else if(NumDirect + NumDirect2 <= numSectors + divRoundUp(moreFileSize, SectorSize)) return FALSE;

int i = numSectors;

numBytes += appFileSize;

numSectors += divRoundUp(moreFileSize, SectorSize);

/*toNextNode 是保留第二个索引节点的扇区号*/

int toNextNode = NumDirect-1; //test if has the second node if(dataSectors[toNextNode] == -1) {

//test if need the second node if(numSectors < toNextNode) for( ; i < numSectors; i++)

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

//need the second node else {

for( ; i< toNextNode ; i++)

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

dataSectors[toNextNode] = freeMap ->Find(); int dataSectors2[NumDirect2]; for ( ; i < numSectors ; i++)

dataSectors2[i - toNextNode] = freeMap->Find();

synchDisk->WriteSector(dataSectors[toNextNode], (char *)dataSectors2); } } /*

* If before appending, there is already a secondary index */

//First read the dataSectors2 from the Disk. //Then, append the file size.

//At last, write back the secondary index block into the sector, else {

int dataSectors2[NumDirect2];

synchDisk->ReadSector(dataSectors[toNextNode], (char *)dataSectors2); for( ; i < numSectors; i++)

dataSectors2[i-toNextNode] = freeMap -> Find();//the var toNextNode==the number of int that synchDisk->WriteSector(dataSectors[toNextNode], (char *)dataSectors2);//the fefault synchDisk } }

return TRUE; /*revised*/ }

运行结果：首先运行命令 ./nachos –f 格式化Nachos磁盘

然后运行 ./nachos –ap test/big big 若干次，知道出现提示，文件太大不能再追究为止。 start value: 1168, amountRead 10, result of write: 10 start value: 1178, amountRead 10, result of write: 10 start value: 1188, amountRead 10, result of write: 10 start value: 1198, amountRead 10, result of write: 10 start value: 1208, amountRead 8, result of write: 8 inodes have been written back

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

Machine halting!

Ticks: total 1091100, idle 1086750, system 4350, user 0 Disk I/O: reads 76, writes 68 Console I/O: reads 0, writes 0 Paging: faults 0

Network I/O: packets received 0, sent 0

Cleaning up...

lu@ubuntu:~/csc2404/nachos-3.4/code/filesys2nodehdr$ ./nachos -ap test/big big The appending file is too big! Appending file failed

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

Ticks: total 4200, idle 3970, system 230, user 0 Disk I/O: reads 7, writes 0 Console I/O: reads 0, writes 0 Paging: faults 0

Network I/O: packets received 0, sent 0

Cleaning up...

然后运行 ./nachos -ap test/small big ，直到可以出现The appending file is too big!

lu@ubuntu:~/csc2404/nachos-3.4/code/filesys2nodehdr$ ./nachos -ap test/small big openFile see filesize 7790 value of start 38

start value: 38, amountRead 10, result of write: 10 start value: 48, amountRead 10, result of write: 10 start value: 58, amountRead 10, result of write: 10 start value: 68, amountRead 8, result of write: 8 inodes have been written back

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

Ticks: total 83100, idle 82470, system 630, user 0 Disk I/O: reads 14, writes 6 Console I/O: reads 0, writes 0 Paging: faults 0

Network I/O: packets received 0, sent 0

Cleaning up...

lu@ubuntu:~/csc2404/nachos-3.4/code/filesys2nodehdr$ ./nachos -ap test/small big The appending file is too big! Appending file failed

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

Ticks: total 4200, idle 3970, system 230, user 0 Disk I/O: reads 7, writes 0 Console I/O: reads 0, writes 0 Paging: faults 0

Network I/O: packets received 0, sent 0

Cleaning up...

然后显示结果，运行命令 ./nachos –D

lu@ubuntu:~/csc2404/nachos-3.4/code/filesys2nodehdr$ ./nachos -D Bit map file header:

FileHeader contents. File size: 128. File blocks: 2

File contents:

\\ff\\ff\\ff\\ff\\ff\\ff\\ff\\ff\\f\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\\\0\\0

Directory file header:

FileHeader contents. File size: 200. File blocks: 3 4

File contents:

\\1\\0\\0\\0\\5\\0\\0\\0big\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\Bitmap set:

0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, Directory contents: Name: big, Sector: 5

FileHeader contents. File size: 7790. File blocks:

6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 File contents:

This is the spring of our discontent.\\aThis is the spring of our discontent.\\aThis is the spring ring of our discontent.\\aThis is the spring of our discontent.\\aThis is the spring of our discontscontent.\\aThis is the spring of our discontent.\\aThis is the spring of our discontent.\\aThis is is the spring of our discontent.\\aThis is the spring of our discontent.\\aThis is the spring of o of our discontent.\\aThis is the spring of our discontent.\\aThis is the spring of our discontent.

tent.\\aThis is the spring of our discontent.\\aThis is the spring of our discontent.\\aThis is the the spring of our discontent.\\aThis is the spring of our discontent.\\aThis is the spring of our dour discontent.\\aThis is the spring of our discontent.\\aThis is the spring of our discontent.\\aTh.\\aThis is the spring of our discontent.\\aThis is the spring of our discontent.\\aThis is the sprispring of our discontent.\\aThis is the spring of our discontent.\\aThis is the spring of our discodiscontent.\\aThis is the spring of our discontent.\\aThis is the spring of our discontent.\\aThis iis is the spring of our discontent.\\aThis is the spring of our discontent.\\aThis is the spring ofng of our discontent.\\aThis is the spring of our discontent.\\aThis is the spring of our discontenontent.\\aThis is the spring of our discontent.\\aThis is the spring of our discontent.\\aThis is ths the spring of our discontent.\\aThis is the spring of our discontent.\\aThis is the spring of ourf our discontent.\\aThis is the spring of our discontent.\\aThis is the spring of our discontent.\\ant.\\aThis is the spring of our discontent.\\aThis is the spring of our discontent.\\aThis is the spe spring of our discontent.\\aThis is the spring of our discontent.\\aThis is the spring of our disr discontent.\\aThis is the spring of our discontent.\\aThis is the spring of our discontent.\\aThisThis is the spring of our discontent.\\aThis is the spring of our discontent.\\aThis is the spring ring of our discontent.\\aThis is the spring of our discontent.\\aThis is the spring of our discontscontent.\\aThis is the spring of our discontent.\\aThis is the spring of our discontent.\\aThis is is the spring of our discontent.\\aThis is the spring of our discontent.\\aThis is the spring of o of our discontent.\\aThis is the spring of our discontent.\\aThis is the spring of our discontent.tent.\\aThis is the spring of our discontent.\\aThis is the spring of our discontent.\\aThis is the the spring of our discontent.\\aThis is the spring of our discontent.\\aThis is the spring of our dour discontent.\\aThis is the spring of our discontent.\\aThis is the spring of our discontent.\\aTh.\\aThis is the spring of our discontent.\\aThis is the spring of our discontent.\\aThis is the sprispring of our discontent.\\aThis is the spring of our discontent.\\aThis is the spring of our discodiscontent.\\aThis is the spring of our discontent.\\aThis is the spring of our discontent.\\aThis iis is the spring of our discontent.\\aThis is the spring of our discontent.\\aThis is the spring ofng of our discontent.\\aThis is the spring of our discontent.\\aThis is the spring of our discontenontent.\\aThis is the spring of our discontent.\\aThis is the spring of our discontent.\\aThis is ths the spring of our discontent.\\aThis is the spring of our discontent.\\aThis is the spring of ourf our discontent.\\aThis is the spring of our discontent.\\aThis is the spring of our discontent.\\ant.\\aThis is the spring of our discontent.\\aThis is the spring of our discontent.\\aThis is the spe spring of our discontent.\\aThis is the spring of our discontent.\\aThis is the spring of our disr discontent.\\aThis is the spring of our discontent.\\aThis is the spring of our discontent.\\aThisThis is the spring of our discontent.\\aThis is the spring of our discontent.\\aThis is the spring ring of our discontent.\\aThis is the spring of our discontent.\\aThis is the spring of our discontscontent.\\aThis is the spring of our discontent.\\aThis is the spring of our discontent.\\aThis is is the spring of our discontent.\\aThis is the spring of our discontent.\\aThis is the spring of o of our discontent.\\aThis is the spring of our discontent.\\aThis is the spring of our discontent.tent.\\aThis is the spring of our discontent.\\aThis is the spring of our discontent.\\aThis is the the spring of our discontent.\\aThis is the spring of our discontent.\\aThis is the spring of our dour discontent.\\aThis is the spring of our discontent.\\aThis is the spring of our discontent.\\aTh.\\aThis is the spring of our discontent.\\aThis is the spring of our discontent.\\aThis is the sprispring of our discontent.\\aThis is the spring of our discontent.\\aThis is the spring of our discodiscontent.\\aThis is the spring of our discontent.\\aThis is the spring of our discontent.\\aThis i

is is the spring of our discontent.\\aThis is the spring of our discontent.\\aThis is the spring ofng of our discontent.\\aThis is the spring of our discontent.\\aThis is the spring of our discontenontent.\\aThis is the spring of our discontent.\\aThis is the spring of our discontent.\\aThis is ths the spring of our discontent.\\aThis is the spring of our discontent.\\aThis is the spring of ourf our discontent.\\aThis is the spring of our discontent.\\aThis is the spring of our discontent.\\ant.\\aThis is the spring of our discontent.\\aThis is the spring of our discontent.\\aThis is the spe spring of our discontent.\\aThis is the spring of our discontent.\\aThis is the spring of our disr discontent.\\aThis is the spring of our discontent.\\aThis is the spring of our discontent.\\aThis\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\

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

Ticks: total 82200, idle 79780, system 2420, user 0 Disk I/O: reads 73, writes 0 Console I/O: reads 0, writes 0 Paging: faults 0

Network I/O: packets received 0, sent 0

Cleaning up... 结果分析：

Directory contents: Name: big, Sector: 5

FileHeader contents. File size: 7790. File blocks:

6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67

原有的nachos 系统中，一个索引节点，一个扇区的大小事128byte，所以，可以保存32个int类型的元素。

其中dataSectors数组最多有30个元素，改为二级索引时，最多有29个有效的元素，加上第二个索引的扇区一共可以有效指向文件的扇区最多有29+32=61个，

这个Name：big的文件所有占有的最多的扇区数目也就是，34-5+67-35=61 ,符合。 说明实现了二级索引节点的文件系统。

（实验目录：/csc2404/nachos-3.4/code/filesys2nodehdr）

结论分析与体会：

本次实验通过完成使Nachos文件系统创建较大的文件，将”文件头”扩大到两个扇区，也就是实现二级索引， 进一步了解了文件系统里面的概念以及实现细节的部分。深刻的理解了对于索引式的文件存储管理方式中， 文件在磁盘上的扇区号如何在索引节点中保存，索引节点空间如何扩大成为使用两个扇区的索引等问题。 同时，注意了对磁盘操作时需要写回磁盘中的操作。

返回

计算机科学与技术学院实验报告：11

实验题目：用户空间的虚拟内存管理 日期：2010-11-20 实验目的： 在原有的Nachos内存管理基础上实现虚拟内存管理，从而可以运行更大的noff格式的文件 硬件环境：

软件环境：

Linux，Nachos，Mips

实验步骤：

1， 理解实现虚拟内存的原理方法，参考Homework3 VirtualMemory.mht文件。

实现虚拟内存的内存管理方式，首先，为了简单方便，不涉及增加更多数据结构，选择了

为每一个进程分配一个Swap的文件，保存在磁盘中，即相当于交换区。这样每一个进程的Addresspace只需 保存它的swap文件即可，swap文件的内容与虚拟页一一对应，可以通过虚拟页号之间访问相应位置，

因而，当指令中需要的虚拟页在内存中不存在时，就可以直接到是swap文件相应位置读入内存的Frame中。 这样做，可以不用创建一个新的map来影射一个进程的虚拟页和在交换区的扇区号，在查找时也可以方便； 但是这样做就不能充分的利用磁盘空间，只能实现局部的页面置换（即在同一个进程之中的， 而不能实现全局页面置换）

2， 使用按需分页方法，首先为设定为每一个进程初始化分配的内存空间，也就是最小分配的空间，设为6； 一个进程可以拥有的最大的内存空间，设为25，用来判断这个进程可以使用内存的最大frame数；

分别定义在初始化的时候，数据段分配2个frame，代码段分配12个frame，userstack分配1个frame。

所以，需要在AddrSpace类定义中，怎么加两个属性，以保存虚拟内存的名字以及已经使用的内存帧数；

3， 修改原有的进程初始化分配内存空间的方法，也就是AddrSpace的构造函数。

首先为代码段分配最小的内存空间，用bitmapt的find方法找到frame，填入页表项。然后分配堆栈段 1frame的空间。将其余页表项的physicalpage设为-1，也就是不分配内存；

然后将可执行文件的相应内容到内存空间，并把可执行文件的代码，初始化数据段都载入到swap文件中， 便于在页错误时候访问。

代码如下：

AddrSpace::AddrSpace(OpenFile *executable) { NoffHeader noffH; unsigned int i,size,size1,check,count1; OpenFile* execFile; char*buffer; executable->ReadAt((char *)&noffH, sizeof(noffH), 0); if ((noffH.noffMagic != NOFFMAGIC)&&(WordToHost(noffH.noffMagic) == NOFFMAGIC)) SwapHeader(&noffH); ASSERT(noffH.noffMagic == NOFFMAGIC); printf(\ printf(\ printf(\ printf(\ size = divRoundUp(noffH.code.size,PageSize) * PageSize + divRoundUp(noffH.initData.size, PageSize)+ UserStackSize; numPages = divRoundUp(size, PageSize); size = numPages * PageSize; printf(\ extern BitMap *Mmbmp; if(numPages<=MinimumPages) check=numPages; else{

check=MinimumPages; int j=0; if(Mmbmp->NumClear()Create(virtualName,size); execFile=fileSystem->Open(virtualName); printf(\ } size1=check*PageSize; ASSERT(check <= Mmbmp -> NumClear());//检测是否有执行线程所需的最少物理页数，没有则不启动任务 DEBUG('a', \

/*初始化count，为可以装入内存的code page 的页数*/ count = divRoundUp(noffH.code.size,PageSize); if(count>CodePages)//可以装入主存的代码页数 count=CodePages; count1=count; pageTable = new TranslationEntry[numPages]; /*为可以装入内存的code page 分配页表*/ printf(\ for (i = 0; i < count; i++) { pageTable[i].virtualPage = i; pageTable[i].physicalPage = Mmbmp->Find(); pageTable[i].valid = FALSE; pageTable[i].use = FALSE; pageTable[i].dirty = FALSE; pageTable[i].readOnly = FALSE; // if the code segment was entirely on // a separate page, we could set its pages to be read-only } /*为不能装载如内存的虚拟页分配页表，即不分配物理祯*/ int last=numPages-1; for (;i < last;i++) {

pageTable[i].virtualPage = i; pageTable[i].physicalPage = -1; pageTable[i].valid = FALSE; pageTable[i].use = FALSE; pageTable[i].dirty = FALSE; pageTable[i].readOnly = FALSE; }

/*为装入内存的1个用户堆栈段分配一个物理祯*/ printf(\ for(i=numPages-1;iFind(); pageTable[i].valid = TRUE; pageTable[i].use = FALSE; pageTable[i].dirty = FALSE; pageTable[i].readOnly = FALSE; /*使用的物理页数加1*/ count++; } /*在内存和swap中加载可执行文件的内容*/

if (noffH.code.size > 0) {

DEBUG('a', \ noffH.code.virtualAddr, noffH.code.size); printf(\ unsigned int numP,firstP,c,amount; firstP = divRoundUp(noffH.code.virtualAddr,PageSize); numP = firstP + count1; for (i=firstP;iReadAt(&(machine->mainMemory[pageTable[i].physicalPage*PageSize]), PageSize,noffH.code.inFileAddr+i*PageSize); printf(\ pageTable[i].valid = TRUE; }

/*如果有没有加入内存的页，就把所有的Code页写入到Swap中*/ if(numPages>MinimumPages){//Load code of the executable into the virtual memory buffer = new char[PageSize];

int j,n1 = divRoundUp(noffH.code.size,PageSize) - 1; printf(\ for(j=0;jReadAt(buffer,PageSize,noffH.code.inFileAddr+j*PageSize); printf(\ execFile->WriteAt(buffer,PageSize,noffH.code.virtualAddr+j*PageSize); } amount=executable->ReadAt(buffer,noffH.code.size-n1*PageSize,noffH.code.inFileAddr+j*Page printf(\ execFile->WriteAt(buffer,noffH.code.size-n1*PageSize,noffH.code.virtualAddr+j*PageSize);/ if(noffH.initData.size == 0){ delete execFile; delete [] buffer; } printf(\ } }

/*为initData分配页表，内存空间，载入到内存，swap中的*/ if (noffH.initData.size > 0) { DEBUG('a', \ printf(\ unsigned int numP,firstP,c; numP = divRoundUp(noffH.initData.size,PageSize); firstP = divRoundUp(noffH.initData.virtualAddr,PageSize); if(numP<=DataPages) c=firstP+numP; else c=firstP+DataPages; for (i=firstP;iFind(); executable->ReadAt(&(machine->mainMemory[pageTable[i].physicalPage*PageSize]),PageSize,noffH.iniize); pageTable[i].valid = TRUE;// } count+=DataPages; if(numPages>MinimumPages){//Load initialdata of the executable into the virtual memory int n1 = divRoundUp(noffH.initData.size,PageSize) - 1 + firstP;

printf(\ for(i=firstP;i

executable->ReadAt(buffer,PageSize,noffH.initData.inFileAddr+(i-firstP)*PageSize); execFile->WriteAt(buffer,PageSize,noffH.initData.virtualAddr+(i-firstP)*PageSize); } executable->ReadAt(buffer,noffH.initData.size-(n1-firstP)*PageSize,noffH.initData.inFileA execFile->WriteAt(buffer,noffH.initData.size-(n1-firstP)*PageSize,noffH.initData.virtualA printf(\ printf(\ delete execFile; delete [] buffer; } }

/*打印页表的内容*/ Print(); }

此外，添加了一个Print（）方法，显示页表的内容：

4， 增加处理页错误的方法，选择页面置换算法为lru算法，仿照在线程优先级调度中的等待队列，在system.cc中声明一个List类型的变量，保留进程使用的虚拟页的页号，最近使用的放在尾部，因而当一个进程需要的 内存空间超过可以分配的最大页的时候，需要进行局部的页面置换，从该链表的头部取得最近最少使用的 虚拟页号，通过查该进程的页表找到该虚拟页对应的物理页，将这个物理页交给需要加载入内存的虚拟页， 然后从swap中找到需要换入的页，读入到内存相应的地址，修改页表相应的项，如果被换出的页面有被修改，即dirty位为true，则还要将被换出的页写回到swap相应的位置。

处理物理地址，逻辑地址翻译工作的方法为machine 中的Translate方法，因而，在此方法中，加入相应的 调整进程以用逻辑页的List中的顺序的代码，即把vpn号从链表中拿出来放到最后，为了完成这个工作，

还需要在List类中新加入方法： void

List::append(unsigned int &key)//将值为key的元素追加到链表尾部 bool

List::remove(unsigned int &key//删掉值为key 的元素 int

List::getlru()//删掉链表头部，并把头部元素的值返回

void List::print()//打印这个链表

bool List::find(unsigned int &key) //检查是否能找到值为key的元素 ExceptionType

Machine::Translate(int virtAddr, int* physAddr, int size, bool writing) { 。。。。

extern List *lru; if(lru->find(vpn)) lru->remove(vpn); lru->append(vpn); 。。。。。。 }

页面置换的具体实现，在exception.cc中实现。

在exception中加入SC_Exit，PageFaultException 异常的处理，

加入SC_Exit异常的处理，因为在Sort.c中，有Exit（A[20]）的Nachos系统调用，也就是把A[20]地址传给了4号寄存器，因而可以通过打印出其内容判断一下sort程序是否正确的执行。

通过打印出 代码如下：

else if((which == SyscallException) && (type == SC_Exit)){

int exitaddr = machine->ReadRegister(4);//读出Exit()调用的参数地址 int *status;

//machine->ReadMem(exitaddr,4,status); status=&exitaddr; if(*status==0) {

printf(\！%d\\n\ }

else

printf(\！%d\\n\ currentThread->Finish(); }

PageFaultException 异常的处理，在发生页错误的时候调用的方法

主要是处理页面置换的方法，如果该进程的space属性中的count属性表示

它没有超过可以使用的最多的物理帧数的话，就可以继续分配一个新的物理帧，这时候没有页面的置换，

将那个页从swap加载进内存的操作；如果count 的值显示它已经占用了最大的内存帧数，则需要进行页面置换。从保存的list中找到最近最少使用的页面，如果它有被修改，还需要写回到swap相应的地址，把新的页加载 到内存被替换的物理帧中，修改页表中相应的项。

if(which == PageFaultException){ extern BitMap *Mmbmp;

execFile=fileSystem->Open((currentThread->space)->virtualName); unsigned int pageFaultAddress,page,vp,amount; pageFaultAddress=machine->registers[BadVAddrReg];

/*page 中保留了需要加载进内存的虚拟页号*/

page=pageFaultAddress/PageSize;//计算发生页错误的虚拟页号，

printf(\ //lru->print();

/*如果使用的内存frame数小于可以使用的最大的frame数，则直接使用位试图找到一个新的物理帧，加载*/ /*修改页表项*/

/* execFile 是进程的swap文件，把swap文件中的相应内容加载到内存*/

if(1<= Mmbmp->NumClear()&&(currentThread->space)->count

(currentThread->space)->pageTable[page].physicalPage = Mmbmp->Find();

(currentThread->space)->count++;

(currentThread->space)->pageTable[page].valid = TRUE; (currentThread->space)->pageTable[page].use = TRUE; (currentThread->space)->pageTable[page].dirty = FALSE;

printf(\

execFile->ReadAt(&(machine->mainMemory[(currentThread->space)->pageTable[page].physicalPage (currentThread->space)->pageTable[page].virtualPage*PageSize);

printf(\

printf(\

}

else{

/*超过可以使用的最大的物理frame数，需要使用页面置换算法*/

printf(\ vp=lru->getlru(); lru->remove(vp);

/*被换出的页如果被修改，要写回swap文件*/ /*修改页表项*/

if((currentThread->space)->pageTable[vp].dirty==TRUE){ printf(\

execFile->WriteAt(&(machine->mainMemory[(currentThread->space)->pageTable[vp].physicalPage*PageS->vp

(currentThread->space)->pageTable[vp].dirty=FALSE; }

(currentThread->space)->pageTable[vp].valid=FALSE;

(currentThread->space)->pageTable[page].physicalPage=(currentThread->space)->pageTable[vp

printf(\

printf(\

/*修改页表项*/

(currentThread->space)->pageTable[page].valid = TRUE; (currentThread->space)->pageTable[page].use = TRUE; (currentThread->space)->pageTable[page].dirty = FALSE;

printf(\

execFile->ReadAt(&(machine->mainMemory[(currentThread->space)->pageTable[page].physicalPage (currentThread->space)->pageTable[page].virtualPage*PageSize);//pageTable[newPage].inFileAddr);

}

delete execFile;

(currentThread->space)->pageTable[page].valid = TRUE;

unsigned int temp=(currentThread->space)->pageTable[page].virtualPage; lru->append(temp);//page

lru->print(); }

实验结果：

lu@ubuntu:~/csc2404/nachos-3.4/code/userprog$ ./nachos -x ../test/sort.noff

The programe information: noffH.code.size:704 noffH.initData.size:48

noffH.uninitData.size:2064 Number of Pages needed: 28

create the swap file

Allocate the minimum code pages to a user programe.

Allocate one frame for the user stack.

Load code page into the main memory! Code Address:0 In File:40

Read Size 128

Code Address:128 In File:168 Read Size 128

Code Address:256 In File:296 Read Size 128

Code Address:384 In File:424 Read Size 128

Code Address:512 In File:552 Read Size 128

Code Address:640 In File:680 Read Size 112

Load code into the virtual memory! Read Size 128 Read Size 128 Read Size 128

Read Size 128 Read Size 128 Read Size 64

END OF LOADING CODE PAGES

Load initial data into the main memory!

Load initial data into the virtual memory! Reading buffer=

END OF LOADING INITIAL DATA PAGES

Page table dump: 28 pages in total

======================================= VirtPage, PhysPage Page 0, 0 Page 1, 1 Page 2, 2 Page 3, 3 Page 4, 4 Page 5, 5 Page 6, 7 Page 7 INVALID Page 8 INVALID Page 9 INVALID Page 10 INVALID Page 11 INVALID Page 12 INVALID Page 13 INVALID Page 14 INVALID Page 15 INVALID Page 16 INVALID Page 17 INVALID Page 18 INVALID Page 19 INVALID Page 20 INVALID Page 21 INVALID Page 22 INVALID Page 23 INVALID Page 24 INVALID Page 25 INVALID Page 26 INVALID

StackPage 27, 6

=======================================

PageFaultAddress: 896 ,PageFaultPage: 7

copy from swap file :execFile to main memoryNumber of occupied pages 10 virtual page 7 -> physical page 8 LRU:0-->5-->6-->1-->27-->2-->7

PageFaultAddress: 1024 ,PageFaultPage: 8

copy from swap file :execFile to main memoryNumber of occupied pages 11 virtual page 8 -> physical page 9 LRU:0-->5-->6-->7-->1-->27-->2-->8

PageFaultAddress: 1152 ,PageFaultPage: 9

copy from swap file :execFile to main memoryNumber of occupied pages 12 virtual page 9 -> physical page 10 LRU:0-->5-->6-->7-->8-->1-->27-->2-->9

PageFaultAddress: 1280 ,PageFaultPage: 10

copy from swap file :execFile to main memoryNumber of occupied pages 13 virtual page 10 -> physical page 11

LRU:0-->5-->6-->7-->8-->9-->1-->27-->2-->10

PageFaultAddress: 1408 ,PageFaultPage: 11

copy from swap file :execFile to main memoryNumber of occupied pages 14 virtual page 11 -> physical page 12

LRU:0-->5-->6-->7-->8-->9-->10-->1-->27-->2-->11

PageFaultAddress: 1536 ,PageFaultPage: 12

copy from swap file :execFile to main memoryNumber of occupied pages 15 virtual page 12 -> physical page 13

LRU:0-->5-->6-->7-->8-->9-->10-->11-->1-->27-->2-->12

PageFaultAddress: 1664 ,PageFaultPage: 13

copy from swap file :execFile to main memoryNumber of occupied pages 16 virtual page 13 -> physical page 14

LRU:0-->5-->6-->7-->8-->9-->10-->11-->12-->1-->27-->2-->13

PageFaultAddress: 1792 ,PageFaultPage: 14

copy from swap file :execFile to main memoryNumber of occupied pages 17 virtual page 14 -> physical page 15

LRU:0-->5-->6-->7-->8-->9-->10-->11-->12-->13-->1-->27-->2-->14

PageFaultAddress: 1920 ,PageFaultPage: 15

copy from swap file :execFile to main memoryNumber of occupied pages 18 virtual page 15 -> physical page 16

LRU:0-->5-->6-->7-->8-->9-->10-->11-->12-->13-->14-->1-->27-->2-->15

PageFaultAddress: 2048 ,PageFaultPage: 16

copy from swap file :execFile to main memoryNumber of occupied pages 19 virtual page 16 -> physical page 17

LRU:0-->5-->6-->7-->8-->9-->10-->11-->12-->13-->14-->15-->1-->27-->2-->16

PageFaultAddress: 2176 ,PageFaultPage: 17

copy from swap file :execFile to main memoryNumber of occupied pages 20 virtual page 17 -> physical page 18

LRU:0-->5-->6-->7-->8-->9-->10-->11-->12-->13-->14-->15-->16-->1-->27-->2-->17

PageFaultAddress: 2304 ,PageFaultPage: 18

copy from swap file :execFile to main memoryNumber of occupied pages 21 virtual page 18 -> physical page 19

LRU:0-->5-->6-->7-->8-->9-->10-->11-->12-->13-->14-->15-->16-->17-->1-->27-->2-->18

PageFaultAddress: 2432 ,PageFaultPage: 19

copy from swap file :execFile to main memoryNumber of occupied pages 22 virtual page 19 -> physical page 20

LRU:0-->5-->6-->7-->8-->9-->10-->11-->12-->13-->14-->15-->16-->17-->18-->1-->27-->2-->19

PageFaultAddress: 2560 ,PageFaultPage: 20

copy from swap file :execFile to main memoryNumber of occupied pages 23 virtual page 20 -> physical page 21

LRU:0-->5-->6-->7-->8-->9-->10-->11-->12-->13-->14-->15-->16-->17-->18-->19-->1-->27-->2-->20

PageFaultAddress: 2688 ,PageFaultPage: 21

copy from swap file :execFile to main memoryNumber of occupied pages 24 virtual page 21 -> physical page 22

LRU:0-->5-->6-->7-->8-->9-->10-->11-->12-->13-->14-->15-->16-->17-->18-->19 -->20-->1-->27-->2-->21 Exit ！20

=====Delete the virtual memory file!======

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

Ticks: total 9769100, idle 43, system 976910, user 8792147 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... Sort.c源文件： /* sort.c

* Test program to sort a large number of integers. *

* Intention is to stress virtual memory system. *

* Ideally, we could read the unsorted array off of the file system, * and store the result back to the file system! */

#include \

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

int b[]={1,2,3,4,5,6,7,87,9,10};

int A[ARRAYSIZE]; int main() {

int i, j, tmp;

/* first initialize the array, in reverse sorted order */ for (i = 0; i < ARRAYSIZE; i++) A[i] = ARRAYSIZE - i - 1;

/* 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; }

Exit(A[20]); /* and then we're done -- should be 0! */ }

实验结果分析：

（使用修改后的sort.c 编译执行的）

使用Nachos运行sort.noff文件，sort的主要工作是对一个长度为516的数组进行升序排序，

本文来源：https://www.bwwdw.com/article/gpx8.html