-
Notifications
You must be signed in to change notification settings - Fork 0
Project2
Danny Chen edited this page May 6, 2015
·
46 revisions
Instructed by Xu Wei
Chen Xiaoqi, Ku Lok Sun, Wu Yijie, Zhang Hanrui
Due on May 6, 2015
creat, open, read, write, close, and unlink, documented in syscall.h.
-
We need to check the users' argument passed to kernel
1. the users' argument passed to kernel should be legitimate 2. Only root can invoke halt()- Returns values defined in test/syscall.h 4. Return -1 on error
-
If there's exception, the user process should be terminated cleanly
- Use UserProcess.readVirtualMemory and UserProcess.writeVirtualMemory; string arguments are null-terminated and shorter than 256 bytes
- Support 16 fd 3. Allow closing stdin/stdout 4. Return error if ThreadedKernel.fileSystem.open() failed 5. fd can be reused; sane fd# for different process may mean different file
Constant
- STDIN = 0
- STDOUT = 1
- MAXFD = 16
Class variable
- fileRecords: hashMap, filename -> (open count, calledUnlink)
FileDescriptor
- FileName
- File
- FileRecord
UserProcess() in UserProcess.java
...
fds = new array of FileDescriptor Objects
stdin = UserKernel.console.openForReading()
stdout = UserKernel.console.openForWriting()
# stdin and stdout have no file name and no file record
fds[STDIN] = new FileDescriptor(null, stdin, null)
fds[STDOUT] = new FileDescriptor(null, stdout, null)
...
complete handleSyscall(int syscall, int a0, int a1, int a2, int a3) by implementing the following handler:
handleHalt() in UserProcess.java
process = UserKernal.currentProcess();
if process is first process (root process)
Machine.halt()
else
return -1;
handleCreat(a0) in UserProcess.java
filename = get string from virtual address a0
# find an unuse file descriptor
fdn = -1
for i in 0..15
if fds[i] == null
fdn = i
break
if fdn == -1
# No empty slot
return -1;
record = fileRecords[filename]
if record != null
if record.calledUnlink
return -1
# file name checked by file system
# Create file, clean the file if it exists (set file length to 0)
file = filesystem.open(filename, true)
if file == null
# filename is invaild or
# Too much file opened
return -1
if record = null
fileRecords[filename] = new FileRecord(1,false)
record = fileRecords[filename]
else
record.count += 1
fds[fdn] = new FileDescriptor(filename, file, record)
return fdn;
handleOpen(a0) in UserProcess.java
filename = get string from virtual address a0
fdn = -1
for i in 0..15
if fds[i] == null
fdn = i
break
if fdn == -1
# No empty slot
return -1;
record = fileRecords[filename]
if record != null
if record.calledUnlink
return -1
# file name checked by file system
# Create file, clean the file if it exists (set file length to 0)
file = filesystem.open(filename, true)
if file == null
# filename is invaild or
# Too much file opened
return -1
if record = null
fileRecords[filename] = new FileRecrd(1,false)
record = fileRecords[filename]
else
record.count += 1
fds[fdn] = new FileDescriptor(filename, file, record)
return fdn;
handleRead(fileDescriptor, a1, count) in UserProcess.java
buffer = get string from virtual address a1
# prevent index out of bound
if fileDescriptor >= MAXFD
return -1
# Get file
file = fds[fileDescriptor].file
# invalid file descriptor
if f == null
return -1
len = f.read(p,buffer,count)
return len
handleWrite(fileDescriptor, a1, count) in UserProcess.java
# prevent index out of bound
if fileDescriptor >= MAXFD
return -1
# Get file current position
file = fds[fileDescriptor].file
# invalid file descriptor
if f == null
return -1
# p seems always valid, p is internal state
len = write buffer to vitual address a1
return len
handleClose(fileDescriptor) in UserProcess.java
# prevent index out of bound
if fileDescriptor >= MAXFD
return -1
fd = fds[fileDescriptor]
# invalid fd
if fd == null
return -1
fd.file.close()
fds[fileDescriptor] = null
record = fd.record
if record.count == 1
if fd.name != null
fileRecords[fd.name] = null
if record.calledUnlink
if !filesystem.remove(fd.name)
return -1
else
record.count -= 1
return 0
handleUnlink(a0) in UserProcess.java
filename = get string from virtual address a0
record = fileRecords[filename]
if record == null
if !filesystem.remove(fd.name);
return -1
else
record.calledUnlink = true
return 0
- disk full
- no string to read
- invalid file descriptor, (hard code, > 16)
- read an write on same file? (use open, not creat to get fd)
- Cyclic reuse of disk; shall not full if file is unlinked properly. 100000*16 file creat/unlink.
- Cyclic reuse of fd; 1000*16 open/close fd pair, write should not write to wrong file.
- Different program opens different files; 1000*16 concurrent opening
- Write after close should cause exit(); unclosed handle should be closed after exit() or exception.
- Unlink the file while another process opened and is reading the file.
Multiple user processes.
- Allocating the machine's physical memory so that different processes do not overlap in their memory usage.
1. Allocate a fixed number of pages for the process's stack (8 pages)
2. a global linked list of free physical pages
3. Use synchronization where necessary when accessing the global linked list:
4. NOT acceptable to only allocate pages in a contiguous block
- Make UserProcess.readVirtualMemory and UserProcess.writeVirtualMemory work with multiple user processes
1. Maintain the pageTable for each user process
2.
The field TranslationEntry.readOnly should be set to true if the page is
coming from a COFF section which is marked as read-only.
3. always return the number of bytes transferred.
- Modify UserProcess.loadSections() so that it allocates the number of pages that it needs.
1. Based on the size of the user program
2. Set up the pageTable structure for the process so that the process is loaded into the correct physical memory pages.
3. exec() should return an error, if the new user process cannot fit into physical memory.
-
UserKernel class.
- use static LinkedList to hold free pages, initialize all physical pages as free:
initialize(){ ... for(i=0;i<number of pysical pages;++i){ add i to free page list } }- implement method
allocateFreePage()andreleaseFreePage(int)for UserProcess. The interrupt should be disabled when allocating free pages:
allocateFreePage(){ returnPage = -1 disable interrupt if list of free pages not empty returnPage = first page in the list restore interrupt return returnPage } releaseFreePage(int pn){ // may need to check argument disable interrupt add pn to the list of free pages restore interrupt } -
UserProcess class.
- use page table (array of TranslationEntry) for each user process
- read/write at virtual address instead of physical address,
use page table to implement
readVirtualMemoryandwriteVirtualMemory:
readVirtualMemory(vaddr){ get vpn (virtual page number) from vaddr entry = pageTable[vpn] if entry is invalid, return -1 get ppn (physical page number) from entry paddr = ppn * pageSize + offset of vaddr if paddr exceed memory length, return 0 copy to data buffer starting from paddr mark entry as used return actual copy length } writeVirtualMemory(vaddr){ get vpn from vaddr entry = pageTable[vpn] if entry is invalid or read-only, return -1 get ppn from entry paddr = ppn * pageSize + offset of vaddr copy from data buffer to memory starting from paddr mark entry as used and dirty return actual copy length }- modify
load,loadSectionsandunloadSectionsfor allocating pages:
load(){ ... (calculate the number of pages needed) ... create new pageTable for(int i=0;i<number of pages;++i){ pageTable[i] = TLE that map i to new allocated page } ... (load sections) }loadSections(){ ... for any section in program{ startPos = first virtual page number of section for(int i=0;i<section.length;++i){ entry = pageTable[startPos+i] endtry.readOnly = section.readOnly load entry.ppn to the section at position i } } }unloadSections(){ close program release all pages in pageTable clear pageTable }
- Stress test the paging system: A=B={a_ij=i+j}, calculate C=AB, A,B,C in M_NN, N=20.
- Test paging overlap by starting 2 or 4 processes, each writing a constant into memory for 10000 times (with sleeping/yielding), then read out all content and check if any is corrupt.
exec, join, and exit. (We will also implement rand() for user program to test)
1. Use readVirtualMemory and readVirtualMemoryString to pass data between kernel and user process
2. Bulletproof
3. A process should have a global unique ID; allow checking next ID to assign
4. Fork/join
1. Parent and Children should not directly share memory or fd
2. Only parent can join children; not grandparent
3. Parent can join even children exit abnormally
5. Exit
1. Upon exit, system do housekeeping (cleanup memory, close fd, etc)
2. Exception also cause exit
3. The exit code should pass to join() call
4. Abnormal exit code is <0
5. The last exit calls Kernel.kernel.terminate() to halt the machine
We mainly modify UserProcess.java. Following modifications are all done in class UserProcess.
Add variables in UserProcess.
- taskCounter: A counter of total number of process ever runned;
- taskPool: A hash table that maps process id of each existing task to its UserProcess object;
- pid: Obviously, the process id;
- parent: Parent process, null if no parent;
- childrenPool: Stores id's of children of the process;
- threadPool: Stores threads within the process;
- joiningPool: Stores threads waiting for current process to join, maps statusAddr to the thread joining to.
- exitStatus: Stores return values of exited processes.
public static int taskCounter
public static map<int, UserProcess> taskPool
private int pid
private UserProcess parent
private set<int> childrenPool
private set<KThread> threadPool
private map<int, KThread> joiningPool
private map<int, int> exitStatus
In public UserProcess(), add:
id = ++taskCounter
parent = null
childrenPool = new set<int>()
threadPool = new set<KThread>()
joiningPool = new map<int, KThread>()
We modify function execute such that when a new thread is forked, it is immediately inserted into the thread pool.
In public boolean execute(String name, String[] args), replace:
new UThread(this).setName(name).fork()
with:
UThread thread = new UThread(this).setName(name)
threadPool.insert((KThread)thread)
taskPool.insert(pid, this)
thread.fork()
The above part of modification will also be used when implementng fork().
To set parent field of a process, we need a function setParent.
Add function:
void public setParent(UserProcess process):
parent = process
To handle exit syscall, we
- Put the return value of current process into exitSTatus;
- Wake up all the threads waiting for the exiting process;
- Put the return value of current process into the correct address given by the process joins it;
- Free all its resources, including opened files;
- Remove its id from its parent's children pool, if it has a parent, and the global task pool;
- Shut the machine down if it is the last process running.
- Kill the current thread, which belongs to the exiting process.
private void handleExit(int status):
exitStatus.insert(pid, status)
for (addr, thread) in joiningPool:
writePhysicalMemory(addr, status)
thread.ready()
unloadSections()
# Close all file
for i in 0..15:
handleClose(i)
if parent != null:
parent.childrenPool.remove(id)
taskPool.remove(id)
if taskPool.size() == 0:
Kernel.kernel.terminate()
KThread.finish()
To handle exec syscall, we
- Create a new process of the correct class and set its parent to be the current process;
- Read the file name and arguments from memory via translation, if it fails, return -1;
- Call UserProcess.execute to get it running and registered, if it fails, return -1;
- If succeeded, insert the new pid into childrenPool of current process and return it.
private int handleExec(int fileAddr, int argc, int argv):
newProcess = newUserProcess()
newProcess.setParent(this)
String name = readVirtualMemoryString(fileAddr)
String[] args = readVirtualMemoryParameters(argc, argv)
if reading fails, return -1
bool flag = (int)(newProcess.execute(name, args))
if flag:
childrenPool.insert(newProcess.pid)
return newProcess.pid
else:
return -1
To handle join syscall, we
- Get the current thread;
- If the process to join is not a child of current process, declare an illegal syscall, kill current process and return -1;
- Otherwise, get the process to join, calculate and insert the physical address to place return value and current thread to joining pool of the process to join;
- Sleep current thread.
private int handleJoin(int id, int statusAddr):
thread = KThread.currentThread
if id not in childrenPool or id not in taskPool:
return -1
UserProcess joining = taskPool[id]
pAddr = getPhysicalAddr(statusAddr)
if getting address fails, return -1
joining.joiningPool.insert((pAddr, thread))
thread.sleep()
if the joining thread ends normally:
return 1
else:
return 0
- Put some statement after exit(0), make sure exit(0) function normally.
- Joining a children twice.
- exit(0) twice. Join a children who exit() twice
- exec() then exit parent; children should run normally.
- exec and join forming a chain; after 1000 level, the final children exit(), then the greatest parent should exit normally, at last.
- A children is joined and then caused exception; parent should continue normally.
- Run multiple processes. Let them call exit(0) in random order and check whether the machine terminates after the last process exits.
- Basic join cases. Let A legal join happen when there are two or more processes running.
- Multiple thread cases. Let one or more of the threads of the parent process join the child. Will be done after fork() implemented.
- Let a thread join a process that is not its child. Check whether it is correctly handled, i.e., the joining process gets killed.
- Basic exec cases. Call exec on legal executable files and check whether it runs well and whether its parent is correctly set.
- Call exec on files that do not exist. Check if the return value is correct.
- Call exec on illegal files that do exist. Check if the return value is correct.
extends PriorityScheduler; must do priority donation. We modified from the suggested solution.
1. Ticket transfer
1. Waiting thread transfer ticket to threads they waited for
2. Ticket count is the sum of owning ticket and all waiter's ticket, not maximum
2. Pick a thread which held the lottery
3. Capacity
1. Ticket number may be large; the actual ticket sum less than Integer.MAX_VALUE
2. Individual priority in [0,Integer.MAX_VALUE]
3. Scheduler should be efficient, not O(total ticket) time
4. Implement LotteryScheduler.increasePriority() and decreasePriority() for process
- lotteryLimit = Integer.MAX_INTEGER
- priorityMinimum = 1
- priorityMaximum = Integer.MAX_INTEGER
Change all method using PriorityQueue to LotteryQueue
LotteryQueue.pickNextThread()
lotterySum = 0
for all threads in waitQueue:
lotterySum += thread.effectivePriority
if waitQueue is empty:
return null;
ticket = random(1, lotterySum) # Include boundary
it = waitQueue.iterator();
next = it.next();
while(ticket > 0){
thread = it.next();
ticket -= thread.getThreadState(next).getEffectivePriority();
}
return thread;
LotteryQueue.donatePriority()
newDonation = 0;
if (transferPriority)：
for all threads in waitQueue:
newDonation += thread
if (newDonation == donation)
return
donation = newDonation;
if (this.resAccessing != null)：
this.resAccessing.resources.put(this , donation);
this.resAccessing.updatePriority();
ThreadState.updatePriority()
newEffectivePriority = originalPriority;
if (!resources.isEmpty()):
for each queue of resource holded by this thread:
LotteryQueue q = queue
newEffectivePriority += q.donation
if (newEffectivePriority == priority):
return;
priority = newEffectivePriority;
if (resourceWaitQueue != null)
resourceWaitQueue.donatePriority();
- Priority Inversion
- Big slow low-priority process blocking the resource needed by bursty, higher priority process, causing live lock. The system should eventually give more time slice to slow process.
- In above case, with priority donation there should not be live lock at all.
- Stress test: creating 10000 processes, with donation in chain, causing total lottery count to n^2.
- Accuracy test: create 10000 process half with priority 2 and half with priority 1, each only increment a counter on disk (causing block); calculate statistics after some time, check average and variance of wake-up count of two classes.
1. The system is indeed bullet-proof to strange user space behavior.
2. The file system worked as intended.
3. The exec()/join() worked as intended.
4. Due to the system's strict requirement over the alignment of argc and argv, some test cases failed to launch and was killed.