[OS] Discussion for exam questions ...

[Petr Tůma]

Hi Immo,

comments inline :)

> void wait(Sem *semaphore) { lock(semaphore->spinlock); 
> semaphore->value--;
> 
> if (semaphore->value < 0) { do { cond_wait(semaphore->cond,
> semaphore->spinlock); } while (semaphore->wakeups < 1); 
> semaphore->wakeups--; } unlock(semaphore->spinlock); }

Reading from top to bottom:

- The function would more typically be called "down". But this would not affect the test grading.

- Doing value -- at the very beginning unconditionally is in theory somewhat dangerous. You could have so many threads attempting to down the semaphore that they would underflow the counter. Of course, if you would use large enough integers then this would not happen in practice, but it is perhaps still better to only do value -- when it is above 0.

- Using a condition variable is, strictly speaking, against the requirements of the question (which only gave you a spinlock), but it is not entirely wrong so would probably earn you some points if the solution were correct.

- The use of an extra wakeup counter is strange, and would not do what a semaphore is supposed to do. Coupled with your implementation of signal (which would more typically be called "up"), you would wake one waiting thread every time you do up, rather than only when the value is non negative.

How about this simpler modification:

void down (Sem *s) {
   lock (s->lock);
   while (true) {
     if (s.value > 0) {
       s.value --;
       break;
     }
     cond_wait (s.cond, s.lock);
   }
   unlock (s->lock);
}

Plus of course the corresponding up function:

void up (Sem *s) {
   lock (s->lock);
   s.value ++;
   cond_signal (s.cond);
   unlock (s->lock);
}

You could also perform the signal conditionally, only when s.value was 0 before increment.

Anyway, this is just a sketch, the main point is that you should not need an extra counter for signaling, you should use the semaphore value.

> I'd consider this implementation to be active waiting, because of the
> use of spinlocks. But if we can't rely on the existence of a mutex
> (not mentioned in the task description) I am not really sure how to
> make the waiting passive instead. Or is the waiting actually passive
> in this case?

Well, the majority of waiting would take place inside the cond_wait function, which is passive. Strictly speaking, an attempt to down or up a semaphore can spend a bit of time in active waiting (inside the spinlock), but that duration is really short so the semaphore as a whole would not be thought of as spinning.

Of course, the question requested only the use of spinlocks (so no cond_wait and no cond_signal), but it mentioned an interface for sleeping, which would take care of the passive waiting.

> getProcesstoRun: if (ReadyQueue.isEmpty) return Exception; process
> highest; for (process p in ReadyQueue): if (highest is unassigned OR
> getPrio(p) > getPrio(highest)): highest = p; return highest;

This is a good start (most answers I saw used a sorted ready queue and just picked first, which would be more practical, but this is OK for the exam). What is missing is some mechanism for (re)computing the priorities to make them dynamic - you could e.g. sketch the internals of your getPrio function and mention it would reflect the time the process was running recently. Also, your answer does not decide how long to run the given process.

> Integer & Pointer are 4 Bytes (32bit int) each. Taking kalisto as an
> example each block contains size, free-indication, pointer to heap
> itself and magic each 32 bit as well, while the footer only contains
> size and magic. So one node-block has an estimated size of 36 bytes.
> -> 1000 Nodes have size of 36000 bytes ~ 36 kB.

This is again relatively OK. The technical details are a bit off (e.g. free indication in Kalisto is a boolean so not 32 bit, but that is not important), but overall you are aware of the existence of headers, which the question was essentially about, so OK. You could also mention alignment (but in Kalisto it is 4 bytes so would not apply to this example). More importantly, you also need to store the integer elements that the tree nodes will refer to, which would about double your memory consumption.

> Would for example 1000 kHz be reasonable choice, so every tick equals exactly one millisecond?

Yes.

> Initial Value: 2^32 + 2^31 + ... 2^0 - 1000 -> Every Rotation is one second

What you are trying to write is MAXINT - 1000 + 1, or simply -1000 in second complement. The 2^32 element in your formula is too much, you should start with 2^31 (32 bits are from 0 to 31), but again I see what you're trying to do and it is essentially OK.

> For each folder a dentry is made after it was accessed first, so the number of disc accesses made is two per file (dentry + fileaccess)

The question emphasizes that there are many files, which in other words means nothing will be in memory and you will have to traverse the full directory structure. Assuming for example the ext2 filesystem, you first need to read the root directory, that is one inode read and one data block read at least. The same goes for the subdirectories, two reads per each, and then the file, again the inode and then the data block.

Hope this helps, Petr