OSDev.org

Well, here I am again to report about my forthcoming with os development:

I am about to implement dynamic selfreferring data structures such as circular lists and queues to handle the management of the different queues and lists in process management module.

So far, I have two queues for runnable processes: round robin and realtime. Round robin processes are moved round the queue as long as they are runnable. realtime processes are put onto the realtime-queue, taken away from there to do their job and then are moved to the blocked/sleeping queue.

This is because I think, realtime processes are to do short, quick jobs as handling hard disk, mouse, tty-consoles and so forth. Keyboard handling and virtual consoles on local computer are handled by a special layer in the kernel thing. Real time processes don't have to sit on ressources eternally. they don't have to perform lengty calculations. They do their job and then suspend til the next time they are requested.

these queues get input from their rear. elements are taken from the front of the queues, so one process after another is given to the processor.

I have to implement functions like suspend(), sleep(),... which abstract queue operations.

Now I am about to think about implementng the list for sleeping/blocking processes. I think I will extend my queue functions with three functions: pick_element(key),delete_element(key).

that's it for now.

stay safe

beyond infinity wrote:
Now I am about to think about implementng the list for sleeping/blocking processes. I think I will extend my queue functions with three functions: pick_element(key),delete_element(key).

well, i'm not 100% sure about what you call a "key" nor about what is "picking" an element using its key (retrieving a process using its PID ?), but if this is the case, i would say that lists aren't the best way to handle key/value pairs.
I would rather have an array, or a hashtable or a B+Tree for that kind of stuff, which will resolve the PID into a pnfo* pointer. Using that pointer, the queues will be able to remove the item immediately (provided that they have a "back" pointer)...

Now of course it depends on how often you must delete any process from the queue ...

Good point, pype.

I gonna implement a binary tree data structure & according functions for process bookkeeping (maybe this is better then to traverse an entire list - crawling throu only one branch of the process tree...) But nevertheless: I am not sure if recursive programming is good style in an operating system. And the example sources I have looked at in internet mostly work with recursion. Should I get rid of that and restyle the functions to an iterative programming style?

Furthermore: how to find an element in an unordered tree? Would it be better to have that thing ordered?

What I consider the key at the moment (and it works, I am astonished) is the adress of the process structure. A list element gets pointers to its next and previous element (in the queues only to the next element) and the element points to the process structure it refers to. Should I extend this or restyle this to search/find processes by PID (or similar?).

pick_element() - this means: take an element specified by the key (PID/pointer to process struct) out of a given list.

When I use the queue mechanism, I only need to take the first element from the list and do with it what ever I want - even put it at the list's end again - this I do in round robin as long as a round robin process is runnable. bad idea?