how 2 start multitasking?

Question about which tools to use, bugs, the best way to implement a function, etc should go here. Don't forget to see if your question is answered in the wiki first! When in doubt post here.
AR

Re:how 2 start multitasking?

Post by AR »

Try a tree with a linked list at the same time:

Code: Select all

struct Thread
{
     Thread *NextThreadInProcess;
     Thread *GlobalTreeLeft;
     Thread *GlobalTreeRight;
     Process *Parent;
     /* ... */
};
This way you can find the process then just go Process->Threads and cycle through (useful for terminating every thread, and enumerating) and you also have a global tree for fast searching by TID.
User avatar
Neo
Member
Member
Posts: 842
Joined: Wed Oct 18, 2006 9:01 am

Re:how 2 start multitasking?

Post by Neo »

Does anyone here who has implemented multi-tasking use a binary tree.?
If so how do you manage parents that may have more than 2 directly related child processes?
Only Human
HOS

Re:how 2 start multitasking?

Post by HOS »

A binary tree is just a data structure for storing/sorting a collection of "nodes." There is no inherent limit on how many nodes total may be in the structure. You could design a process heirarchy that contained a binary tree structure for each process. Each node of this binary tree could be the process identifier number for a child process. Each child process could have its own binary tree of children and/or a binary tree (or other structure) representing multiple threads of execution. What makes a binary tree a binary tree is that each node can have at most two "children" for searching purposes but this concept is not directly related to the concept of a process having "children." Each member of the binary tree (there could be hundreds) can be a child of the original parent process.
User avatar
Neo
Member
Member
Posts: 842
Joined: Wed Oct 18, 2006 9:01 am

Re:how 2 start multitasking?

Post by Neo »

I do know what binary trees are.
I just wanted to know if anyone had some other method of using binary trees for PID's when a parent has more than 2 directly realted children.
If not then I don't think we could use binary tree for a process hierarchy.
Corrections and Suggestions welcome.
Only Human
User avatar
Colonel Kernel
Member
Member
Posts: 1437
Joined: Tue Oct 17, 2006 6:06 pm
Location: Vancouver, BC, Canada
Contact:

Re:how 2 start multitasking?

Post by Colonel Kernel »

I think what HOS was suggesting is that you could track processes via a tree of trees. Your parent/child process hierarchy would be structured as a general tree, so each parent process could have as many children as you like. For each process (i.e. -- each node in the general tree), rather than store its children as a list, you can store them in a binary tree sorted by PID. This would provide a faster lookup by PID when processes have many children (assuming the trees are well-balanced).

If you wanted to look up child processes based on some criteria other than PID, use yet another tree... This is just like indexing in databases, only in memory.

@HOS and Pype: Is my interpretation correct?
Top three reasons why my OS project died:
  1. Too much overtime at work
  2. Got married
  3. My brain got stuck in an infinite loop while trying to design the memory manager
Don't let this happen to you!
User avatar
Neo
Member
Member
Posts: 842
Joined: Wed Oct 18, 2006 9:01 am

Re:how 2 start multitasking?

Post by Neo »

I guess an example might help clarify things better.
Consider this situation, I have a total of 13 processes.
1 parent (root) which has 3 child processes.
Each child (of the root) has in turn 3 child processes each.
That's it (no more children).
Now how would this be represented as a binary tree? ???

This is how a general tree of it would look (hope the formatting doesn't mess it too much)

Code: Select all

         o

  o      o      o

o o o  o o o  o o o 
Only Human
User avatar
Candy
Member
Member
Posts: 3883
Joined: Tue Oct 17, 2006 11:33 pm
Location: Eindhoven

Re:how 2 start multitasking?

Post by Candy »

Neo wrote: I do know what binary trees are.
I just wanted to know if anyone had some other method of using binary trees for PID's when a parent has more than 2 directly realted children.
If not then I don't think we could use binary tree for a process hierarchy.
Corrections and Suggestions welcome.

You give EACH process its own entire binary tree. ALL children in the tree belong to that one process as children.

You make a free-form tree of the processes and put all the children of a given parent in a binary tree listing that level. It's hard to visualise, but look at the normal parent-child tree as the X and Y axis of the tree, and the binary tree used only for storing practicality as the Z axis. You don't use the binary tree itself.
User avatar
Neo
Member
Member
Posts: 842
Joined: Wed Oct 18, 2006 9:01 am

Re:how 2 start multitasking?

Post by Neo »

So the binary tree is created only for a PID lookup?
Nothing else?
Only Human
User avatar
Pype.Clicker
Member
Member
Posts: 5964
Joined: Wed Oct 18, 2006 2:31 am
Location: In a galaxy, far, far away
Contact:

Re:how 2 start multitasking?

Post by Pype.Clicker »

yep, that was my purpose: binary tree for PID lookup. Note that i don't mind about parents of a thread, only for processes. So all i need to keep is what process holds a given thread. From there i can have all the threads of the process or retrieve a specific thread from its identifier.
User avatar
Neo
Member
Member
Posts: 842
Joined: Wed Oct 18, 2006 9:01 am

Re:how 2 start multitasking?

Post by Neo »

Ok (got that cleared at last) :).
So do you use a splay tree for this or is that overkill.
Only Human
User avatar
Candy
Member
Member
Posts: 3883
Joined: Tue Oct 17, 2006 11:33 pm
Location: Eindhoven

Re:how 2 start multitasking?

Post by Candy »

Neo wrote: Ok (got that cleared at last) :).
So do you use a splay tree for this or is that overkill.
From a practical point of view, I'd use a linked list. It's easy to implement, doesn't have a lot of overhead and there's no point trying to get more performance. You're mainly going to use it for killing child threads -> you'll always need all of them then.
User avatar
Brendan
Member
Member
Posts: 8561
Joined: Sat Jan 15, 2005 12:00 am
Location: At his keyboard!
Contact:

Re:how 2 start multitasking?

Post by Brendan »

Hi,
Candy wrote:From a practical point of view, I'd use a linked list. It's easy to implement, doesn't have a lot of overhead and there's no point trying to get more performance. You're mainly going to use it for killing child threads -> you'll always need all of them then.
From an even more practical point of view, first decide on how your OS will behave - specifically, what the relationship between processes, threads, etc will be.

For my OS a process is just a container, all threads belong to a process, and threads get CPU time (while processes never do). If a thread spawns another thread, then both threads will belong to the same process. If only one thread belongs to a process and that thread terminates, then the process itself is terminated.

For this I use an array of "process data areas" (for e.g. "PDA[process_ID"). Each process data area contains a list of thread IDs and some other information (process name, number of threads, amount of CPU time used by threads, etc).

For threads there's an array of "thread data areas" (for e.g. TDA[thread_ID"). Each thread data area contains the process_ID for the process that the thread belongs to and some other information (FPU/MMX/SSE state save area, message queue head & tail, thread name, etc).

Basically, I use arrays and very little else. The nice thing is that everything is a fixed size with a fixed position in an array, and finding one thing from another is very fast (without searches) - for e.g. finding the address of a PDA from a thead ID involves 2 shift lefts and one memory read.

Some OS's allow processes to fork or exec other processes and keep track of which process started what, where killing one process will automatically kill it's "child" processes. Here you'd want something (a tree) to keep track of the relationship between processes. For my OS this isn't necessary, as a process is never owned by anything and is never a "child".

For example, imagine process A is a command line interpretter, and the user types in "edit something.txt". Process B would be created for the text editor. Now, if the user kills the CLI what happens to the text editor?

For a command line environment where the CLI is unusable until you exit the text editor it makes more sense for the text editor to be a child process. For a GUI environment, it's better to be able to start 5 text editors and exit the CLI leaving the text editors running.


Cheers,

Brendan
For all things; perfection is, and will always remain, impossible to achieve in practice. However; by striving for perfection we create things that are as perfect as practically possible. Let the pursuit of perfection be our guide.
HOS

Re:how 2 start multitasking?

Post by HOS »

Brendan wrote: For a command line environment where the CLI is unusable until you exit the text editor it makes more sense for the text editor to be a child process. For a GUI environment, it's better to be able to start 5 text editors and exit the CLI leaving the text editors running.
I like this idea and have been planning to implement it as well. However, I was thinking to "re-parent" all graphical processes to the GUI/window manager process so that they will at least stay a part of the process tree and could all be killed by killing the GUI process. Not sure if that is where I'll end up going or not...

@Colonel Kernel: That interpretation is mostly correct. My thought was that each process had two trees (or some such structures): One of PID's of children processes and one of threads in the current process. The thing I think Neo was hiccupping on for a bit was that the "child nodes" of PID's in the binary tree representing processes were not really "child processes." They were simply children of that node in the tree, used for searching, not actually representing the process tree as a binary tree. Rather, all nodes in the binary tree are direct children of the process.
User avatar
Brendan
Member
Member
Posts: 8561
Joined: Sat Jan 15, 2005 12:00 am
Location: At his keyboard!
Contact:

Re:how 2 start multitasking?

Post by Brendan »

Hi,
HOS wrote:
Brendan wrote: For a command line environment where the CLI is unusable until you exit the text editor it makes more sense for the text editor to be a child process. For a GUI environment, it's better to be able to start 5 text editors and exit the CLI leaving the text editors running.
I like this idea and have been planning to implement it as well. However, I was thinking to "re-parent" all graphical processes to the GUI/window manager process so that they will at least stay a part of the process tree and could all be killed by killing the GUI process. Not sure if that is where I'll end up going or not...
I'm using "connections to a user interface", where a single thread can have multiple connections to multiple user interfaces. When UI connections need to be broken by the UI (for e.g. if the user logs off), the UI sends a "disconnected" message to each of it's clients and ignores anything they send after that.

By "re-parenting" the process, the process would need a parent in the first place so you'll need a tree structure to keep track of the relationships between processes. This idea (with or without re-parenting) generally breaks if you need more than one parent for a process. For example, if you've got a web browser process and the user starts a second web browser, you may need to load everything from disk again to start a new process (no data sharing). OSs that use the "process tree" model get around this by cloning the address space of one process to create the new process (which can be messy and/or less efficient as you'd need to know what data should be shared by both processes).

For my OS I can just send a message to the web browser process telling it to create an extra connection to a UI (it may or may not spawn new threads to handle the extra connection). This is faster than starting a whole new process, and also allows long running processes. An example of this would be the "system log" which is always running in the background - it uses a single thread that makes and breaks connections to UIs as needed. For the "process tree" model you'd need to set up a client/server relationship and create client processes to display the log (more overhead due to creating and destroying processes, more IPC overhead, etc).

Of course a fully asynchronious event driven programming model helps a lot - the single "system log" thread can accept new data for the log while writing cached data to disk and managing hundreds of UI connections (without "UI responsive-ness" being effected) - not too bad for a single thread...


Cheers,

Brendan
For all things; perfection is, and will always remain, impossible to achieve in practice. However; by striving for perfection we create things that are as perfect as practically possible. Let the pursuit of perfection be our guide.
viral

Re:how 2 start multitasking?

Post by viral »

Hey its easy to assing PID to tasks arrange in binary tree (NOTE: one parent can have atmost 2 childs)..
1. Assign Left child '0'
2. Right child '1'
3. To know PID of perticular task traverse it from root till task. The no (binary 0010...) is PID of perticular task..

Works only when we restrict overself in 2 child .
Post Reply