ideas for delaying os

[beyondsociety]

I would like my os to delay between messages. I will be writing this piece of code in c.

I could use a for loop or while, but the delay would be different on each computer tested, as with bochs delay timings would be different also.

I would like to know what is the best way to go about this?

[darklife]

Poll on the timer inside a loop using...

Code: Select all

        XOR     AX,AX               ;Segment = 0000
        MOV     ES,AX
        MOV     AX,ES:[046Ch]       ;Get Timer Word..

I dunno how well this works in pmode, or if it works at all ::) Hope it helps. Should work in multitasking environments also.
Err, conversion to C shouldn't be too hard.

[Tim]

A general Sleep(milliseconds) system calls works like:

• Set a wake_time value in the current thread to current_time + milliseconds
• Insert the current thread into a list of sleeping threads
• Make the current thread not ready
• Continue to schedule other threads
• In the scheduler, look at the list of sleeping threads, and make ready any where current_time >= wake_time

For extra points, keep the sleeping list sorted by wake_time, so you only have to check the start of the list within the scheduler.

[beyondsociety]

A general Sleep(milliseconds) system calls works like:

Set a wake_time value in the current thread to current_time + milliseconds

Insert the current thread into a list of sleeping threads

Make the current thread not ready

Continue to schedule other threads

In the scheduler, look at the list of sleeping threads, and make ready any where current_time >= wake_time

For extra points, keep the sleeping list sorted by wake_time, so you only have to check the start of the list within the scheduler.

So If I choose this method, I would have to write a scheduler and setup threads/multitasking? I havent gotten that far yet.

[Tim]

This method lets one thread sleep for a period of time while others keep on running. If there's no multitasking then you might as well poll on the timer. It should be enough to do the pmode equivalent of what darklife suggests.

Write an IRQ 0 handler and increment an uptime variable on each tick. Then you can poll on this variable (with interrupts enabled) until it's passed the wake_time value. For extra points, use the HLT instruction inside the loop to reduce the CPU usage.

[FlashBurn]

@tim

How many threads are usually on the sleeping queue? Does your scheduler put the threads on the sleeping queue?

I want my scheduler to be as small as possible. So I think that I maybe use another list where threads got till they will be put on another list by the taskmanager! So I can sort the sleeping queue by time and my scheduler is small!

[Ozguxxx]

Hey, can you be a little more specific about your idea on how scheduler will be small?

[FlashBurn]

My OS has 5 queues:
-ready (high, med and low priority)
-ran (high, med and low priority)
-wait
-sleep
-kill

My scheduler looks like this:

Code: Select all

dec time_to_run
-> != 0 then iret
-> = 0

enqueue thread:

do nothing with the thread
-> put thread on the ran queue (high, med or low)
kill the thread
-> put it on the kill queue
thread wants to wait
-> put it on the wait queue
thread wants to go sleeping
-> put it on the sleep queue

dequeue thread:

-> take 1st thread with the highest priority from the ready list (I remove this item from the list)
   -> there is no ready thread? then put all items from the ran queues on the ready queues
-> is this a thread which will be killed?
   -> put it on the kill queue and dequeue next thread

My thread struc look like this:

Code: Select all

dd ptr 2 prev item
dd ptr 2 next item
rest of thread struc

So that I don?t need to alloc mem for putting a thread onto a queue and my threads can be only on one queue! I use the thread pointers and because of that the ptrs, for the items of a queue, are part of my thread struc, it?s easy for me to put it on a queue and to remove it from a queue!

Another idea can be to put a thread, which wants to wait, sleep or get killed, on a queue for the taskmanager which then will put the thread on the right queue and he can then also sort the lists, because I think that this shouldn?t be done by the scheduler (sort the lists)!

[Tim]

How many threads are usually on the sleeping queue?

As many as are currently sleeping -- i.e. no limit.

Does your scheduler put the threads on the sleeping queue?

Well, the ThrSleep function does. The scheduler removes them when their time is up.

ThrSleep looks like this:
1. Set this current->wait_end = sc_uptime + milliseconds
2. Find the entry in the sleeping queue whose wait_end time is greater than current->wait_end
3. If an entry is found in (2), insert a new entry just before it
4. If no entry is found in (2), append a new entry to the sleeping queue
5. Remove current from the ready queue for its priority level
6. Set the sc_needschedule flag, to cause ScSchedule to be called before returning from this interrupt

The relevant part of ScSchedule looks like this:
While sc_uptime > [head of sleeping queue]->wait_end:
-- Add [head of sleeping queue] to the ready queue for its priority
-- Remove [head of sleeping queue] from sleeping queue

[Ozguxxx]

Hey I still cannot understand how it will be smaller FlashBurn. You are telling about the simple logic of a scheduler, but in fact I think it is more complicated I mean for example think about this while some lower priority thread is running suppose a high priority thread woke up, so system should immediately see this and dispatch currently running low priority thread BEFORE its time quanta is finished and start running the high priority thread. OR another scenario: Will you dispatch a thread waiting for a mutex to be freed? Or will you give it its all time quanta so that it can wait if mutex will be freed some time and thread can go into critical section. On the other hand, you can dispatch thread immediately after seeing that mutex is not free (which is the way I am doing) because while waiting for some mutex what a thread does is an idle infinite loop polling mutex variable. So it is meaningless to wait for a mutex is free or not, thread just checks for once and then it is dispatched... Well my point is that a scheduler is very complex in the way that everything does not end up like you expected.

[Pype.Clicker]

what seems to worth notice in Flashburn's design is that the 'dispatcher' (i.e. the software entity that enforces task switches) do not re-schedule threads when they're done: it enqueues them instead in a special queue, waiting for some external system to process those threads...

Also, i'd like to say that waking up a thread which is done sleeping is quite identical from the scheduler's point of view from waking up a thread which was waiting for a given resource.

There were older threads discussing the sleep/wake-up problem but i lack time to search for them ...

[Schol-R-LEA]

While it requires an additional queue and some extra logic, I would suggest a delta queue as a more efficient solution to the issue of sleeping processes (i.e., those waiting for a specific time period, as opposed to those waiting on a semaphore or message).

A delta queue is a list in which each node has a pointer to the task record, tr, and an unsigned integer counter, delta, and a following link, next. To set a task to sleep, you remove the task from the scheduler queue and add it to a new node. You then walk through the queue, subtracting the new node's delta value from the current node's delta, until either the current nodes delta value is higher than the new node's delta, or until you reach the end of the queue; you then insert the new node after that current node, and subtract delta the delta of the node after it (if any) .

The advantage of this comes when you have to update the timer information: all you need to do is decrement the head node's delta value on each click, and when it reaches zero, you remove it from the sleep queue and return it to the scheduler queue; of course, if the node after the head is also zero (that is, the were waiting on the same clock time), you'll need to move them to the scheduler as well.

Here's some example code (assumes the existence of functions for adding and removing task records from the scheduler):

Code: Select all

#define NULL '\000'

typedef struct {int dummy;} taskrec; 

typedef struct srec
{
   taskrec *tr;
   unsigned long int delta;
   struct srec *next;
} sleeprec; 

typedef sleeprec* sleepnode;
typedef taskrec*  tasknode;
typedef unsigned long int size_t;

void sched_remove(tasknode tr);
void sched_add(tasknode tr);
void* kmalloc(size_t s);

sleepnode sleepq = NULL;

void sleep(tasknode task, unsigned long int timer)
/* 
removes task from the scheduler queue, and adds it
to the sleep queue. The sleep queue is ordered by
the difference in clock ticks from each node, starting
from the first. Thus if a new node has to wait 5 ticks, and the
existing nodes have values of 2, 2, 0, 1, then the new node
is inserted between the third and fourth nodes, and assigned
a value of 1, and the node following it assigned 0, resulting in
a queue that orders as 2, 2, 0, 1, 0. 
*/
{
  sleepnode curr_node = sleepq, next_node = NULL, new_node = NULL;

  sched_remove(task);  
  // removes task from schedq but does not trigger a reschedule

  new_node = (sleepnode) kmalloc((size_t) sizeof(sleeprec)); // allocate new node
  new_node->tr = task;

  if (NULL  == curr_node)
  {
      new_node->next = NULL;
      sleepq = new_node;
  }      
  else if  (timer < curr_node->delta) 
  {
      new_node->next = sleepq;
      sleepq->delta -= timer;
      sleepq = new_node;
  }      
  else 
  { 
      next_node = curr_node->next;

      while ((NULL != next_node) && (timer >= curr_node->delta))
      {
           timer -= curr_node->delta;
           curr_node = next_node;
           next_node = curr_node->next;
       } 
    
       if  (NULL != next_node)
       {  
           next_node->delta -= timer;
       }

       new_node->next = next_node;
       curr_node->next = new_node;
  }
  
  new_node->delta = timer;
}

void awaken()
/* 
checks the sleeping tasks and wakens any that a ready to run
Should be called on every n clock ticks (where n is system dependent).
Each clock tick, the head node's delta value is decremented;
when it reaches zero, it is removed from the queue, along with 
any node that follows it which are also at zero.  
 */
{
   sleepnode next_node = NULL, curr_node = sleepq;

   if (NULL != curr_node)
   {
       (curr_node->delta)--;
       next_node = curr_node->next;
       
       while  (NULL != curr_node && 0 == curr_node->delta)
       {
           sched_add(curr_node->tr); 
           // adds tr to top of schedq but does not trigger a reschedule
           next_node = curr_node->next;
           free(curr_node);           // free empty node    
           curr_node = next_node;
       }
       sleepq = curr_node; // update global queue head to first non-zero node
   }
}

Note that this approximate code, and untried. I know that it will compile, but I have not tested it. I will try to add more comments later, if I have the chance. The declarations at the top are just dummy code, so that it compiles correctly. Douglas Comer's Xinu book describe the technique in detail.

[FlashBurn]

I have the problem that I can?t use the PIT for my timer stuff! Because my threads can go sleeping and can give up and when they are doing this the timer get faster than it should be. What could I use instead to make a timer?

[Pype.Clicker]

I have the problem that I can?t use the PIT for my timer stuff! Because my threads can go sleeping and can give up and when they are doing this the timer get faster than it should be. What could I use instead to make a timer?

i beg your pardon ??
you mean ??

[Tim]

The PIT is fine and runs at a fixed speed as long as you don't change it. Unless you're running in Bochs -- the timer in Bochs is broken.