Problem with semaphores

[garfield]

Hi,
I have some problems with my (basic) implementation of a semaphore.
The kernel is written in C++ and based on OOStuBS. It was started in school and I continued to develop it after class.
Currently it doesn't do a lot: interrupts and user-level-threads. Scheduling is time based and uses self implemented versions of get-/setcontext and make-/swapcontext.
It doesn't have any memory management or processes yet.
Before, every thread had to disable and enable interrupts when printing onto screen. To make that unnecessary, I have implemented a semaphore which blocks threads that request access to the screen when it is already in use.
The problem I have is that after the first thread has been switched out, the Scheduler::resume() doesn't get called based on timer interrupts anymore but rather every "cycle" of the thread. In addition, sometimes an exception gets thrown (either 1, 6 or 13).
The problem seems to come with the resume() call when a thread tries to get access to the screen but gets blocked because it is in use already. When it is commented out, the scheduler gets called as intended and no exceptions get thrown (but the screen is messed up of course ), but I just can't find the mistake >.<

Scheduler::resume()

Code: Select all

void Scheduler::resume()
{
	cpu.disable_int();
	Thread *temp = activeThread;
	do
	{
		threads.enqueue(temp);
		temp = threads.dequeue();
	}
	while(!temp->isReady());
	dispatch(*temp);
}

Semaphore::wait & Semaphore::signal

Code: Select all

void Semaphore::wait(Thread* thread)
{
	cpu.disable_int();
	if(count > 0)
	{
		count = 0;
		cpu.enable_int();
		kout << endl;
	}
	else
	{
		queue.enqueue(thread);
		cpu.enable_int();
		thread->block();
	}
}

void Semaphore::signal()
{
	cpu.disable_int();
	if(queue.isEmpty())
		count = 1;
	else
		queue.dequeue()->ready();
	cpu.enable_int();
}

I don't know if that's enough code, if something's missing just point it out

Thanks in advance

[Combuster]

The semaphore code isn't SMP-safe. It relies on having exactly one processor core and IF being a guaranteed method of not getting scheduled out.

The real purpose of resume() is vague, and to some extent, so are the semantics of the functions called from there. There's also an unmatched cli/??? pair in there.

[bwat]

Currently it doesn't do a lot: interrupts and user-level-threads. Scheduling is time based and uses self implemented versions of get-/setcontext and make-/swapcontext.

Doesn't do a lot? I disagree. If you can get a computer to boot your little OS then you've got yourself a platform to make the machine do anything you want it to. However, you will need to get semaphores sorted out if you want to share and communicate between threads. You seem to have limited yourself to binary semaphores (mutexes). You'll probably want full counting semaphores as they can do so much more. You will want a counting semaphore with an initial count of 1 for your screen mutex.

I include psuedo-code for wait and signal. It assumes the OS has a ready queue that contains all threads that are competing for the processor. Also, each semaphore has a waiting queue that contains all threads that are competing for the semaphore. No thread is on more than one queue. The currently executing thread is on no queue. When the processor is assigned to a thread, the processor status word that was current when the thread was previously preempted or blocked is restored.

Most of the really important things are left out. There's no point me doing everything for you. There's probably no point just copying the code and fitting it to your system. You will, however, probably want to try to understand the design behind it all. I think this is a fairly canonical design.

Code: Select all

void
wait (uint32_t semid)
{
  processor_status_word_t old_psw; 
  struct thread *tptr;  /* pointer to the OS thread structure */

  /* disable interrupts */
  get_processor_status_word_and_disable_interrupts(&old_psw); 

  /* I assume semid is a valid semaphore id */

  /* 
   * Decrement the semaphore count.
   * After the decrement:
   *   If count < 0 then there are abs(count) threads in the semaphore waiting queue.
   *   If count > 0 then there is "room" for count threads to pass through 
   */ 
  if(--semtable[semid].count < 0)
    {
     /* 
      * No "room" so place the current thread on the semaphore waiting queue 
      * and give up the processor.
      */
      tptr = &threadtable[get_current_thread_id()];
      tptr->state = WAITING_FOR_A_SEMAPHORE;
      queue_insert(&semtable[semid].queue, tptr);
      /* Give the processor to the highest priority ready thread */
      reschedule();
    }
  /* restore previous interrupt status */
  set_processor_status_word(old_psw);  
}


void
signal (uint32_t semid, uint32_t count)
{
  processor_status_word_t old_psw; 
  struct thread *tptr; /* pointer to the OS thread structure */

  /* disable interrupts */
  get_processor_status_word_and_disable_interrupts(&old_psw); 

  /* I assume semid is a valid semaphore id */

  while(count--)
    {
      /* Increment the semaphore count */
      semtable[semid].count++;

      /* Remove the head of the semaphore's waiting queue */
      tptr = queue_remove(&semtable[semid].queue); 
      if(tptr)
        {
          /* unblock the waiting thread, put it on the ready queue */
          tptr->state = READY_TO_RUN;
          queue_insert(ready_queue, tptr);
       }
    }

  /* Make sure the highest prioritiy thread is now running */
  reschedule();

  /* restore previous interrupt status */
  set_processor_status_word(old_psw);  
}

[garfield]

Hi,
I'm sorry, I probably should have posted the general design of the scheduler/thread/semphore:
The scheduler has a queue of threads, the functions resume(), ready(Thread &thread), schedule(Thread &first) and exit().
ready() takes a new thread into the queue, schedule() starts the scheduling with a thread, resume() switches to the next thread in the queue and exit() removes the current thread from the queue.
Semaphore has a queue as well, a counter and the functions wait(Thread *thread) and signal(), they pretty much do what you suggested now.
Thanks for your help with the semaphore pseudocode , I already had a lot of material from uni, but it definitely helps.
I've got it to work now, thanks

To Combuster: would the processor itself make use of multiple cores without being told to? My threads are software based and lack any hardware support atm.
To the enable/disable interrupts, the matching counterpart is in the dispatch(Thread *t), I forgot to post that one, sorry :/

[bwat]

It looks like your primitives always assume they're being executed with interrupts enabled --- at the end of your critical sections you enable interrupts. If a thread which had disabled interrupts called wait, then it would always have interrupts enabled before the return from wait. Is that what you want?

[garfield]

Actually, no. I think it would be sufficient to safe the state of the interrupt flag everytime I have to disable and enable them and restore it afterwards?
E.g. in wait(*):

Code: Select all

cpu.disable_int();
...
cpu.retore_interrupt_state();

, where restore_interrupt_state() is

Code: Select all

inline void restore_interrupt_state()
{
	asm
	(
		"pushl %0\n"
		"popf\n"
		:
		:"r"(oldFlag)
	);
}

and oldFlag an int variable in the cpu-class