OSDev.org

cyr1x wrote:Why not just

Code: Select all

 mp = (mp* /* or how you named it*/) address;

This is just the same as assigning the values like you do it, but is alot cleaner.

MarkOS wrote:1 - When I start an AP processor, I must also go to Protected Mode with it and initialize its descriptors (GDT, IDT and TSS)?

2 - With ACPI and MP can I do only CPUs detection? Or also other things?

AJ wrote:

MarkOS wrote:1 - When I start an AP processor, I must also go to Protected Mode with it and initialize its descriptors (GDT, IDT and TSS)?

Yes. The CPU is in real mode, so you send the Startup IPI, telling it where to start executing your 'trampoline code'. That code mus reside under 1MB in physical RAM (the AP does not have paging yet and is in real mode), and must switch the processor in to whatever state you want it to be in.

To do this, I use a sequence of signals between my BSP and AP's (in a shared, locked memory location), which tells the trampoline code where to find my system tables and so on. As I use the same trampoline binary for PMode and Long Mode, it also tells the AP whether to attempt the switch to 64 bit mode.

2 - With ACPI and MP can I do only CPUs detection? Or also other things?

http://www.acpi.info/
http://www.intel.com/design/pentium/datashts/242016.htm

Cheers,
Adam

MarkOS wrote: Will I have same descriptors for all APs?
PDBR is shared between all APs?

Must I change something in my scheduler or paging code?
Must I change something in my interrupts code?

MarkOS wrote: what???

      mp.signature = *address;
      mp.config = *(address+4);
      mp.length = *(unsigned char*)(address+8);
      mp.version = *(unsigned char*)(address+9);
      mp.checksum = *(unsigned char*)(address+10);
      mp.features1 = *(unsigned char*)(address+11);
      mp.features2 = *(unsigned char*)(address+12);
      mp.features3[0] = *(unsigned char*)(address+13);
      mp.features3[1] = *(unsigned char*)(address+14);
      mp.features3[2] = *(unsigned char*)(address+15);

MultiProcessorFloatingPointer* mp = (MultiProcessorFloatingPointer* /*or how you named it*/ )address;

cyr1x wrote:@AJ How about assigning a thread to a specific core and they allways run the same threads, now if one CPU runs out of threads it calls "balance()" or something and it takes some threads of other CPU's queues. This is like it's done in Linux. I think Brenden has (again) great theory for this.

• - each CPU was entirely independant (there was no "reschedule_everything()" to simulataneously delay all CPUs in the computer)
  - there were 4 different scheduling groups, called "scheduling policies".
  - there were 256 different priorities within each scheduling policy (effectively 65536 priorities, sort of).
  - "Policy 0" was intended for very high priority threads (e.g. the device drivers for my micro-kernel), and used a "the highest priority thread that can run does run" algorithm. This was implemented as 256 seperate run queues per CPU (or one run queue per priority per CPU).
  - "Policy 1" was intended for high priority threads (e.g. GUI and user-interface threads), and used a "variable frequency" algorithm (where a thread with twice as much priority got twice as many fixed length time slices). This was implemented as one run queue per CPU. This algorithm also caused problems with a large number of running threads, because the list of running threads was searched up to twice when the scheduler needed to find a new thread to give CPU time to (it wasn't "O(1)" like the other algorithms).
  - "Policy 2" was intended for normal priority threads, and used a "variable time slice" algorithm (where a thread with twice as much priority got twice as much CPU time). This was implemented as one run queue per CPU.
  - "Policy 3" was intended for idle priority threads, and also used a "variable time slice" algorithm, with one run queue per CPU.
  - when deciding which thread to give CPU time to, the scheduler would check if any Policy 0 threads could run (and choose one of them if it can), then check if any Policy 1 threads could run (and choose one of them if it can), then check if any Policy 2 threads could run (and choose one of them if it can). If the scheduler didn't find anything it'd give CPU time to an idle thread (there's always at least one idle thread per CPU, that never blocks).
  - this gave me a total 259 seperate run queues per CPU (e.g. 1036 run queues for a computer with 4 CPUs). Each run queue had it's own reentrancy lock, so the scheduler could be choosing a thread to run from one run queue while a different CPU modifies a different run queue. Lock contention was only possible if 2 or more CPUs are trying to modify the same run queue, and because this is all "per CPU" it should've scaled very well (more CPUs means more chance of CPUs potentially trying to acquire the same lock, but more CPUs also means more locks, so the chance of lock contention stays roughly the same regardless of how many CPUs are present).
  - each thread had a "CPU affinity" bitmask, where each bit represents a CPU (where "clear" means the thread can't run on that CPU, and "set" means the thread can run on that CPU).
  - when a thread is given CPU time it's removed from the run queue it was on.
  - when a thread is stops using the CPU (either by preemption or blocking), or if something happens to unblock a blocked thread (e.g. it's "sleep()" time expires, it receives a message while it's blocked waiting for a message, etc), then the scheduler inserts the thread back on a run queue. To do this the scheduler first needs to decide which run queue to put the thread onto.
  - to decide which run queue to put the thread onto, the scheduler calculates a score for each CPU that is allowed (in the thread's CPU affinity bitmap) and selects the run queue (for the thread's policy and priority) who's CPU had the best score.
  - the score was calculated as "number of threads already on the queue", so the thread was scheduled to run on the CPU that has the least number threads already in it's run queue. This was a bad way to calculate the score (it was far too simplistic - more on that later).

bewing wrote:Brendan's mechanism is impressive, but kinda fails the fourth important concept of KISS.

I am intending to implement an earlier suggestion, myself. Each core has an independent scheduler, with an independent task queue. In my system, independent "jobs" own "threads" as subtasks. When a new job is created, it is assigned to the core with the least load at that time. The job then creates all its child threads on that same core.

If one core's scheduler runs out of >idle priority runnable tasks, it requests a load balance from the most loaded core. The most loaded core picks a fairly high priority job, and dumps that entire job worth of threads all at once to that empty core -- ie. the "affinity" for the entire job gets modified all at once.

I like the basic idea of one-shot tickless systems. However, the idea scares me, too. What happens if the timer fails to deliver the next one-shot interrupt to the CPU? Nothing in a system is absolutely 100% guaranteed, including interrupt delivery. I would really want to have some sort of backup mechanism to wake up a CPU that missed a one-shot interrupt, and got stuck running the same task forever.
In a tick-based system, at least you can always count on the fact that another timer tick will come along the next time around.

What's the point of multi-threading if the threads are running on a single CPU only?

wouldn't it be better if they could run on seperate CPU's so both parts are done simultaneously, rather than on a single CPU where they are sharing cylces?

cyr1x wrote:
This is .. ehm ... bad.

You can just assign the pointer to the "mp" and it will be "filled in"(not the right word) automaticly. Like so

Code: Select all

MultiProcessorFloatingPointer* mp = (MultiProcessorFloatingPointer* /*or how you named it*/ )address;