Project 2 Common Errors

From CS415

Below are the common notes I had for Project 2. Some bullet points are more severe than others, some are just hints -- points may or may not be deducted depending on the severity.


Table of contents

Synchronization

  • Any and all access to shared memory that has read-write conflict must be protected with synchronization.
    • Synchronization code should not be a part of the queue/multi_queue, but the calling functions must ensure that queue accesses are synchronized
  • Absolutely no blocking when interrupts are disabled i.e. no while(atomic_test_and_set()); loops with interrupts disabled. (if your semaphore_V or something uses spin locks and you call it with interrupts disabled, you are affected)
    • Only exception is a loop with a yield in the body plus properly resetting the interrupt level after the minithread_switch inside the yeild returns. In this case, you need to be careful that synchronization is reaquired since yield may end up freeing up locks, mutexes or enabling interrupts.
  • If some shared memory is protected by one kind of primitive (spin lock, mutex/semaphore, disabled interrupts), all other protection must be of the same type. Otherwise one thread could hold a spin lock and another could hold the mutex/semaphore and both could race.
  • A spin lock must not be freed by a thread that does not hold it. i.e. under no circumstances should you set it to 0 twice after it is acquired. The reason is that if an interrupt occurs after setting it to 0 the first time, another thread could get scheduled and acquire the lock; if the first thread then sets it to zero again, then the lock opens even though the second thread has it.
  • There is a race condition between when the alarm is registered and when the sleeper thread blocks that needs to be protected/avoided.

Priority

  • Changing the current_level when there are no thread at the current level biases the priority queue towards the lower priority threads. It is possible that at tick 1/80 for prio 1, there is not thread at prio 1, but the thread in prio 2 creates a new thread. On tick 3, it is this new thread that should be executed and not a long dormant thread from prio 3.

Efficiency

  • Disabling of interrupts must be using sparingly. i.e. maybe twice or thrice in the entire project!
  • Critical sections should be protected by mutex/semaphores when possible, if not, then with spin locks if possible, if not, only then with interrupt disabling.
  • In general, almost everything in minithread should be a mutex/semaphore, everything in synch should be a spin lock, and really only the 'ticks' counter and minithread_switch need to be protected with disabled interrupts.
  • Spinning on a spin lock waiting for an interrupt to switch to a thread is quite pointless when you can yeild() in the body of the while loop and switch out immediately.
  • Memory that is not shared between threads, or shared memory that is does not have read-write conflicts need not be protected by synchronization primitives.
  • Avoid recomputing the same values in the interrupt handler. Avoid using slow operations in the interrupt handler. A prime example is using % in the handler. It is much faster to decrement a counter and check when it hits 0 as opposed to performing %. The idea is that code with interrupts disabled must be lightning fast.

Coding Style

  • Memory leaks (when you least expect them) ... like leaking memory in multiqueue_create -- if one of the sub-queue's fail to be created, all previously created sub-queues are leaked as the function immediately returns NULL, etc.