操作系统实验报告

四川大学

操作系统课程设计报告

学院：软件学院

专业：软件工程专业

年级：2007级

组编号：第14组

组成员：XXXXXXXXXXXX

XXXXXXXXXXXX

XXXXXXXXXXXX

提交时间：2009年6月20 日

指导教师评阅意见：

.

. . . .

指导教师评阅成绩：XXX1：

XXX1：

XXX1：

XXX1：

XXX1：

实验项目三

实验项目名称：Nachos内存管理模块升级

实验项目目的：

本实验要实现对Nachos内存管理升级，使其能弥补原来Nachos平台一次只能运行一个用户程序，以及用户程序大小必须小于物理内存空间的不足。能够实现多个线程共同在Nachos上运行和“分页式”存储管理机制，并且使程序可用空间不限制大小。即需要改进Nachos的内存分配方式，实现虚拟内存的管理，完善和优化Nachos的内存管理功能，提升整体系能。

参与人员及分工：

实验环境：Vmware虚拟机的Linux平台上的Nachos系统

实验内容：

【实验简述】

1.原Nachos系统描述：

原Nachos系统由于加载程序的时候，在AddrSpace的构造函数中，构造了线程页表，并执行了清零操作。因此，Nachos系统一次只能运行一个线程。并且线程的虚拟地址与物理地址是相等的，并没有完成虚拟地址与物理地址之间的高级映射。并且，在加载用户程序的时候，在Load函数载入一个用户程序的时候，

限制了程序大小。因此，Nachos系统只能加载大小小于系统限制的程序。

2.实验要求

本次实验希望通过对Nachos核心代码的修改来实现一下几个目标：

1.通过改进Nachos的内存分配方式，使得多个线程可以同时存在于内存之

中，这些线程可以按照“优先级”的方式进行调度。

2.实现“分页式”存储管理机制（基于分页机制的虚拟内存），也就是说不

需要实现真正的内存管理，只需要建立一个虚拟页表，当加载用户程序

的时候为其分配一个虚拟页号，方便之后的存储管理。

3.（可选）实现缺页中断，即当所需的页不在内存中的时候，可以有一个

缺页中断处理程序，当遇到缺页的时候，用户程序停止运行，跳转到中

断服务程序，经过处理之后，置换出一个页，将需要的页置换到内存中。

4.（可选）不限制程序的大小，由于现在Nachos中的程序加载要受到系统

的限制。因此，本实验希望通过改变底层代码，实现Nachos系统可以加

载任意大小的用户程序。

【实验过程】

1.问题分析

Nachos系统在Machine.h中定义了pageSize = 128，NumPhysPage = 128，而MemorySize = （NumPhysPages*PageSize）=16384 bytes.用来表示对物理内存的分页，并且限制了物理内存的大小。因此，要加载多个线程，必须要有一个虚拟页表来维护多个线程的页表中页的虚拟地址和物理地址的映射操作，并且可以方便之后的缺页中断管理和页的置换。

系统在创建AddrSpace的每个地址空间对象的时候后，都维护了一个页表。这个页表是线程页表也就是用户程序页表，AddrSpace构造的时候，只是简单的将虚拟页表与物理分页一一对应，并且执行了bzero函数，将mainMemory清零。这样的话，Nachos系统便无法同时运行多个互用程序。而要解决这个问题，我

们首先需要删除AddrSpace中的维护线程页表以及内存的清零操作。将线程也表的维护转移到load函数中去，而内存的清零操作在~AddrSpace中执行。并且在维护线程页表的时候，不能简单的将虚拟页表与物理分页一一对应，而是要采取一定的转换机制。

要实现缺页中断，则必须有一定的原则来进行页的换入换出操作。在这里，我们采用的是最近使用的原则。在TranslateEntry中增加了一个新的属性recUsed来记录当前页的使用状态，当发生缺页中断的时候进行页的换入换出。首先，系统发送一个缺页中断的报告，然

后用一个for循环找出最近最少使用的页表实体，将实体进行标志，然后换出当前的页表实体记录的内容，返回空闲页号。

总的来说，要解决Nachos系统一次只能运行一个用户程序的问题，系统需要同时维护三类页表：实页页表，虚页页表和用户程序页表。其中实页页表与用户程序页表系统已经自己定义了，因此，我们需要在Mahine.h中定义一个虚页页表来进行管理。

其中整个Nachos系统之维护一个实页页表和虚页页表，它们都占用宿主机的内存。每个执行的用户进程都有一张页表，该页表在其进程控制结构中，同样是占用宿主机的内存。实页页表中的每个页表项对应于一个实页，记录该实页的使用状态。虚页页表中的每个页表项对应于一个虚页，记录虚页的映射信息、使用状态等情况；每个虚页内容或者对应于一个实页内容，或者不在内存里；线程页表中的每一项都对应于一个虚页。系统中的共享层次位于虚页页表和线程页表之间，多个线程页表项可共享同一个虚页，而一个虚页最多只能对应于一个实页。系统页表的总体布局如图 fig3.1所示：

2.具体实现

以下是小组在具体实践该实验的步骤：

Step1：在userprog中增加MemManager.h和https://www.doczj.com/doc/d219004780.html,两个文件。

根据老师PPT的提示以及小组的思考讨论，我们决定增加一个新的类来专门

进行内存管理，这样可以方便很多操作。以下是MemManger.h的头文件的定义：class MemManeger{

public:

MemManeger(TranslationEntry *pt);

~MemManeger();

/*

* Assing a physical page

*/

int assignPage();

/*

* Release a physical page

*/

void Release(int pn);

private:

TranslationEntry *m_pageTable;

}

Step2：在c++example中增加queue.h 和https://www.doczj.com/doc/d219004780.html,。

由于Nachos给我们提供的只有List和Stack结构，并且都不符合我所希望的要求，因此创建了一个新的数据结构来管理后面所要实现的内容。具体的类的

定义如下所示：

class Queue{

public:

Queue();

~Queue();

void push(int value,SpaceId spId);

QueueElement remove();

void empty();

private:

QueueElement *first;

QueueElement *last;

}

Step3：删除AddrSpace中的线程初始化部分（pageTable = new TranslationEntry[NumPhysPages]……）和内存的清零操作

（bzero(kernel->machine->mainMemory, MemorySize)）。在AddrSpace构造函数中创建MemManager的对象，并且全局只设置一个MemManager的对象，改对象用来管理内存。

Step4：实现创建虚拟页表和增加维护空闲页表等操作，用来为实现多道系统做准备。

①在Mahine中创建一个全局变量的虚页页表VirPageTable，此表用来记录全

局页表。

②修改Machine的构造函数，初始化pageTable和virPageTable,具体的函数

实现如下所示：

Machine::Machine(bool debug)

{

int i;

pageTableSize = NumPhysPages;

virtPTSize = NumPhysPages*2;

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

registers[i] = 0;

mainMemory = new char[MemorySize];

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

mainMemory[i] = 0;

#ifdef USE_TLB

tlb = new TranslationEntry[TLBSize];

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

tlb[i].valid = FALSE;

pageTable = NULL;

#else // use linear page table

tlb = NULL;

pageTable = new TranslationEntry[pageTableSize];

for( i =0;i

pageTable[i].virtualPage = i;

pageTable[i].physicalPage = i;

pageTable[i].valid = FALSE;

pageTable[i].readOnly = FALSE;

pageTable[i].use = FALSE;

pageTable[i].dirty = FALSE;

pageTable[i].recUsed = 0;

pageTable[i].spaceId = 0;

}

virtPTable = new TranslationEntry[virtPTSize];

for(i = 0;i

virtPTable[i].virtualPage = i;

virtPTable[i].physicalPage = i%NumPhysPages;

virtPTable[i].valid = FALSE;

virtPTable[i].readOnly = FALSE;

virtPTable[i].use = FALSE;

virtPTable[i].dirty = FALSE;

virtPTable[i].recUsed = 0;

virtPTable[i].spaceId = 0;

}

blockQueue = new Queue();

#endif

singleStep = debug;

CheckEndian();

}

③修改TanslateEntry实体类，增加属性recUsed（int；用标识页表实体

的使用频率），spaceId（SpaceId；用来表示改页表实体所对应的线程）和priority（int，用来表示改页表实体所对应线程的优先级，方便之后的页的置换）

④在Machine中增加Machine::FindPage()函数，用来返回系统全局页表的

空闲页号，当没有空闲页号的时候，进行缺页中断处理操作。

int Machine::FindPage(){

int i;

//subtract the recUsed all the pages

for(i=0;i

pageTable[i].recUsed--;

//Find if any pages is free

for(i=0;i

if(pageTable[i].valid)

continue;

pageTable[i].valid = TRUE;

pageTable[i].recUsed ++;

return i;

}

//if there is no page is free, then cause PageFaultException

if(i==NumPhysPages){

int newPage = 0;

int tempRecUsed = pageTable[0].recUsed;

for(int j =1;j

if(tempRecUsed > pageTable[j].recUsed){

newPage = j;

tempRecUsed = pageTable[j].recUsed;

}

}

print("Page fault,allocate page %d",newPage);

kernel->stats->numPageFaults++;

pageTable[newPage].recUsed++;

return newPage;

}

}

⑤在AddrSpace中增加A_FindPage()函数，用来为新创建的线程分配一个

虚拟页号。函数具体实现与Machine中的FindPage相似，但是不同的是，由于此时为线程分配的是虚拟页号，因此，多个线程页表项可以同时对应到一个虚页页表项中，此时不会发生缺页中断。但是由于多个线程页表项可以对应到一个虚拟也表中，在装载到实页页表的过程中会发生错误。而要解决这个错误就需要采取一定的机制，来保证一次只能装在一个线程也表到实页页表中去。因此在前面所新增的Queue类便起作用了。在维护空闲页表的时候，我们将找到的页号大于128的页表项加入到队列中去，并且每次选出的时候，按照优先级来选择可使用的页表项。具体的A_FindPage函数如下所示，而加入到队列的操作将在后面load

函数的实现中给出。

int A_FindPage(){

int i;

int size = NumPhysPages;

//subtract the recUsed all the pages

for(i=0;i

kernel->machine->virtPTable[i].recUsed--;

//Find if any pages is free

for(i=0;i

if(kernel->machine->virtPTable[i].valid)

continue;

kernel->machine->virtPTable[i].valid = TRUE;

kernel->machine->virtPTable[i].recUsed ++;

return i;

}

if(i==size){

int j = 0;

int temp = kernel->machine->virtPTable[0].recUsed;

for(i=0;i

if(temp > pageTable[i].recUsed){

j = i;

temp = pageTable[i].recUsed;

}

}

return j+128;

}

}

⑥在AddrSpace中增加在AddrSpace类里加一数据成员addr_reg，用来保存当前调度的时候寄存器的内容。

Step5：装载和初始化线程页表

修改了AddrSpace中的Load函数，在函数中增加了对线程也表的初始化造作，以及更改了将原来系统中AddrSapce构造函数中的pageTable[i].physicalPage = i 改成pageTable[i].physicalPage = numPage（其中numPage =A_FindPage()）。并且增加了一个将虚拟地址转化为物理页号的步骤，比如：phyAddr = pageTable[virAddr / PageSize].physicalPage * PageSize + virAddr % PageSize 。具体的load函数实现如下所示：

bool AddrSpace::Load(char *fileName)

{

OpenFile *executable = kernel->fileSystem->Open(fileName);

NoffHeader noffH;

unsigned int size;

if (executable == NULL) {

cerr << "Unable to open file " << fileName << "\n";

return FALSE;

}

executable->ReadAt((char *)&noffH, sizeof(noffH), 0);

if ((noffH.noffMagic != NOFFMAGIC) &&

(WordToHost(noffH.noffMagic) == NOFFMAGIC))

SwapHeader(&noffH);

ASSERT(noffH.noffMagic == NOFFMAGIC);

pageTable = new TranslationEntry[NumPhysPages];

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

pageTable[i].virtualPage = i;

int pageNum = A_FindPage();

if(pageNum<128){

pageTable[i].physicalPage = pageNum;

pageTable[i].priority = 1;

}else{

pageNum = pageNum-128;

pageTable[i].physicalPage = pageNum;

pageTable[i].priority = 2;

queue.push(i, SpaceId spID);

}

pageTable[i].valid = TRUE;

pageTable[i].use = FALSE;

pageTable[i].dirty = FALSE;

pageTable[i].readOnly = FALSE;

pageTable[i].spaceId = spID;

}

#ifdef RDATA

// how big is address space?

size = noffH.code.size + noffH.readonlyData.size + noffH.initData.size + noffH.uninitData.size + UserStackSize;

// we need to increase the size to leave room for the stack

#else

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

#endif

numPages = divRoundUp(size, PageSize);

size = numPages * PageSize;

ASSERT(numPages <= NumPhysPages);

// check we're not trying to run anything too big --

//at least until we have virtual memory

DEBUG(dbgAddr, "Initializing address space: " << numPages << ", " << size);

// then, copy in the code and data segments into memory

// Note: this code assumes that virtual address = physical address if (noffH.code.size > 0) {

DEBUG(dbgAddr, "Initializing code segment.");

DEBUG(dbgAddr, noffH.code.virtualAddr << ", " << noffH.code.size);

int curAddress = pageTable[noffH.code.virtualAddr/PageSize].physicalPage*PageSize+nof fH.code.virtualAddr%PageSize;

executable->ReadAt(

&(kernel->machine->mainMemory[curAddress]),

noffH.code.size, noffH.code.inFileAddr);

}

if (noffH.initData.size > 0) {

DEBUG(dbgAddr, "Initializing data segment.");

DEBUG(dbgAddr, noffH.initData.virtualAddr << ", " << noffH.initData.size);

int curAddress = pageTable[noffH.code.virtualAddr/PageSize].physicalPage*PageSize+nof fH.code.virtualAddr%PageSize;

executable->ReadAt(

&(kernel->machine->mainMemory[curAddress]),

noffH.initData.size, noffH.initData.inFileAddr);

}

#ifdef RDATA

if (noffH.readonlyData.size > 0) {

DEBUG(dbgAddr, "Initializing read only data segment.");

DEBUG(dbgAddr, noffH.readonlyData.virtualAddr << ", " << noffH.readonlyData.size);

executable->ReadAt(

&(kernel->machine->mainMemory[noffH.readonlyData.virtualAddr]),

noffH.readonlyData.size, noffH.readonlyData.inFileAddr);

}

#endif

delete executable; // close file

return TRUE; // success

}

Step6:修改保存和恢复状态的函数，增加释放物理内存空间的函数。

①对AddrSpace:SaveState的修改。该函数是用来保存系统的运行状态，保存

寄存器的值。通过循环调用machine->ReadRegister函数，将目前该程序用到的

寄存器的值都存储到AddrSpace类的s_reg数据成员中。具体的函数实现如下：void AddrSpace::SaveState()

{

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

addr_reg[i] = kernel->machine->ReadRegister(i);

}

②对AddrSpace:RestoreState的修改。该函数是用来恢复系统的运行状态，恢复上一次保存的寄存器的值。在原函数中，增加了通过循环调用machine->WriteRegister函数，将程序AddrSpace类中addr_reg数据成员里保

存的寄存器的值赋给nachos虚拟机的寄存器的操作。具体实现如下所示：void AddrSpace::RestoreState()

{

machine->pageTable = pageTable;

machine->pageTableSize = numPages;

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

kernel->machine->WriteRegister(i, addr_reg[i]);

}

③在AddrSpace中增加了释放物理内存空间的函数。该函数调用了

MemManager中的release函数，当一个用户程序消亡时，需要释放物理空间

以供其他用户程序使用。具体实现如下所示：

void AddrSpace::Reclaim()

{

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

memManager.Release( pageTable[i].physicalPage );

}

实验结果和结论：

【实验完成情况】

本项目的要求满足了以下三个要求：

1. 实现了多个线程可以同时存在于内存之中。

2. 实现了“分页式”存储管理机制（基于分页机制的虚拟内存）

3. 实现了“缺页中断”

完成了上述三个部分的编码，编译通过，能够正常运行。

参考文献：

1.《操作系统原理课程设计实验手册》

2.《A Road Map Through Nachos》

3.《操作系统设计（nachos

4.1）》

4. 《操作系统原理》

实验项目四

实验项目名称：Nachos的文件管理模块升级

实验项目目的：

本实验希望通过对Nachos文件管理模块的升级，弥补原来Nachos系统一次只能有一个线程访问一个文件系统，文件目录结构简单等的不足。通过对底层代码的改进，实现多个线程能同时对一个文件进行操作，将目录简单的顺序结构改成树状结构，文件的更名、拷贝、删除以及文件尺寸的限制等功能。完善和优化Nachos的文件管理机制，提升整体性能。

参与人员及分工：

实验环境：Vmware虚拟机的Linux平台上的Nachos系统

实验内容：

【实验要求】

1.实现多线程访问文件系统的机制。目前Nachos系统无法实现多线程同时对一

个文件进行写操作，但是可以同时进行读操作。因此，本实验希望通过加入信号量的方法来实现多线程同时对文件的写操作。

2.实现多目录机制。目前Nachos系统是采用简单的顺序结构来实现目录制，该

结构显然不能满足用户对文件系统管理的需要。因此，本实验希望通过增加树状结构，来实现目录的多级管理制度。

3.实现文件的更名、拷贝、删除。目前Nachos文件系统的功能十分不完善，因

此，本实验系统通过编写几个完整的系统调用来实现文件的更名、拷贝和删除等操作。

4.（可选）对文件尺寸的限制。目前Nachos系统采取的是直接索引的方法，导

致文件的尺寸受到限制，甚至还大小还不能大大4K。因此，本实验希望通过建立一个索引链表，将文件的索引变得不限大小，这样的话，文件也能不限大小。

【问题分析】

Nachos的文件系统是建立在Nachos的物理磁盘上的，文件系统的实现结构如图Fig4.1所示。

Fig4.

①文件系统模块（文件https://www.doczj.com/doc/d219004780.html, filesys.h）

Nachos系统中，实现了两套文件系统，它们对外接口是完全一样的。一套是FILESYS_STUB文件系统，它是建立在UNIX 文件系统之上的，而不使用Nachos 的模拟磁盘。另一套是Nachos 的文件系统，它是实现在Nachos 的虚拟磁盘上的。当整个系统完成之后，只能使用第二套文件系统的实现。

而Nachos 的文件系统，是通过位图（文件https://www.doczj.com/doc/d219004780.html,，bitmap.h）来管理空闲块的。Nachos 的物理磁盘是以扇区为访问单位的，将扇区从0 开始编号。所谓位图管理，就是将这些编号填入一张表，表中为0的地方说明该扇区没有被占用，而非0 位置说明该扇区已被占用。并且Nachos采用的是顺序结构，一次限制了最多只能有10个DirectoryEntry 。

在Nachos的文件顺序结构中，有两个扇区所存放的内容是固定的，分别是：

A.第0号扇区。始终规定存放FreeMapFile的FileHeader，FreeMapFile一个位表（bitmap），用于标识磁盘中有哪些扇区已被使用。

B.第1号扇区。始终规定存放DirectoryFile的FileHeader,此文件用于记录文件系统中各个文件的目录结构。

其具体结构如下所示：

改进思路：根据上面的分析可以知道，Nachos 实际的文件结构，一个文件的实际大小还达不到4K 。而要解决这个问题，需要将数组存储方式改为链表的存储方式，使文件索引可以无限制的增加，这样的话，也可以不限制文件的大小。

② 目录模块（文件https://www.doczj.com/doc/d219004780.html, ，directory.h ）

每个文件目录都对应一个目录文件，目录文件由目录项组成，目录项使得字符形式的文件名与实际文件的文件头相对应，这样用户就能方便地通过文件名来访问文件。但是Nachos 的实际文件目录的存储形式是顺序存储的，这样的存储方式非常不人性化，查找效率也很不高。

改进思路：将Nachos 的顺序文件目录存储方式转化成树状结构，采用链表指针的方式。这样不仅可以很容易的遍历文件，也可以使得文件索引没有大小的限制。

③ 打开文件结构（文件https://www.doczj.com/doc/d219004780.html, ，openfile.h ）

该模块定义了一个打开文件控制结构。当用户打开了一个文件时，系统即为其产生一个打开文件控制结构，以后用户对该文件的访问都可以通过该结构。打开文件控制结构中的对文件操作的方法同UNIX 操作系统中的系统调用。

④ 文件头模块（文件https://www.doczj.com/doc/d219004780.html, filehdr.h ）

文件头实际上就是UNIX 文件系统中所说的inode 结构，它给出一个文件除了文件名之外的所有属性，包括文件长度、地址索引表等等（文件名属性在目录中Fig4.2

给出）。所谓索引表，就是文件的逻辑地址和实际的物理地址的对应关系。通过文件头可以获取文件的所有信息。Nachos 的文件头可以存放在磁盘上，也可以存放在宿主机内存中，在磁盘上存放时一个文件头占用一个独立的扇区。

⑤同步磁盘（文件https://www.doczj.com/doc/d219004780.html, synchdisk.h）

和其它设备一样，Nachos 模拟的磁盘是异步设备。当发出访问磁盘的请求后立刻返回，当从磁盘读出或写入数据结束后，发出磁盘中断，说明一次磁盘访问真正结束。

Disk模块出现的问题：限制了多线程对文件系统进行访问.

Synchdisk的解决方法：

A．信号量

B.每次发出读写请求后,信号量在P操作上等待

C.每次磁盘读写完成后,信号量执行V操作

限制：同一时间只能进行一次读/写操作

改进思路：根据经典的读者\写着问题对该模块进行改进，采用信号量的方式，控制线程的读写访问。

【具体实现步骤】

1.线程同时访问文件系统机制

采用信号量机制进行线程的同步来解决这个读者-写者问题。

Step1：在Disk类的ReadRequest函数中注释掉Assert（！active）。

因为该句限制了一次只允许一个线程对磁盘的读写。

Step2：修改SynchDisk类，增加成员变量count（short;记录当前访问文件系统的线程数，用户控制访问数量），semData（Semaphore;控制队文件系统的访问），semCount（Semaphore;控制对count的访问）.

增加的这几个参数是实现读写问题的关键，同时需要在SynchDisk类的构造函数里对他们初始化。

Step3：修改ReadSector和WriteSector两个成员函数。

Nachos的原函数只是简单的对读写操作进行上锁和处理，并不能实现多个线程对磁盘的访问，具体的改进方法如下所示：

void SynchDisk::ReadSector(int sectorNumber, char* data)

{

semCount->P();

count++;

if(count==1)semData->P();

semCount->V();

disk->ReadRequest(sectorNumber, data);

count--;

if(count==0)semData->V();

semCount->V();

semaphore->P();

}

void SynchDisk::WriteSector(int sectorNumber, char* data)

{

semData->P();

disk->WriteRequest(sectorNumber, data);

semData->V();

semaphore->P();

}

2.多级目录的实现

经过小组讨论，以及结合老师PPT上的内容，我们决定将Nachos文件的顺序结构转化为树状结构，具体的图形如Fig4.3所示：