Lab #4: Design and Implementation of Kernel Essentials
In this lab, you begin writing the actual code for your implementation
of the YAK kernel. You will be required to implement a small number of
the kernel functions in order to run a very basic application
program. You are expected to complete this lab with a partner.
Start by creating a directory with all the source files necessary for your
kernel, including the makefile. Suggested filenames and their purposes are given in the
YAK Specification document. Make sure you
backup often so that you never
accidentally lose any of your source files! It is also recommended that
you make a new copy of your code in a new folder for each lab.
Once you have your files set up, you can begin writing your kernel according
to the implementation decisions you made in the last lab.
For this lab you only need to implement a small subset of YAK's overall
specification. The kernel features you must implement are listed below:
In addition to these required functions, you must have ISRs and
interrupt handlers that function exactly as in lab 3. Keep in mind
all the other YAK functions that will be added to your code in later
labs. If you are not careful or if you take shortcuts then you may
need to rewrite and re-debug parts of your code in later labs. In
particular, think about what functions must be reentrant in your
kernel, and be sure to recognize and address critical sections in the
code you write. This can save you many hours of added work down
- YKInitialize - Initializes all required kernel data structures
- YKEnterMutex - Disables interrupts
- YKExitMutex - Enables interrupts
- YKIdleTask - Kernel's idle task
- YKNewTask - Creates a new task
- YKRun - Starts actual execution of user code
- YKScheduler - Determines the highest priority ready task
- YKDispatcher - Begins or resumes execution of the next task
- YKCtxSwCount - Global variable that tracks context switches
- YKIdleCount - Global variable incremented by idle task
The application code you will use for this lab, lab4b_app.c, creates a total of three
tasks. The first task, task A, is created in main()
before YKRun() is called. Task B is then created within
task A, but has a lower priority than task A, and therefore should not
run. Next, task C is created within task A and task C has a higher
priority than task A, and should therefore run immediately. This will
help verify that your kernel can properly create, schedule, and
Once you have implemented these functions, your kernel must be able to run the
application code correctly without
crashing. As before, your code must work correctly even when a key is held down
or when any key sequence is typed in rapid succession. It must also support a
tick frequency of every 750 instructions.
When your kernel runs correctly, the application program's output should closely
resemble the following after it starts running:
The only thing that may differ when run with your kernel is the position of the
"TICK n" lines relative to the other lines of output.
Creating task A...
Task A started!
Creating low priority task B...
Creating task C...
Task C started after 2 context switches!
Executing in task C.
Executing in task C.
Executing in task C.
Executing in task C.
When your kernel runs the given application code correctly, show and
demonstrate your code to a TA. Since you must demonstrate working
code to a TA, please consider their lab schedule well in advance.
If you complete the lab after the last TA hours on the due date, you
can still get full credit based on the time stamps on the relevant
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
Important Notes and Recommendations
- Known tool problems. There are some bugs with the tools that you should be aware of.
It is strongly recommended that you take a good
look at the Known Tool Problems page so that you don't waste any time
trying to figure out bugs that aren't yours.
- yakk.h and yaku.h. You should start
writing the files yakk.h and yaku.h (or whatever
you have chosen to name them)
as part of this lab. The file yakk.h should include the things
that the application code may need access too. For example, it should include
extern declarations for things defined in yakc.c, such as YKCtxSwCount and YKIdleCount,
as well as the prototypes for the kernel functions. This file should not include
any code or definitions that the application programmer might need to modify.
Anything that the application programmer might need to modify should be part
of the file yaku.h. This will include the
#define statements for the maximum number of tasks, the maximum number of semaphores,
and the maximum number of message queues (semaphores and queues will be
added in later labs). Ask a TA for clarification if any of this is unclear to you.
- Saving and restoring context. When saving or restoring the context do not push or pop
the registers SP or SS. When it is needed, use other methods to save and restore
SS and SP as part of a task's context (e.g., the mov instruction). You can use the pushf
instruction to save flags, but keep in mind that CS, IP, and the flags are saved automatically by the CPU when an interrupt occurs.
When leaving an ISR or dispatching a
task, iret should always be the last
instruction executed. This is important since it is the only way to restore CS, IP,
and the processor flags in one atomic operation. Also, keep in mind that restoring the flags restores the interrupt flag (IF),
which enables or disables interrupts.
- Pointers, lists, and TCBs in C. For those new to C and
not entirely comfortable with pointers and the creation and
manipulation of linked lists, please note that some code
fragments of interest have been posted. Check out the Code Sample
here, or by going to the main lab page and clicking on the code
example link under "C Help". The code gives a sample TCB struct definition
and gives examples of insertion in and deletion from a doubly linked
You will also need to define NULL in one of your header files
if you intend to use it. Normally
NULL is defined in the library .h files you include, since it is often used with library
functions. However, since none of our library functions use NULL, it has not yet
been defined. It is often defined in the following way:
#define NULL 0
- Setting up the environment for development and
debugging. Make sure you are using scroll bars, a decent file
organization, and make files. Command
completion and a prompt with the full current path can also be useful.
Links to information about
all of these are readily found on the class lab page. Take the time
to make the changes up front.
- Designing for debugging. For most of you it will prove
extremely useful to create routines that dump internal kernel state in
an organized way that can be called at any point in your code as
needed when debugging. For example, you will probably need to see
everything that is on the ready list, and/or see the state of all
current tasks. Taking the time to write this code up front can save
you many hours over the long haul. To keep the code size small when
debug statements are not needed, you can use #ifdef to avoid allocating space
for these routines when you don't need them. You should also
avoid writing code in assembly language except where absolutely necessary.
Assembly code is much more difficult to debug and maintain. You are also
strongly encouraged to avoid all inline assembly.
Here is the key point:
as you design and implement your kernel, think about how you will
debug it, and don't hesitate to build some infrastructure to make
testing and debugging easier.
- Test as you go. Don't fall into the trap of writing your entire
kernel then running it for the first time to find that it doesn't work. Try to test your
code as you progress so that you know the parts you have written work the way
you expect. Doing so can save you debugging time in the long run.
This is especially important for tricky pieces of code such as
inserting into and searching linked lists and queues.
- Thorough design. How can you ensure that you have
considered everything you need in the design stage? You should
carefully consider all the information on the YAK description page as well
as the questions from the lab 4a.
Beyond that, there is no sure-fire way to avoid all problems, but you
are encouraged to think about the sequence of events in the
execution of the application program provided with this lab.
YKInitialize first sets up kernel data structures, then a task is created.
No task should begin execution until
the call to YKRun is made, which ends the initialization
phase and begins the execution phase. During initialization,
interrupts should be ignored and the scheduler and dispatcher should
never run, even though routines will be called (such as YKNewTask) which
would normally call the scheduler, which could then call the dispatcher.
How might you implement this? You could, for example,
use a global flag of some type that is initialized to one value, then
set to a second value by YKRun. Certain routines will need to test
this flag to make sure that the application is running. After setting
the flag, YKRun must call the scheduler, which then calls the dispatcher, to fire up the highest
priority ready task. Note that this is NOT a normal function call;
execution will never return to this main function once YKRun is
- Pacing yourself. Plan on starting each part of this lab early and allocating plenty
of time. Debugging this type of code is very difficult
and can be very time consuming.
Here is a statistical summary of the total time spent on part B in Fall 2017,
according to the reports submitted by each group:
- Low: 5.0 hours
- High: 21.0 hours
- Average: 11.4 hours
- Amount of code to be written. The kernel web page
recommends a particular file organization for your source code. As a
general indication of the effort required, here are the sizes of
Dr. Archibald's source files for all of lab 4 (parts b, c, and d, not counting
comments, documentation, and debugging code):
- myinth.c: 21 lines
- myisr.s: 32 lines
- yaku.h: 3 lines
- yakk.h: 12 lines
- yakc.c: 158 lines
- yaks.s: 65 lines
The link below points to a list of comments from student reports for lab 4
(parts B, C, and D) describing specific problems they encountered.
You are strongly encouraged to read the list. However, take all these
with a grain of salt; the submitters may have made very
different design decisions than you have. However, you can glean a
great deal of useful information by reading them carefully.
Student Problem List
Last updated 4 September 2019