Lab #6: Message Queues
In this lab you are to add functions that create, pend on, and post to
message queues so that you can correctly execute the application
program lab6app.c without modification. You
are expected to complete this lab with a partner.
You must add these kernel functions to your kernel. You should
implement each function exactly according to the prototype given on the
YAK Kernel webpage. Refer to that web page
for additional details about these functions.
- YKQCreate - Create and initialize a message queue
- YKQPend - Obtain the oldest message from a queue
- YKQPost - Append a message to a queue
For this lab, you should modify your interrupt handlers in the
- Your interrupt handler on a keypress should no longer generate
output; its sole action should be to set GlobalFlag to 1.
- Your reset handler requires no modification from the previous
- The user code tick handler should no longer output "TICK n" as in
previous labs. Instead, it should be rewritten so that it posts a message to a
message queue each time it runs.
An example of the code required for your keypress and tick handlers
can be found in the file lab6inth.c. You will also need the file
lab6defs.h, which is used by the sample file lab6inth.c and the
application code. The
mytick() handler code in lab6inth.c should be called by your tick ISR in addition
to your kernel's YKTickHandler code. Note that the sample tick handler code assumes the
existence of the global variable YKTickNum, which should already be
defined in your kernel code and is assumed to also be declared as extern in yakk.h.
The tick handler code in the sample file initializes objects of type
"struct msg". This struct type is defined in lab6defs.h. The tick field in this struct is set to the current tick
count and the data field is set to a pseudo-random number. A pointer
to the object is then posted to the message queue. A task in the
application code removes the pointers from the queue (i.e., pends on the queue)
and reads the object pointed to by the pointer.
The task then displays the tick field read from the object followed by the
minimum data field value read so far and the maximum data field
value read so far. A sample of what the program's output should look like
is shown below.
Implement the required functions and make sure that the application
program runs correctly. For full credit on this lab, the system
should not crash when key presses occur in rapid succession, even with
the timer tick frequency increased to 750 instructions. While
your code should not crash at higher tick rates, it may not
give exactly the same output because there may not be enough time
between ticks for all tasks to finish what they would normally do for
that tick. For full credit, your kernel must be efficient enough to
avoid dropping any messages at the default tick rate (1 tick every
10,000 instructions). At the default tick rate, the application's
output should match the following (other than the CPU usage):
Note that the Ticks column lists the tick numbers in
sequential order, without skipping any numbers.
The Min column gets smaller, eventually reaching 0, and the
Max column gets larger, eventually reaching 99.
Welcome to the YAK kernel
Determining CPU capacity
Ticks: 1 Min: 89 Max: 89
Ticks: 2 Min: 78 Max: 89
Ticks: 3 Min: 67 Max: 89
Ticks: 4 Min: 56 Max: 89
Ticks: 5 Min: 45 Max: 89
Ticks: 6 Min: 34 Max: 89
Ticks: 7 Min: 23 Max: 89
Ticks: 8 Min: 12 Max: 89
Ticks: 9 Min: 1 Max: 89
Ticks: 10 Min: 1 Max: 90
Ticks: 11 Min: 1 Max: 90
Ticks: 12 Min: 1 Max: 90
Ticks: 13 Min: 1 Max: 90
Ticks: 14 Min: 1 Max: 90
Ticks: 15 Min: 1 Max: 90
Ticks: 16 Min: 1 Max: 90
Ticks: 17 Min: 1 Max: 90
Ticks: 18 Min: 1 Max: 90
Ticks: 19 Min: 1 Max: 91
Ticks: 20 Min: 1 Max: 91
Ticks: 21 Min: 1 Max: 91
Ticks: 22 Min: 1 Max: 91
Ticks: 23 Min: 1 Max: 91
Ticks: 24 Min: 1 Max: 91
Ticks: 25 Min: 1 Max: 91
Ticks: 26 Min: 1 Max: 91
Ticks: 27 Min: 1 Max: 91
<<<<< Context switches: 62, CPU usage: 11% >>>>>
Ticks: 28 Min: 1 Max: 92
Ticks: 29 Min: 1 Max: 92
Ticks: 30 Min: 1 Max: 92
Eventually, as the tick frequency increases, messages will be dropped
because the task that removes messages from the queue won't be able to
keep up with all the entries posted to the queue by the tick handler.
When this happens, you will see tick numbers being skipped and error
messages indicating that messages have been dropped. For full credit,
at 750 instructions/tick, the task should still be able to
occasionally remove an object from the queue and display the
"Ticks: # Min: # Max: #" text, even if you are holding
down a key and causing the CPU hog to run.
Pressing a key sets a global flag that causes a task to run. This
task saturates the CPU for five clock ticks and causes a series
of periods ('.') to be displayed. This output must be generated when
a key is pressed.
When the kernel runs the application code correctly, show and
demonstrate your code to a TA. Since you must demonstrate working
code to a TA on or before the due date, please consider their lab
schedule well in advance.
In addition to the demonstration, you must a written summary of
problems you encountered, if any, in completing this lab. You should
also include a report of the number of hours you spent on the lab,
including coding and debugging. A realistic estimate is
sufficient. Send a submission even if you didn't encounter any
noteworthy bugs along the way. You will not receive full credit for
the lab unless you send a report.
New for Fall 2019: we want both your report and your
source code for the lab. The easiest way to do this is to create a
report file (for consistency call it report.txt or report.pdf), to add
it to the working directory for the lab, to create a compressed tar
file (with all the files in your directory), and then to upload that
file to Learning Suite.
To review, if 425/labx is your working directory for this lab, type
the following in the 425 directory:
and then upload the resulting compressed tar file (submission.tar.gz)
to Learning Suite.
tar -cvzf submission.tar.gz labx
- This application code illustrates the use of message
queues. A steady stream of messages is generated by the tick handler
and sent to a specific queue emptied by a dedicated task (A). If the
queue is large enough, no data is lost even if the processing task is
unable to run for several clock cycles. Task B is a CPU hog that
keeps task A from running. Its busy bursts are triggered by the press
of any key and last for five clock ticks. Since additional keypresses
do not increase this total, the size of the queue should be such that
it does not overflow. (It would be easy to tinker with the
application source code and cause the queue to overflow, however.
Feel free to experiment with this.)
- Pacing yourself. Here is a statistical summary of hours
reported per team to complete this lab in Fall 2017:
- Low: 0.5 hours
- High: 6.0 hours
- Average: 3.6 hours
- Amount of code to be written. For comparison, here are
the sizes of the source files for my lab6 code written for the 8086
- myinth.c: 28 lines
- myisr.s: 32 lines
- yaku.h: 5 lines
- yakk.h: 49 lines
- yakc.c: 388 lines
- yaks.s: 65 lines
Here are comments from student reports (edited only for length)
describing their problems on this lab and how they tracked them down.
As always, take them with a grain of salt.
- We forgot to make sure that all global variables that are used in
multiple modules are declared as an extern.
- We didn't use Enter and Exit Mutex around the critical sections of
YKQPend and YKQPost.
- Didn't increment YKTickNum in modified interrupt handler. You need
to remember to do that.
- We'd re-enable interrupts right before we called the scheduler
(after posting to a queue) and sometimes we'd return to an ISR or
other function and the interrupts would be still be enabled when they
really needed to be disabled. A few Mutex() in the right places and
our lab worked fine!
- We forgot to return 1 from YKQPost so our interrupt handler kept
printing "Message queue full".
- We incremented our last parameter of the queue before assigning
the first value to the queue, so it gave a wrong initial tick count.
- We forgot to call YKDecrementDelay from the new tick handler,
caused functions to be delayed indefinitely, also forgot to have
YKQPend take tasks off the ready list when they were blocked, so some
messages were nonsense data.
- Problem: making sure that an ISR posting to a queue doesn't call
the scheduler. Fix: We used the ISR counter to determine that we were
at depth zero before calling the scheduler.
- We had a problem with a queue being stored to a void pointer at
the beginning of our YKQPend function. We did not check to see if
there were any messages in the queue until after we had made the
assignment. This made the void pointer point to something that it
should not have been pointing to. The variable needed to be assigned
after the delay of the queue becuase the queue was empty. We just
swapped a couple lines of code and then it worked fine.
- Our only bug was forgetting to call YKTickHandler() in the tick
- We had some logical errors in while checking to see which task
was pending on a given message. We had || instead of &&. easy fix.
- We didn't include everything from the tick isr when we copied it
over from lab 5. we assumed it was working fine when it wasn't.
- The most significant bug was in the tick handler. When the new
tick handler added for this lab would be executed, then only the idle
task would run after a few ticks. I had a routine in the original
tick handler that managed blocked tasks, and forgot to include that in
the new tick handler. When that was added to the new one, it worked
fine. Another bug I had was not making the pointer to the message in
YKQ a ** instead of a *.
- The only problem we encountered was that we were using the wrong
number to wrap our messges around.
- The bug that took some time to figure out was in our Dispatcher.
The problem came because we were enabling interrupts the instruction
before calling iret. So the code was getting interrupted before it
could pop the context off of the stack. This caused the currently
running task stack to overrun its bounds, overwrite some data, and
cause the system to crash. The thing we didn't know was that the iret
instruction effectively re-enable's interrupts by popping the flags
off the stack. So, our re-enable interrupts was redundant anyway.
The difficult thing about this bug was that it only occurred at high
tick frequencies. At low frequencies the interrupt didn't occur at
the critical point.
- The kernel bug had to do with our scheduler. We would disable
interrupts before calling it, but would not reenable them when
returning from it. This caused havoc with the lab 6 application code
because whenever task B would execute the interrupts would be disabled
(because the scheduler that placed task B in the running state never
reenabled them). Since task B depended on the ticker to know when to
exit we got caught in an infinite loop.
- The other bug was with our queue. We initially accessed the
queue using pointers. We don't know what the bug was, but it had
something to do with our pointers. When we suspected this we just
tossed out our whole message queue implementation and rewrote it using
a queue pointer with indexes for accessing its members instead of
pointers. After this our kernel worked.
- As soon as the queue functions were working properly, our main
bug was that we had a critical section of code that was being
interrupted. As soon as we disabled interrupts for that critical
section, our code worked fine.
- We did not have a firm understanding of the "static" qualifier as
used inside a function. We were re-initializing the 'next' and 'data'
static variables to 0 every time we entered YKTickHandler. This caused
dropped messages any time we hit a key to switch to the task that did
the prime number calculations (the program actually printed out
several times that the same tick was dropped), and the min and max
values were always 89. Fixing that problem was all we needed to do to
get our code working properly.
- We had problems designing our struct for the queue. We tried to
do it with pointers to the actual messages but when we changed it to
indexs in an array it worked great. We forgot to change the index for
the oldest message that we want to remove in the case that there are
no messages in the queue and we have to block it and call the
Scheduler. We needed to plan better at the begining too.
- I only had one minor bug that gave me trouble, when YKPost is
called from the interrupt handler it should not call YKScheduler. I
was getting some interesting errors, until I read about that on the
- A couple of the bugs that we spent some time on were not
re-enabling interrupts after returning from a call to the scheduler.
Another bug was not moving the tail if we returned from being blocked.
- We were not keeping track of the front and rear of the queue
properly. The head was sometimes moved 1 too many places. Sometimes we
would return that the queue was empty when in fact there was 1 message
in the queue.
- We didn't originally disable interrupts in YKQPost. When this
function was interrupted strange things would happen. Adding enter and
exit mutexes so the whole function was a critical section solved the
Last updated 26 August 2019