CSE 451 Project 1 FAQ

CSE 451

Introduction to Operating Systems

Autumn 1997

CSE 451 Project 1 FAQ

What's with those funky typedefs in queue.h?

There are three things going on here.

1) First, you want the clients of your queue code (those #including queue.h and linking with queue.c) to be able to put anything in the queue that they want. So in C the hack that everyone uses to get generic data structures to make everything a void*. This allows you to use the queue for storing anything that will fit in the space occupied by a void*, where a void* is a 32-bit (or 64-bit on the Alpha) pointer to something. This is the purpose of any_t, as it is used in the queue operations:

/* any_t is a pointer.  This allows you to put arbitrary structures on
   the queue as well as use the value to store data types that are
   smaller than sizeof(void *). */
typedef void *any_t;

2) Second, you want the person implementing queue.c to be able to implement the queue in any fashion they please. This means that to people #including queue.h, the queue_t should be an "opaque" type; a type where they have no idea what's inside. Again, void* is used, this time to get an opaque type. Inside queue.c, whenever someone passes you a queue_t you'll have to cast it to whatever type it actually is. This will probably mean casting it to a pointer to some sort of struct representing a queue head, but it can be anything that you want to make it:

/* queue_t is a pointer to an internally maintained data structure.
   Clients of this package do not need to know how queues are
   represented.  They see and manipulate only queue_t's.  */
typedef any_t *queue_t;

3) Third, you want clients of your queue code to be able to apply one of their functions to each item on the queue, even though they can't see what elements are on the queue. PFany is just the type of function that can be used like this for iterating over each element in the queue. When the client calls queue_iterate() then this function should be called once for each element in the queue.

/* PFany is a pointer to a function that can take two any_t arguments
   and return an integer. */
typedef int (*PFany)(any_t, any_t);

If any of this doesn't make sense, curse Kernighan and Ritchie, ask the person next to you what's going on, sleep on it, read the code again, and try some yoga or deep breathing exercises...

In queue.[hc], is it an error to try to dequeue an element from an empty queue?

One could argue either way, but let's say that it is not an error. That is, you should return 0 if this happens.

With queue.[hc], is it an error to iterate over an empty queue?

Nope. Iterating over an empty queue is fine.

My timegetpid says that procedure calls take 0.000000 seconds and getpid() takes 0.000001 seconds. What did i do wrong?

Probably nothing. Alphas are very fast. Procedure calls take far less than a microsecond on orcas and sanjuan. System calls take less than a microsecond as well. So you'll need to print out the time with more precision, using printf("%.9f ....

Ans.

cse451-webmaster@cs.washington.edu