NACHOS BUILD LOG
John K. Joachim ( joachimj@usa.net)
CSCI - 503 - Spring 2000
Tuesday, 11 Jan, 2000
First day of class. After leaving IUPUI, printed off NACHOS Project Overview info and CVS documentation.
Wednesday, 12 Jan, 2000
Plans to install and build NACHOS on Sun box tomorrow evening. Read through NACHOS System documentation.
I installed and de-compressed Nachos 3.4 on to my home directory:
gunzip nachos-3.4.tar.gz
tar -xvf nachos-3.4.tar
/jjoachim/nachos-3.4/code
Makefile
Makefile.dep Makefile.common
filesys/
network/ threads/
vm/ bin/
machine/ test/
userprog/
/jjoachim/nachos-3.4/code/filesys
Makefile directory.h
filehdr.h filesys.h
openfile.cc synch disk.cc
directory.cc filehdr.cc filesys.cc
fstest.cc openfile.h
disk.h
test/
/jjoachim/nachos-3.4/code/filesys/test
big medium small
/jjoachim/nachos-3.4/code/network
Makefile README
nettest.cc post.cc post.h
/jjoachim/nachos-3.4/code/threads
Makefile list.h
scheduler.cc switch.h
synch.h synchlist.o
system.o threadtest.cc
utility.h copyright.h
list.o scheduler.h
switch.s synch.o
sysdep.o thread.cc
threadtest.o utility.o
interrupt.o main.cc
scheduler.o swtch.s
synchlist.cc system.cc
thread.h timer.o
list.cc main.o
stats.o synch.cc
synchlist.h system.h
thread.o utility.cc
/jjoachim/nachos-3.4/code/vm
Makefile
/jjoachim/nachos-3.4/code/bin
Makefile coff2flat.c
d.c encode.h
halt int.h
noff.h out.c
coff.h coff2noff.c
disasm.c execute.c
instr.h main.c
opstrings.c system.c
/jjoachim/nachos-3.4/code/machine
bool.h disk.cc
interrupt.h mipssim.cc
network.h sysdep.cc
timer.h console.cc
disk.h machine.cc
mipssim.h stats.cc
sysdep.h translate.cc
console.h interrupt.cc
machine.h network.cc
stats.h timer.cc
translate.h
jjoachim/nachos-3.4/code/test
Makefile halt.c
halt.o matmult.c shell
sort start.o
halt halt.coff* matmult
script shell.c
sort.c start.s
jjoachim/nachos-3.4/code/userprog
Makefile addrspace.cc
addrspace.h bitmap.cc
bitmap.h exception.cc
progtest.cc syscall.h
/home/jjoachim/nachos-3.4/doc
README filesys.ps
mechanics.tex network.ps
overview.tex thread.tex
vm.ps course.ps
filesys.tex nethelp.ps
network.tex reading.ms
userprog.ps vm.tex
course.tex mechanics.ps
nethelp.tex overview.ps
thread.ps userprog.tex
Thursday, 13 Jan, 2000
One compilation error has been reported, by Matthew Stephens (mstephen@cs.iupui.edu):
"I get an error when trying to compile the Nachos code.
The error is in
the sysdep.cc file and has to do with it calling an undefined
method
pagesize(). Has anyone else gotten this error and fixed
it?"
As late as 3:00 PM today, no one has responded to this report.
Friday, 14 Jan, 2000
Last night after class, we formed our group:
Ramesh Muthyala rmuthyal@cs.iupui.edu
John Joachim
joachimj@usa.net
Bindu Jain
binduj199@yahoo.com
John Schuck
JSchuck@FDIC.gov or jcncschuck@earthlink.net
Michael Boyes hadn't completed the compilation, since "hangs on finding a file called "bool.h".
Later, Mike posted this message:
"I found the "booh.h" file which I was talking about.
It was
in /usr/local/lib/g++-include/, but now I
also get the get
pagesize error which Matthew is experiencing."
... to which Matthew responded:
"I found the getpagesize() method in <unistd.h>.
Including this in your
file gets rid of the error about getpagesize but
you get two new errors
which I'm not sure what they mean."
Dong Hoang responded::
"I checked and also had this problem which we did not experience
last year.
I will check to see is there anything changed with
our system here or
anything wee need to change in order to get nachos
installed. If anyone
found out the reason, pls share with the class."
Peng Wang supposedly found a solution to these:
"We just finished compiling Nachos. To do that, you need:
1) Include the bool.h according
to Michael.
2) Declare
int getpagesize();
in machine/sysdep.cc
3) Include the standard
strings.h file in several of the files.
4) Change the Makefile in
test directory according to the webpage of Dong.
That is it.. Enjoy..."
... to which Michael Boyes responded:
"Yes, that worked. But, all we did is add a declaration
for a function
that is not there (or doesn't appear to be). Are we sure
this won't
introduce runtime linking errors later? Shouldn't we find
the
getpagesize() function or macro also? What does everyone
think?"
Friday afternoon Dong concluded:
"From my discussion with Jagan, I understand that Nachos
uses C function
getpagesize to compile its codes. The detail of this function
can be found
by issuing "man getpagesize" in unix system console. The
problem with
nachos installation might be related with reorganization
or upgrading of
our system here to meet Y2K :) ( I just guess). I think
your nachos will
be fine if you get your coding right with the incoming
project phases."
Sunday, 16 Jan, 2000
Just a list of tasks to do tomorrow at IUPUI:
1) Install/configure NACHOS
2) Install/configure CVS
3) Finish up reading through Chapter 5 in Silbershatz text
4) Read "Intro to Thread programming"
5) Finish reading through NACHOS Tour Guide
Monday, 17 Jan, 2000
NACHOS finally compiled without any errors. To do this, I had to take the following steps:
1) make a copy of booh.h into my nachos/code/machine file (I
did this via Solaris GUI File Manager -- a first-time for me);
2) add the line int getpagesize to machine/sysdep;
3) modify the code/Makefile.common and code/Makefile.dep
(and not just the Makefile in the /test directory;
4) Edit and source .cshrc with added paths
5) add the system call #include <strings.h> , as errors appeared
while compiling, to four files:
i. /userprog/addrspace.cc
ii. /filesys/openfile.cc
iii. /network/post.cc
iv. /machine/network.cc
Reagrding 5) above: After completing setps 1) through 4), I compiled
but got a missing include error.
After editing the designated file, I would get the same error, but
designating a different file. This happened
four times (sub-points i - iv).
Also, installing CVS-1.10 was a success.
Tuesday, 18 Jan, 2000
Assignment #1 was posted on the class internet set. Three tasks:
1) Implementation of locks and condition variables (see synch.h)
2) Implementation of syncronous send-and-receive message system
3) Implementation of preemptive priority scheduling
Thursday, 20 Jan, 2000
We met briefly as a group tonight after class, mainly to arrange do-able future meeting times.
Wednesday, 26 Jan, 2000
Group met tonight, and began discussing the layout and design of the tasks for Assignment #1
Monday, 31 Jan, 2000
We met as a group tonight, and discussed the syncronization process
(the following is from an e-mail
Ramesh wrote to all of us):
class Lock {
private:
char *name;
bool busy;
Thread *currently_held_thread;
List *queue;
}
void Lock::Acquire()
{
1. Disable the interrupts
2. If (busy) add the thread to the queue of the lock;
3. while(busy)
sleep();
4. busy = true;
5. currently_held_thread = currentThread
}
void Lock::Release()
{
ASSERT (is_held_by_currentThread());
busy = false;
next_thread = (thread *) queue->remove();
scheduler->Ready_to_run(next_thread);
}
Tuesday, 1 February, 2000
After class tonight, we decided not to meet tomorrow night (only because
prgress over the two
days since yesterday, our most recent meeting, was not sufficient to
warrant another sharing of
ideas), but instead meet Satueday morning at 9:00.
Moreover,since we had made suffiicient "brainstorming" on the three
assignments of Phase 1 as
a group, we have decided to divide the fine-tuning responsibilities
separately among members of
the group. I will be concentrating on Part 2, syncronous send-and-receive
word messages,
between now and Saturday morning.
On a related note, here's a thread begun on the class mailing list:
Since I know Liu, I was teasing him a litle. I mean that
it is good enough
to design a mail box so that it can synchronize sending
and receiving and
it is not required to be sure about who will send to whom.
If Liu want to
make it perfect he can put a lot efforts to make it ....
Sorry for confusion,
Dong
On Tue, 1 Feb 2000, Michael Boyles wrote:
> Dong,
>
> Sorry, but I don't understand what you are trying to
say in the last
> statement in the second paragraph:
>
> " Mail box will not have responsibility to ensure about
who will
> get a message from whom, except you want it to!!! "
>
> Can you try to explain what you mean? Thanks,
> - Mike
> ________________________________________________
> _/ \_
> | Michael Boyles Lead Research Programmer |
> | mjboyles@iupui.edu Advanced Visualization Lab |
> |_ www.avl.iupui.edu/~mjboyles Indiana University _|
> \________________________________________________/
>
> On Tue, 1 Feb 2000, Dong Hoang wrote:
>
> > it is not required the n-th receiver will get the
message from exactly
> > n-th sender. If you want to do this way more things
you have to take care
> > of, so it is not good!!!.
> >
> > Here you have a mail box which has send() and receive()
methods and
> > differents thread are using these methods concurrently
to send or receive
> > messages. Mail box will not have responsibility to
ensure about who will
> > get a message from whom, except you want it to!!!
> >
> > About multiple senders waiting for receivers... I
think the first one will
> > have its "message" copy first since you are using
list structure from the
> > file call list.* and it follows FIFO algorithm.
> >
> > Dong
> >
> > On Tue, 1 Feb 2000, liuy wrote:
> >
> > > Hi, Dong,
> > > I've a question about the Mailbox. Suppose there
are multiple receivers
waiting
> > > for the sender, should the Mailbox ensure the first
receiver always got
the
> > > first message available? And also if multiple senders
waiting for the
receiver,
> > > should the first sender reach the Mailbox has its
message copied first?
> > >
> > > Yang
Wednesday - Thursday, 2-3 February, 2000
Here's what I have so far:
A port is created using a port_create system call. Ports have
a finite size, which is passed as a
parameter to the
port_create system call. A port is successfully
created if (1) the number of
ports in the system does not exceed MAX_PORTS and (2) the size is valid
(greater than 0, and less
than MAX_PORT_SIZE. On successful completion, the system call returns
a unique port identifier,
which is to be used for other port operations. MAX_PORTS and MAX_PORT_SIZE
are kernel
defined constants (see below).
A port is accessed from user programs through port_send and
port_receive
system calls. A
port_send call will allow a process to write data to the port.
A port_receive call will allow a
process to retrieve data from a port.
The
port_send and port_receive calls thus represent
En-queue and De-queue operations on the
conceptually infinite queue implemented by the Port. This means that
(1)
port_send always
inserts at the tail of the conceptual queue, and (2) port_receive
always removes data from the head
of the conceptual queue.
Both port_send and port_receive are blocking
and reliable. (i.e., a port_send call returns only
after the data has been successfully deposited). Likewise, a
port_receive
call only returns when a
data has been successfully retrieved.
The port_send and port_receive are also atomic in
the following sense: If two processes
concurrently attempt to send data to the port using a send_port
call, then the data from the two
processes will not beinterleaved. For example, if process A does port_send,
concurrently
with process B's port_send, then the data sent by one process
will be always be placed in
contiguous locations in the port.
This is the same for port_receive call, that is a single call
to
port_receive will retrieve data
from contiguous locations in the port (like the write and
read
system calls in Unix).
A port is kept alive so long as there are active processes with access
rights to it. When there are no
processes left with access rights to a port, it is destroyed. Any data
left in the port is destroyed as well.
Once a port has been destroyed, its identifier may be reused by the
kernel.
Test as we build, working in incremental steps:
1) Create a Port (port.h, port.cc) class to handle the operations
on a single port.
2) Create a Port Manager class (portmgr.h, portmgr.cc), along
the lines of a process manager,
to manage all ports in the system (allocating
port ids, keeping track of active ports, etc.).
3) Within the Port class, use an array to implement a circular
buffer.
4) The utils directory has a Semaphore class (synch.h, synch.cc),
which will "perform" synchronization.
I figure this synchronization requirements
are similar to the producer-consumer problem in text.
5) The implementation requires moving data from user address
space to kernel and vice-versa.
I have no idea how to do this.
(John - see the function system_read_null
in syscall.cc to see how the kernel can read
a null terminated string
from a user program address space).
6) We'll need to write two functions will need to be written
to read (write) a string of given length
(instead of null-terminated) from
(to) user process address space to (from) kernel. These will be
useful for port_send
and port_receive system calls.
The following constitutes the system call interface (and should be added
to the syscall.h) file in the
include directory. The interpretation of the system calls is as defined
above. All system calls
return -1 in case of an error. Ports accept character data (note:
1 character = 1 byte), and the port
size defines how many characters it can hold.
#define MAX_PORT_SIZE 50 /* maximum size (bytes) of a port */
#define MAX_PORTS 20 /* maximum ports in the
system */
/* system call codes */
#define SC_port_create 8
#define SC_port_send 9
#define SC_port_receive 10
/* system call prototypes */
int port_create(int size) ;
int port_send(int portId, char *buffer, int size) ;
int port_receive(int portId, char *buffer, int size) ;
Thursday, 4 February, 2000
Tonight in class, we met with Prof. Bukhres to confirm with him that we are meeting.
I shared the information regarding the Mailbox assignment with Ramesh
and Bindu. Design is
basically squared away, except for the priority scheduling (John Schuck's
doing that).
Friday, 5 February, 2000
Looks like some more progress was made after our meeting last night. Got this e-mail this morning:
Please send the synch.h and synch.cc files on which
we were working
yesterday night, trying to implement Locks, Condition
and Mailbox, so that
everybody has a copy of it to analyse the things
before we meet tomorrow.
Also, I think we might need to change the Mailbox
class so that it
works in all kinds of scenario. The way we thought
we will implement
things might not work in a couple of scanrio. We
will discuss this
tomorrow in our group meeting.
Saturday, 6 February, 2000
We met this morning on campus, and finalized our design (and began the coding).
We traded phone numbers, in the event of last-minute file updates:
John Schuck: 579-1459
Bindu:
954-1837 (home) or 278-2948 (235 lab)
Ramesh 570-6907
For the prority scheduling assignment:
We decided to implement a semaphore, based on time-slices, among (3) buffers (values = 0, 1, 2):
1st - time-slice < 8 ms (aviliable for pre-emptive
scheduling)
2nd - time-slice >8ms , < 24 ms
3rd - time-slice > 24 ms
After a process is sent to the ready-queue, and subsequently to the
CPU, it will be sent to one of the
above-noted buffers in the event the process has not yet completed.
The process repeats until the
process is completed.
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Here's what we're turning in Tuesday afternoon:
Implementation of locks and condition variables
class Lock {
private:
char *name;
bool busy;
Thread *currently_held_thread;
List *queue;
}
void Lock::Acquire()
{
1. Disable the interrupts
2. If (busy) add the thread to the queue
of the lock;
3. while(busy)
sleep();
4. busy = true;
5. currently_held_thread = currentThread
}
void Lock::Release()
{
ASSERT (is_held_by_currentThread());
busy = false;
next_thread = (thread *) queue->remove();
scheduler->Ready_to_run(next_thread);
}
Implementation of syncronous send-and-receive message system
A port is created using a port_create system call. Ports have
a finite size, which is passed as a
parameter to the
port_create system call. A port is successfully
created if (1) the number of
ports in the system does not exceed MAX_PORTS and (2) the size is valid
(greater than 0, and less
than MAX_PORT_SIZE. On successful completion, the system call returns
a unique port identifier,
which is to be used for other port operations. MAX_PORTS and MAX_PORT_SIZE
are kernel
defined constants (see below).
A port is accessed from user programs through port_send and
port_receive
system calls. A
port_send call will allow a process to write data to the port.
A port_receive call will allow a
process to retrieve data from a port.
The
port_send and port_receive calls thus represent
En-queue and De-queue operations on the
conceptually infinite queue implemented by the Port. This means that
(1)
port_send always
inserts at the tail of the conceptual queue, and (2) port_receive
always removes data from the head
of the conceptual queue.
Both port_send and port_receive are blocking
and reliable. (i.e., a port_send call returns only
after the data has been successfully deposited). Likewise, a
port_receive
call only returns when a
data has been successfully retrieved.
The port_send and port_receive are also atomic in
the following sense: If two processes
concurrently attempt to send data to the port using a send_port
call, then the data from the two
processes will not beinterleaved. For example, if process A does port_send,
concurrently
with process B's port_send, then the data sent by one process
will be always be placed in
contiguous locations in the port.
This is the same for port_receive call, that is a single call
to
port_receive will retrieve data
from contiguous locations in the port (like the write and
read
system calls in Unix).
A port is kept alive so long as there are active processes with access
rights to it. When there are no
processes left with access rights to a port, it is destroyed. Any data
left in the port is destroyed as well.
Once a port has been destroyed, its identifier may be reused by the
kernel.
Test as we build, working in incremental steps:
1) Create a Port (port.h, port.cc) class to handle the operations
on a single port.
2) Create a Port Manager class (portmgr.h, portmgr.cc), along
the lines of a process manager,
to manage all ports in the system (allocating
port ids, keeping track of active ports, etc.).
3) Within the Port class, use an array to implement a circular
buffer.
4) The utils directory has a Semaphore class (synch.h, synch.cc),
which will "perform" synchronization.
I figure this synchronization requirements
are similar to the producer-consumer problem in text.
5) The implementation requires moving data from user address
space to kernel and vice-versa.
I have no idea how to do this.
(John - see the function system_read_null
in syscall.cc to see how the kernel can read
a null terminated string
from a user program address space).
6) We'll need to write two functions will need to be written
to read (write) a string of given length
(instead of null-terminated) from
(to) user process address space to (from) kernel. These will be
useful for port_send
and port_receive system calls.
The following constitutes the system call interface (and should be added
to the syscall.h) file in the
include directory. The interpretation of the system calls is as defined
above. All system calls
return -1 in case of an error. Ports accept character data (note:
1 character = 1 byte), and the port
size defines how many characters it can hold.
#define MAX_PORT_SIZE 50 /* maximum size (bytes) of a port */
#define MAX_PORTS 20 /* maximum ports in the
system */
/* system call codes */
#define SC_port_create 8
#define SC_port_send 9
#define SC_port_receive 10
/* system call prototypes */
int port_create(int size) ;
int port_send(int portId, char *buffer, int size) ;
int port_receive(int portId, char *buffer, int size) ;
Preemptive prority scheduling
We decided to implement a semaphore, based on time-slices, among (3) buffers (values = 0, 1, 2):
1st - time-slice < 8 ms (aviliable for pre-emptive
scheduling)
2nd - time-slice >8ms , < 24 ms
3rd - time-slice > 24 ms
After a process is sent to the ready-queue, and subsequently to the
CPU, it will be sent to one of the
above-noted buffers in the event the process has not yet completed.
The process repeats until the
process is completed.
The buffers do not prioritize, hence no locks will be implemented on them.
Add to Thread Class
ThreadPriority = 1 // Assign a default value of one to
newly created thread.
0 (zero) is reserved for pre-emption.
Add to Synchlist
PriorityRemove
int counter
for (counter=0;counter < n; counter ++)
// n represents number of threads
HighestPriority = ThreadPriority (T1) //
grabs priority of first thread; T1
represents thread 1
if ThreadPriority (Tn) < Highest Priority
then ReadytoRun Thread = Tn; //
check for lowest number (highest priority)
and assigns it to run next
return
Change all instances of Remove() to PriorityRemove()
// Pulls next thread
based on assigned priority
Change all queues from List to Synchlist
Add to Scheduler
If ThreadPriority(CurrentThread) > ThreadPriority(ReadytoRun)
then SWITCH()
// Pre-empt current thread if higher priority
arrives
// This is the part I am unsure of the coding.
We can make it time based
using stats->totalTicks for a time reference.
// We will have to have a happy medium for
the value of q. We don't want the
CPU to spend all of it's time switching
// (spinning in a circle) or letting a process
hog the CPU for days at a
time.
// For pre-emption, anything with a priority
of 0 will execute until
completion. We can use that value to assign
to lower priority processes if
higher priority processes are waiting on
them. I don't know of any other
circumstances we have now that require pre-empting.
...Process Begins...
startTime = stats->totalTicks
...Process executes...
If totalTicks - startTime => q then (ThreadPriority(currentThread)
++ ;
SWITCH())
// We have to assign a value to q. Maybe
100 to start ???
I increased the
value of the ThreadPriority to decrease it's priority.
If a process doesn't
fully execute because it ran out of time, then it makes
way for higher (or
equal) priority processes to prevent their starvation.
I also CC'd my work email for your reference.
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
(please see attached code for first-draft modifications)
Here is the Semaphore code we added to synch.cc, which implements the locks and mailbox structure:
Lock::Lock(char* debugName)
{
name = debugName;
queue = new List;
}
Lock::~Lock()
{ delete queue;
}
void Lock::Acquire()
{
IntStatus oldLevel = interrupt->SetLevel(IntOff);
// disable interrupts
while (busy) {
// semaphore not available
queue->Append((void
*)currentThread);
// so go to sleep
currentThread->Sleep();
}
busy = true;
currentlyHeldThread = currentThread;
// semaphore available,
// consume its value
(void) interrupt->SetLevel(oldLevel); // re-enable interrupts
}
bool Lock::isHeldByCurrentThread()
{
return (currentlyHeldThread
== currentThread);
}
void Lock::Release()
{
Thread * next_thread;
IntStatus oldLevel = interrupt->SetLevel(IntOff);
ASSERT (isHeldByCurrentThread());
busy = false;
next_thread = (Thread *) queue->Remove();
scheduler->ReadyToRun(next_thread);
(void) interrupt->SetLevel(oldLevel);
}
Condition::Condition(char* debugName)
{
name = debugName;
queue = new List();
}
Condition::~Condition()
{
delete queue;
}
void Condition::Wait(Lock* conditionLock)
{
// ASSERT(FALSE);
IntStatus oldLevel = interrupt->SetLevel(IntOff);
conditionLock->Release();
queue->Append((void *)currentThread);
currentThread->Sleep();
conditionLock->Acquire();
(void) interrupt->SetLevel(oldLevel);
}
void Condition::Signal(Lock* conditionLock)
{ Thread *nextThread;
ASSERT(conditionLock->isHeldByCurrentThread());
IntStatus oldLevel = interrupt->SetLevel(IntOff);
conditionLock->Release();
// ????????????
nextThread = (Thread *) queue->Remove();
scheduler->ReadyToRun(nextThread);
(void) interrupt->SetLevel(oldLevel);
}
void Condition::Broadcast(Lock* conditionLock)
{
Thread *nextThread;
ASSERT(conditionLock->isHeldByCurrentThread());
IntStatus oldLevel = interrupt->SetLevel(IntOff);
conditionLock->Release();
// ????????????
nextThread = (Thread *)queue->Remove();
while(nextThread != NULL)
{
scheduler->ReadyToRun(nextThread);
}
(void) interrupt->SetLevel(oldLevel);
}
MyMailBox::MyMailBox(char *debugname)
{
name = debugname;
empty = new Semaphore("empty", 1);
full = new Semaphore("full", 0);
mutex = new Semaphore("mutex",1);
waitingThread = NULL;
}
MyMailBox::~MyMailBox()
{
delete empty;
delete full;
delete mutex;
}
void MyMailBox::Send(int *message)
{
empty->P();
// Waiting for the mailbox to b empty to write the message
mutex->P();
msg = *message;
mutex->V();
waitingThread = currentThread;
full->V();
// Signal the mailbox to be full
currentThread->Sleep();
return;
}
void MyMailBox::Receive(int *message)
{
full->P();
// Waiting for the mailbox to be full to read the message
mutex->P();
*message = msg;
mutex->V();
if (waitingThread != NULL)
scheduler->ReadyToRun(currentThread);
empty->V();
// Signal the mailbox to be empty
}
Monday, 7 February, 2000
This message was in my e-mail last night, from Ramesh and Bindu:
Yesterday, we(myself and Bindu) were speaking to
Dong and he suggested
that we will introduce another
function in 'SynchList' class called say,
'PriorityRemove()' which will
remove the highest priority object from the
List and return it. And we will
replace all the calls to 'Remove()' with
this function, That way we don't
need to code another class called
'Priority List'.
Also we need to change all the
queues to be using 'SynchList' instead of
'List'.
We thought it was a very good suggestion from Dong. What do you think ?
Any progress regarding the coding for 3rd problem ?
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
As of this morning, there are no plans to meet tonight on campus.
Tuesday, 8 February, 2000
Friday, 11 February, 2000
The following modifications were made to the code:
The function MyMailboxTest() function was added to main.cc,
now one of the five
external functions during the kernel iniialization (extern void):
extern void MyMailBoxTest();
//extern void LockAndConditionTest(void);
// SynchList *synchlist = new SynchList();
Lock *integerLock = new Lock("Integer
Lock");
int globalInt;
MyMailBox *globalMailBox = new MyMailBox("Global");
In the list.cc file, the List:PriorityRemove
function was created, so that
items from the list can be removed,, according to priority:
#include "thread.h"
void *List::PriorityRemove()
{
printf("Entering Priority
Remove.");
ListElement *highestPrtyElem
= first, *previousElem = first,
*currentElem = NULL, *highestPrtyElemPrev = NULL;
void *thing;
Thread *currentThreadL, *highestPrtyThread;
if (IsEmpty())
return
NULL;
thing = highestPrtyElem->item;
if (first == last)
{
first =
last = NULL;
}
else
{
if
(previousElem != NULL)
currentElem = previousElem->next;
while(currentElem
!= NULL)
{
currentThreadL = (Thread *)currentElem->item;
highestPrtyThread = (Thread *)highestPrtyElem->item;
printf("Current Highest Priority Thread is : %s", highestPrtyThread->getName());
if (currentThreadL->GetPriority() < highestPrtyThread->GetPriority())
{
highestPrtyElem = currentElem;
highestPrtyElemPrev = previousElem;
}
previousElem = currentElem;
currentElem = currentElem->next;
}
if (highestPrtyElemPrev != NULL)
highestPrtyElemPrev->next = highestPrtyElem->next;
thing = highestPrtyElem->item;
printf ("BD - The value of highestPrtyElem is : %d ", &highestPrtyElem);
delete highestPrtyElem;
printf ("AD - The value of highestPrtyElem is : %d ", &highestPrtyElem);
printf("Returning the Thread--> %s", ((Thread *)thing)->getName());
}
return thing;
}
It was decided that icoming threads are set to default to a priority
value of 10, and that starvation
avoidance would need to be added to this code tomorrow: as soon as
a thread with the highest
priority is removed and goes to the CPU. all other threads in READY
are aged bu a value of 1.
In the scheduler.cc file, the Schedule:readyToRun
function was modified, so that the thread
running goes into READY, nre threads coming in are put on the READY
list, then the thread
that was currently running goes back to the CPU:
void
Scheduler::ReadyToRun (Thread *thread)
{
DEBUG('t', "Putting
thread %s on ready list.\n", thread->getName());
printf("putting
the thread in ready list %s \n", thread->getName());
if (thread->GetPriority()
< currentThread->GetPriority())
{
IntStatus oldLevel = interrupt->SetLevel(IntOff);
currentThread->setStatus(READY);
readyList->Append((void *) currentThread);
scheduler->Run(thread);
(void) interrupt->SetLevel(oldLevel);
}
else
{
thread->setStatus(READY);
readyList->Append((void *)thread);
}
}
It was decied that priority inversion would need to be added to this code tomorrow.
In the thread.cc, the Thread:~Thread() was
modified so that a priority value was given
to the new thread, and the following lines would be printed out:
"deleting thread ______________" (this was in the original code)
"______________ is the thread to be destroyed"
"and the current thread is ___________"
Thread::~Thread()
{
DEBUG('t', "Deleting
thread \"%s\"\n", name);
printf(
" %s is the thread to be destroyed\n", getName());
printf(
" and the current Thread is %s \n ", currentThread->getName());
ASSERT(this !=
currentThread);
if (stack !=
NULL)
DeallocBoundedArray((char *) stack, StackSize * sizeof(int));
}
// ---------------------------------------------------------------
// the function to set-priority
// ---------------------------------------------------------------
void Thread::SetPriority(int prty)
{
priority = (prty > 10)? 10
: prty;
}
// ---------------------------------------------------------------
// the function to get-priority
// ---------------------------------------------------------------
int Thread::GetPriority()
{
return priority;
}
Also in thread.cc, priority is initally set to 10. It was decied
that we will implement another
function so that threads age: once a thread agres to 50 (or something
less -- we'll have to
experiement), it will bump back to a priority value 9.
The follwoing additions were made to the threadtest.cc file:
#include <iostream.h>
#include "synch.h"
extern MyMailBox *globalMailBox;
extern Lock *integerLock;
extern int globalInt;
/* #include <iostream.h>
#include "synchlist.h"
extern SynchList *synchlist;
void Append(int x)
{
cout << "The
Current thread is " << x ; // currentThread->getName() ;
cout << " Appending
:" << x << endl;
synchlist->Append((void
*) (& x));
}
void Remove()
{
cout << "The
Current thread is " << 0 ; //currentThread->getName() ;
int *x = (int *)synchlist->Remove();
cout << " Removing
:" << *x << endl;
}
void LockAndConditionTest()
{
DEBUG('t', "Entering
LockAndConditionTest ");
Thread *t1 = new
Thread("forked thread");
t1->Fork(Append,
1);
Remove();
}
*/
//----------------------------------------------------------------------
// SimpleThread
//
Loop 5 times, yielding the CPU to another ready thread
//
each iteration.
//
//
"which" is simply a number identifying the thread, for debugging
//
purposes.
//----------------------------------------------------------------------
void
SimpleThread(int which)
{
/* int num;
for (num = 0;
num < 5; num++) {
printf("*** thread %d looped %d times\n", which, num);
currentThread->Yield();
}
*/
cout << "Running the thread
" << which << endl;
//
$Id$
integerLock->Acquire();
globalInt = which;
currentThread->Yield();
cout << "Running the thread
" << which << endl;
cout << "The Value of GlobalInt
: " << globalInt << endl;
printf ("Going to call Release function
on the lock");
printf ("\nthe value of integerLock
: %d :\n", &integerLock);
integerLock->Release();
return;
}
//----------------------------------------------------------------------
// 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 *t = new Thread("forked thread");
t->Fork(SimpleThread,
1);
SimpleThread(0);
}
void Recieve(int x)
{ int message;
cout << "Running the
thread " << currentThread->getName() << endl;
globalMailBox->Recieve(&message);
cout << "Message retrieved
" << message << "By " << currentThread->getName();
cout << endl;
}
void Send(int message)
{
cout << "Running the
Thread " << currentThread->getName() << endl;
globalMailBox->Send(&message);
cout << "Message :
" << message << "Sent by thread " << currentThread->getName()
;
cout << endl;
}
void MyMailBoxTest()
{
DEBUG('t', "Entering
SimpleTest");
Thread *t1 = new
Thread( "t1",2);
Thread *t2 =
new Thread( "t2",9);
Thread *t3 =
new Thread( "t3",9);
Thread *t4 =
new Thread("t4",5);
t1->Fork(Recieve,0);
t2->Fork(Send,100);
t3->Fork(Send,200);
t4->Fork(Recieve,0);
}
Saturday, 12 February, 2000
We finished up everything today, except for some of the scheduling algorithm.
The following files were modifoed this afternoon:
The synch.cc file has been modified to add the Lock::Acquire() function:
The synch.h has been modified to call this above-noted call:
The thread.cc has been once again modified
(specifically, the get-priority
and set-priority sections added yesterday), to
set into place the priority
sycnchronization:
The list.cc was again modified to include the List::mapcar function.
The list.h was modified accordingly.
Bindu is going to add all comments tomorrow, and
the rest of us will continue
to tire over the scheduling algorithm. John and
I will be debugging the threadtest.cc
file to test mailbox communication. Although
we had decided that this "works,"
we're going to test it anyway and try to establish
some kind of limit.
Monday, 14 February, 2000
Tonight we spent finishing the priority scheduling, and the commenting of all the code.
It was decided that my copy of NACHOS would remain "native" (untouched,
unmodified), in the
event we need to "start over."
Wednesday, 16 February, 2000
I did not submit my journal for Phase 1, until today.
Wednesday, 17 February, 2000
Phase 2 was posted today on the class web page (two parts):
1. System call and exception handling implementation
2. Multiprogramming implementation (with time-slicing)
(a) come up with a way of allocating physical memory frames
so that multiple programs can be loaded into memory at
once (cf. bitmap.h)
(b) provide a way of copying data to/from the kernel from/to the
user's virtual address space (now that the addresses the user
program sees are not the same as the ones the kernel sees)
(c) use
timer interrupts to force threads to yield after a certain
number of ticks. Note that scheduler.cc now saves and
restores user machine state on context switches.
Thursday, 18 February, 2000
We have unanamously decided that rather than divide the two assigments
two ways, where each
group member would pair up with another member of the group, we would
instead divide the tasks
of both assignments four ways, so that we all have a hand in both parts.
The first requirement of the design of the system call implementation
is to support all of
the system calls defined in syscall.h (except for Fork()
and Yield()).
[Note: Algorithms will be added to this day's entry as they become realized]
Exec():
Requirements:
Create an address
space for the given program, load the program, and begin
executing its main thread.
Each process
keeps track of its child threads to enable a join.
If the execution
generates an exception, that exception should be passed to
the exception handler to be handled.
Algorithm:
Read in the
virtual address of the filename passed via the register.
Translate the
address into it's corresponding physical address and
read the filename from the memory location pointed to by it.
Allocate a structure (process) for keeping track of the child address
space. A pointer to this structure is added to a list in the calling process.
The structure contains a pointer to the child address space, an exit
value,
open file Ids, and semaphores for synchronization with the child.
Create
an address space, then call the loader to load the user program.
On an error,
this function will return an error, but the calling program will
continue execution. Error conditions are:
file not found,
file is not a valid program, there is not enough memory.
Increment the
PC and return to user program.
Join():
Requirements:
Return the child
process's exit status code.
Return immediately
if the child process has already completed. Otherwise goes to
sleep until it has finished.
Detect a call
for join with a non-child process. Ignore the call in such a case.
A process can
only join with its child processes.
Algorithm:
Read in the
child process ID (SpaceId).
Search the calling
address space's child process list for the given spaceID.
If the spaceID
is not found (there was no child with that spaceID), return.
When the child
process is found, a semaphore is called with a P(). This will wait until
the child process has finished if it has not already.
Once the child
signals that it has finished, read it's exit status and signal it so it
can
terminate (semaphore->V()).
The PC is incremented
and the child's exit status returned.
Exit():
Requirements:
Waits until
all child processes are finished (joins them).
Close all the
process's open files.
Terminates the
process.
Delete the address
space.
Algorithm:
Read in the
process's exit status passed in via register 4.
Enumerate the
address space's list of open file IDs and close them.
Then removes them from the list.
Exit enumerates
the list of child processes and performs a join on each
one to make sure they will all terminate.
Exit then sets
the return value in the address space's process structure,
and does a V() on the process semaphore to mark it as finished.
If it needs
to wait for a join then it does so.
Once join is
done (or in case it didn't have to wait) the process terminates.
The address
space is then deleted (delete kernel->CurrentThread->space).
The thread is
marked as finished.
Create():
Requirements:
Create a nachos
file called "name".
If no name is
given, print out error message.
Algorithm:
Read in the
file name address. translate it and check it's validity.
kernel->FileSystem->Create(name).
Increment the
PC and return.
Open():
Requirements:
Open a nachos
file called "name".
More than one
process may not have the same file open at the same time.
If the no name
was given, print out error message.
If file is already
open, then print out an error message.
The file name
is added to the process's list in order for it to keep track of all it's
open files.
The file name
is added to a list of open files in the kernel for tracking.
Algorithm:
Read file name.
Check if it
is already open.
If not, open
it: ID = kernel->filesystem->open(name)
Add the file
to list of open files.
Increment PC
and return file Id.
Read() / Write():
Requirements:
Reads/Writes
to/from a file identified by a fileID.
A process can
only access files that it has previously opened.
Buffers may
span physical page boundaries.
The program
can read or write beyond the buffer as long as it is in its own
address space, but may not spill over to another address space.
Algorithm:
read in file
Id, size and virtual address of source/destination.
The list of
files in the address space's open file list is scanned to make sure the
given fileID is owned by this process. An error is returned if it is not
found.
A temporary
kernel buffer is allocated to transfer the information. Read reads
the file into this buffer, then copies it to the program's buffer. Write
does
the opposite. A copying function will need to be created to copy the data
safely. If there is an error copying the data, the user program will be
terminated by the function.
The temporary
buffer is freed, the PC incremented, and the function returns.
Close():
Requirements:
Closes a file.
Only files previously
opened by this process may be closed.
Algorithm:
The list of
open file IDs in the process's address space is scanned. If the handle
is not found, an error message is returned.
The file is
removed from the process's file list.
The file is
removed from the kernel's file list.
PC is incremented
and program resumed.
I also began "thinking" about Part Two of Phase 2, the multiprogramming
with time-splicing (three sub-sections). Here's what I have so
far:
[Note: Algorithms for this second part will be added to this day's
entry as they
become realized]
A: Allocate physical memory to allow multiple programs to coexist on the machine
The run-time mapping from virtual to physical address is done by
the
memory-management unit (MMU), which is a hardware device.
(Siverschatz, p. 245)
Requirements:
Each program has its own address space.
Pages of the virtual address space can
be mapped to different,
noncontiguous physical
pages.
Programs can only access data within
their virtual address space.
Provide an algorithm for keeping track
of free physical pages.
Provide a translation algorithm to determine
the physical mapping of
a virtual page.
Algorithm:
Add a bitmap array to the kernel to
keep track of free/used physical
pages. To create a mapping for a virtual
page, the bitmap is scanned
for the first free block. The virtual
page's data is copied into the
physical page. This translation is stored
in the address space class
in pageTable.
The translate function will enforce that
programs only access data
in its page table. It looks up a virtual
address in the address
space's translation table, and returns
a physical address.
On program termination, go through the
address space's page table,
and mark each of the used physical pased
unused in the kernel's bitmap.
-----
B: Provide a way to copy data between the kernel and user programs'
address
space.
Requirements:
Write 2 new functions, AddrSpace::WriteTo
and AddrSpace::ReadFrom which
read/write data between
a physical address of a kernel buffer and a
virtual address in
the address space.
Ensure data is not copied to or from
invalid pages. If the buffer
spans one or more
invalid pages, an exception is thrown.
Buffers which span multiple virtual
pages in the user program must work.
Algorithm:
The functions must first must translate
the virtual address into a
physical address. The translate function
will perform validity checking
on this. It then copies data until the
end of the given buffer is reached
or the end of the physical page is encountered,
whichever comes first.
(The page boundary is calculated once
at the beginning of the function to
avoid the overhead of translating the
virtual address of every byte.)
The program repeats this process until
the end of buffer is reached, or
an error is encountered. An error would
result if a given virtual address
has no physical translation. On a translation
error, the user program
is terminated.
The translate procedure in the address
space was modified to take
an additional optional arguement, a
pointer to a variable to contain
the number of bytse to the end of the
page. The copying functions use
this value to tell when to call Translate
to update the address
mapping. This eliminates unnecessary
address translation.
------
C: Synchronize the creation and deletion of address spaces.
Requirement:
Only one thread may modify an address
space translation at a time.
Algorithm:
Create a semaphore (initially available)
in the kernel. In the AddrSpace
constructor and destructor, use this
semaphore around the code that
allocates and frees the address space's
memory and modifies the kernel's
free/used memory block bitmap.
After class tonight, we met briefly to discuss design plans. It
was decided that some
"PC incrementing" algorithm is both required and feasible.We agreed
to meet again
tomorrow night at a greater length.
Algorithms (a first draft, anyway) for implementing the Create
(), Open (), and
Read()/Write() system calls were added
to the Monday, 21 February
journal entry.
Wednesday, 23 February, 2000
This morning I added Requirments and Algorithms for Part
Two of
Phase 2 (see Tuesday,
22 February for the active log of this second part).
No additions to Part One
.
Meeting last night, we decided to divide the syscalls amongst ourselves.
Our projected
completion date is next Wednesday, March 1. Here are the assignments:
John Joachim - Open()& Close()
John Schuck - Create() & Read()/Write()
Binda Jain - Exit()& Halt()
Ramesh Muthyala- Exec()& Join()
Next meeting is planned for this Saturday, 2-4 PM - just to check everyone's
progress
(or lack thereof).
Thursday, 23 February, 2000
Our group met with Bukhres after class tonight, to verify with him that
we're still on track.
We still have plans to meet Saturday afternoon, just to check each
others' progress.
Saturday, 25 February, 2000
This afternoon afternoon I added an algorithm [albeit tentative !!]
for the
exit() and join() system
calls (see Monday, 21 February
for details).
Still working out the close() system call (hoping to have at least the
algorithm by this Wednesday).
I'm assuming that all open files need to be "scanned" before one of
them is actually closed. The
file must be removed from both the process's file list and the kernel's
file list (sequential ?).
Sunday, 26 February, 2000
I added a tentative algorithm for the close() system call (see Monday, 21 February for details).
Here's a question for the group, to discuss maybe Wednesday evening
(I thought about this after
re-reading Chapter 3 in Silberschatz): Do these system calls we're
writing need to take resource
allocation, multi-use "protection", and resource accounting into consideration?
Will this be
accomplished at the "incrementation" process?
Tuesday, 28 February, 2000
Design and code for Part One of Phase 2 is now completed.
Tuesday, 7 March, 2000
Plans to meet tonight were cancelled. We'll be meeting again this
weekend to implement the
Part One code onto NACHOS.
Thursday, 9 March, 2000
Dong posted some code on the class web site, some assistance for Part 2 of Phase 2.
Monday, 8 March, 2000
Since last week, we have made some refinements to the system calls(
) for Part One of
Phase Two, and it sounds like (from e-mails within the group that the
Design for Part One
and Part Two are ready to be submitted (due tomorrow).
Sunday, 12 March, 2000
More refinements on the code was done today. Last-minute changes
to the Part Two design
were discussed, and changed appropriately (see Tuesday,
February 22, 2000).
Wednesday, 15 March, 2000
Design for Phase Two was submitted. Plans to meet this weekend
and finish all the coding is
still on schedule.
Wednesday, 22 March, 2000
Phase Two was turned in today (a day late, but we've still have three
"late days" left.
Thursday, 23 March, 2000
Phases Three and Four are posted on the internet. I sent the
following message
to everyone this morning:
Just wanted to touch base with everyone about the
last two phases on NACHOS.
Both are posted on the class web page. Phase 3 is
due 4/11, and Phase 4 is
due 4/23. Both phases include an assignment that is
EXTRA CREDIT. Please
note this on the web page.
In class last night, Bukhres also said that a FINAL
ORAL PRESENTATION will be
required of each group (lessons learned, how we'd
do
it differently, what we
learned, etc.).
Our next meeting is this Monday at 7:30 (if this
will not work, like a later
time, or a different day, please tell EVERYONE as
soon as you can).
Personally, I'd like to move this up to 7:00, but
I
know this might not work
with everyone.
For Phase Three, each team member is responsible for
the design, code, AND
TESTING of their respective parts. If there are
problems doing any of this,
be it the design, or code writing, or testing, that
member needs to contact
the rest of the group as soon as possible .... don't
wait for the weekend,
don't wait until the class meeting, etc. .... we all
have e-mail.
Phase Two blew up in our faces, because as a group,
we took an entire week
off, there were work constraints (planned AND
unplanned), and in short, we
didn't take advantage of our e-mail, or communicate
adequately.
We decided last night that we all worked hard, but
we DIDN'T WORK TOGETHER: I
worked on and submitted a lot of the design, and
John (Schuck) wrote more than
his share of the code, but neither of us tested any
code (until the last
minute). Bindu and Ramesh worked long hours in the
Sun lab; but because we
didn't work together as a team, the testing took
much longer than necessary.
I am sorry to summarize the problems we had in just
those few short words. I
didn't mean to gloss over anything (if I did).
We CANNOT take any more time off (except for work
constraints), and we MUST
communicate with each other, AND OFTEN. Otherwise,
we can expect the same
thing to happen on the next project (which nobody
wants). All apologies were
shared last night, and it's time to move forward.
We have the talent in our
group to do well on the last two assignments -- in
case you didn't see, we got
a perfect 100% on the first assignment. We can do
the same for the last two,
and PERHAPS, just PERHAPS, we can work on the Extra
Credit to bring our grade
on Phase Two back up.
See you all Monday night.
John Joachim
Everytime a new entry is added to TLB (Translation Lookaside Buffer), print out the content of TLB.
Friday, 24 March, 2000
This morning, Dong posted the following message to the class mailing list:
Hello everyone,
I had made changes in the project mechanics about you should
submit all nachos code directory for testing instead of
submitting
only files you had changed. If you did not submit whole
code
directory pls resubmit it on Friday March 24th.
thank you
Dong
Since Ramesh submitted all the modified code earlier this week, I suspect
he'll
take care of this.
Monday, 27 March, 2000
We met tonight on campus for about an hour.
We decided that since we have both Phase 3 and Phase 4 to work on concurrently,
we will focus largely on Phase 4 - file system creation (since we need
to be able to
have good tests from Phase 2, which unfortunately hasn't happened yet).
Bindu will be bringing in a textbook to class tomorrow, which elaborates
on UNIX
system calls (maybe we can salvage something out of the system calls
from Phase 2 to
make Phase 3 complete - who knows).
Tuesday, 28 March, 2000
Some notes I wrote last night:
[Running log of design for Phase 3 will be listed below]
OVERVIEW:
The third phase of NACHOS involves the implementation of virtual
memory for use programs. In this phase NACHOS uses (TLB) to
map virtual addresses into physical addresses instead of the page table
used in Phase 2. The TLB keeps track of all the physical frames
and
the virtual page information of the current process.
VIRTUAL MEMORY
Virtual memory is implemented by allocating a swap space (a physical
file) for each process. When the process is loaded, it will be
loaded into
the vurtual memory instead of main memory. When the machine starts
executing the instructions of the user program, a PageFault exception
occurs. The Exception Handler, which takes care of the exceptions,
comes into action. It gets the virtual address from the Bad Address
register
(Register 39), and then reads the swap space. If the read is
successful, it
loads into the immediate free frame available, returns the control
to the user
program to start at the same instruction (which caused the PageFault
in the
first place). If the read is unsuccessful, the machine aborts
--
after printing the Debug information.
TLB is like a cache for the translation pageTable. This structure can
contain,
for example, 4 entries of virtual page to physical page mapping. When
an
address reference occurs, the OS first looks in the TLB for the proper
translation. If a TLB misses, a PageFault exception occurs. The
OS then
checks to see if the page is in the memory. If it is, then add the
page to
TLB. If not, the virtual memory systerm is invoked. A page
is found replace
in the TLB when a new entry was added. When a context switch
occurs, all
the entries of TLB will be invalidated.
PHYSICAL FRAME SELECTION PROCESS:
A global inverted page table is used to keep track of the machine's
main
memory. Also, the page table has one more element to indicate
the current
position in the page table. When a page fault occurs and the
virtual memory
indicated by the user program is usccessfully read into the buffer,
we use this
Page Table to select the Physical frame for which this data needs to
be laoded.
Starting with the current Cursor position we sweep through the entire
Page
Table, to find the next avilable free frame. If any frame is
not selected to
load, it's use-bit is set to FALSE, so that this page can be selected
for
replecement in the next sweep if it is not referenced in between.
In other
words, this is giving the recently-used page a SECOND CHANCE.
Once
the frame is selected for replecement, the dirty-bit is examined if
the selected
frame needs to be written back to the Back Store. Once the concurrency
of
the selected frame is taken care of, the data in the Buffer is loaded
into the
Memory.
NEW FUNCTIONS:
Create a new function, AddToTLB(), to the kernel. The
fuction uses clock
algorithm to find a page to replace and add the new entry to the
TLB.
MODIFIED FUNCTIONS:
Modify the exception handler was modified. In particular, change the
PageFaultExcetpion. This case now goes through the process of
checking to see if the page is in the memory. If so the that new entry
is loaded to TLB and the program continues with the same instruction.
If not, virtual memory is invoked.
Modify the Run() function in threads/scheduler.cc
. When a context switch
occurs, all the valid bits of TLB entries are invalidated.
ALGORITHM:
AddToTLB():
-check the use bit.
-if use bit is on, set it false and increment the clock handle.
-if use bit is false, replace it by copying the entry to TLB field
by field, and
turn on the use bit.
==============================
Part 2: Virtual memory Implementation
A virtual memory system providing the abstraction of an almost unlimited
memory size with a performance close to that provided by physical memory
was implemented. User programs should run even if they require
more
memory than is currently available. A core map table that keeps
track of
mappings between physical memory pages and the corresponding virtual
location was also created. It was also necessary, we felt, to
have the ability
to swap out pages from physical memory to disk writing the contents
out if
the dirty bit is set and updating the core map table. Ability
to swap in a page
from disk into physical memory was also included, updating the core
map table
to reflect the change, providing the capability to find a page to replace
when a
new page needs to be loaded.
CLASSES ADDED OR MODIFIED:
A core map table structure was added to the kernel. This structure contains
the same fields as in a TranslationEntry object with a few additions.
It is indexed by the PPN (physical page Number) and contains
additional fields that point to the owning process's swap file, it's
hash
table (formerly known as pageTable), it keeps track of the offset of
the
page into the swap file and it's length and gives the capability of
implementing a second chance replacement algorithm with the 'chance'
field. This will beexplained below.
When virtual memory is invoked and a page needs to be swapped out the
core
map table is consulted to find where the page being replaced should
be
written to. The dirty bit is also examined to determine if the page
needs
to be written back or wether we can simply overwrite it in memory.
The process's page table was changed from a linear structure into a
hash table. This
was done inorder to allow for easy expansion when adding memory mapped
files. A hash function was also written to be used with the hash table.
Hashing
is performed on the virtual page number (VPN).
INVERTED PAGE TABLE:
The following is the structure of the Inverted Page Table used to keep
track of
all the physical memory frames of the machine:
IPEntry - Pointer to an array of 'InvertedPageEntry.' This
is the table that
keeps track of all the frames
(one InvertedPageEntry per physical
frame).
CurrentCurPos - this keeps track of the current position from
where the
search should start when
trying to load a new page of data.
PhysicalPageId - the sequential number for the physical frame
OwnerProcessId - the Process ID of the Process currently owning
the
process
VirtualPageNumber - the virtual page number of the current frame.
MemoryUseBit - Use-Bit used to know if it is presently being
used. The
selection process uses this
bit to determine if this framecan be selected
for loading the new page.
DirtyBit - Dirty-Bit used to indicate if it has been modified
by the
user-process using it OR
the OS
This Page Table Entry wil be used to keep track of the information of
all
the physical frames. All the coding changes for the above page
table are
done in system.h and system.cc.
Since all the system calls and OS functions update the TLB when a page
is read or modified, the information in the Global Inverted Page Table
(GIPT) does not truly reflect the current scenario. The GIPT
should have
correct information so that it can be of any help in assisting the
Page-replacement decisions.
The GIPT is updated using the TLB whenever any of the following occurs:
1) There is a context change
2) a Page-fault occurs
3) A process finishes
NEW FUNCTIONS:
findPage() . This function scans the core map table
to find the page
to replace. The replacement algorithm used
is clock replacement with
a flavor of the second chance list. We first look
for an unused page,
setting the use bit to false as we go along. When
we encounter an
unused page we examine the dirty bit. Should this
bit be true, the page
is given a second chance and we continue searching.
However, when
we return to this page the next time around, it
will get replaced unless
it was used meanwhile.
SwapOut(): This routine accepts a physical page number
provided by the
previous function, findPage(), and moves that page
to disk. It uses the
core map table to find the owner of the page. The
core map table is also
updated by setting that page's valid bit to FALSE.
swapIn(): Opposite of SwapOut(), this routine takes
a PPN and loads the
requested VPN of the current process into it. It
updates the core map table
to reflect the new changes to the physical memory.
MODIFIED FUNCTIONS:
The loader was modified in such a way that it no longer loads the pages
of
the new process into physical memory. Instead, it assigns an address
space
to the process only. When the process begins to execute none of its
pages
are in memory. Needed pages are swapped in by virtual memory.
The exception handler is modified. in particular, the PageFaultException
case is changed. This case now goes through the process of checking
to see
if the page is in memory. If so the TLB is loaded with that page's
information
and the program continues with the same instruction. if not, virtual
memory is
invoked. FindPage() returns a page to replace. If that
page is dirty
SwapOut() is called to write the page out to disk.
If page is not dirty we
continue. The core map table is then updated with the information for
the page to be loaded and SwapIn() is called to go
to disk and load that
page. Program execution then continues with the same instruction. This
time,
the address exception will find the page in memory, the TLB gets updated,
and
execution resumes.
We implemented a circular queue to take in determining which physical
frame
is the perfect candidate for loading the data from virtual memory.
In this data
element 'currentCurPos' is used to start searching for as suitable
candidate. If
a frame's useBit is TRUE, it will not be selected for loading the new
page. At
the same time its useBit is set to FALSE, giving the frame just one
more chance.
Once the frame is selected for loading the new page of data,
we examine the
dirtyBit. If it is set to TRUE, we write back the data from the
memory to
the virtual memory (swap space). Then we copy the data from the
current-address
space's virtual memory to the physical frame (and the the TLB is updated).
Control is then returned to the user process, to start executing from
the same
instruction that caused the PageFaultException in the first place (if
the virtual address
that caused a PageFault Exception is really a bad address, the DEBUG
information
is printed, and the then is ABORTed).
ALGORITHMS:
findPage():
- Check use bit.
- If false check dirty bit, if set give page a second chance.
- If dirty bit is not set, replace the page.
- If use bit was set, unset it and continue.
SwapOut():
- Use the PPN and the core map table to get the swap file and offset
into it.
- Write the page out to disk.
- Update the core map table by setting the page's valid bit to FALSE.
SwapIn():
- Use the PPN and the core map table to get the swap file and offset
into it.
- Read the page from disk.
- Update the core map table by setting the page's valid bit to TRUE.
Load():
- Create a swap file for the process.
- Open the executable and verify it is valid.
- Find it's size and create an address space for it.
- Load the pages into the swap file.
Exception handler(): (implemented in exception.cc)
SyscallPageFaultException:
- If page does not exist in the process's
address space then it is an invalid
address reference
- abort the process.
- If the valid bit is set then the page
is in memory. Load the TLB and return.
- if valid bit is not set then call
virtual memory:
- Find a page to replace.
- if dirty then swap out.
- update core map table.
- swap in new page.
- update core map table.
- resume program execution.
----------------------------------------------------------
----------------------------------------------------------
Wednesday, 29 March, 2000
Last night I sent my design plans for Part 1 of Phase 3.
I sent this e-mail to he group this morning:
Since I wil NOT be able to attend tonight, I will be
sending a rough draft of my ideas for the design of
Part Two of Phase Three later this afternoon. (if
you didn't get Part One yesterday, please write me).
As of now, I have not studied the extra credit. I figured
I should concentrate on the code of Phase Three, and get
a
feel for the design of Part Four BEFORE I worry about any
extra credit (and even then, I'm more likely to work on the
extra credit for Phase Four then Phase Three).
See you all Thursday evening.
John Joachim
I'll send another e-mail later today.
Thursday, 30 March, 2000
I e-mailed everyone my design plans for Part 2 of Phase 3.
Friday, 31 March, 2000
Plans to meet tomorrow om campus are still on.
Saturday, 1 April, 2000
We met on campus today to make some last-minute changes on the Phase
3 design
(see Tuesday, March 28 for additions),
and we began writing the code (in an attempt
to make sure the design is do-able). Everything is surprisingly
on schedule.
Monday, 3 April, 2000
We met tonight to make some last-minute revisions to the design (see
Tuesday,
March 28).
Design is just about ready to submit (grammar and spelling will be
reviewed tomorrow
morning).
Tuesday, 4 April, 2000
Phase 3 design is ready to be submitted, but I'm going to wait until
after class, just in case
any more revisions are made (we're planning to meet briefly after class
tonight).
Wednesday, 5 April, 2000
We're actually making better progress on Phase 3 than expected.
Design is valid and
workable, and we began working on the code tonight (see Saturday,
8 April for details).
Friday, 7 April, 2000
We met for a couple of hours tonight. Much of the code was written,
but getting a few
errors.While compiling threadtest.cc, we got a UNIX error
128. Plans to meet meet
tomomorrow at 10:00 AM still on schedule.
Code for system.cc, system.h,
threadtest.cc,
addrspace.cc,
and addrspace.h
was
modified and tested.
// system.cc
// Nachos initialization and cleanup routines.
//
// Copyright (c) 1992-1993 The Regents of the University of California.
// All rights reserved. See copyright.h for copyright notice
and limitation
// of liability and disclaimer of warranty provisions.
#include "copyright.h"
#include "system.h"
#include <strings.h>
// This defines *all* of the global data structures used by Nachos.
// These are all initialized and de-allocated by this file.
Thread *currentThread;
// the thread we are running now
Thread *threadToBeDestroyed;
// the thread that just finished
Scheduler *scheduler;
// the ready list
Interrupt *interrupt;
// interrupt status
Statistics *stats;
// performance metrics
Timer *timer;
// the hardware timer device,
// for invoking context switches
#ifdef FILESYS_NEEDED
FileSystem *fileSystem;
#endif
#ifdef FILESYS
SynchDisk *synchDisk;
#endif
#ifdef USER_PROGRAM // requires either FILESYS or FILESYS_STUB
Machine *machine; // user program memory and registers
#ifdef CHANGED
SpaceIdEntry SpaceIdTable[MAX_SPACEID]; // SpaceId
Table
OpenFileEntry FileIdTable[MAX_OPENFILE]; //
FileId Table
Lock *SpaceIdLock; // lock used to access
SpaceId Table
Condition *SpaceIdCond; // condition variable
used for
// parent waiting its child to finish
Console *shellConsole; // console
used for user program
Semaphore *shellRead; // synchronize
read from console
Semaphore *shellWrite; // synchronize
write to console
void ShellRead(int arg) { shellRead->V(); }
// called when there
is a character available
// from console
for user to read
void ShellWrite(int arg) { shellWrite->V();
}
// called when write
a character to console is done
BitMap * pageMap; // manage
physical memory usage, each
// bit corresponding to a physical memory frame.
// bit is set when the memory frame is used, and
// bit is clear when the memory frame is free.
InvertedPageTable *globalInvertedPageTable;
#endif
#endif
#ifdef NETWORK
PostOffice *postOffice;
#endif
// External definition, to allow us to take a pointer to this function
extern void Cleanup();
//----------------------------------------------------------------------
// TimerInterruptHandler
// Interrupt handler for the timer device. The timer
device is
// set up to interrupt the CPU periodically (once every TimerTicks).
// This routine is called each time there is a timer interrupt,
// with interrupts disabled.
//
// Note that instead of calling Yield() directly (which would
// suspend the interrupt handler, not the interrupted thread
// which is what we wanted to context switch), we set a flag
// so that once the interrupt handler is done, it will appear
as
// if the interrupted thread called Yield at the point it
is
// was interrupted.
//
// "dummy" is because every interrupt handler takes one argument,
// whether it needs it or not.
//----------------------------------------------------------------------
static void
TimerInterruptHandler(int dummy)
{
if (interrupt->getStatus() != IdleMode)
interrupt->YieldOnReturn();
}
//----------------------------------------------------------------------
// Initialize
// Initialize Nachos global data structures. Interpret
command
// line arguments in order to determine flags for the initialization.
//
// "argc" is the number of command line arguments (including
the name
// of the command) -- ex: "nachos
-d +" -> argc = 3
// "argv" is an array of strings, one for each command line
argument
// ex: "nachos -d +" -> argv = {"nachos",
"-d", "+"}
//----------------------------------------------------------------------
void
Initialize(int argc, char **argv)
{
int argCount, i;
char* debugArgs = "";
bool randomYield = FALSE;
fprintf(stdout,"\nNachos startup ...\n"
"=====================\n\n");
#ifdef USER_PROGRAM
bool debugUserProg = FALSE; // single step user
program
#ifdef CHANGED
for (i=0; i<MAX_SPACEID; i++) {
// initialize the SpaceId table
SpaceIdTable[i].status=NotUse;
SpaceIdTable[i].exitcode=0;
SpaceIdTable[i].ParentId=0;
}
fprintf(stdout,"Initialised space table ...\n");
for (i=0; i<MAX_OPENFILE; i++) {
// initialize the OpenFileId table
FileIdTable[i].openFile=NULL;
FileIdTable[i].ownerId=0;
}
fprintf(stdout,"Initialised filetable\n" );
SpaceIdLock = new Lock("SpaceIdTable Lock");
SpaceIdCond = new Condition("SpaceIdTable Condition");
pageMap = new BitMap(NumPhysPages);
// intialize GIPT.
globalInvertedPageTable = new InvertedPageTable(NumPhysPages);
for(i=0; i<NumPhysPages; i++)
{
globalInvertedPageTable->IPEntry[i].physicalPageId
= i;
globalInvertedPageTable->IPEntry[i].ownerProcessId
= 0;
globalInvertedPageTable->IPEntry[i].ownerAddrSpace
= 0;
globalInvertedPageTable->IPEntry[i].virtualPageNum
= 0;
globalInvertedPageTable->IPEntry[i].useBit
= FALSE;
globalInvertedPageTable->IPEntry[i].dirtyBit
= FALSE;
}
fprintf(stdout,"Initialised GIPT ..\n");
#endif
#endif
#ifdef FILESYS_NEEDED
bool format = FALSE; // format
disk
#endif
#ifdef NETWORK
double rely = 1;
// network reliability
int netname = 0;
// UNIX socket name
#endif
for (argc--, argv++; argc > 0; argc -= argCount,
argv += argCount) {
argCount = 1;
if (!strcmp(*argv, "-d")) {
if (argc == 1)
debugArgs = "+";
// turn on all debug flags
else {
debugArgs = *(argv + 1);
argCount = 2;
}
} else if (!strcmp(*argv, "-rs")) {
ASSERT(argc > 1);
RandomInit(atoi(*(argv
+ 1))); // initialize pseudo-random
// number generator
randomYield = TRUE;
argCount = 2;
}
#ifdef USER_PROGRAM
if (!strcmp(*argv, "-s"))
debugUserProg = TRUE;
#endif
#ifdef FILESYS_NEEDED
if (!strcmp(*argv, "-f"))
format = TRUE;
#endif
#ifdef NETWORK
if (!strcmp(*argv, "-l")) {
ASSERT(argc > 1);
rely = atof(*(argv +
1));
argCount = 2;
} else if (!strcmp(*argv, "-m")) {
ASSERT(argc > 1);
netname = atoi(*(argv
+ 1));
argCount = 2;
}
#endif
}
DebugInit(debugArgs);
// initialize DEBUG messages
stats = new Statistics();
// collect statistics
interrupt = new Interrupt;
// start up interrupt handling
scheduler = new Scheduler();
// initialize the ready queue
#ifndef CHANGED
if (randomYield)
// start the timer (if needed)
timer = new Timer(TimerInterruptHandler, 0,
randomYield);
#endif
#ifdef CHANGED // start the timer, for time-slice user program
// executing
timer = new Timer(TimerInterruptHandler, 0,
randomYield);
// if no `-rs' option, time slice will be
// DEFAULT value 100 ticks
#endif
threadToBeDestroyed = NULL;
// We didn't explicitly allocate the current
thread we are running in.
// But if it ever tries to give up the CPU,
we better have a Thread
// object to save its state.
currentThread = new Thread("main");
currentThread->setStatus(RUNNING);
interrupt->Enable();
CallOnUserAbort(Cleanup);
// if user hits ctl-C
#ifdef USER_PROGRAM
machine = new Machine(debugUserProg);
// this must come first
bzero(machine->mainMemory, (NumPhysPages
* PageSize));
#ifdef CHANGED
currentThread->SpaceId=0; //
SpaceId 0 reserved to the user
// progam running in `main' thread
SpaceIdTable[0].status=InUse;
shellRead = new Semaphore("console read", 0);
shellWrite = new Semaphore("console write",
1);
#endif
#endif
#ifdef FILESYS
synchDisk = new SynchDisk("DISK");
#endif
#ifdef FILESYS_NEEDED
fileSystem = new FileSystem(format);
#endif
#ifdef NETWORK
postOffice = new PostOffice(netname, rely, 10);
#endif
}
//----------------------------------------------------------------------
// Cleanup
// Nachos is halting. De-allocate global data structures.
//----------------------------------------------------------------------
void
Cleanup()
{
printf("\nCleaning up...\n");
#ifdef NETWORK
delete postOffice;
#endif
#ifdef USER_PROGRAM
delete machine;
#ifdef CHANGED
delete SpaceIdLock;
delete SpaceIdCond;
delete shellRead;
delete shellWrite;
delete pageMap;
if (shellConsole) delete shellConsole;
#endif
#endif
#ifdef FILESYS_NEEDED
delete fileSystem;
#endif
#ifdef FILESYS
delete synchDisk;
#endif
delete timer;
delete scheduler;
delete interrupt;
Exit(0);
}
#ifdef CHANGED
//----------------------------------------------------------------------
// Function to copy the information from TLB to GIPT
//----------------------------------------------------------------------
#ifdef USER_PROGRAM
void copyTLBtoGIPT()
{
for(int i=0; i < TLBSize ; i++)
{
if((machine->tlb[i].valid) &&
(machine->tlb[i].use || machine->tlb[i].dirty))
{
int j = machine->tlb[i].physicalPage;
globalInvertedPageTable->IPEntry[j].useBit
= machine->tlb[i].use;
globalInvertedPageTable->IPEntry[j].dirtyBit
= machine->tlb[i].dirty;
}
}
}
#endif
#endif
// system.h
// All global variables used in Nachos are defined here.
//
// Copyright (c) 1992-1993 The Regents of the University of California.
// All rights reserved. See copyright.h for copyright notice
and limitation
// of liability and disclaimer of warranty provisions.
#ifndef SYSTEM_H
#define SYSTEM_H
#include "copyright.h"
#include "utility.h"
#include "thread.h"
#include "scheduler.h"
#include "interrupt.h"
#include "stats.h"
#include "timer.h"
#include "synch.h"
// Initialization and cleanup routines
extern void Initialize(int argc, char **argv); // Initialization,
// called before anything else
extern void Cleanup();
// Cleanup, called when
// Nachos is done.
extern Thread *currentThread;
// the thread holding the CPU
extern Thread *threadToBeDestroyed;
// the thread that just finished
extern Scheduler *scheduler;
// the ready list
extern Interrupt *interrupt;
// interrupt status
extern Statistics *stats;
// performance metrics
extern Timer *timer;
// the hardware alarm clock
#ifdef USER_PROGRAM
#include "machine.h"
extern Machine* machine; // user program memory
and registers
#ifdef CHANGED
#include "console.h"
#include "bitmap.h"
#define MAX_SPACEID 100 // Maximum SpaceId can be allocated
#define MAX_OPENFILE 100 // Maximum File can
be opened
#define MAX_NAME_LN 50 // used for name length of thread
name
// and user program name
enum SpaceIdStatus {NotUse, InUse, FINISH};
class SpaceIdEntry { // Entry for SpaceId table,
for tracking
// the user program status and dependency
public:
int ParentId; // parent's
SpaceId
SpaceIdStatus status; // status
of the user program using
// this SpaceId
int exitcode; // exit status when
this user program exit
};
class OpenFileEntry { // Entry for FileId table,
for tracking
// openen file in user program
public:
int ownerId; // SpaceId of
the user program open this file
OpenFile *openFile; // OpenFile object manage
this opend file
};
extern SpaceIdEntry SpaceIdTable[MAX_SPACEID]; // SpaceId
Table
// SpaceId assigned
to user program is used as index entry
// of this table,
0 is reserved to the user program
// executing in
`main' thread
extern OpenFileEntry FileIdTable[MAX_OPENFILE]; // FileId Table
// OpenFileId assigned
to opened file is used as index
// entry of this
table. 0 is reserved to standard input,
// 1 is reserved
to standard output
extern Lock *SpaceIdLock; // lock used to access SpaceId
Table
extern Condition *SpaceIdCond; // condition variable
used for
// parent waiting for
its child finish
extern Semaphore *shellRead; // semaphore
used to synchronize
// read from the shell
console
extern Semaphore *shellWrite; // semaphore used
to synchronize
// write to the shell
console
extern Console *shellConsole; // console used by user
program
extern void ShellRead(int arg); // called when there is a
// character available from console for user to read
extern void ShellWrite(int arg); // called when
write a
// character to console is done
extern BitMap *pageMap; // manage physical memory usage,
each
// bit corresponding to a physical memory frame.
// bit is set when the memory frame is used, and
// bit is clear when the memory frame is free.
// Class defined to keep track of each physical page
class InvertedPageEntry
{
public:
int physicalPageId; // Physical Page id..
int ownerProcessId; // The process ID of the process owning
this page frame
AddrSpace *ownerAddrSpace ;
int virtualPageNum; // The Virtual page number of the frame
in the process's addressspace.
bool useBit; // Flag indicating if the frame is currently
in use.
bool dirtyBit; // Flag indicating if the frame was
modified.
};
class InvertedPageTable
{ public:
InvertedPageEntry *IPEntry; // Pointer to the inverted page
table entry.
int currentCurPos; // Current cursor position. We will start
searching from this position in the table to load a new page.
InvertedPageTable(int num=16)
{ IPEntry = new InvertedPageEntry[num];
currentCurPos = 0; };
};
extern InvertedPageTable *globalInvertedPageTable;
#endif // CHANGED
#endif // USER_PROGRAM
#ifdef FILESYS_NEEDED // FILESYS
or FILESYS_STUB
#include "filesys.h"
extern FileSystem *fileSystem;
#endif
#ifdef FILESYS
#include "synchdisk.h"
extern SynchDisk *synchDisk;
#endif
#ifdef NETWORK
#include "post.h"
extern PostOffice* postOffice;
#endif
#endif // SYSTEM_H
#ifdef CHANGED
// To copy the information from TLB to Global Inverted Page Table
-- to make sure that GIPT
// has correct information.
extern void copyTLBtoGIPT();
#endif
// threadtest.cc
// Simple test case for the threads
assignment.
//
// Create two threads, and have them
context switch
// back and forth between themselves
by calling Thread::Yield,
// to illustratethe inner workings
of the thread system.
//
// Copyright (c) 1992-1993 The Regents of the University of California.
// All rights reserved. See copyright.h for copyright notice
and limitation
// of liability and disclaimer of warranty provisions.
#include "copyright.h"
#include "system.h"
//----------------------------------------------------------------------
// SimpleThread
// Loop 5 times, yielding the CPU
to another ready thread
// each iteration.
//
// "which" is simply a number identifying
the thread, for debugging
// purposes.
//----------------------------------------------------------------------
void
SimpleThread(int which)
{
int num;
for (num = 0; num < 5; num++) {
printf("*** thread %d
looped %d times\n", which, num);
currentThread->Yield();
}
}
//----------------------------------------------------------------------
// 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 *t = new Thread("forked thread");
t->Fork(SimpleThread, 1);
SimpleThread(0);
}
// addrspace.cc
// Routines to manage address spaces (executing user programs).
//
// In order to run a user program, you must:
//
// 1. link with the -N -T 0 option
// 2. run coff2noff to convert the object file to Nachos
format
// (Nachos object code format is
essentially just a simpler
// version of the UNIX executable
object code format)
// 3. load the NOFF file into the Nachos file system
// (if you haven't implemented the
file system yet, you
// don't need to do this last step)
//
// Copyright (c) 1992-1993 The Regents of the University of California.
// All rights reserved. See copyright.h for copyright notice
and limitation
// of liability and disclaimer of warranty provisions.
#include "copyright.h"
#include "system.h"
#include "addrspace.h"
#include "noff.h"
#include <strings.h>
#include <stdlib.h>
//----------------------------------------------------------------------
// SwapHeader
// Do little endian to big endian conversion on the bytes
in the
// object file header, in case the file was generated on
a little
// endian machine, and we're now running on a big endian
machine.
//----------------------------------------------------------------------
static void
SwapHeader (NoffHeader *noffH)
{
noffH->noffMagic = WordToHost(noffH->noffMagic);
noffH->code.size = WordToHost(noffH->code.size);
noffH->code.virtualAddr = WordToHost(noffH->code.virtualAddr);
noffH->code.inFileAddr = WordToHost(noffH->code.inFileAddr);
noffH->initData.size = WordToHost(noffH->initData.size);
noffH->initData.virtualAddr = WordToHost(noffH->initData.virtualAddr);
noffH->initData.inFileAddr = WordToHost(noffH->initData.inFileAddr);
noffH->uninitData.size = WordToHost(noffH->uninitData.size);
noffH->uninitData.virtualAddr = WordToHost(noffH->uninitData.virtualAddr);
noffH->uninitData.inFileAddr = WordToHost(noffH->uninitData.inFileAddr);
}
//----------------------------------------------------------------------
// AddrSpace::AddrSpace
// Create an address space to run a user program.
// Load the program from a file "executable", and set everything
// up so that we can start executing user instructions.
//
// Assumes that the object code file is in NOFF format.
//
// First, set up the translation from program memory to physical
// memory. For now, this is really simple (1:1), since
we are
// only uniprogramming, and we have a single unsegmented
page table
//
// "executable" is the file containing the object code to
load into memory
//----------------------------------------------------------------------
AddrSpace::AddrSpace(OpenFile *executable)
{
NoffHeader noffH;
unsigned int i, size;
#ifdef CHANGED
int pageOffset, addrOffset; // Offset
of physical and virtual address
#endif
executable->ReadAt((char *)&noffH, sizeof(noffH),
0);
if ((noffH.noffMagic != NOFFMAGIC) &&
(WordToHost(noffH.noffMagic)
== NOFFMAGIC))
SwapHeader(&noffH);
ASSERT(noffH.noffMagic == NOFFMAGIC);
// 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);
size = numPages * PageSize;
#ifndef CHANGED
ASSERT(numPages <= NumPhysPages);
// check we're not trying
// to run anything too big --
// at least until we have
// virtual memory
DEBUG('a', "Initializing address space, num pages
%d, size %d\n",
numPages, size);
// first, set up the translation
pageTable = new TranslationEntry[numPages];
//#ifdef CHANGED
pageOffset = pageMap->Find(numPages);// check
pageMap to find
// a continuous free memory space
// for this user program
ASSERT(pageOffset>=0);
addrOffset = pageOffset*PageSize;
// caculate memory address
// oppset between physical and virtual address
DEBUG('o', "\nAllocate address space for user
program\n\t"
"<%s> in thread \"%s\"\n",
currentThread->userProgName, currentThread->getName());
DEBUG('o', "Physical address space, \n\t"
"num pages: %d, physical page [%d] <==> [%d]\n\n",
numPages, pageOffset, pageOffset+numPages-1);
//#endif
for (i = 0; i < numPages; i++) {
pageTable[i].virtualPage = i; // for now, virtual
page # = phys page #
//#ifndef CHANGED
pageTable[i].physicalPage = i;
//#endif
//#ifdef CHANGED
pageTable[i].physicalPage = i + pageOffset;
// different user
program use different physical memory frame
//#endif
pageTable[i].valid = TRUE;
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
}
#endif /* Made the code ineffective for Phase III */
/* processId = currentThread->SpaceId; // Assigning the SpaceId to the Address Space. */
strcpy(nameForSwapFile,"swap-");
char trailor[80];
TLBbackup = new TranslationEntry[TLBSize];
DEBUG('a',"Space id:%d:\n", currentThread->SpaceId);
lltostr(currentThread->SpaceId + 1,trailor);
fprintf(stdout,"I am here\n");
strcat(nameForSwapFile, trailor);
DEBUG('a', " Name of the swapFile :%s: Trailor:%s:\n", nameForSwapFile,trailor);
fileSystem->Create(nameForSwapFile,size);
swapSpace = fileSystem->Open(nameForSwapFile);
char *bufferForTransfer;
bufferForTransfer = new char[1000];
if (noffH.code.size > 0)
{
DEBUG('a', "Initializing
code segment, at 0x%x, size %d\n",
noffH.code.virtualAddr, noffH.code.size);
executable->ReadAt(bufferForTransfer,noffH.code.size,
noffH.code.inFileAddr);
swapSpace->WriteAt(bufferForTransfer,noffH.code.size,noffH.code.virtualAddr);
// Read code section into the virtual memory (swap File for the address
space).
}
if (noffH.initData.size > 0)
{
DEBUG('a', "Initializing
initData segment, at 0x%x, size %d\n",
noffH.initData.virtualAddr, noffH.initData.size);
executable->ReadAt(bufferForTransfer,noffH.initData.size,
noffH.initData.inFileAddr);
swapSpace->WriteAt(bufferForTransfer,noffH.initData.size,noffH.initData.virtualAddr);
// Read initData section into the virtual memory (swap File for the address
space).
}
// zero out the entire address space, to zero the unitialized data
segment
// and the stack segment
#ifndef CHANGED
//#ifndef CHANGED
bzero(machine->mainMemory, size); // moved to
system.cc
//#endif
//#ifdef CHANGED
bzero(&(machine->mainMemory[addrOffset]),
size);
//#endif
// then, copy in the code and data segments into memory
if (noffH.code.size > 0) {
DEBUG('a', "Initializing
code segment, at 0x%x, size %d\n",
noffH.code.virtualAddr, noffH.code.size);
//#ifndef CHANGED
executable->ReadAt(&(machine->mainMemory[noffH.code.virtualAddr]),
noffH.code.size, noffH.code.inFileAddr);
//#endif
//#ifdef CHANGED
executable->ReadAt(&(machine->
mainMemory[noffH.code.virtualAddr+addrOffset]),
noffH.code.size, noffH.code.inFileAddr);
// Read code section into different physical memory location.
//#endif
}
if (noffH.initData.size > 0) {
DEBUG('a', "Initializing
data segment, at 0x%x, size %d\n",
noffH.initData.virtualAddr, noffH.initData.size);
//#ifndef CHANGED
executable->ReadAt(&(machine->mainMemory[noffH.initData.virtualAddr]),
noffH.initData.size, noffH.initData.inFileAddr);
//#endif
//#ifdef CHANGED
executable->ReadAt(&(machine->
mainMemory[noffH.initData.virtualAddr+addrOffset]),
noffH.initData.size, noffH.initData.inFileAddr);
// Read data section into different physical memory location.
//#endif
}
#endif /* Making the code ineffective for Phase III
*/
//ASSERT (machine->tlb == NULL);
fprintf(stdout,"Out of constuctor ... \n");
}
//----------------------------------------------------------------------
// AddrSpace::~AddrSpace
// Dealloate an address space. Nothing for now!
//----------------------------------------------------------------------
AddrSpace::~AddrSpace()
{
// Making the following code in-effective for PhaseIII
//#ifdef CHANGED
#ifndef CHANGED
for (int i=0; i<numPages; i++)
pageMap->Clear(pageTable[i].physicalPage);
// free physical memory
used by this user program
DEBUG('o', "\nDe-Allocate address space for user
program\n\t"
"<%s> in thread \"%s\"\n",
currentThread->userProgName, currentThread->getName());
DEBUG('o', "Free physical address space, \n\t"
"num pages: %d, physical page [%d] <==> [%d]\n\n",
numPages,pageTable[0].physicalPage,pageTable[numPages-1].physicalPage);
//#endif
delete pageTable;
#endif
// End of commening of the code.
// Code start for Phase III
#ifdef CHANGED
DEBUG('a',"The address Space for process : %d is being deleted", currentThread->SpaceId);
for(int i=0; i < TLBSize ; i++)
{ int j;
if (machine->tlb[i].valid)
{
j = machine->tlb[i].physicalPage;
DEBUG('a',"Physical page:%d is being indicated to re-used",j);
globalInvertedPageTable->IPEntry[j].ownerProcessId
= 0;
globalInvertedPageTable->IPEntry[j].ownerAddrSpace
= NULL;
globalInvertedPageTable->IPEntry[j].virtualPageNum
= 0;
globalInvertedPageTable->IPEntry[j].useBit
= FALSE;
globalInvertedPageTable->IPEntry[j].dirtyBit
= FALSE;
}
}
if (!fileSystem->Remove(nameForSwapFile))
DEBUG ('a',"unable to remove the File:%s
from the file system\n", nameForSwapFile);
delete [] TLBbackup;
#endif
}
//----------------------------------------------------------------------
// AddrSpace::InitRegisters
// Set the initial values for the user-level register set.
//
// We write these directly into the "machine" registers,
so
// that we can immediately jump to user code. Note
that these
// will be saved/restored into the currentThread->userRegisters
// when this thread is context switched out.
//----------------------------------------------------------------------
void
AddrSpace::InitRegisters()
{
int i;
for (i = 0; i < NumTotalRegs; i++)
machine->WriteRegister(i, 0);
// Initial program counter -- must be location
of "Start"
machine->WriteRegister(PCReg, 0);
// Need to also tell MIPS where next instruction
is, because
// of branch delay possibility
machine->WriteRegister(NextPCReg, 4);
// Set the stack register to the end of the address
space, where we
// allocated the stack; but subtract off a bit, to
make sure we don't
// accidentally reference off the end!
machine->WriteRegister(StackReg, numPages *
PageSize - 16);
DEBUG('a', "Initializing stack register to %d\n",
numPages * PageSize - 16);
}
//----------------------------------------------------------------------
// AddrSpace::SaveState
// On a context switch, save any machine state, specific
// to this address space, that needs saving.
//
// For now, nothing!
//----------------------------------------------------------------------
void AddrSpace::SaveState()
{
copyTLBtoGIPT();
/*
for(int i = 0; i < TLBSize ; i++)
{
TLBbackup[i].virtualPage = machine->tlb[i].virtualPage
;
TLBbackup[i].physicalPage = machine->tlb[i].physicalPage;
TLBbackup[i].valid = machine->tlb[i].valid;
TLBbackup[i].readOnly = machine->tlb[i].readOnly
;
TLBbackup[i].use = machine->tlb[i].use;
TLBbackup[i].dirty = machine->tlb[i].dirty;
}
*/
}
//----------------------------------------------------------------------
// AddrSpace::RestoreState
// On a context switch, restore the machine state so that
// this address space can run.
//
// For now, tell the machine where
to find the page table.
//----------------------------------------------------------------------
void AddrSpace::RestoreState()
{
/* machine->pageTable = pageTable;
machine->pageTableSize = numPages;
*/
for(int i = 0; i < TLBSize ; i++)
{
DEBUG('a',"In restore state, i = %d\n", i);
DEBUG('a', "machine:%d:\n", machine);
DEBUG('a', "machine->tlb[i]:%d:\n", machine->tlb[i]);
DEBUG('a',"TLBbackup:%d:\n", TLBbackup[i]);
machine->tlb[i].virtualPage = TLBbackup[i].virtualPage;
machine->tlb[i].physicalPage = TLBbackup[i].physicalPage;
machine->tlb[i].valid = TLBbackup[i].valid;
machine->tlb[i].readOnly = TLBbackup[i].readOnly;
machine->tlb[i].use = TLBbackup[i].use;
machine->tlb[i].dirty = TLBbackup[i].dirty;
}
}
// addrspace.h
// Data structures to keep track
of executing user programs
// (address spaces).
//
// For now, we don't keep any information
about address spaces.
// The user level CPU state is saved
and restored in the thread
// executing the user program (see
thread.h).
//
// Copyright (c) 1992-1993 The Regents of the University of California.
// All rights reserved. See copyright.h for copyright notice
and limitation
// of liability and disclaimer of warranty provisions.
#ifndef ADDRSPACE_H
#define ADDRSPACE_H
#include "copyright.h"
#include "filesys.h"
#define UserStackSize 1024 // increase this as necessary!
class AddrSpace {
public:
AddrSpace(OpenFile *executable);
// Create an address space,
// initializing it with the program
// stored in the file "executable"
~AddrSpace();
// De-allocate an address space
void InitRegisters();
// Initialize user-level CPU registers,
// before jumping to user code
void SaveState();
// Save/restore address space-specific
void RestoreState();
// info on a context switch
private:
TranslationEntry *pageTable;
// Assume linear page table translation
// for now!
unsigned int numPages;
// Number of pages in the virtual
// address space
TranslationEntry *TLBbackup; // TLB
backup to be saved and loaded while context switch.
public:
char nameForSwapFile[80];
OpenFile *swapSpace;
/* SpaceId processId;
// Process Id of the process using the address space. */
};
#endif // ADDRSPACE_H
~
~
~
~
[taken from /userprogexception.cc -- last function on file]
//--------------------------------------------------------------------------
// checkOpenFile
//
// Check for unclosed files. Close them if there are any
and update the
// FileID table.
//--------------------------------------------------------------------------
void
checkOpenFile()
{
OpenFile *closedFile;
DEBUG('e', "Check for unclosed files.\n");
for (int i=2; i<MAX_OPENFILE; i++)
if ((FileIdTable[i].openFile != NULL) &&
(FileIdTable[i].ownerId
== currentThread->SpaceId)) {
closedFile = FileIdTable[i].openFile;
FileIdTable[i].openFile
= NULL;
delete closedFile;
DEBUG('e', "File (OpenFileId:%d)
has been closed.\n",i);
}
}
void checkMemory()
{
int i;
for (i=0; i<NumPhysPages ; i++)
{
DEBUG('e', "Process: %d is being exited.\n",
currentThread->SpaceId);
if (globalInvertedPageTable->IPEntry[i].ownerProcessId
= currentThread->SpaceId)
{
globalInvertedPageTable->IPEntry[i].useBit
= FALSE;
DEBUG('e',
"Physical Page:%d has been set to NOT IN USE for process %d.\n",i,currentThread->SpaceId);
}
}
}
void SyscallPageFaultHandle()
{
int i;
int badVaddr = machine->ReadRegister(BadVAddrReg);
int badVPageNum = badVaddr / PageSize;
int startAddrToRead = badVPageNum * PageSize;
AddrSpace *currentAddrSpace = currentThread->space;
char swapBuffer[PageSize];
copyTLBtoGIPT();
DEBUG('a' , "The value returned is %d", currentAddrSpace->swapSpace->ReadAt(swapBuffer,
PageSize,
startAddrToRead));
DEBUG('a', "curr-addr:%d, swapSpace:%d, swap-file name:%s
\n", currentAddrSpace, currentAddrSpace->swapSpace,
currentAddrSpace->nameForSwapFile);
if (currentAddrSpace->swapSpace->ReadAt(swapBuffer, PageSize,
startAddrToRead) > 0)
{
DEBUG('e', "User program \"%s\"
abort due to the "
"Page Fault exception.\n",currentThread->userProgName);
ASSERT(FALSE);
}
for(i=globalInvertedPageTable->currentCurPos ; ; i
= (i+1) % NumPhysPages )
{
if(globalInvertedPageTable->IPEntry[i].useBit
== FALSE)
{
int startPhysAddr = i * PageSize;
if(globalInvertedPageTable->IPEntry[i].dirtyBit
== TRUE )
{
int VAddrToBeWritten
= globalInvertedPageTable->IPEntry[i].virtualPageNum * PageSize;
OpenFile *prevPageSwapFile
= globalInvertedPageTable->IPEntry[i].ownerAddrSpace->swapSpace;
prevPageSwapFile->WriteAt(&(machine->mainMemory[startPhysAddr]), PageSize, VAddrToBeWritten);
}
strcpy( & (machine->mainMemory[startPhysAddr]),
swapBuffer);
globalInvertedPageTable->IPEntry[i].dirtyBit
= FALSE;
globalInvertedPageTable->IPEntry[i].ownerProcessId
= currentThread->SpaceId;
globalInvertedPageTable->IPEntry[i].ownerAddrSpace
= currentAddrSpace;
globalInvertedPageTable->IPEntry[i].virtualPageNum
= badVPageNum;
break;
}
}
}
#endif
Tuesday, 18 April, 2000
We met briefly after tonight's test to discuss the status of Phase 4
(and potential
meeting times this weekend).
Wednesday, 19 April, 2000
This morning I sent this message to all group members:
Hello, all.
I would like to get some feedback on each of the four phases,
so I can throw together a few PowerPoint slides for our
presentation. Please don't lose any sleep straining
your
brain for ideas. For each phase, just list something that
we
could have improved on, had we done it over again. For example:
Phase 1: I believed port designations were ideal, although we
ended up using time-release semaphores. As a result, I spent
too much time designing port designations.
Phase 2: I was not able to write any of my own assigned code,
and as a result, the whole group suffered.
Phase 3: I was pleasantly surprised with the output of this
phase -- none of us expected much, but it all pulled through.
Phase 4: because of time constraints, we were late getting
the deisgn ready. Had I worked on Phase 4's design while
we
struggled with Phase 3 (like I said I was going to), things
might had turned out differently.
Bindu: You mentioned a couple of weeks ago that you had a
textbook that discussed UNIX file system function calls.
Would
this be useful for Phase 4? If so, would you mind bringing
this texbook to our meeting on Thursday ?
I have a book that essentially assists the reader on hot-wiring
Windows 95/WinNT for the same tasks that we did for NACHOS (the
book is called "Advanced Windows Programing" by Jeffrey Richter).
I'll bring this book to class tomorrow evening. And a fair
warning: any ideas I get for the file system implementation for
Phase 4 will be derived from this book (in other words, take my
suggestions lightly).
See all of you tomorrow night.
John Joachim
Thursday, 20 April, 2000
We gave our oral presentation today (see the Epilogue for details on this)
// openfile.h
//
#ifndef OPENFILE_H
#define OPENFILE_H
#include "copyright.h"
#include "utility.h"
#ifdef FILESYS_STUB
// Temporarily implement calls to
// Nachos file system as calls to UNIX!
// See definitions listed under #else
class OpenFile {
public:
OpenFile(int f) { file = f; currentOffset =
0; } // open the file
~OpenFile() { Close(file); }
// close the file
int ReadAt(char *into, int numBytes, int position)
{
DEBUG('f',"inside read at inside stub");
Lseek(file, position, 0);
return ReadPartial(file, into, numBytes);
}
int WriteAt(char *from, int numBytes, int position)
{
Lseek(file, position, 0);
WriteFile(file, from, numBytes);
return numBytes;
}
int Read(char *into, int numBytes) {
int numRead = ReadAt(into, numBytes, currentOffset);
currentOffset += numRead;
return numRead;
}
int Write(char *from, int numBytes) {
int numWritten = WriteAt(from, numBytes, currentOffset);
currentOffset += numWritten;
return numWritten;
}
int Length() { Lseek(file, 0, 2); return Tell(file); }
private:
int file;
int currentOffset;
};
#else // FILESYS
class FileHeader;
class OpenFile {
public:
OpenFile(int sector);
// Open a file whose header is located
// at "sector" on the disk
~OpenFile();
// Close the file
void Seek(int position);
// Set the position from which to
// start reading/writing -- UNIX lseek
int Read(char *into, int numBytes); // Read/write
bytes from the file,
// starting at the implicit position.
// Return the # actually read/written,
// and increment position in file.
int Write(char *from, int numBytes);
int ReadAt(char *into, int numBytes, int position);
// Read/write bytes from the file,
// bypassing the implicit position.
int WriteAt(char *from, int numBytes, int position);
int Length();
// Return the number of bytes in the
// file (this interface is simpler
// than the UNIX idiom -- lseek to
// end of file, tell, lseek back
char *name;
private:
FileHeader *hdr;
// Header for this file
int seekPosition;
// Current position within the file
int fileSector;
};
#endif // FILESYS
#endif // OPENFILE_H
========================================================================================================================================================
// openfile.cc
//----------------------------------------------------------------------
// OpenFile::OpenFile
// Open a Nachos file for reading
and writing. Bring the file header
// into memory while the file is
open.
//
// "sector" -- the location on disk
of the file header for this file
//----------------------------------------------------------------------
OpenFile::OpenFile(int sector)
{
hdr = new FileHeader;
// hdr->FetchFrom(sector);
seekPosition = 0;
fileSector = sector;
}
//----------------------------------------------------------------------
// OpenFile::~OpenFile
// Close a Nachos file, de-allocating
any in-memory data structures.
//----------------------------------------------------------------------
OpenFile::~OpenFile()
{
delete hdr;
#ifdef CHANGED
int i;
for(i = 0; i < MAX_FILES_GLOBAL; i++)
{
if( strcmp(fileTable[i].name,name)
== 0)
{
if (( -- fileTable[i].openCount == 0) && ( fileTable[i].deleteBit
== TRUE))
{
fileSystem->Remove( fileTable[i].name);
fileTable[i].name = NULL;
fileTable[i].fileLock = NULL;
fileTable[i].deleteBit = FALSE;
}
break;
}
}
delete name;
#endif
}
//----------------------------------------------------------------------
// OpenFile::Seek
// Change the current location within
the open file -- the point at
// which the next Read or Write will
start from.
//
// "position" -- the location within
the file for the next Read/Write
//----------------------------------------------------------------------
void
OpenFile::Seek(int position)
{
seekPosition = position;
}
//----------------------------------------------------------------------
// OpenFile::Read/Write
// Read/write a portion of a file,
starting from seekPosition.
// Return the number of bytes actually
written or read, and as a
// side effect, increment the current
position within the file.
//
// Implemented using the more primitive
ReadAt/WriteAt.
//
// "into" -- the buffer to contain
the data to be read from disk
// "from" -- the buffer containing
the data to be written to disk
// "numBytes" -- the number of bytes
to transfer
//----------------------------------------------------------------------
int
OpenFile::Read(char *into, int numBytes)
{
DEBUG('f',"The value of into:%s: and its length is
%d before calling Read\n", into, strlen(into));
int result = ReadAt(into, numBytes, seekPosition);
DEBUG('f',"The value of the result %d \n",result);
seekPosition += result;
DEBUG('f',"Leaving the function Read\n");
return result;
}
int
OpenFile::Write(char *into, int numBytes)
{
DEBUG('f',"In the Write function ");
int result = WriteAt(into, numBytes, seekPosition);
seekPosition += result;
return result;
}
//----------------------------------------------------------------------
// OpenFile::ReadAt/WriteAt
// Read/write a portion of a file,
starting at "position".
// Return the number of bytes actually
written or read, but has
// no side effects (except that Write
modifies the file, of course).
//
// There is no guarantee the request
starts or ends on an even disk sector
// boundary; however the disk only
knows how to read/write a whole disk
// sector at a time. Thus:
//
// For ReadAt:
// We read in all
of the full or partial sectors that are part of the
// request, but
we only copy the part we are interested in.
// For WriteAt:
// We must first
read in any sectors that will be partially written,
// so that we don't
overwrite the unmodified portion. We then copy
// in the data
that will be modified, and write back all the full
// or partial sectors
that are part of the request.
//
// "into" -- the buffer to contain
the data to be read from disk
// "from" -- the buffer containing
the data to be written to disk
// "numBytes" -- the number of bytes
to transfer
// "position" -- the offset within
the file of the first byte to be
//
read/written
//----------------------------------------------------------------------
int
OpenFile::ReadAt(char *into, int numBytes, int position)
{
int fileLength = hdr->FileLength();
int i, firstSector, lastSector, numSectors;
char *buf;
DEBUG('f',"In the ReadAt function\n");
#ifdef CHANGED
hdr->FetchFrom(fileSector);
#endif
if ((numBytes <= 0) || (position >= fileLength))
return 0;
// check request
if ((position + numBytes) > fileLength)
numBytes = fileLength
- position;
DEBUG('f', "Reading %d bytes at %d, from file
of length %d.\n",
numBytes, position, fileLength);
firstSector = divRoundDown(position, SectorSize);
lastSector = divRoundDown(position + numBytes
- 1, SectorSize);
numSectors = 1 + lastSector - firstSector;
// read in all the full and partial sectors that
we need
buf = new char[numSectors * SectorSize];
for (i = firstSector; i <= lastSector; i++)
synchDisk->ReadSector(hdr->ByteToSector(i
* SectorSize),
&buf[(i - firstSector) * SectorSize]);
DEBUG('f',"After Readsector
in function ReadAt\n");
// copy the part we want
bcopy(&buf[position - (firstSector * SectorSize)],
into, numBytes);
delete [] buf;
DEBUG('f',"Leaving the function Readat\n");
return numBytes;
}
int
OpenFile::WriteAt(char *from, int numBytes, int position)
{
DEBUG('f',"In the WriteAt function. \n\n");
int fileLength = hdr->FileLength();
int i, firstSector, lastSector, numSectors;
bool firstAligned, lastAligned;
char *buf;
#ifdef CHANGED
int j, numFileRow;
int newFileLength = position + numBytes;
int numSectorsAlloc = divRoundUp(fileLength, SectorSize);
int numSectorsNeeded = divRoundUp(newFileLength, SectorSize);
int numSectorsToBeAlloc = numSectorsNeeded -
numSectorsAlloc;
DEBUG('f',"In the Starting of Changed \n");
for(numFileRow=0; numFileRow < MAX_FILES_GLOBAL;
numFileRow++)
if ((fileTable[numFileRow].name != NULL)
&& (strcmp(name,fileTable[numFileRow].name) == 0))
break;
ASSERT(numFileRow < MAX_FILES_GLOBAL);
fileTable[numFileRow].fileLock->Acquire();
hdr->FetchFrom(fileSector);
DEBUG('f',"After fetch from");
if (numSectorsToBeAlloc > 0)
{
DEBUG ('f',"In the IF condition.\n");
BitMap *freeMap = new BitMap(NumSectors);
freeMapFileLock->Acquire();
DEBUG('f', "After getting
the lock on the free Map\n");
DEBUG('f',"fileSystem:%d:
freeMapFile:%d:\n", fileSystem, fileSystem->freeMapFile);
freeMap->FetchFrom(fileSystem->freeMapFile);
DEBUG('f',"Before ASSERT\n");
ASSERT(freeMap->NumClear()
>= numSectorsToBeAlloc);
DEBUG('f',"After ASSERT\n");
for(j=numSectorsAlloc; j <
numSectorsToBeAlloc ; j++)
hdr->dataSectors[j]
= freeMap->Find();
DEBUG('f',"After allocating
the new datasectors\n");
freeMap->WriteBack(fileSystem->freeMapFile);
delete freeMap;
freeMapFileLock->Release();
DEBUG('f',"After releasing lock\n");
hdr->WriteBack(fileSector);
}
fileTable[numFileRow].fileLock->Release();
#endif
DEBUG('f',"Out of the CHANGED\n");
#ifndef CHANGED
if ((numBytes <= 0) || (position >= fileLength))
return 0;
// check request
if ((position + numBytes) > fileLength)
numBytes = fileLength
- position;
#endif
DEBUG('f', "Writing %d bytes at %d, from file
of length %d.\n",
numBytes, position, fileLength);
firstSector = divRoundDown(position, SectorSize);
lastSector = divRoundDown(position + numBytes
- 1, SectorSize);
numSectors = 1 + lastSector - firstSector;
DEBUG('f',"number of sectors :%d:Sector:%d:bufsize:%d:\n",
numSectors, SectorSize,(numSectors * SectorSize));
buf = new char[numSectors * SectorSize];
firstAligned = (position == (firstSector * SectorSize));
lastAligned = ((position + numBytes) == ((lastSector + 1) * SectorSize));
DEBUG('f',"The value of firstAligned:%d:\n",
firstAligned);
// read in first and last sector, if they are to be partially modified
if (!firstAligned)
{
DEBUG('f',"Calling ReadAt
from WriteAt 1\n");
ReadAt(buf, SectorSize,
firstSector * SectorSize);
}
if (!lastAligned && ((firstSector !=
lastSector) || firstAligned))
{
DEBUG('f',"Calling
ReadAt from WriteAt 2\n");
ReadAt(&buf[(lastSector
- firstSector) * SectorSize],
SectorSize, lastSector * SectorSize);
}
// copy in the bytes we want to change
bcopy(from, &buf[position - (firstSector
* SectorSize)], numBytes);
// write modified sectors back
for (i = firstSector; i <= lastSector; i++)
synchDisk->WriteSector(hdr->ByteToSector(i
* SectorSize),
&buf[(i - firstSector) * SectorSize]);
delete [] buf;
return numBytes;
}
//----------------------------------------------------------------------
// OpenFile::Length
// Return the number of bytes in
the file.
//----------------------------------------------------------------------
int
OpenFile::Length()
{
return hdr->FileLength();
}
=================================================================
=================================================================
// fstest.cc
// Simple test routines for the file
system.
//
// We implement:
// Copy -- copy
a file from UNIX to Nachos
// Print -- cat
the contents of a Nachos file
// Perftest --
a stress test for the Nachos file system
//
read and write a really large file in tiny chunks
//
(won't work on baseline system!)
//
// Copyright (c) 1992-1993 The Regents of the University of California.
// All rights reserved. See copyright.h for copyright notice
and limitation
// of liability and disclaimer of warranty provisions.
#include "copyright.h"
#include "utility.h"
#include "filesys.h"
#include "system.h"
#include "thread.h"
#include "disk.h"
#include "stats.h"
#define TransferSize 10 // make it small, just to be difficult
//----------------------------------------------------------------------
// Copy
// Copy the contents of the UNIX
file "from" to the Nachos file "to"
//----------------------------------------------------------------------
void
Copy(char *from, char *to)
{
FILE *fp;
OpenFile* openFile;
int amountRead, fileLength;
char *buffer;
// Open UNIX file
if ((fp = fopen(from, "r")) == NULL) {
printf("Copy: couldn't
open input file %s\n", from);
return;
}
// Figure out length of UNIX file
fseek(fp, 0, 2);
fileLength = ftell(fp);
fseek(fp, 0, 0);
// Create a Nachos file of the same length
DEBUG('f', "Copying file %s, size %d, to file
%s\n", from, fileLength, to);
// if (!fileSystem->Create(to, fileLength))
{ // Create Nachos file
if (!fileSystem->Create(to,
100)) { // Create Nachos file
printf("Copy: couldn't
create output file %s\n", to);
fclose(fp);
return;
}
openFile = fileSystem->Open(to);
ASSERT(openFile != NULL);
// Copy the data in TransferSize chunks
buffer = new char[TransferSize];
while ((amountRead = fread(buffer, sizeof(char),
TransferSize, fp)) > 0)
openFile->Write(buffer,
amountRead);
delete [] buffer;
// Close the UNIX and the Nachos files
delete openFile;
fclose(fp);
printf("Leaving the function COPY \n");
}
//----------------------------------------------------------------------
// Print
// Print the contents of the Nachos
file "name".
//----------------------------------------------------------------------
void
Print(char *name)
{
OpenFile *openFile;
int i, amountRead;
char *buffer;
if ((openFile = fileSystem->Open(name)) == NULL)
{
printf("Print: unable
to open file %s\n", name);
return;
}
buffer = new char[TransferSize];
while ((amountRead = openFile->Read(buffer,
TransferSize)) > 0)
for (i = 0; i < amountRead;
i++)
printf("%c", buffer[i]);
delete [] buffer;
delete openFile;
// close the Nachos file
return;
}
void FunctionOne(int x)
{
int i=0;
OpenFile * newOpenFile = fileSystem->Open("small");
printf(" Printing the file : %s by the thread %d for the
%d time.\n",newOpenFile->name, x,++i);
Print(newOpenFile->name);
currentThread->Yield();
printf("Removing the file : %s by the thread %d
\n",newOpenFile->name,x);
fileSystem->Remove("small");
printf(" Thread %d about to finish\n",x);
}
void FunctionThree(int x);
void FunctionTwo(int x)
{
int i=0;
OpenFile *newOpenFile = fileSystem->Open("small");
Thread *t3 = new Thread("Three");
t3->Fork(FunctionThree, 3);
printf("running the thread %d starting with the function : FunctionTwo\n\n", x);
printf("Printing the file: %s by the thread %d for
the %d time. \n", newOpenFile->name, x, ++i);
Print(newOpenFile->name);
currentThread->Yield();
printf("Just before the %d READ\n", i+1);
printf("Printing the file: %s by the thread %d for
the %d time. \n", newOpenFile->name, x, ++i);
Print(newOpenFile->name);
currentThread->Yield();
printf("Just before the %d READ\n", i+1);
printf("Printing the file: %s by the thread %d for
the %d time. \n", newOpenFile->name, x, ++i);
Print(newOpenFile->name);
currentThread->Yield();
printf("Just before the %d READ\n", i+1);
printf("Printing the file: %s by the thread %d for
the %d time. \n", newOpenFile->name, x, ++i);
Print(newOpenFile->name);
currentThread->Yield();
}
void FunctionThree(int x)
{
int i=0,position;
char *writeString = new char(100);
printf("running the thread %d starting with the function :
FunctionThree\n\n", x);
OpenFile *newOpenFile = fileSystem->Open("small");
position = newOpenFile->Length();
newOpenFile->Seek(1);
printf("Just before the %d write\n", i+1);
sprintf(writeString," Writing by thread time\n" );
newOpenFile->Write(writeString, strlen(writeString));
Print("small");
currentThread->Yield();
printf("Just before the %d write\n", i+1);
sprintf(writeString," Writing by thread %d into the File for
the %d time\n", x, ++i);
newOpenFile->Write(writeString, strlen(writeString));
currentThread->Yield();
printf("Just before the %d write\n", i+1);
sprintf(writeString," Writing by thread %d into the File for
the %d time\n", x, ++i);
newOpenFile->Write(writeString, strlen(writeString));
currentThread->Yield();
printf("Just before the %d write\n", i+1);
sprintf(writeString," Writing by thread %d into the File for
the %d time\n", x, ++i);
newOpenFile->Write(writeString, strlen(writeString));
currentThread->Yield();
}
void SynchronizationTest()
{
// Thread *t1 = new Thread("one");
// Thread *t2 = new Thread("two");
// t1->Fork(FunctionOne, 1);
// t2->Fork(FunctionTwo, 2);
OpenFile *newFile = fileSystem->Open("small");
printf("Printing the file before modifying.\n");
Print("small");
newFile->Write("Hello ! Welcome to Nachos", 20);
printf("Printing the file after modifying.\n");
Print("small");
return;
}
//----------------------------------------------------------------------
// PerformanceTest
// Stress the Nachos file system
by creating a large file, writing
// it out a bit at a time, reading
it back a bit at a time, and then
// deleting the file.
//
// Implemented as three separate
routines:
// FileWrite -- write
the file
// FileRead -- read the
file
// PerformanceTest --
overall control, and print out performance #'s
//----------------------------------------------------------------------
#define FileName "TestFile"
#define Contents "1234567890"
#define ContentSize strlen(Contents)
#define FileSize ((int)(ContentSize
* 5000))
static void
FileWrite()
{
OpenFile *openFile;
int i, numBytes;
printf("Sequential write of %d byte file, in
%d byte chunks\n",
FileSize, ContentSize);
if (!fileSystem->Create(FileName, 0)) {
printf("Perf test: can't create
%s\n", FileName);
return;
}
openFile = fileSystem->Open(FileName);
if (openFile == NULL) {
printf("Perf test: unable
to open %s\n", FileName);
return;
}
for (i = 0; i < FileSize; i += ContentSize)
{
numBytes = openFile->Write(Contents,
ContentSize);
if (numBytes < 10)
{
printf("Perf test: unable to write %s\n", FileName);
delete openFile;
return;
}
}
delete openFile; // close
file
}
static void
FileRead()
{
OpenFile *openFile;
char *buffer = new char[ContentSize];
int i, numBytes;
printf("Sequential read of %d byte file, in %d
byte chunks\n",
FileSize, ContentSize);
if ((openFile = fileSystem->Open(FileName)) ==
NULL) {
printf("Perf test: unable
to open file %s\n", FileName);
delete [] buffer;
return;
}
for (i = 0; i < FileSize; i += ContentSize)
{
numBytes = openFile->Read(buffer,
ContentSize);
if ((numBytes < 10)
|| strncmp(buffer, Contents, ContentSize)) {
printf("Perf test: unable to read %s\n", FileName);
delete openFile;
delete [] buffer;
return;
}
}
delete [] buffer;
delete openFile; // close
file
}
void
PerformanceTest()
{
printf("Starting file system performance test:\n");
stats->Print();
FileWrite();
FileRead();
if (!fileSystem->Remove(FileName)) {
printf("Perf test: unable to remove
%s\n", FileName);
return;
}
stats->Print();
}
============================================================
============================================================
// filesys.h
// Data structures to represent the
Nachos file system.
//
// A file system is a set of files
stored on disk, organized
// into directories. Operations
on the file system have to
// do with "naming" -- creating,
opening, and deleting files,
// given a textual file name.
Operations on an individual
// "open" file (read, write, close)
are to be found in the OpenFile
// class (openfile.h).
//
// We define two separate implementations
of the file system.
// The "STUB" version just re-defines
the Nachos file system
// operations as operations on the
native UNIX file system on the machine
// running the Nachos simulation.
This is provided in case the
// multiprogramming and virtual memory
assignments (which make use
// of the file system) are done before
the file system assignment.
//
// The other version is a "real"
file system, built on top of
// a disk simulator. The disk
is simulated using the native UNIX
// file system (in a file named "DISK").
//
// In the "real" implementation,
there are two key data structures used
// in the file system. There
is a single "root" directory, listing
// all of the files in the file system;
unlike UNIX, the baseline
// system does not provide a hierarchical
directory structure.
// In addition, there is a bitmap
for allocating
// disk sectors. Both the root
directory and the bitmap are themselves
// stored as files in the Nachos
file system -- this causes an interesting
// bootstrap problem when the simulated
disk is initialized.
//
// Copyright (c) 1992-1993 The Regents of the University of California.
// All rights reserved. See copyright.h for copyright notice
and limitation
// of liability and disclaimer of warranty provisions.
#ifndef FS_H
#define FS_H
#include "copyright.h"
#include "openfile.h"
#ifdef FILESYS_STUB
// Temporarily implement file system calls as
// calls to UNIX, until the real file system
// implementation is available
class FileSystem {
public:
FileSystem(bool format) {}
bool Create(char *name, int initialSize) {
int fileDescriptor =
OpenForWrite(name);
if (fileDescriptor ==
-1) return FALSE;
Close(fileDescriptor);
return TRUE;
}
OpenFile* Open(char *name) {
int fileDescriptor
= OpenForReadWrite(name, FALSE);
if (fileDescriptor
== -1) return NULL;
return new
OpenFile(fileDescriptor);
}
bool Remove(char *name) { return Unlink(name) == 0; }
};
#else // FILESYS
class FileSystem {
public:
FileSystem(bool format);
// Initialize the file system.
// Must be called *after* "synchDisk"
// has been initialized.
// If "format", there is nothing on
// the disk, so initialize the directory
// and the bitmap of free blocks.
bool Create(char *name, int initialSize);
// Create a file (UNIX creat)
OpenFile* Open(char *name); // Open a file (UNIX open)
bool Remove(char *name); // Delete a file (UNIX unlink)
void List(); // List all the files in the file system
void Print(); // List all the files and their contents
OpenFile* freeMapFile;
// Bit map of free disk blocks,
// represented as a file
private:
OpenFile* directoryFile;
// "Root" directory -- list of
// file names, represented as a file
};
#endif // FILESYS
#endif // FS_H
=============================================================
=============================================================
// filesys.h
//
#ifndef FS_H
#define FS_H
#include "copyright.h"
#include "openfile.h"
#ifdef FILESYS_STUB
// Temporarily implement file system calls as
// calls to UNIX, until the real file system
// implementation is available
class FileSystem {
public:
FileSystem(bool format) {}
bool Create(char *name, int initialSize) {
int fileDescriptor =
OpenForWrite(name);
if (fileDescriptor ==
-1) return FALSE;
Close(fileDescriptor);
return TRUE;
}
OpenFile* Open(char *name) {
int fileDescriptor
= OpenForReadWrite(name, FALSE);
if (fileDescriptor
== -1) return NULL;
return new
OpenFile(fileDescriptor);
}
bool Remove(char *name) { return Unlink(name) == 0; }
};
#else // FILESYS
class FileSystem {
public:
FileSystem(bool format);
// Initialize the file system.
// Must be called *after* "synchDisk"
// has been initialized.
// If "format", there is nothing on
// the disk, so initialize the directory
// and the bitmap of free blocks.
bool Create(char *name, int initialSize);
// Create a file (UNIX creat)
OpenFile* Open(char *name); // Open a file (UNIX open)
bool Remove(char *name); // Delete a file (UNIX unlink)
void List(); // List all the files in the file system
void Print(); // List all the files and their contents
OpenFile* freeMapFile;
// Bit map of free disk blocks,
// represented as a file
private:
OpenFile* directoryFile;
// "Root" directory -- list of
// file names, represented as a file
};
#endif // FILESYS
#endif // FS_H
Saturday, 20 April, 2000
This morning we had plans to finish up Phase 4 by testing the thread synchronization from Phase 2 with the file system implementation of Phase 4. Well, it worked, but a few critical design flaws affecting part 2.
Tuesday, 23 April, 2000
Last day of class tonight, apparently. We have resolved to take full advantage of the three "slack days" remaining for this project, since we have not yet worked out the file system implementation.
We met for about two hours tonight,and the new design is completed:
Part 1 :
Synchronization and late deletion :
---------------------------------
Command Line for testing : nachos -f -t test/small small
Verifying the results :
We have put in
a lot of printf statements to illustrate the run-time environment of nachos.
Whenever a openfile is deleted we print the opencount and
when the file is removed by a process we print the same information . Also
information is printed out when the file is actually deleted from the file
system.
Test Case :
We create a new
file " small" by copying the physical file small from the physical directory
test . Once the file has been created with some intial contents we spawn
two threads t1 and t2 .Thread t1 tries to write some more while thread
t2 tries to read the same file .Nachos ensures synchronization between
reads and writes by various threads .
Once thread t1 is done with its processing it deletes the file. Only after that does the thread read the file the second time and print it on the screen . Nachos ensures that the file does not get deleted while it is still being used by atleast one thread.
printf statements have been included inside the code to illustrate the test case.
NOTE : Since we were using threads for synchronization we
have hardcoded the name of the file "small".
Part 2 :
Supporting Extending of the File Beyond 4K using Indirect
Datasectors:
----------------------------------------------------------------------
Command Line for testing : nachos -f -cp test/filename filename
TestCase:
We have created a very big file in
the "test" directory for the purpose. The name of the file is "large".
One can test it by using the command line "nachos
-f -cp test/large large". We have the structure of the fileheader to include
one indirect datasector pointing to a sector containing another fileheader.
This will enable to put in 29 direct datasetcors and 1indirect datasector.
The one indirect datasector inturn can point to one more indirect datasector
and so oon.
We are copying the file large from the physical file
'test/large' and then reading it out and then printing it out. This verifies
that the filesystem implemented supports large files.
Extra Credit:
Dynamic allocation of Datasectors as the file size increases:
------------------------------------------------------------
Command Line for testing : nachos -f -cp test/filename filename
Narration:
The original allocation methodology has been
replaced by us to Dynamic allocation of datasectors.
We are allocating more space when a Process issues a 'Write
' that goes beyond the present file-size. printf statements are included
in the output when we allocate new sector(S) to the file. The following
printf statements can be seen in the output when nachos allocates a new
datasector for the file:
"File :filename: has being extended by :numsectors:"
Saturday, 8 April, 2000
Phase 4 was submitted - surprisingly one day ahead of schedule.
Saturday, 29 April, 2000
I finished up all pertanent Build Log info (e.g., added Epilogue), and is now ready to submit.
Final Changes:
filesys.cc (17K)
filehdr.cc (7K)
filesys.h (3K)
filehdr.h (2K)
openfile.cc (13K)
openfile.h (3K)
fstest.cc (10K)
main.cc (7K)
filesys.cc (17K)
Back to top of Final
Changes
// filesys.cc
// Routines to manage the overall
operation of the file system.
// Implements routines to map from
textual file names to files.
//
// Each file in the file system has:
// A file header,
stored in a sector on disk
//
(the size of the file header data structure is arranged
//
to be precisely the size of 1 disk sector)
// A number of
data blocks
// An entry in
the file system directory
//
// The file system consists of several
data structures:
// A bitmap of
free disk sectors (cf. bitmap.h)
// A directory
of file names and file headers
//
// Both the bitmap and the directory
are represented as normal
// files. Their file headers
are located in specific sectors
// (sector 0 and sector 1), so that
the file system can find them
// on bootup.
//
// The file system assumes that the
bitmap and directory files are
// kept "open" continuously while
Nachos is running.
//
// For those operations (such as
Create, Remove) that modify the
// directory and/or bitmap, if the
operation succeeds, the changes
// are written immediately back to
disk (the two files are kept
// open during all this time).
If the operation fails, and we have
// modified part of the directory
and/or bitmap, we simply discard
// the changed version, without writing
it back to disk.
//
// Our implementation at this point
has the following restrictions:
//
// there is no
synchronization for concurrent accesses
// files have a
fixed size, set when the file is created
// files cannot
be bigger than about 3KB in size
// there is no
hierarchical directory structure, and only a limited
//
number of files can be added to the system
// there is no
attempt to make the system robust to failures
// (if Nachos
exits in the middle of an operation that modifies
// the file
system, it may corrupt the disk)
//
// Copyright (c) 1992-1993 The Regents of the University of California.
// All rights reserved. See copyright.h for copyright notice
and limitation
// of liability and disclaimer of warranty provisions.
#include "copyright.h"
#include "system.h"
#include "disk.h"
#include "bitmap.h"
#include "directory.h"
#include "filehdr.h"
#include "filesys.h"
// Sectors containing the file headers for the bitmap of free sectors,
// and the directory of files. These file headers are placed
in well-known
// sectors, so that they can be located on boot-up.
#define FreeMapSector
0
#define DirectorySector
1
// Initial file sizes for the bitmap and directory; until the file
system
// supports extensible files, the directory size sets the maximum
number
// of files that can be loaded onto the disk.
#define FreeMapFileSize
(NumSectors / BitsInByte)
#define NumDirEntries
10
#define DirectoryFileSize (sizeof(DirectoryEntry)
* NumDirEntries)
//----------------------------------------------------------------------
// FileSystem::FileSystem
// Initialize the file system.
If format = TRUE, the disk has
// nothing on it, and we need to
initialize the disk to contain
// an empty directory, and a bitmap
of free sectors (with almost but
// not all of the sectors marked
as free).
//
// If format = FALSE, we just have
to open the files
// representing the bitmap and the
directory.
//
// "format" -- should we initialize
the disk?
//----------------------------------------------------------------------
FileSystem::FileSystem(bool format)
{
DEBUG('f', "Initializing the file system.\n");
if (format) {
BitMap *freeMap = new
BitMap(NumSectors);
Directory *directory
= new Directory(NumDirEntries);
FileHeader *mapHdr =
new FileHeader;
FileHeader *dirHdr =
new FileHeader;
DEBUG('f', "Formatting the file system.\n");
// First, allocate space for FileHeaders for
the directory and bitmap
// (make sure no one else grabs these!)
freeMap->Mark(FreeMapSector);
freeMap->Mark(DirectorySector);
// Second, allocate space for the data blocks
containing the contents
// of the directory and bitmap files.
There better be enough space!
ASSERT(mapHdr->Allocate(freeMap,
FreeMapFileSize));
ASSERT(dirHdr->Allocate(freeMap,
DirectoryFileSize));
// Flush the bitmap and directory FileHeaders
back to disk
// We need to do this before we can "Open" the
file, since open
// reads the file header off of disk (and currently
the disk has garbage
// on it!).
DEBUG('f', "Writing headers
back to disk.\n");
mapHdr->WriteBack(FreeMapSector);
dirHdr->WriteBack(DirectorySector);
// OK to open the bitmap and directory files
now
// The file system operations assume these two
files are left open
// while Nachos is running.
freeMapFile = new OpenFile(FreeMapSector);
directoryFile = new
OpenFile(DirectorySector);
#ifdef CHANGED
freeMapFile->name = "$FreeMap";
directoryFile->name = "$Drctory" ;
int i;
for( i =0; i < MAX_FILES_GLOBAL; i++)
{
if (fileTable[i].name == NULL)
{
fileTable[i].name
= new char(strlen("$FreeMap") + 1);
strcpy(fileTable[i].name,
"$FreeMap");
fileTable[i].deleteBit
= FALSE;
fileTable[i].openCount
= 1;
char *lockString
= new char[20];
sprintf(lockString,"File
Lock :%d:", i);
fileTable[i].fileLock
= new Lock(lockString);
break;
}
}
for( i =0; i < MAX_FILES_GLOBAL; i++)
{
if (fileTable[i].name == NULL)
{
fileTable[i].name
= new char(strlen("$Drctory") + 1);
strcpy(fileTable[i].name,
"$Drctory");
fileTable[i].deleteBit
= FALSE;
fileTable[i].openCount
= 1;
char *lockString
= new char[20];
sprintf(lockString,"File
Lock :%d:", i);
fileTable[i].fileLock
= new Lock(lockString);
break;
}
}
#endif
// Once we have the files "open", we can write
the initial version
// of each file back to disk. The directory
at this point is completely
// empty; but the bitmap has been changed to
reflect the fact that
// sectors on the disk have been allocated for
the file headers and
// to hold the file data for the directory and
bitmap.
DEBUG('f', "Writing bitmap
and directory back to disk.\n");
freeMap->WriteBack(freeMapFile);
// flush changes to disk
DEBUG('f',"Wrote FreeMap
\n");
directory->WriteBack(directoryFile);
if (DebugIsEnabled('f'))
{
freeMap->Print();
directory->Print();
}
} else {
// if we are not formatting the disk, just open
the files representing
// the bitmap and directory; these are left
open while Nachos is running
freeMapFile = new OpenFile(FreeMapSector);
directoryFile = new
OpenFile(DirectorySector);
}
}
//----------------------------------------------------------------------
// FileSystem::Create
// Create a file in the Nachos file
system (similar to UNIX create).
// Since we can't increase the size
of files dynamically, we have
// to give Create the initial size
of the file.
//
// The steps to create a file are:
// Make sure the file
doesn't already exist
// Allocate a sector
for the file header
// Allocate space on
disk for the data blocks for the file
// Add the name to the
directory
// Store the new file
header on disk
// Flush the changes
to the bitmap and the directory back to disk
//
// Return TRUE if everything goes
ok, otherwise, return FALSE.
//
// Create fails if:
//
file is already in directory
//
no free space for file header
//
no free entry for file in directory
//
no free space for data blocks for the file
//
// Note that this implementation
assumes there is no concurrent access
// to the file system!
//
// "name" -- name of file to be created
// "initialSize" -- size of file
to be created
//----------------------------------------------------------------------
bool
FileSystem::Create(char *name, int initialSize)
{
Directory *directory;
BitMap *freeMap;
FileHeader *hdr;
int sector;
bool success;
printf("Creating file :%s:, size %d\n", name, initialSize);
directory = new Directory(NumDirEntries);
DEBUG('f',"In create before calling FetchFrom
\n");
#ifdef CHANGED
directory->directoryLock->Acquire();
#endif
directory->FetchFrom(directoryFile);
DEBUG('f',"In create after calling FetchFrom
\n");
if (directory->Find(name) != -1)
success = FALSE;
// file is already in directory
else {
freeMap = new BitMap(NumSectors);
#ifdef CHANGED
freeMapFileLock->Acquire();
#endif
freeMap->FetchFrom(freeMapFile);
sector = freeMap->Find();
// find a sector to hold the file header
if (sector == -1)
success = FALSE;
// no free block for file header
else if (!directory->Add(name,
sector))
success = FALSE; // no space in directory
else {
hdr = new FileHeader;
if (!hdr->Allocate(freeMap, initialSize))
success = FALSE; // no space
on disk for data
else {
success = TRUE;
// everthing worked, flush all changes back to disk
hdr->WriteBack(sector);
directory->WriteBack(directoryFile);
freeMap->WriteBack(freeMapFile);
}
delete hdr;
}
delete freeMap;
#ifdef CHANGED
freeMapFileLock->Release();
#endif
}
#ifdef CHANGED
directory->directoryLock->Release();
#endif
delete directory;
return success;
}
//----------------------------------------------------------------------
// FileSystem::Open
// Open a file for reading and writing.
// To open a file:
// Find the location
of the file's header, using the directory
// Bring the header into
memory
//
// "name" -- the text name of the
file to be opened
//----------------------------------------------------------------------
OpenFile *
FileSystem::Open(char *name)
{
Directory *directory = new Directory(NumDirEntries);
OpenFile *openFile = NULL;
int sector;
DEBUG('f', "Opening file %s\n", name);
DEBUG('f',"In Open before calling FetchFrom
\n");
directory->FetchFrom(directoryFile);
DEBUG('f',"In open after calling FetchFrom \n");
DEBUG('f',"name : %s: directory : %d:", name,
directory);
sector = directory->Find(name);
DEBUG('f',"Before IF ---\n");
if (sector >= 0)
{
openFile = new OpenFile(sector);
// name was found in directory
openFile->name = new
char( strlen(name) + 1);
strcpy(openFile->name,
name);
}
DEBUG('f',"after IF --- before deleting directory\n");
delete directory;
#ifdef CHANGED
int i;
// If already opened by some other process it
would be present in the GLOBAL FileTable.
// Return the same pointer. Otherwise, get the
file information from the directory.
DEBUG('f'," Before the first Loop");
for( i =0; i < MAX_FILES_GLOBAL; i++)
if((fileTable[i].name
!= NULL) && (strcmp(name, fileTable[i].name) == 0))
{
fileTable[i].openCount
++;
break;
}
DEBUG('f', "Before second Loop, after first Loop .\n\n");
if ( i >= MAX_FILES_GLOBAL)
for( i =0; i < MAX_FILES_GLOBAL; i++)
{
printf(" Value of i:%d:\n",
i);
if (fileTable[i].name == NULL)
{
printf("
For Value of i=:%d: inside the If\n", i);
printf("
File Table pointer :%d: and the name is :%s:\n", fileTable[i], name);
fileTable[i].name
= new char(strlen(name) + 1);
printf (
"ONE
");
strcpy(fileTable[i].name,
name);printf(" TWO ");
fileTable[i].deleteBit
= FALSE; printf(" THREE ");
fileTable[i].openCount
= 1; printf(" FOUR ");
char *lockString
= new char[20];printf (" FIVE ");
sprintf(lockString,"File
Lock :%d:", i); printf (" SIX ");
fileTable[i].fileLock
= new Lock(lockString); printf(" SEVEN ");
break;
}
}
ASSERT (i < MAX_FILES_GLOBAL);
#endif
return openFile; // return NULL if not found
}
//----------------------------------------------------------------------
// FileSystem::Remove
// Delete a file from the file system.
This requires:
// Remove
it from the directory
// Delete
the space for its header
// Delete
the space for its data blocks
// Write
changes to directory, bitmap back to disk
//
// Return TRUE if the file was deleted,
FALSE if the file wasn't
// in the file system.
//
// "name" -- the text name of the
file to be removed
//----------------------------------------------------------------------
bool
FileSystem::Remove(char *name)
{
Directory *directory;
BitMap *freeMap;
FileHeader *fileHdr;
int sector;
directory = new Directory(NumDirEntries);
DEBUG('f',"In file system remove -- before calling
FETCHFROM\n");
directory->FetchFrom(directoryFile);
#ifdef CHANGED
directory->directoryLock->Acquire();
#endif
DEBUG('f',"In file system remove -- after calling
FETCHFROM\n");
sector = directory->Find(name);
if (sector == -1) {
#ifdef CHANGED
directory->directoryLock->Release();
#endif
delete directory;
return FALSE;
// file not found
}
#ifdef CHANGED
for(int i =0; i < MAX_FILES_GLOBAL; i++)
{
if (strcmp(fileTable[i].name,
name) == 0 )
if (fileTable[i].openCount
== 0)
{
delete fileTable[i].name;
delete fileTable[i].fileLock;
fileTable[i].deleteBit = FALSE;
break;
}
else
{
fileTable[i].deleteBit = TRUE;
delete directory;
return TRUE;
}
}
#endif
printf("Deleting the file:%s: from the FileSystem.\n", name);
return TRUE;
fileHdr = new FileHeader;
fileHdr->FetchFrom(sector);
freeMap = new BitMap(NumSectors);
#ifdef CHANGED
freeMapFileLock->Acquire();
#endif
printf("ONE\n");
freeMap->FetchFrom(freeMapFile);
printf("TWO\n");
// fileHdr->Deallocate(freeMap);
// remove data blocks
freeMap->Clear(sector);
// remove header block
printf("THREE\n");
directory->Remove(name);
printf("FOUR\n");
freeMap->WriteBack(freeMapFile);
// flush to disk
#ifdef CHANGED
freeMapFileLock->Release();
#endif
printf("5\n");
directory->WriteBack(directoryFile);
// flush to disk
#ifdef CHANGED
directory->directoryLock->Release();
#endif
printf("6\n");
delete fileHdr;
delete directory;
delete freeMap;
#ifdef CHANGED
printf("Deleting the file:%s: from the FileSystem.\n",
name);
#endif
return TRUE;
}
//----------------------------------------------------------------------
// FileSystem::List
// List all the files in the file
system directory.
//----------------------------------------------------------------------
void
FileSystem::List()
{
Directory *directory = new Directory(NumDirEntries);
directory->FetchFrom(directoryFile);
directory->List();
delete directory;
}
//----------------------------------------------------------------------
// FileSystem::Print
// Print everything about the file
system:
// the contents of the
bitmap
// the contents of the
directory
// for each file in the
directory,
//
the contents of the file header
//
the data in the file
//----------------------------------------------------------------------
void
FileSystem::Print()
{
FileHeader *bitHdr = new FileHeader;
FileHeader *dirHdr = new FileHeader;
BitMap *freeMap = new BitMap(NumSectors);
Directory *directory = new Directory(NumDirEntries);
printf("Bit map file header:\n");
bitHdr->FetchFrom(FreeMapSector);
bitHdr->Print();
printf("Directory file header:\n");
dirHdr->FetchFrom(DirectorySector);
dirHdr->Print();
freeMap->FetchFrom(freeMapFile);
freeMap->Print();
directory->FetchFrom(directoryFile);
directory->Print();
delete bitHdr;
delete dirHdr;
delete freeMap;
delete directory;
}
filehdr.cc (7K)
Back to top of Final
Changes
// filehdr.cc
// Routines for managing the disk
file header (in UNIX, this
// would be called the i-node).
//
// The file header is used to locate
where on disk the
// file's data is stored. We
implement this as a fixed size
// table of pointers -- each entry
in the table points to the
// disk sector containing that portion
of the file data
// (in other words, there are no
indirect or doubly indirect
// blocks). The table size is chosen
so that the file header
// will be just big enough to fit
in one disk sector,
//
// Unlike in a real system, we do
not keep track of file permissions,
// ownership, last modification date,
etc., in the file header.
//
// A file header can be initialized
in two ways:
// for a new file,
by modifying the in-memory data structure
//
to point to the newly allocated data blocks
// for a file already
on disk, by reading the file header from disk
//
// Copyright (c) 1992-1993 The Regents of the University of California.
// All rights reserved. See copyright.h for copyright notice
and limitation
// of liability and disclaimer of warranty provisions.
#include "copyright.h"
#include "system.h"
#include "filehdr.h"
//----------------------------------------------------------------------
// FileHeader::Allocate
// Initialize a fresh file header
for a newly created file.
// Allocate data blocks for the file
out of the map of free disk blocks.
// Return FALSE if there are not
enough free blocks to accomodate
// the new file.
//
// "freeMap" is the bit map of free
disk sectors
// "fileSize" is the bit map of free
disk sectors
//----------------------------------------------------------------------
bool
FileHeader::Allocate(BitMap *freeMap, int fileSize)
{ int i;
numBytes = fileSize;
numSectors = divRoundUp(fileSize, SectorSize);
if (freeMap->NumClear() < (numSectors+1))
return FALSE;
// not enough space
int directSectors = numSectors % NumDirect;
for (i = 0; i < directSectors; i++)
dataSectors[i] = freeMap->Find();
if ((numSectors / NumDirect) > 0)
{
indirectHdrSector = freeMap->Find();
FileHeader *hdr = new FileHeader;
for (i = 0 ; i < (numSectors
- directSectors); i++)
hdr->dataSectors[i]
= freeMap->Find();
hdr->WriteBack(indirectHdrSector);
delete hdr;
}
return TRUE;
}
//----------------------------------------------------------------------
// FileHeader::Deallocate
// De-allocate all the space allocated
for data blocks for this file.
//
// "freeMap" is the bit map of free
disk sectors
//----------------------------------------------------------------------
void
FileHeader::Deallocate(BitMap *freeMap)
{ int i;
int directSectors = numSectors % NumDirect;
for (i = 0; i < directSectors; i++) {
ASSERT(freeMap->Test((int)
dataSectors[i])); // ought to be marked!
freeMap->Clear((int)
dataSectors[i]);
}
if (indirectHdrSector != 0)
{
FileHeader *hdr = new FileHeader;
hdr->FetchFrom(indirectHdrSector);
for(i =0; i < (numSectors - directSectors)
; i++)
{
ASSERT(freeMap->Test((int)
hdr->dataSectors[i]));
freeMap->Clear((int)
hdr->dataSectors[i]);
}
delete hdr;
}
}
//----------------------------------------------------------------------
// FileHeader::FetchFrom
// Fetch contents of file header
from disk.
//
// "sector" is the disk sector containing
the file header
//----------------------------------------------------------------------
void
FileHeader::FetchFrom(int sector)
{
DEBUG('z'," Reading the sector from FileHeader:%d:\n",
sector);
synchDisk->ReadSector(sector, (char *)this);
}
//----------------------------------------------------------------------
// FileHeader::WriteBack
// Write the modified contents of
the file header back to disk.
//
// "sector" is the disk sector to
contain the file header
//----------------------------------------------------------------------
void
FileHeader::WriteBack(int sector)
{
synchDisk->WriteSector(sector, (char *)this);
}
//----------------------------------------------------------------------
// FileHeader::ByteToSector
// Return which disk sector is storing
a particular byte within the file.
// This is essentially a translation
from a virtual address (the
// offset in the file) to a physical
address (the sector where the
// data at the offset is stored).
//
// "offset" is the location within
the file of the byte in question
//----------------------------------------------------------------------
int
FileHeader::ByteToSector(int offset)
{
int SectorNum = offset/ SectorSize;
if (SectorNum < NumDirect)
return dataSectors[SectorNum];
else
{
FileHeader *hdr
= new FileHeader;
hdr->FetchFrom(indirectHdrSector);
int returnNum
= hdr->dataSectors[ SectorNum - NumDirect];
delete hdr;
return returnNum;
}
// return(dataSectors[offset / SectorSize]);
}
//----------------------------------------------------------------------
// FileHeader::FileLength
// Return the number of bytes in
the file.
//----------------------------------------------------------------------
int
FileHeader::FileLength()
{
return numBytes;
}
//----------------------------------------------------------------------
// FileHeader::Print
// Print the contents of the file
header, and the contents of all
// the data blocks pointed to by
the file header.
//----------------------------------------------------------------------
void
FileHeader::Print()
{
int i, j, k;
char *data = new char[SectorSize];
printf("FileHeader contents. File size:
%d. File blocks:\n", numBytes);
for (i = 0; i < numSectors; i++)
printf("%d ", dataSectors[i]);
printf("\nFile contents:\n");
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("%c", data[j]);
else
printf("\\%x", (unsigned char)data[j]);
}
printf("\n");
}
delete [] data;
}
#ifdef CHANGED
void FileHeader::SetFileAttr(int TotBytes, int TotSectors)
{
numBytes = TotBytes;
numSectors = TotSectors;
}
#endif
filesys.h (3K)
Back to top of Final
Changes
// filesys.h
// Data structures to represent the
Nachos file system.
//
// A file system is a set of files
stored on disk, organized
// into directories. Operations
on the file system have to
// do with "naming" -- creating,
opening, and deleting files,
// given a textual file name.
Operations on an individual
// "open" file (read, write, close)
are to be found in the OpenFile
// class (openfile.h).
//
// We define two separate implementations
of the file system.
// The "STUB" version just re-defines
the Nachos file system
// operations as operations on the
native UNIX file system on the machine
// running the Nachos simulation.
This is provided in case the
// multiprogramming and virtual memory
assignments (which make use
// of the file system) are done before
the file system assignment.
//
// The other version is a "real"
file system, built on top of
// a disk simulator. The disk
is simulated using the native UNIX
// file system (in a file named "DISK").
//
// In the "real" implementation,
there are two key data structures used
// in the file system. There
is a single "root" directory, listing
// all of the files in the file system;
unlike UNIX, the baseline
// system does not provide a hierarchical
directory structure.
// In addition, there is a bitmap
for allocating
// disk sectors. Both the root
directory and the bitmap are themselves
// stored as files in the Nachos
file system -- this causes an interesting
// bootstrap problem when the simulated
disk is initialized.
//
// Copyright (c) 1992-1993 The Regents of the University of California.
// All rights reserved. See copyright.h for copyright notice
and limitation
// of liability and disclaimer of warranty provisions.
#ifndef FS_H
#define FS_H
#include "copyright.h"
#include "openfile.h"
#ifdef FILESYS_STUB
// Temporarily implement file system calls as
// calls to UNIX, until the real file system
// implementation is available
class FileSystem {
public:
FileSystem(bool format) {}
bool Create(char *name, int initialSize) {
int fileDescriptor =
OpenForWrite(name);
if (fileDescriptor ==
-1) return FALSE;
Close(fileDescriptor);
return TRUE;
}
OpenFile* Open(char *name) {
int fileDescriptor
= OpenForReadWrite(name, FALSE);
if (fileDescriptor
== -1) return NULL;
return new
OpenFile(fileDescriptor);
}
bool Remove(char *name) { return Unlink(name) == 0; }
};
#else // FILESYS
class FileSystem {
public:
FileSystem(bool format);
// Initialize the file system.
// Must be called *after* "synchDisk"
// has been initialized.
// If "format", there is nothing on
// the disk, so initialize the directory
// and the bitmap of free blocks.
bool Create(char *name, int initialSize);
// Create a file (UNIX creat)
OpenFile* Open(char *name); // Open a file (UNIX open)
bool Remove(char *name); // Delete a file (UNIX unlink)
void List(); // List all the files in the file system
void Print(); // List all the files and their contents
OpenFile* freeMapFile;
// Bit map of free disk blocks,
// represented as a file
private:
OpenFile* directoryFile;
// "Root" directory -- list of
// file names, represented as a file
};
#endif // FILESYS
#endif // FS_H
filehdr.h (2K)
Back to top of Final
Changes
// filehdr.h
// Data structures for managing a
disk file header.
//
// A file header describes where
on disk to find the data in a file,
// along with other information about
the file (for instance, its
// length, owner, etc.)
//
// Copyright (c) 1992-1993 The Regents of the University of California.
// All rights reserved. See copyright.h for copyright notice
and limitation
// of liability and disclaimer of warranty provisions.
#include "copyright.h"
#ifndef FILEHDR_H
#define FILEHDR_H
#include "disk.h"
#include "bitmap.h"
#define NumDirect ((SectorSize
- 3 * sizeof(int)) / sizeof(int))
#define MaxFileSize (NumDirect * SectorSize)
// The following class defines the Nachos "file header" (in UNIX
terms,
// the "i-node"), describing where on disk to find all of the data
in the file.
// The file header is organized as a simple table of pointers to
// data blocks.
//
// The file header data structure can be stored in memory or on
disk.
// When it is on disk, it is stored in a single sector -- this
means
// that we assume the size of this data structure to be the same
// as one disk sector. Without indirect addressing, this
// limits the maximum file length to just under 4K bytes.
//
// There is no constructor; rather the file header can be initialized
// by allocating blocks for the file (if it is a new file), or
by
// reading it from disk.
class FileHeader {
public:
bool Allocate(BitMap *bitMap, int fileSize);//
Initialize a file header,
// including allocating space
// on disk for the file data
void Deallocate(BitMap *bitMap);
// De-allocate this file's
// data blocks
void FetchFrom(int sectorNumber);
// Initialize file header from disk
void WriteBack(int sectorNumber);
// Write modifications to file header
// back to disk
int ByteToSector(int offset);
// Convert a byte offset into the file
// to the disk sector containing
// the byte
int FileLength();
// Return the length of the file
// in bytes
void Print();
// Print the contents of the file.
#ifdef CHANGED
void SetFileAttr(int TotBytes, int TotSectors);
#endif
int dataSectors[NumDirect];
int indirectHdrSector;
private:
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
};
#endif // FILEHDR_H
openfile.cc (13K)
Back to top of Final
Changes
// openfile.cc
// Routines to manage an open Nachos
file. As in UNIX, a
// file must be open before we can
read or write to it.
// Once we're all done, we can close
it (in Nachos, by deleting
// the OpenFile data structure).
//
// Also as in UNIX, for convenience,
we keep the file header in
// memory while the file is open.
//
// Copyright (c) 1992-1993 The Regents of the University of California.
// All rights reserved. See copyright.h for copyright notice
and limitation
// of liability and disclaimer of warranty provisions.
#include "copyright.h"
#include "filehdr.h"
#include "openfile.h"
#include "system.h"
#include <strings.h>
//----------------------------------------------------------------------
// OpenFile::OpenFile
// Open a Nachos file for reading
and writing. Bring the file header
// into memory while the file is
open.
//
// "sector" -- the location on disk
of the file header for this file
//----------------------------------------------------------------------
OpenFile::OpenFile(int sector)
{
hdr = new FileHeader;
hdr->FetchFrom(sector);
seekPosition = 0;
fileSector = sector;
}
//----------------------------------------------------------------------
// OpenFile::~OpenFile
// Close a Nachos file, de-allocating
any in-memory data structures.
//----------------------------------------------------------------------
OpenFile::~OpenFile()
{
printf(" File : %s : is of length: %d: when
deleted \n", name, hdr->FileLength());
delete hdr;
#ifdef CHANGED
int i;
for(i = 0; i < MAX_FILES_GLOBAL; i++)
{
if( strcmp(fileTable[i].name,name)
== 0)
{
if (( -- fileTable[i].openCount == 0) && ( fileTable[i].deleteBit
== TRUE))
{
fileSystem->Remove( fileTable[i].name);
fileTable[i].name = NULL;
fileTable[i].fileLock = NULL;
fileTable[i].deleteBit = FALSE;
}
break;
}
}
printf(" For file :%s: the open count is :%d:\n",
name, fileTable[i].openCount);
delete name;
#endif
}
//----------------------------------------------------------------------
// OpenFile::Seek
// Change the current location within
the open file -- the point at
// which the next Read or Write will
start from.
//
// "position" -- the location within
the file for the next Read/Write
//----------------------------------------------------------------------
void
OpenFile::Seek(int position)
{
seekPosition = position;
}
//----------------------------------------------------------------------
// OpenFile::Read/Write
// Read/write a portion of a file,
starting from seekPosition.
// Return the number of bytes actually
written or read, and as a
// side effect, increment the current
position within the file.
//
// Implemented using the more primitive
ReadAt/WriteAt.
//
// "into" -- the buffer to contain
the data to be read from disk
// "from" -- the buffer containing
the data to be written to disk
// "numBytes" -- the number of bytes
to transfer
//----------------------------------------------------------------------
int
OpenFile::Read(char *into, int numBytes)
{
DEBUG('f',"The value of into:%s: and its length is
%d before calling Read\n", into, strlen(into));
int result = ReadAt(into, numBytes, seekPosition);
DEBUG('f',"The value of the result %d \n",result);
seekPosition += result;
DEBUG('f',"Leaving the function Read\n");
return result;
}
int
OpenFile::Write(char *into, int numBytes)
{
DEBUG('f',"In the Write function ");
int result = WriteAt(into, numBytes, seekPosition);
seekPosition += result;
return result;
}
//----------------------------------------------------------------------
// OpenFile::ReadAt/WriteAt
// Read/write a portion of a file,
starting at "position".
// Return the number of bytes actually
written or read, but has
// no side effects (except that Write
modifies the file, of course).
//
// There is no guarantee the request
starts or ends on an even disk sector
// boundary; however the disk only
knows how to read/write a whole disk
// sector at a time. Thus:
//
// For ReadAt:
// We read in all
of the full or partial sectors that are part of the
// request, but
we only copy the part we are interested in.
// For WriteAt:
// We must first
read in any sectors that will be partially written,
// so that we don't
overwrite the unmodified portion. We then copy
// in the data
that will be modified, and write back all the full
// or partial sectors
that are part of the request.
//
// "into" -- the buffer to contain
the data to be read from disk
// "from" -- the buffer containing
the data to be written to disk
// "numBytes" -- the number of bytes
to transfer
// "position" -- the offset within
the file of the first byte to be
//
read/written
//----------------------------------------------------------------------
int
OpenFile::ReadAt(char *into, int numBytes, int position)
{
int fileLength = hdr->FileLength();
int i, firstSector, lastSector, numSectors;
char *buf;
DEBUG('f',"In the ReadAt function\n");
#ifdef CHANGED
int numFileRow;
bool releaseFlag = FALSE;
hdr->FetchFrom(fileSector);
fileLength = hdr->FileLength();
for(numFileRow=0; numFileRow < MAX_FILES_GLOBAL;
numFileRow++)
if ((fileTable[numFileRow].name != NULL) &&
(strcmp(name,fileTable[numFileRow].name) == 0))
break;
DEBUG('f',"BEFORE ASSERTION \n");
ASSERT(numFileRow < MAX_FILES_GLOBAL);
if (!(fileTable[numFileRow].fileLock->isHeldByCurrentThread()))
{
DEBUG('f',"acquiring Lock in ReadAt function\n");
releaseFlag = TRUE;
fileTable[numFileRow].fileLock->Acquire();
}
#endif
DEBUG('z',"numBytes :%d: position:%d:\n", numBytes, fileLength);
#ifndef CHANGED
if ((numBytes <= 0) || (position >= fileLength))
return 0;
// check request
#endif
#ifdef CHANGED
if ((numBytes <= 0) || (position >= fileLength))
{
if (releaseFlag)
{
DEBUG('f',"Releasing
Lock in ReadAt function\n");
fileTable[numFileRow].fileLock->Release();
}
return 0;
}
#endif
if ((position + numBytes) > fileLength)
numBytes = fileLength
- position;
DEBUG('z', "Reading %d bytes at %d, from file
of length %d.\n",
numBytes, position, fileLength);
firstSector = divRoundDown(position, SectorSize);
lastSector = divRoundDown(position + numBytes
- 1, SectorSize);
numSectors = 1 + lastSector - firstSector;
// read in all the full and partial sectors that
we need
buf = new char[numSectors * SectorSize];
DEBUG('z',"FirstSEctor:%d: LastSector:%d:\n",
firstSector, lastSector);
for (i = firstSector; i <= lastSector; i++)
{
DEBUG('z',"Name of the
File:%s:", name);
DEBUG('z'," Reading
sector from OpenFile:%d:\n", hdr->ByteToSector(i * SectorSize));
if (strcmp(name,"$FreeMap")
== 0)
synchDisk->ReadSector(2,
&buf[(i - firstSector) * SectorSize]);
else
synchDisk->ReadSector(hdr->ByteToSector(i
* SectorSize),
&buf[(i - firstSector) * SectorSize]);
}
DEBUG('f',"After Readsector
in function ReadAt\n");
// copy the part we want
bcopy(&buf[position - (firstSector * SectorSize)],
into, numBytes);
delete [] buf;
DEBUG('f',"Leaving the function Readat\n");
#ifdef CHANGED
if (releaseFlag)
{
DEBUG('z',"Releasing Lock in ReadAt
function\n");
fileTable[numFileRow].fileLock->Release();
}
#endif
return numBytes;
}
int
OpenFile::WriteAt(char *from, int numBytes, int position)
{
DEBUG('f',"In the WriteAt function. \n\n");
int fileLength = hdr->FileLength();
int i, firstSector, lastSector, numSectors;
bool firstAligned, lastAligned;
char *buf;
#ifdef CHANGED
bool releaseFlag = FALSE;
int j, numFileRow;
int newFileLength = position + numBytes;
int numSectorsAlloc = divRoundUp(fileLength, SectorSize);
int numSectorsNeeded = divRoundUp(newFileLength, SectorSize);
int numSectorsToBeAlloc = numSectorsNeeded -
numSectorsAlloc;
DEBUG('f',"In the Starting of Changed \n");
DEBUG('f',"FileLength:%d: NewFileLength:%d:\n", fileLength,
newFileLength);
for(numFileRow=0; numFileRow < MAX_FILES_GLOBAL;
numFileRow++)
if ((fileTable[numFileRow].name != NULL)
&& (strcmp(name,fileTable[numFileRow].name) == 0))
break;
ASSERT(numFileRow < MAX_FILES_GLOBAL);
if (!fileTable[numFileRow].fileLock->isHeldByCurrentThread())
{
DEBUG('z',"acquiring Lock in WriteAt function\n");
releaseFlag = TRUE;
fileTable[numFileRow].fileLock->Acquire();
}
hdr->FetchFrom(fileSector);
DEBUG('f',"After fetch from");
if (numSectorsToBeAlloc > 0)
{
DEBUG ('f',"In the IF condition.\n");
printf(" File :%s : has being extended
by :%d: sectors\n", name,numSectorsToBeAlloc);
BitMap *freeMap = new BitMap(NumSectors);
freeMapFileLock->Acquire();
DEBUG('f', "After getting the
lock on the free Map\n");
DEBUG('f',"fileSystem:%d:
freeMapFile:%d:\n", fileSystem, fileSystem->freeMapFile);
freeMap->FetchFrom(fileSystem->freeMapFile);
DEBUG('f',"Before ASSERT\n");
ASSERT(freeMap->NumClear()
>= numSectorsToBeAlloc);
DEBUG('f',"After ASSERT\n");
for(j=numSectorsAlloc; j <
numSectorsToBeAlloc ; j++)
hdr->dataSectors[j]
= freeMap->Find();
DEBUG('f',"After allocating
the new datasectors\n");
freeMap->WriteBack(fileSystem->freeMapFile);
delete freeMap;
freeMapFileLock->Release();
DEBUG('f',"After releasing lock\n
name of the file:%s:\n",name);
}
hdr->SetFileAttr(newFileLength, numSectorsNeeded);
hdr->WriteBack(fileSector);
if (releaseFlag)
{
DEBUG('z',"releasing Lock in WriteAt function\n");
fileTable[numFileRow].fileLock->Release();
}
#endif
DEBUG('f',"Out of the CHANGED\n");
#ifndef CHANGED
if ((numBytes <= 0) || (position >= fileLength))
return 0;
// check request
if ((position + numBytes) > fileLength)
numBytes = fileLength
- position;
#endif
DEBUG('f', "Writing %d bytes at %d, from file
of length %d.\n",
numBytes, position, fileLength);
DEBUG('f',"WriteContent:%s:",from);
firstSector = divRoundDown(position, SectorSize);
lastSector = divRoundDown(position + numBytes
- 1, SectorSize);
numSectors = 1 + lastSector - firstSector;
DEBUG('f',"number of sectors :%d:Sector:%d:bufsize:%d:\n",
numSectors, SectorSize,(numSectors * SectorSize));
buf = new char[numSectors * SectorSize];
firstAligned = (position == (firstSector * SectorSize));
lastAligned = ((position + numBytes) == ((lastSector + 1) * SectorSize));
DEBUG('f',"The value of firstAligned:%d:\n",
firstAligned);
// read in first and last sector, if they are to be partially modified
if (!firstAligned)
{
DEBUG('f',"Calling ReadAt
from WriteAt 1\n");
ReadAt(buf, SectorSize,
firstSector * SectorSize);
}
if (!lastAligned && ((firstSector !=
lastSector) || firstAligned))
{
DEBUG('f',"Calling
ReadAt from WriteAt 2\n");
ReadAt(&buf[(lastSector
- firstSector) * SectorSize],
SectorSize, lastSector * SectorSize);
}
// copy in the bytes we want to change
bcopy(from, &buf[position - (firstSector
* SectorSize)], numBytes);
// write modified sectors back
for (i = firstSector; i <= lastSector; i++)
{
if (strcmp(name,"$FreeMap")
== 0)
synchDisk->WriteSector(2,
&buf[(i - firstSector) * SectorSize]);
else
synchDisk->WriteSector(hdr->ByteToSector(i
* SectorSize),
&buf[(i - firstSector) * SectorSize]);
}
delete [] buf;
return numBytes;
}
//----------------------------------------------------------------------
// OpenFile::Length
// Return the number of bytes in
the file.
//----------------------------------------------------------------------
int
OpenFile::Length()
{
hdr->FetchFrom(fileSector);
return hdr->FileLength();
}
Back to top of Final
Changes
openfile.h (3K)
Back to top of Final
Changes
// openfile.h
// Data structures for opening, closing,
reading and writing to
// individual files. The operations
supported are similar to
// the UNIX ones -- type 'man open'
to the UNIX prompt.
//
// There are two implementations.
One is a "STUB" that directly
// turns the file operations into
the underlying UNIX operations.
// (cf. comment in filesys.h).
//
// The other is the "real" implementation,
that turns these
// operations into read and write
disk sector requests.
// In this baseline implementation
of the file system, we don't
// worry about concurrent accesses
to the file system
// by different threads -- this is
part of the assignment.
//
// Copyright (c) 1992-1993 The Regents of the University of California.
// All rights reserved. See copyright.h for copyright notice
and limitation
// of liability and disclaimer of warranty provisions.
#ifndef OPENFILE_H
#define OPENFILE_H
#include "copyright.h"
#include "utility.h"
#ifdef FILESYS_STUB
// Temporarily implement calls to
// Nachos file system as calls to UNIX!
// See definitions listed under #else
class OpenFile {
public:
OpenFile(int f) { file = f; currentOffset =
0; } // open the file
~OpenFile() { Close(file); }
// close the file
int ReadAt(char *into, int numBytes, int position)
{
DEBUG('f',"inside read at inside stub");
Lseek(file, position, 0);
return ReadPartial(file, into, numBytes);
}
int WriteAt(char *from, int numBytes, int position)
{
Lseek(file, position, 0);
WriteFile(file, from, numBytes);
return numBytes;
}
int Read(char *into, int numBytes) {
int numRead = ReadAt(into, numBytes, currentOffset);
currentOffset += numRead;
return numRead;
}
int Write(char *from, int numBytes) {
int numWritten = WriteAt(from, numBytes, currentOffset);
currentOffset += numWritten;
return numWritten;
}
int Length() { Lseek(file, 0, 2); return Tell(file); }
private:
int file;
int currentOffset;
};
#else // FILESYS
class FileHeader;
class OpenFile {
public:
OpenFile(int sector);
// Open a file whose header is located
// at "sector" on the disk
~OpenFile();
// Close the file
void Seek(int position);
// Set the position from which to
// start reading/writing -- UNIX lseek
int Read(char *into, int numBytes); // Read/write
bytes from the file,
// starting at the implicit position.
// Return the # actually read/written,
// and increment position in file.
int Write(char *from, int numBytes);
int ReadAt(char *into, int numBytes, int position);
// Read/write bytes from the file,
// bypassing the implicit position.
int WriteAt(char *from, int numBytes, int position);
int Length();
// Return the number of bytes in the
// file (this interface is simpler
// than the UNIX idiom -- lseek to
// end of file, tell, lseek back
char *name;
private:
FileHeader *hdr;
// Header for this file
int seekPosition;
// Current position within the file
int fileSector;
};
#endif // FILESYS
#endif // OPENFILE_H
fstest.cc (10K)
Back to top of Final
Changes
// fstest.cc
// Simple test routines for the file
system.
//
// We implement:
// Copy -- copy
a file from UNIX to Nachos
// Print -- cat
the contents of a Nachos file
// Perftest --
a stress test for the Nachos file system
//
read and write a really large file in tiny chunks
//
(won't work on baseline system!)
//
// Copyright (c) 1992-1993 The Regents of the University of California.
// All rights reserved. See copyright.h for copyright notice
and limitation
// of liability and disclaimer of warranty provisions.
#include "copyright.h"
#include "utility.h"
#include "filesys.h"
#include "system.h"
#include "thread.h"
#include "disk.h"
#include "stats.h"
#define TransferSize 200 // make it small, just to be difficult
//----------------------------------------------------------------------
// Copy
// Copy the contents of the UNIX
file "from" to the Nachos file "to"
//----------------------------------------------------------------------
void Print(char *);
void WriteMore(char *);
void
Copy(char *from, char *to)
{
FILE *fp;
OpenFile* openFile;
int amountRead, fileLength;
char *buffer;
// Open UNIX file
if ((fp = fopen(from, "r")) == NULL) {
printf("Copy: couldn't
open input file %s\n", from);
return;
}
// Figure out length of UNIX file
fseek(fp, 0, 2);
fileLength = ftell(fp);
fseek(fp, 0, 0);
// Create a Nachos file of the same length
DEBUG('f', "Copying file %s, size %d, to file
%s\n", from, fileLength, to);
if (!fileSystem->Create(to, fileLength))
{ // Create Nachos file
// if (!fileSystem->Create(to, 100)) {
// Create Nachos file
printf("Copy: couldn't
create output file %s\n", to);
fclose(fp);
return;
}
openFile = fileSystem->Open(to);
ASSERT(openFile != NULL);
// Copy the data in TransferSize chunks
buffer = new char[TransferSize];
while ((amountRead = fread(buffer, sizeof(char),
TransferSize, fp)) > 0)
openFile->Write(buffer,
amountRead);
delete [] buffer;
// Close the UNIX and the Nachos files
delete openFile;
fclose(fp);
printf("\n");
Print(to);
printf(" \nBefore calling the WriteMore
function :\n");
WriteMore(to);
printf(" \nAfter calling the WriteMore function :\n");
Print(to);
printf("Leaving the function COPY \n");
}
//----------------------------------------------------------------------
// Print
// Print the contents of the Nachos
file "name".
//----------------------------------------------------------------------
void
Print(char *name)
{
OpenFile *openFile;
int i, amountRead;
char *buffer;
printf(" PRINTING STARTED----------------\n");
if ((openFile = fileSystem->Open(name)) == NULL)
{
printf("Print: unable
to open file %s\n", name);
return;
}
buffer = new char[TransferSize];
while ((amountRead = openFile->Read(buffer,
TransferSize)) > 0)
for (i = 0; i < amountRead;
i++)
printf("%c", buffer[i]);
delete [] buffer;
delete openFile; // close the Nachos file
printf(" PRINTING ENDED ------------------\n");
return;
}
void FunctionOne(int x)
{
int i=0;
OpenFile * newOpenFile = fileSystem->Open("small");
printf(" Printing the file : %s by the thread %d for the
%d time.\n",newOpenFile->name, x,++i);
Print(newOpenFile->name);
// currentThread->Yield();
printf("Removing the file : %s by the thread %d
\n",newOpenFile->name,x);
delete newOpenFile;
fileSystem->Remove("small");
printf(" Thread %d about to finish\n",x);
}
void FunctionThree(int x);
void FunctionTwo(int x)
{
int i=0;
OpenFile *newOpenFile = fileSystem->Open("small");
// Thread *t3 = new Thread("Three");
// t3->Fork(FunctionThree, 3);
currentThread->Yield();
currentThread->Yield();
printf("Printing the file: %s by the thread %d for
the %d time. \n", newOpenFile->name, x, ++i);
currentThread->Yield();
currentThread->Yield();
Print(newOpenFile->name);
currentThread->Yield();
printf("\n Printing the File : %s : second time from
the Thread: %d :\n", newOpenFile->name, x);
Print(newOpenFile->name);
/*
printf("Just before the %d READ\n", i+1);
printf("Printing the file: %s by the thread %d for
the %d time. \n", newOpenFile->name, x, ++i);
Print(newOpenFile->name);
// currentThread->Yield();
printf("Just before the %d READ\n", i+1);
printf("Printing the file: %s by the thread %d for
the %d time. \n", newOpenFile->name, x, ++i);
Print(newOpenFile->name);
// currentThread->Yield();
printf("Just before the %d READ\n", i+1);
printf("Printing the file: %s by the thread %d for
the %d time. \n", newOpenFile->name, x, ++i);
Print(newOpenFile->name);
// currentThread->Yield();
*/
delete newOpenFile;
printf("About to finish Thread:%d:\n", x);
}
void FunctionThree(int x)
{
int i=0,position;
char *writeString = new char(100);
printf("running the thread %d starting with the function :
FunctionThree\n\n", x);
OpenFile *newOpenFile = fileSystem->Open("small");
position = newOpenFile->Length();
newOpenFile->Seek(position);
printf("Just before the %d write\n", i+1);
sprintf(writeString," Writing by thread time\n" );
newOpenFile->Write(writeString, strlen(writeString));
Print("small");
// currentThread->Yield();
printf("Just before the %d write\n", i+1);
sprintf(writeString," Writing by thread %d into the File for
the %d time\n", x, ++i);
newOpenFile->Write(writeString, strlen(writeString));
// currentThread->Yield();
printf("Just before the %d write\n", i+1);
sprintf(writeString," Writing by thread %d into the File for
the %d time\n", x, ++i);
newOpenFile->Write(writeString, strlen(writeString));
// currentThread->Yield();
printf("Just before the %d write\n", i+1);
sprintf(writeString," Writing by thread %d into the File for
the %d time\n", x, ++i);
newOpenFile->Write(writeString, strlen(writeString));
// currentThread->Yield();
}
void SynchronizationTest()
{
Thread *t1 = new Thread("one");
Thread *t2 = new Thread("two");
t1->Fork(FunctionOne, 1);
t2->Fork(FunctionTwo, 2);
return;
}
//----------------------------------------------------------------------
// PerformanceTest
// Stress the Nachos file system
by creating a large file, writing
// it out a bit at a time, reading
it back a bit at a time, and then
// deleting the file.
//
// Implemented as three separate
routines:
// FileWrite -- write
the file
// FileRead -- read the
file
// PerformanceTest --
overall control, and print out performance #'s
//----------------------------------------------------------------------
#define FileName "TestFile"
#define Contents "1234567890"
#define ContentSize strlen(Contents)
#define FileSize ((int)(ContentSize
* 5000))
static void
FileWrite()
{
OpenFile *openFile;
int i, numBytes;
printf("Sequential write of %d byte file, in
%d byte chunks\n",
FileSize, ContentSize);
if (!fileSystem->Create(FileName, 0)) {
printf("Perf test: can't create
%s\n", FileName);
return;
}
openFile = fileSystem->Open(FileName);
if (openFile == NULL) {
printf("Perf test: unable
to open %s\n", FileName);
return;
}
for (i = 0; i < FileSize; i += ContentSize)
{
numBytes = openFile->Write(Contents,
ContentSize);
if (numBytes < 10)
{
printf("Perf test: unable to write %s\n", FileName);
delete openFile;
return;
}
}
delete openFile; // close
file
}
static void
FileRead()
{
OpenFile *openFile;
char *buffer = new char[ContentSize];
int i, numBytes;
printf("Sequential read of %d byte file, in %d
byte chunks\n",
FileSize, ContentSize);
if ((openFile = fileSystem->Open(FileName)) ==
NULL) {
printf("Perf test: unable
to open file %s\n", FileName);
delete [] buffer;
return;
}
for (i = 0; i < FileSize; i += ContentSize)
{
numBytes = openFile->Read(buffer,
ContentSize);
if ((numBytes < 10)
|| strncmp(buffer, Contents, ContentSize)) {
printf("Perf test: unable to read %s\n", FileName);
delete openFile;
delete [] buffer;
return;
}
}
delete [] buffer;
delete openFile; // close
file
}
void
PerformanceTest()
{
printf("Starting file system performance test:\n");
stats->Print();
FileWrite();
FileRead();
if (!fileSystem->Remove(FileName)) {
printf("Perf test: unable to remove
%s\n", FileName);
return;
}
stats->Print();
}
void WriteMore(char *to)
{
OpenFile *fileToBeWrtn = fileSystem->Open(to);
int position = fileToBeWrtn->Length();
printf("the Position to set to writeAt:%d:", position);
fileToBeWrtn->Seek(position);
char *StringToBeWritten = "Writing More in the WritMore
Function into the file\n";
fileToBeWrtn->Write(StringToBeWritten, strlen(StringToBeWritten));
strcpy(StringToBeWritten,"Writing the second time time\n");
fileToBeWrtn->Write(StringToBeWritten, strlen(StringToBeWritten));
strcpy(StringToBeWritten,"Writing More for the Third time
time\n");
fileToBeWrtn->Write(StringToBeWritten, strlen(StringToBeWritten));
delete fileToBeWrtn;
return;
}
Back to top of Final
Changes
main.cc (7K)
Back to top of Final
Changes
// main.cc
// Bootstrap code to initialize the operating system kernel.
//
// Allows direct calls into internal operating system functions,
// to simplify debugging and testing. In practice,
the
// bootstrap code would just initialize data structures,
// and start a user program to print the login prompt.
//
// Most of this file is not needed until later assignments.
//
// Usage: nachos -d <debugflags> -rs <random seed #>
// -s -x <nachos file> -c <consoleIn>
<consoleOut>
// -f -cp <unix file> <nachos
file>
// -p <nachos file> -r <nachos
file> -l -D -t
//
-n <network reliability> -m <machine id>
//
-o <other machine id>
//
-z
//
// -d causes certain debugging messages to be
printed (cf. utility.h)
// -rs causes Yield to occur at random (but repeatable)
spots
// -z prints the copyright message
//
// USER_PROGRAM
// -s causes user programs to be executed in
single-step mode
// -x runs a user program
// -c tests the console
//
// -shell load shell into the nachos, user program
shell
// is located at userprog/nachos.shell/
//
// FILESYS
// -f causes the physical disk to be formatted
// -cp copies a file from UNIX to Nachos
// -p prints a Nachos file to stdout
// -r removes a Nachos file from the file system
// -l lists the contents of the Nachos directory
// -D prints the contents of the entire file
system
// -t tests the performance of the Nachos file
system
//
// NETWORK
// -n sets the network reliability
// -m sets this machine's host id (needed for
the network)
// -o runs a simple test of the Nachos network
software
//
// NOTE -- flags are ignored until the relevant assignment.
// Some of the flags are interpreted here; some in system.cc.
//
// Copyright (c) 1992-1993 The Regents of the University of California.
// All rights reserved. See copyright.h for copyright notice
and limitation
// of liability and disclaimer of warranty provisions.
#define MAIN
#include "copyright.h"
#undef MAIN
#include "utility.h"
#include "system.h"
// External functions used by this file
extern void ThreadTest(void), Copy(char *unixFile, char *nachosFile);
extern void Print(char *file), PerformanceTest(void);
extern void StartProcess(char *file), ConsoleTest(char *in, char
*out);
extern void MailTest(int networkID);
extern void SynchronizationTest();
//----------------------------------------------------------------------
// main
// Bootstrap the operating system kernel.
//
// Check command line arguments
// Initialize data structures
// (optionally) Call test procedure
//
// "argc" is the number of command line arguments (including
the name
// of the command) -- ex: "nachos
-d +" -> argc = 3
// "argv" is an array of strings, one for each command line
argument
// ex: "nachos -d +" -> argv = {"nachos",
"-d", "+"}
//----------------------------------------------------------------------
int
main(int argc, char **argv)
{
int argCount;
// the number of arguments
// for a particular command
DEBUG('t', "Entering main");
(void) Initialize(argc, argv);
#ifdef THREADS
ThreadTest();
#endif
for (argc--, argv++; argc > 0; argc -= argCount,
argv += argCount) {
argCount = 1;
if (!strcmp(*argv, "-z"))
// print copyright
printf (copyright);
#ifdef USER_PROGRAM
if (!strcmp(*argv, "-x"))
{ // run a user program
ASSERT(argc > 1);
#ifdef CHANGED
shellConsole = new Console(NULL,
NULL, ShellRead, ShellWrite, 0);
// initialized a console
for user program
#endif // CHANGED
StartProcess(*(argv + 1));
argCount = 2;
#ifdef CHANGED
interrupt->Halt();
// shut down nachos, return from
// StartProcess only when the
// executable file does not exist.
#endif // CHANGED
} else if (!strcmp(*argv,
"-c")) { // test the console
if (argc == 1)
ConsoleTest(NULL, NULL);
else {
ASSERT(argc > 2);
ConsoleTest(*(argv + 1), *(argv + 2));
argCount = 3;
}
interrupt->Halt();
// once we start the console, then
// Nachos will loop forever waiting
// for console input
}
#ifdef CHANGED
if (!strcmp(*argv,"-shell")) { // add
`-shell' option
shellConsole = new Console(NULL,
NULL, ShellRead, ShellWrite, 0);
// initialize a console
used for shell and user program
StartProcess("nachos.shell/shell");
// load user program
shell into nachos
interrupt->Halt();
// shut down nachos. return from
// StartProcess
only when the `shell' is not found
}
#endif // CHANGED
#endif // USER_PROGRAM
#ifdef FILESYS
if (!strcmp(*argv, "-cp")) {
// copy from UNIX to Nachos
ASSERT(argc > 2);
fprintf(stderr,"Calling
the Copy function in Main");
Copy(*(argv + 1), *(argv
+ 2));
SynchronizationTest();
argCount = 3;
} else if (!strcmp(*argv, "-p")) { //
print a Nachos file
ASSERT(argc > 1);
Print(*(argv + 1));
argCount = 2;
} else if (!strcmp(*argv, "-r")) { //
remove Nachos file
ASSERT(argc > 1);
fileSystem->Remove(*(argv
+ 1));
argCount = 2;
} else if (!strcmp(*argv, "-l")) { //
list Nachos directory
fileSystem->List();
} else if (!strcmp(*argv, "-D")) { //
print entire filesystem
fileSystem->Print();
} else if (!strcmp(*argv, "-t")) { //
performance test
Copy(*(argv + 1), *(argv + 2));
SynchronizationTest();
//
PerformanceTest();
}
#endif // FILESYS
#ifdef NETWORK
if (!strcmp(*argv, "-o"))
{
ASSERT(argc > 1);
Delay(2);
// delay for 2 seconds
// to give the user time to
// start up another nachos
MailTest(atoi(*(argv + 1)));
argCount = 2;
}
#endif // NETWORK
}
currentThread->Finish(); //
NOTE: if the procedure "main"
// returns, then the program "nachos"
// will exit (as any other normal program
// would). But there may be other
// threads on the ready list. We switch
// to those threads by saying that the
// "main" thread is finished, preventing
// it from returning.
return(0);
// Not reached...
}
[Note -- the proceeding info was taken directly - ver batim - from the slides of our oral presentation ]
Lessons Learned: NACHOS
Ramesh Muthyala, John Joachim,
Bindu Jain, John Schuck
CSCI 503 Spring 2000, IUPUI
Phase 1:
Comfortable w/ Programming/Designing abilities,
but …
Mailbox using semaphores, instead of condition
variables
Debugging skills learned
we expected a learning experience, but ...
Phase 2:
“complete” design (we worked separately)
Syscall () ordering ….
“Collective Lack” of syscall() knowledge
Problems with testing
“Resolution”: Design --> Test --> Design --->
Code --> Test --> Design --> Test
Phase 3:
A Positive experience -->
unexpectedly successful !!
We didn’t expect it to work, due to lack
of testing in Phase 2
“Good” grasp of virtual memory implementation
(just a bit rushed)
Phase 4:
…. Original Plan: Work on Phase 3 & 4 Concurrently
….
Foreknowledge of UNIX/Windows system calls a plus
John k Joachim:
| Grade for | Grade | Total possible |
|---|---|---|
| Homework #1 | 44 | 50 |
| Project #1 | 100 | 100 |
| Homework #2 | 25 | 50 |
| Project #2 | 75 | 100 |
| Project #3 | 90 | 100 |
| Project #4 | 100 | 100 |
ound 6 row(s)