[IMPORTANT] Davidson's Blog is moved to mszheng.com

Please notice that my blog is moved,

for further update, please refer to mszheng.com.

此部落格将停止更新，

请关注mszheng.com获取更多信息。

このブログは mszheng.comに移転しましたよ。

ぜひご覧になってください！

Memory Management, Paging

Page frames or frames: memory is partitioned into equal, fixed-size chunks

Pages: memory of processes are divided into chunks with same size

Pages fit into any free page frame.

Benefits: No external fragmentation. Relatively little internal fragmentation(a part of a page).

For each process, a page table is associated with it. It records the information about which

page is in which page frame.

Virtual Address = Page number + Page offset = vaddr / page size + vaddr % page size

Some calculations:

Suppose a logical address is 32 bits and a page is 8 kbytes

Bits of the logical address are used to address bytes within a page:

8kbytes = 2^10 * 2^3 = 2^13; least significant 13 bits

Number of bytes can be addressed with a logical address:

2^32

Number of logical pages:

2^20

If a PTE is 4 bytes, space required for the page table:

2^20*2*2 = 2*22 bytes, 22 bits to represent

Memory Management, part 2

Another way to partition memory is Dynamic Partition.

Partitions vary depending on the size of a process. The placement with dynamic allocation

is to allocate exactly the size of a process in the memory.

However, when processes exit, holes might be created between every two processes.

This is called External Fragmentation.

When OS move processes down to eliminate holes, larger free space are created.

This action is called Memory Compaction.

We need to know what is the maximum size of a process at load time. Otherwise, we

must be able to add to its partition, potentially relocating it.

To keep track of memory allocation, we can use Bitmaps.

Placement Heuristics:

Memory compaction is time-consuming. We can reduce compaction if we systematically

allocate memory. The following techniques give us an idea how this can be achieved.

First-fit, allocate the first block large enough, appears to be the BEST choice, leave

external fragmentation at start of memory

Next-fit, allocate the block where previous search ends at, a variation of first-fit,

free space becomes fragmented more rapidly

Best-fit, scans through the blocks and finds the most suitable block in size,

small, unusable fragments

Worst-fit, find the largest block

Quick-fit, keep multiple free lists for common block sizes,

fast allocation, harder to coalesce

Relocation:

a way to change the physical memory reference

Dynamic relocation:

execution-time binding of addresses, hardware translates to physical addresses as instructions are executed.

base address + relative address = physical address <= limit address

Basic problems that cause internal fragmentation and external fragmentation and so on...:

we assume processes are allocated to contiguous block of memory

Solution: Paging

To be continued...

Memory Management

The Quiz 1 is coming soon I am kind of falling behind the schedule. I decide to spend some times

to go over the concepts that have been covered in the lecture so hopefully I won't "fail" this course the second time.

I've been dealing with the memory management problems all the time when I implementing

the thread sub-system and system call functions.

Why should each process has its own address space? Why do we even come to this abstraction?

First, we want to protect the OS from being modified or trashed or whatever easily because of easy access to physical memory.

Second, we want to run multiple programs at once.

When multiple programs are running, two programs present: protection and relocation.

Address space creates a kind of abstract memory for programs.

It is a set of addresses for processes to address memory.

Each process then owns its private address space, continuous and contiguous.

An important concept to remember is "Address Translation". It is the process of mapping addresses in the programs, mostly referred to the variables or symbolic addresses that

programmers use, into physical addresses.

To deal with memory problems, two strategies are commonly used: swapping and virtual memory.

Swapping means to swap process in and out from memory and to put the inactive process

on the disk. Virtual memory allows program to run even when they are partially in main memory. This is insane technology! I will go over it later since there's quite a few things.

In the lecture, we discussed about the Partition problem. Process will grow as they run.

We must determine whether to partition the memory into fixed-size chunks or dynamically

allocate the memory. We want to allocate extra memory for a process to reduce the overhead

associated with swapping processes that no longer fit in out from the memory.

It is somewhat complicated here. Let's start over again.

When the space is no longer large enough for a process, it will be swapped out and it has

to wait until a lager hole in the memory becomes available. The static/fixed-size allocation

is simpler to implement, but it creates Internal Fragmentation. In this case, memory

is wasted if process in a partition is smaller. For programs that are larger than the partitions,

we have Overlay problems. Then those programs have to get the hell out of the memory. (:<)

Gotta sleep now.

To be continued...

os161 - fork(), part 2

If a process is running a user program in user mode and needs a system service, such as reading

data from a file, it has to execute a "trap" instruction to transfer control to the OS.

When an interrupt signal occurs, there has to be some reasons for the occurrence.

The information needed to be handled are pushed onto the stack in user space.

The system handler is just a function in os161 that takes a pointer to trapframe as argument.

In os161, we define a structure called trapframe, which describe what is saved on the stack

during entry to the exception handler. The first 4 32-bit arguments are passed in the 4

argument registers a0-a3 by convention. 64-bit arguments are passed in aligned pairs of

registers, either a0/a1 or a2/a3. The system call number is passed in the v0 register.

On success, the return value is passed in the v0 register. a3 is set to 0.

For example, 0 is returned to the child process after fork() succeed.

On failure, error code is passed in v0 and a3 is set to 1.

Upon syscall return, the PC stored in the trapframe (tf_epc) must be incremented by 4 bytes,

which is the length of one instruction. Otherwise the return code restart at the same point.

Look closely inside syscall() in kern/arch/mips/syscall/syscall.c, we shall see how it works.

In the case of fork(), the OS will pass the trapframe pointer and PID into sys_fork.

For the parent process, the syscall function will examine the return value(a PID or error code)

of sys_fork to set the register values. Then the parent process shall proceed.

In sys_fork(), the parent process will allocate some memory in the heap and make a copy

of the trapframe on the stack for the child process. A pointer to this trapframe will be passed into thread_fork().

Later the child will free the memory allocated previously by the parent on the heap.

Then the thread_fork() is called to create the a new thread structure for the child process.

What thread_fork() will do first is to allocate a new stack, get a new PID of the child, do some

address space copy from its parent, and it also copies the working directory.

After the new thread structure is set up, it will initialize the switch frame for the new thread.

But what the hell is a switchframe? This is actually the PCB(process control block) of

a thread. The sf registers of this "switchframe" will hold the arguments from

thread_fork(): a function poiner "entrypoint", the trapframe copied from the address space

of the parent process to the child process's, and some garbage "data2".

Then we call thread_make_runnable() to make the new thread runnable.

The funnction "entrypoint" will be implemented in syscall.c.

The child process will start at this function and free the trapframe passed to it.

It will create its own trapframe on the stack in its address space and sets up the

return values in the registers. It finally increment the program counter by 4 bytes and

calls mips_usermode to warp to user space.

Eventually, we will see fork returns twice:

0 and PID of child process.

This is my understanding so far, after a night without sleep. The next thing I will do is to

implement execv(), which is quite similar to runprogram().

OS161-Writing Fork(), part 1

In assignment 2, we are asked to implement fork in the system os161.

It has been said that implementing fork() is the most difficult part in this assignment and is very crucial to understand how new process are created.

Despite the very details of the thread subsystem in os161, we will step through the process of the implementation of fork() in order to deepen our understanding of system calls.

fork() does the following things:

- it makes a copy of the invoking process and makes sure that the parent and child processes

each observe the correct return value.

- it returns 0 to the child and a new PID to the parent.

- the core of the fork() system call will invoke "thread_fork()" in kern/thread/thread.c

to create a new kernel thread

The child process should inherit exactly the same state of the parent at the time the parent

had when it made the system call.

By inspecting the code of "runprogram()" in /kern/syscall/runprogram.c, we can get some

insights of how fork() can be implemented.

runprogram() will show us how a program returns user space after a system call.

runprogram() takes a "string" (or char *) program_name and return an integer(EINVAL if error). loadexec() is the core code to load an executable into memory.

loadexec() will

- call kstrdup() to make a new name for the process

- call vfs_open() to load the program / open the file,

- call as_create() to make a new address space ,

- replace the old address spaces of the current thread with the new address spaces,

- call as_activate to make the new address space "seen" by the processor,

- call load_elf() to load the executable indicated by its argument "entrypoint", a virtual address

- call as_define_stack() to set up the user stack region in the address space, which make the

stack pointer point back to USERSTACK, the initial stack pointer for the new process,

- wipe out the old address space,

- change the current thread's name to reflect the new process.

After this, enter_new_process(), in /kern/arch/mips/locore/trap.c,

is called to warp to user mode. This function is used to go to user mode after loading an executable. It creates an ersatz (what the heck is this, figure it out later) trapframe,

sets the program counter to a virtual address,

stores the "argc" into register tf_a0, stores the pointer to arguments

into register tf_a1, and sets the stack pointer. Finally it calls mips_usermode(&tf) to enter

user mode.

Now we will go through the code of fork() step by step.

fork() takes two arguments: a pointer to trapframe an integer (the PID of the parent process).

It will first malloc some spaces in the heap to copy the trapframe, because we might return

to user level and make another system call, which might change the trapframe, before the

child runs. The child will free the copy of the trapframe in the heap. Then we call thread_fork().

Honestly, I have no idea how to implement thread_fork() from scratch. This is super duper hard for me. But...so what? I am going to get the jobs done anyway.

To create a new thread, call thread_create().

We will stick some magic numbers on the bottom end of the stack to catch kernel stack overflow.

Then we need to allocate some memory to the new thread and create a new PID for it.

Then we need to set up various fields associated with the new thread.

For example, we need to copy the virtual address space and current working directory from

its parent.

To be continued...

CSC300 Service Learning: Website for the Global Roots Garden

I met with our service partner Sara and another classmate Andrew yesterday.
Up to this point, we have built a prototype of the website for the Global Roots Garden.
Andrew and I were both super busy during these two weeks. Fortunately, the website
does not require any fancy function. Web users can listen to the stories of the gardeners
by using the Google reader mp3 player embedded in the web page. Inspired from the website
http://mycitylives.com/, people can view the gardeners' profiles by clicking on a "seed" icon
spread on a image. They then will see the photo of the gardener who is telling the story so that people feel more connected to the story as if they are told by the gardener himself/herself.
I am also responsible for creating a different language version of the website, allowing people from different countries to access.

As a result, our contribution to the community and the neighborhood is positive. We can not see any change or consequence right away since the website is not online and the stories have not been uploaded to the server yet. However, our service partner Sara is quite satisfied with our cooperation. Due to the deadline of this course, our service also comes to an end. I hope this project will help foster the improvement of the cultural diversity within the city.