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.

CSC300 Service Learning: Storytelling

This should be posted a two weeks ago but I was too busy to write the thing down. I went to the the garden at St.Clair West & Bathurst to help our service partner, Sara, with interviewing a Chinese Woman, from Dongbei province in China. Surprisingly Sara learned Chinese before when she was teaching as a TA in Shanghai Jiao Tong University, in Shanghai.
Since Sara had difficulties fully understanding her words, she asked me to help translate the story and any questions/answers from the Chinese woman. This is very helpful for the story recording because there may be a chance the woman tell the story without understanding Sara's question. We still spent a whole afternoon to make sure the woman's telling the story relevantly. She mentioned her experience of growing food fifty years ago in China. She also told us what is her life like after she moved to Canada. She told us how different was the food grew locally in Toronto from the food she grew in Beijing. Eventually these stories will be visible to the public through the web. I was pleased that I helped collect the story and build the interface for more people to access to the story in this project. It was quite an amazing experience.

CSC300 Service Learning: Second Meeting

The second meeting was on Wednesday 2pm, March 9. The attendants were Andrew, Mariyam, Sara and I. Prior to the meeting, I had a chance to read part of Sara's paper about the Global Roots Project. She also gave us a few links to the websites that record stories told about specific geographic locations. One similar project is known as the "murmur" project. People listen to the stories and get to know the histories and ancedotes of the local people. The "murmur" project unveiled the private truths and tales that make up the city. Information hidden from eyes and things being forgotten by the new generation are picked up and translated into the form of voices. I think this is something that people nowadays don't usually find in someone's blog or social networking spaces. Hence I'm provided a great opportunity to help improve the situation.

Our objective again is to help Sara with the project The Global Roots Project and get the audio recordings of the gardeners' narratives displayed within the garden and on the internet. More precisely, the Global Roots garden we provide services for is one of the two locations in Toronto that the Stop Community Food Center operates. People from different ethnic communities are given a 20-by-13 ft plot to grow non-local vegetables. There are different events going on each week for them to socialize. The design of the garden and the diversity of the plants tell the story of how people share their cultures. Inspired by the "murmur" project, the Global Roots Project will also record the stories of all the gardeners in all languages. The stories told in other languages other than English will be translated. Although it's suggested to listen to the story throughout the garden, we still need to build a website for the larger public.

During the meeting we discussed the rough idea of the website we are going to build. Andrew and I will be responsible for it. We consider to put a image of the garden with plots. Stories are wrapped in a tag or label or button scattered throughout the image like a geographic location in a map. By clicking the the tag/label/button, people get access to the audio files of the stories.
We still need to design the different level of the website. We also considered the possibilities to have interactive feature such as providing comments or feedback. However, such interaction may require a database in the back-end to store all the information sent by users and add more
complexity to the project.

CSC300 2011 Winter Service Learning, First Meeting

Today Andrew, Mariyam and I met with our service partner, Sara, at Noir Cafe near The Stop Community Food Center. She briefly introduced The Global Root Project to us and brought us to the Stop Green Barn, located at St. Clair and Christie.

Our main duties associated with this project include building a website that host the oral histories of the gardeners in the neighborhood and creating the audio installation within the garden. The primary goal is to allow people in the community to get more familiar with the history and background of the local green food and urban agriculture. People may hear about the concept but they seldom have the chances to directly access to the stories behind the scenes. People get the source of information directly through listening to a short storytelling audio clip, which is more reliable.

The gardeners being interviewed by our service partner Sara come from all over the world such as Canada, India, China, Kenia, and etc. Most of them is able to speak English. People with different cultural background share their knowledge of food, gardening here.

Test 3 Q3 review - Problem Solving

Below is the last question in test 3 i did hours ago. I wrote down the proof briefly which may not be that convincible, so i decide to prove it again.

Prove L(1*(0+e)1*(0+e)1*) = L2, the language has at most two zeros.

To prove the equivalence, we actually prove that for any element x , it can be represented by
L(1*(0+e)1*(0+e)1*) or L2. The former one looks a little bit complicated but actually it is possible to simplify it to make the proof much easier and shorter. By applying the distributivity, the transformation is going to be like:
L(1*(0+e)1*(0+e)1*) <=> L((1*0+1*e)(1*0+1*e)1*) , apply identity and annihilator for concatenation here, we get L((0+1*)(0+1*)1*), then apply idempotence of Kleene star, the simplest form is L((0+1*)(0+1*)).
Now, we are really just proving L((0+1*)(0+1*)) = L2.

In first part, we prove L((0+1*)(0+1*)) is a subset of L2.
L2 tells us how we rewrite L((0+1*)(0+1*)), that is to say, the number of zero is crucial.
It's definitely true by just looking at L((0+1*)(0+1*)), but we need demonstrate it with stronger reason. All cases include zero-free, one zero and two zeros. (0+1*) has either one zero or repetition of 1 or e. Then the concatenation of two (0+1*) has two zeros at most which satisfies L2. Then x \in L((0+1*)(0+1*)) implies x \in L2.

In second part, we prove L2 is a subset of L((0+1*)(0+1*)).
In this part, the setting for the typical elemtent x depends on L((0+1*)(0+1*)).
Since there are at most two zeros, i don't think there are too much things to worry about.
We just ensure x can be zero-free or with one zero or with two zeros.
x = (0+1/e/1*)(0+1/e/1*), (0+1*) is satisfying the language L((0+1*)(0+1*)) here.
Hence, the proof is done.

For such questions, once the languages on both sides are well understood, the proof will be just following the formal procedure.

Chapter Seven Review

#############
Formal Language:
#############
Any set of strings can be empty, finite, or infinite.
Length of string: s, number of symbols in s, ex: "+"=1, "e"=0.

#############
Regular Expressions(Regex):
#############
Basis : empty, empty string, one-symbol character;
Kleene star can be used to restrict the pattern of a regex:
even or odd numbers of some characters;
Idempotence of Kleene star: R** = R*
Distributivity: (A(B+C)) = (AB+AC), ((B+C)A) = (BA + BC)

Proving equality of two languages => Prove mutual inclusion:
1. Analyze the pattern of a language and divide into pieces if possible;
2. Transformations: in general case, expand some terms to make up the equality;
3. Check from both directions, conclusion.

###
FSA
###
Proof procedure, induction:
Basis: x=e, &*(q_e,x)=q_e. P(e) true.
Induction Step: Assume x = x'a, assume P(x'). Analyze the cases.
In all cases, x = x'a and &*(s,x) = &*(q_e,x'a)=&(&*(q_e,x'),a)
according to our induction hypothesis.
Then using the transistions functions, we prove P(x') => P(x), in all cases.

####
NFSA
####
Difference: Each transition takes the machine to a subset of states rather than a unique
state.

Notes:
Every regex has equivalent NFSA.
Every NFSA has equivalent DFSA.