Processes and Tasks - is my understanding correct?

[Mercury1964]

I'm implementing scheduling and processes in my operating system. I think I understand what I have to do:

Task Struct

• PID
• Register struct (EFLAGS, EIP, ESP, EAX, etc.)
• Pointer to page directory
• Pointer to next task to run

Creating Tasks

• Allocate new page directory
• Copy program to new memory
• Set task's register struct's values to 0
• Set task's register struct's EIP to starting address
• Set task's register struct's ESP to stack address
• Place in queue

Running/Switching Tasks

• Run code until IRQ0 (PIT pulse)
• Save registers to current task's register struct
• Figure out which task to run next (from current task's pointer or by looping around the queue)
• Switch page directory to new task's
• Load registers from new task's register struct
• Jump to new task's EIP

It seems like I'm missing something. Is this correct? Is there a better way to do this?

Thanks,
John

[madanra]

A couple of thoughts:

• You will want to be able to switch tasks at times other than IRQ0, so the task switcher should be separate from the interrupt handler.
• You've described a round robin scheduler, which is fine to begin with, but you'll want to make sure that can be changed in the future.

[Mercury1964]

Is everything else sound?

[madanra]

Ah, well, I haven't actually implemented processes myself, so I can't be sure - there are probably a lot of other 'gotchas' that I've missed! Hopefully some others with more experience will share their wisdom.

[iansjack]

You might want to also consider how you end tasks and free up the resources they are using. This is not as entirely trivial as it may at first seem.

I presume that you are supporting just a single CPU at present so you don't need to worry about the complications involved in multiple CPUs.

[Brendan]

Hi,

First, I think you need to define "task" - it's not like "process" or "thread" (which have reasonably well defined meanings), and different OSs (and different books, etc) use the word "task" for different/incompatible things.

I'm implementing scheduling and processes in my operating system. I think I understand what I have to do:

Task Struct

• PID
• Register struct (EFLAGS, EIP, ESP, EAX, etc.)
• Pointer to page directory
• Pointer to next task to run

• Task's current state (running, sleeping, blocked for file IO, blocked for swap, waiting for IPC, etc)
• Task's kernel stack (if you're using "one kernel stack per task")
• Some performance hints (e.g. whether the task uses FPU/MMX/SSE or AVX, so the kernel knows whether to load/save those)
• CPU affinity (e.g. a 1 bit per CPU mask saying which CPUs the task may use)
• Parent's PID
• CPU time this task has consumed so far
• Time when this task was started (for calculating "elapsed wall clock time since started")
• Memory usage statistics (allocated and actual)
• Other statistics (task switches, number of times blocked, number of page faults - whatever might be useful)
• Some sort of name and/or identifier (e.g. so that if it crashes or you have a utility to see which tasks are consuming how much time/memory you can show a descriptive name like "Apache" rather than just a number/PID).
• The state of debug registers (e.g. DR0 to DR7) for "per task debugging"
• Performance monitoring counters and configuration for "per task performance monitoring"
• Task's userID (if you're planning to support multi-user and file IO permissions)
• Any special access it has (e.g. if it's allowed to use network or log keypresses or whatever)
• A list of open file descriptors maybe
• Task priority (after you're finished with "round robin")

Running/Switching Tasks

• Run code until IRQ0 (PIT pulse)

Definitely not. Tasks stop running for a large number of reasons (e.g. calling "sleep()", waiting for file IO, waiting for networking, waiting for some other task to exit, waiting to receive data from another process, being pre-empted by a more important task, etc). The timer (IRQ0) is the least important cause of a task switch.


Cheers,

Brendan

[Mercury1964]

Running/Switching Tasks

• Run code until IRQ0 (PIT pulse)

Definitely not. Tasks stop running for a large number of reasons (e.g. calling "sleep()", waiting for file IO, waiting for networking, waiting for some other task to exit, waiting to receive data from another process, being pre-empted by a more important task, etc). The timer (IRQ0) is the least important cause of a task switch.


Cheers,

Brendan

What's a good way of noting what the process is waiting for? An enum coupled with an int or two for data (for instance, STATE_SLEEPING, ticks elapsed since sleep(), ticks to sleep() for)? A separate taskState struct?

[Combuster]

A thread has something to do and can be run, or it has nothing to do (because it waits) and then it shouldn't run. From the scheduler point of view a boolean is thus enough.


Any other data you need to toggle between running and sleeping states is more of an implementation detail. Because it waits, the thing that's busy with performing the other task is more likely to know which threads to wake upon a result, and that data has to be primarily kept there.

[mallard]

What's a good way of noting what the process is waiting for? An enum coupled with an int or two for data (for instance, STATE_SLEEPING, ticks elapsed since sleep(), ticks to sleep() for)? A separate taskState struct?

My approach, which I'm not claiming to be the best way to do it, is to allow threads to "block" on arbitrary conditions. When a thread blocks, it provides a pointer to a function (and pointer to any parameters needed) which the scheduler can use to determine whether it's runnable or not (i.e. where a "conventional" scheduler does something like "if(thread.runnable)", mine does something like "if(thread.blockcheck(thread.param))".)

My "sleep()" call (when I get around to implementing it, I've not needed "sleep()" so far; the technique is used for all the blocks I have so far implemented though) will look something like this:

Code: Select all

void sleep(int mills){
    uint64_t endTime = calculate_sleep_end_time(mills);
    block(&sleep_blockcheck, (void*)&endTime);
}

bool sleep_blockcheck(void* param){
    return *(uint64_t*)param >= current_time();
}

Of course, I'm sure Brendan will disagree with this way of doing things, berate me for being a disgrace to the human species and describe his completely perfect alternative soon...

[xenos]

The obvious drawback of this idea of providing a "block check function" for every task is that the scheduler must run this function on every rescheduling, for every task, until it has found a runnable task. This takes lots of time, and rescheduling happens frequently, so it's even more important to do it as quickly as possible. Just checking a boolean value is much faster that that, and moving all blocked tasks out of the queue as soon as they block (i.e., having a separate structure only for runnable tasks and moving tasks in and out only when their state changes, by IPC or interrupt) is even faster.

[mallard]

The obvious drawback of this idea of providing a "block check function" for every task is that the scheduler must run this function on every rescheduling, for every task, until it has found a runnable task. This takes lots of time, and rescheduling happens frequently, so it's even more important to do it as quickly as possible. Just checking a boolean value is much faster that that, and moving all blocked tasks out of the queue as soon as they block (i.e., having a separate structure only for runnable tasks and moving tasks in and out only when their state changes, by IPC or interrupt) is even faster.

Yes, there is an effect on performance, but by keeping the "blockcheck" functions as simple as possible (almost all of mine are one-liners) it's manageable IMHO. I also reduce overhead by "pre-scheduling" in batches, so the actual task/thread switcher only follows a linked list (with a check to make sure the thread/task hasn't been made non-runnable since the last pre-schedule). The last element in the linked list is always the special "pre-scheduler" thread.

I'm not wedded to this approach, but I quite like its flexibility and simplicity. The alternative is often to keep lists of waiting threads/tasks for all the different conditions, which is itself a complicated exercise.

[madanra]

My plan (which as I've already mentioned, I haven't implemented yet, so may turn out to be stupid and/or impossible) is for a process to be set to runnable precisely when it recieves a message, and set to not runnable precisely when it blocks waiting for a message. Then you don't need to keep track of what a process is waiting for - it just waits until whatever it was waiting on sends it a message with the result. Of course this all presumes a message passing OS.

[Brendan]

Hi,

What's a good way of noting what the process is waiting for? An enum coupled with an int or two for data (for instance, STATE_SLEEPING, ticks elapsed since sleep(), ticks to sleep() for)? A separate taskState struct?

A simple enum can be fine - it's mostly only used for getting information (e.g. so kernel can tell a debugger or something the state of each thread in a process) and for sanity checking (e.g. code that unblocks a task can check if the task is actually blocked for the right reason and panic if something is wrong).

More interesting is that "next" field you already had. When a task is not blocked (ready to run) you'd use the "next" field for a linked list of ready to run tasks; when the task is sleeping you might use the "next" field for a linked list of tasks that should wake up at a certain time; when a task is waiting for swap space you might use the "next" field for a linked list of tasks waiting for data from swap space, etc.

Of course later on you might want multiple lists (e.g. one list per task priority, one list per CPU, whatever).

The other thing I'd consider is cache locality (for both cache lines and TLB entries) - cache misses are expensive, and avoiding them helps performance. That task structure is relatively big (compared to cache line size), and different fields are used at different times - e.g. the "next" field and task priority is used when blocking/unblocking tasks and deciding which task to run next, the task's registers and kernel stack are only used during task switches, etc. To improve cache locality you could split the structure into multiple structures (with one structure for each group of things that are accessed at similar times); so that (e.g.) all fields that used when blocking/unblocking tasks and deciding which task to run next (e.g. the "next" field and the task's priority) are packed together into a little structure and all of those little structures (for all tasks) are in the same area (more likely to be sharing the same cache lines and same TLB entries and less likely to cause cache/TLB misses).

Also; it's a bad idea to store a "ticks elapsed since sleep()" because every tick you'd have to update this field for every sleeping task. It's more fun to store a "wake up time" that doesn't need to be updated every tick (and is only set once when a task calls "sleep()" or "nanosleep()" or something). Note that timing is far more complex than people first imagine; partly because it's used for many things (e.g. sleeping and alarms and timeouts) and needs to be "low overhead", and partly because things need to be done in chronological order (and sorted lists are slow when there's many items on the list), and partly because you want very good precision for some things (e.g. "nanosleep()") and don't care much about precision for other things (e.g. networking timeouts), and partly because it's a good idea to support whichever timers the hardware could provide (time stamp counter, local APIC, HPET, PIT, etc) and detect what hardware supports during boot and use the best timer/s that happen to exist. Because it's complex, if you're interested, I'd recommend asking about it (in a different topic) when you're ready to implement it (e.g. possibly after you've got task switching working).


Cheers,

Brendan