Levels (where to?)/Scheduler (where is it?)

[OSMAN]

Hi.

Please tell me what levels I should put each operation of the kernel to (like interrupts, "supervisor calls", scheduler...).

I don't understand this scheduling thing. Where is the scheduler? I haven't found any from any source codes.

For example: there is an floppy.c. Now, when the time comes and some program calls this floppy_task, does the scheduler do it like this:

EXECUTION ORDER
floppy_task_line1();
...turn of some other processes
...turn of some other processes
...turn of some other processes
floppy_task_line2();
...turn of some other processes
...turn of some other processes
...turn of some other processes
floppy_task_line3();
...turn of some other processes
...turn of some other processes
...turn of some other processes
floppy_task_return;

and so on?
(Correct me If I am totally learned this wrong way from Tanenbaum's book)

PS. what is the scheduling algorithm used by modern OS:s?

[Brendan]

Hi,

Please tell me what levels I should put each operation of the kernel to (like interrupts, "supervisor calls", scheduler...).

Please tell me how your kernel and scheduler works, and what kind of tasks it runs!

I don't understand this scheduling thing. Where is the scheduler? I haven't found any from any source codes.

For example: there is an floppy.c. Now, when the time comes and some program calls this floppy_task, does the scheduler do it like this:

EXECUTION ORDER
floppy_task_line1();
...turn of some other processes
...turn of some other processes
...turn of some other processes
floppy_task_line2();
...turn of some other processes
...turn of some other processes
...turn of some other processes
floppy_task_line3();
...turn of some other processes
...turn of some other processes
...turn of some other processes
floppy_task_return;

and so on?
(Correct me If I am totally learned this wrong way from Tanenbaum's book)

Once "floppy.c" is compiled there's no way to tell what code came from which source code line (it's all converted into CPU instructions). Even something simple like "A = B++" would probably be split into 2 CPU instructions where the scheduler could do a task switch in between the instructions (e.g. after the "B++" but before the "A = ").

In general there's only 3 reasons why a task switch would occur:

• The amount of time a task was given ran out (end of time slice pre-emption)
  The task doesn't need the CPU for a while (CPU voluntarily released)
  Something more important became ready to run (priority pre-emption)

Some of these might not apply (it all depends on the scheduler and task), but normally they all do.

Imagine if the scheduler switched tasks every 1 second (an extremely simple "round-robin" scheduler), and all of the tasks use as much CPU time as they can. In this case all tasks would run for millions of instructions (depending on how fast the CPU is) and tasks wouldn't be able to predict when a task switch would occur. The scheduler would give a "slice of time" to each task, and each task would run until it's time slice ran out. This is "end of time slice pre-emption".

A lot of tasks can only do so much work before they need to wait for something. Examples would be an application that needs to wait for a keypress to be received, or a floppy driver that needs to wait for the hardware to send an IRQ (or for a new read/write request to be recevied), or a task that is waiting for data to be loaded from a file. The task could simply wait, using something like "while( can_I_continue() ) {};" but this wastes a huge amount of CPU time. It would be much better if the task told the scheduler that it doesn't need any more CPU time until something happens. That way the CPU can do other things until the task needs can continue. Usually (for high level languages) this is hidden from the programmer inside functions like "sleep()", "getc()", "select()", etc. This is "CPU voluntarily released".

Now, the imaginary "round-robin" scheduler isn't very good because if something important happens like the user presses a key, then the keyboard's task would need to wait for it's turn before the keypress is processed (which could be ages). A better scheduler would know that the keyboard is more important, and when a key is pressed it'd stop running anything less important and do a task switch to the keyboard's task. For this to work the scheduler needs to know how important each task is, so each task would be assigned a "priority", where more important tasks have a higher priority and pre-empt lower priority tasks. This is "priority pre-emption".

If you combine all of this, then it's impossible to determine when any task switch will occur in advance - for example, you can't predict when a user might press a key.

PS. what is the scheduling algorithm used by modern OS:s?

Modern OS's tend to have several complex scheduling algorithms, rather than one easily explained scheduling algorithm.

For Linux, see:
http://www.oreilly.com/catalog/linuxker ... /ch10.html

For Windows NT, see:
http://www.windowsitpro.com/Article/Art ... 2/302.html


Cheers,

Brendan

[OSMAN]

Hi,

My kernel will be a monolithic one, and for the benginning I want a round-robin/priority-scheduler or something like that.

Well, I knew that the floppy.c is as binary for the CPU, but I was just visualizing the problem.

So, Is it like: I don't need scheduler until I have a filesystem where to load the executables to memory and run them ("simultaenously").

But I still didn't get the meaning: where is the scheduler, what does a skeleton of a one look like (please lend me one for example)?

Does the scheduler interrupt any system tasks like: read_keyboard(), write_a_byte_to_disk()? Because I have heared they do CLI before the actual code.

What should I do next; write drivers then FS-commands then MM-commands then THE SCHEDULER then the applications?
(I can say that there's not very good skeleton of the kernel at the moment)

[Brendan]

Hi,

But I still didn't get the meaning: where is the scheduler, what does a skeleton of a one look like (please lend me one for example)?

The scheduler is a set of functions (and usually a timer IRQ handler) built into the kernel.

Most schedulers don't make too much sense unless you understand the environment they're designed to operate in. For example, here's the Linux scheduler, which IMHO is a bad example - it's too complex, but useful to get a rough idea of what's involved for a modern OS and where the scheduler lives:

http://lxr.linux.no/source/kernel/sched.c


My advice here is to break the scheduler into several parts. Start by trying to implement a single function (in the kernel) that switches from one task to another - something like:

Code: Select all

void goto_task(new_task_ID) {
   ..some stuff...
}

You'll need to decide what that "new_task_ID" parameter is. What does your OS need? Perhaps it's a TSS descriptor in the GDT ("unsigned short new_task_ID"), but perhaps (in the beginning) it'll be the address of a structure that looks something like:

Code: Select all

typedef struct {
   void *task_ESP;
} TASK;

Maybe it's not a structure - it could be an index into a table of structures, or an index that's used for several arrays. I don't know, it's up to you (for my OS it's an index used for 2 "arrays of structures").

Anyway once you've figured this out, continue with the code to switch to a new task. Sooner or later you'll need a way to actually create a new task. When you get to this point, just write code to create a new task that runs inside the kernel at CPL=0 (and a function to convert the currently running code into a task).

Once you've got all of this working, you can do something like:

Code: Select all

void init_code(void)
{
   TASK first_task_ID;
   TASK second_task_ID;
   TASK third_task_ID;

   first_task_ID = create_this_tasks_scheduler_data();
   second_task_ID = spawn_kernel_task(&task2);
   third_task_ID = spawn_kernel_task(&task3);
   for(;;) {
      videoMemory[0]++;
      goto_task(second_task_ID);
   }
}

void task2(void)
{
   for(;;) {
      videoMemory[3]++;
      goto_task(third_task_ID);
   }
}

void task3(void)
{
   for(;;) {
      videoMemory[6]++;
      goto_task(first_task_ID);
   }
}

Now you'll have task switching working (and tested), but nothing to decide which task to run next. This is where you start implementing a scheduling algorithm. To start, how about something like:

Code: Select all

void find_new_task_to_run(void) {
   TASK new_task_ID;

    new_task_ID = current_task_ID + 1;
    if(new_task_ID >= total_tasks) new_task_ID = 0;

    current_task_ID = new_task_ID;
    goto_thread(new_task_ID);
}

And then something like:

Code: Select all

void PIT_IRQ_handler(void) {
    current_timer_tick++;
    if( (current_timer_tick & 15) == 0) find_new_task_to_run();
}

[continued next post]

[Brendan]

[continued from previous post]

After that, your kernel should be able to do something like this:

Code: Select all

void init_code(void)
{
   TASK first_task_ID;
   TASK second_task_ID;
   TASK third_task_ID;

   first_task_ID = create_this_tasks_scheduler_data();
   second_task_ID = spawn_kernel_task(&task2);
   third_task_ID = spawn_kernel_task(&task3);
   start_the_scheduler_timer();
   for(;;) {
      videoMemory[0]++;
   }
}

void task2(void)
{
   for(;;) {
      videoMemory[3]++;
   }
}

void task3(void)
{
   for(;;) {
      videoMemory[6]++;
   }
}

If everything works correctly, you'd end up with 3 flashing dots (or characters) on the screen - one for each task that's being given small chunks of CPU time by the scheduler.

BTW, please don't take any of the code above literally - it's only there to give you some ideas...

Does the scheduler interrupt any system tasks like: read_keyboard(), write_a_byte_to_disk()? Because I have heard they do CLI before the actual code.

This answer is different for different OS designs. For my OS the scheduler can pre-empt any device driver at any time, and there's nothing the device drivers can do to prevent it (device drivers run at CPL=3 and the "CLI" instruction causes a general protection fault).

What should I do next; write drivers then FS-commands then MM-commands then THE SCHEDULER then the applications?
(I can say that there's not very good skeleton of the kernel at the moment)

I always try to implement things in the following order:

• Boot code
  Memory manager/s
  Scheduler
  Messaging (IPC)
  Other kernel stuff
  System stuff (virtual file system support, hardware auto-detection, etc)
  Device drivers, applications, etc.

For my OS it'd be impossible not to implement things in that order - the scheduler needs to allocate memory from the memory managers (when it's creating new threads/processes, etc), the IPC code needs to use scheduler functions (make a thread sleep until a message arrives and wake threads up when they receive a message), all of the "System stuff" run as seperate threads and need the scheduler and IPC, and it's impossible to load device drivers from the virtual file system before the virtual file system is started (and it doesn't make sense to start a device driver before you know if it's hardware is present).

Usually it doesn't go exactly like that as I end up adding things to earlier parts while I'm doing later parts. For example, I'd implement enough of the memory managers to allow the scheduler to do it's job, but I'd leave things like swap space support and memory mapped files until much later.

Exception handlers should be in there somewhere too.


Cheers,

Brendan

[OSMAN]

Hi again,

There flashed something deep in my brain when I was reading your reply.
Are you saying --this is what's difficult to figure out-- that it can be planned when to switch kernel tasks (written in C) by a single statement; I thought it must be binar-program [as it is; I'm just visualizing again] and the scheduler just reads the binary-code blindly and executes it, then switches to read another executable's code from a position... do you get what I mean?
I visualize again:

//START OF CODE

exec(/prog/init)
// loads init into a process table slot
// PID of init is 1
// and creates a pointer (IC[1], instruction counter) and sets it to 0

//then the skeleton
int TASK_COUNTER=0;
long INSTRUCTION; // the current machine instruction

while(1) {
TASK_COUNTER=0;
while(TASK_COUNTER<100) { //max number of processes is 100
if ( task_exist(TASK_COUNTER) ) {
INSTRUCTION = read_binary_code( IC[ TASK_COUNTER ] );
exec_binary_code( INSTRUCTION );
}
TASK_COUNTER++;
}
}

//END OF CODE

Does this kind of process switching (only one machine instruction per process per round) do any sense (not of course)?! I mean, have I understood this "switching between processes"-thing?

[CloudNine]

Nope, not correct, unless you wanted to run every instruction under emulation which would be *very slow*. The scheduler only switches a task, the CPU processes each instruction and executes it. Every once in a while (perhaps every 10ms), the CPU is interrupted by the PIT (timer), it pushes all it's information onto the stack and that calls the scheduler code. The scheduler might decide to switch tasks/processes/threads, and it'll load a new stack pointer, which pops all the registers (including the instruction pointer), and so the CPU executes at a different address.

You do have interrupts and the PIT set up?

[OSMAN]

Well Hi again.

That code doesn't belong to my OS. I'd say there's nothing belonging to my OS yet. I keep asking until I get the answer:

Let's say we have two programs:
1010101010101000
0010101010010111
0001111010110100
1010011101010010
1010101100001011

and:
0001111010110100
1010011101010010
1010101100001011
1010101010101000
0010101010010111

Now, an instruction is 16 bit long, and there are 5 of them in both programs.

Then this command happens:
exec(program1);

As I suppose, it allocates a slot from the Process Table, it resets there some variables, loads the code somewhere into memory from HDisk, and makes up pointers to the code in the memory. Is it right?

Now please tell me HOW to multiprocess these "machine-language&OS-call/I mean normal executable like ELF"-processes IN THE FORM OF C-CODE!
(I'd like to research some example scheduling code because I don't think you can help me anyway else.)

[bubach]

I don't think that you really understand what the timer is used for (after reading the code you posted above). I'll try to explain it simple, but as I have never done any multitasking you better check it with someone that knows for sure.

1) You set up interrupts, and most importantly the timer interrupt at a specific rate.
2) You start any program, fill in you tables and whatever...
3) The program runs the number of milliseconds or whatever you programmed your timer thing to.
4) The CPU jumps to your timer IRQ handler, and is expected to go back to your program once finished...
5) ..instead you check if it's time to change to another program, by checking your tables or whatever, modyfies the returning address and voila, when you do the "iret" you jump to another proccess..

Did that made any sense at all? :S

[Pype.Clicker]

okay, let's try to sketch it from scratch in a clean way.

You have programs running. Each program has some binary code to be executed by the processor and an execution context made of e.g. registers state, stack content, etc.

Since you have a single CPU, you have a single program executed at a given moment and its execution context is the state of the cpu's registers while you may have plenty of programs sleeping, waiting for their turn with their context saved in OS's datastructures, right ?

Now, the OS has set up a timer interrupt, which causes the OS call a specific interrupt service routine at regular interval. When the timeslot for the current program runs out, the routine will save the current CPU context into a datastructure, select a new program to be run for the next timeslot, and load the CPU registers with the values that were saved in that process's datastructure.

If you still want to figure out, imagine a machine with an accumulator and a stack pointer. You can save the machine state, switch and restore another machine state with

Code: Select all

PUSH    ;; put the accumulator's content on stack
LOAD [current_pid]  ;; put it in the accumulator
STORE_SP [context_table+ACC]
;; get somehow the next pid into ACC, without using the stack
LOAD_SP [context_table+ACC]
POP     ;; get back the accumulator's content
IRET     ;; end of interrupt

Now imagine two programs on that machine, e.g.

Code: Select all

IMM 0  ;; into accumulator
here:
INC     ;; accumulator++
JMP here

and

Code: Select all

IMM 0
there:
DEC   ;; accumulator
JMP there

You should be able to emulate the behaviour of that machine if --say-- you have a interrupt every 10+some_number_you_get_by_rolling_a_dice machine instruction

And you'll see it can continue working on program 1 after it has been interrupted for 10+ instructions by program 2.

Of course "10+dice" is not enough to get decent performances. On modern systems, your timeslice is usually of a few milliseconds, which makes millions of instructions!

[OSMAN]

Thanks for help.

So, the switching of the tasks is caused through the Clock interrupt (as you tried to tell me before)!
::) Now I just need the memory addresses of the interrupts.
Or, would you have any clear tables of all the memory locations, interrupts, ports and everything I need in OS programming (in protected mode)?

[Pype.Clicker]

http://www.osdev.org/osfaq2/index.php/GdtForDummies
http://www.osdev.org/osfaq2/index.php/I ... ForDummies

there are no "location for interrupts": there are mechanism to tell the CPU where you store information about interrupts.