Project 1 FAQ

From CS415

Table of contents

Indirection in the queue functions

Q: Why is that all the append and prepend queue functions accept an any_t parameter, while dequeue accepts an any_t * item? Since any_t is already a void pointer, are we supposed to return a pointer to a pointer ?

That's C's method of returning multiple results from a function. Remember that C only uses call-by-value. dequeue is supposed to return true/false based on its success. It is also supposed to return a pointer to an element. It does the former by just issuing a statement like "return 0". It does the latter by taking a pointer to a location, and patching that location with the value it would like to return.

E.g. let's say you have a function that is supposed to return height (which is 10) and width (say, 20). If you do the obvious:

int getheightwidth(int width) { 
    width = 20; 
    return 10; 
} 

main() { 
   int h = 0,w = 0; 
   h = getheightwidth(w); 
}

The change you made to width will not be visible to the calling routine - w will still be 0 after the call, because C uses call-by-value parameters.

You can get around this problem by passing in a pointer:

int getheightwidth(int *width) { 
    *width = 20; 
    return 10; 
} 

main() { 
    int h = 0,w = 0; 
    h = getheightwidth(&w); 
}

Working through an example and convincing yourself that this approach works is the best thing to do. If you have further questions, please see the course staff during one of the TA hours.

The initial context

Q: In section today, we were told that we could represent the thread that = NT gives us as a minithread. But what I don't see is where we get the NT stack's base and top to initialize our minithread structure. How do we get such information and more importantly, what is the exact purpose of representing the kernel thread as a minithread? It was suggested that the kernel thread could serve as the manager thread.

Bootstrapping is a problem for any OS. In minithreads, just like in a real system, you have the problem of going from the initial bootloader context to switching between threads that you have created. In our case, the initial stack assigned to us by NT is the bootloader stack, and you would like to then start context switching between minithreads. There are a couple of things one could do here. For instance, you could take a context_switch out of the initial stack, and never return there. This is OK, but you would in effect be throwing away the entire initial stack, which is wasteful.

A better approach is to use the initial stack provided to you by the bootloader (NT in our case) as if it were a minithread stack. The problem is that you don't know the base or the top of the stack assigned to you by NT. But why do you need to know the base or the top ? You need the base if you want to ever free the stack, and you need the top when you need to initialize the stack. But the boot stack is already initialized, and if you turn the initial boot context into the idle thread or the stack cleaner thread, then it will never terminate. Hence, you'll never need to free its stack.

So it's perfectly OK to create a special TCB for the initial context. In effect, you have the context already, and you are legitimizing it in your threads package by wrapping it in a TCB. Unlike every other TCB, this one may have NULLs for stack base and top, but that's ok. You get the nice property that you do not lose or discard any of the memory available to you, including the initial stack.

Queue_delete signature

Q: Also, with the new definition of queue_delete(queue_t, any* item), what is the purpose of the any* item? Is it so that we can return a ptr to the data of what we are deleting? If this is the case, then how do we identify what it is we are to delete?

In queue_delete, *item is a pointer to the queue element the calling application wants you to delete. queue_delete does not return a pointer, do the (any_t *) is not strictly necessary. So why is there a level of indirection? For no fundamental reason, only to keep the queue_dequeue interface identical to queue_delete, so people will not make mistakes when they use either of the routines that take items off of a queue.

Queue_iterate semantics

Q: How should queue iterate work?

Queue iterate should continue iterating through the queue as long as the function returns 0. It should stop and return as soon as the iterator function returns a non-zero value.

Q: What should queue_iterate return?

Whatever the iterator function returned when the iteration ended. That is, 0 if the function always returned 0 and the end of the queue was reached, or else whatever the function returned last to terminate the iteration.