[OSy] Third extended assignment
Vojtech Horky
horky at d3s.mff.cuni.cz
Thu Nov 8 08:32:23 CET 2018
Dear all,
please see attached the assignment of the 3rd extended semestral task of
the Operating Systems course. This extended assignment is intended for
those who want to solve the task independently at home in order to gain
the "conditionally fulfilled" status for this topic.
However, please read and try to understand the text of the extended
assignment even if you plan to attend the labs. The assignment for the
labs will be related to the extended assignment (the topic will be
synchronization too) and also the required knowledge and recommended
literature will be the same.
Practically, a good plan is to start work on the extended assignment
before the labs (at least prepare the basic skeleton of the assignment),
come to the labs and in the event of failing the labs, finish the
homework. Definitely the time spent implementing the extended assignment
will not be lost even if you plan to attend the labs.
If you choose to implement the extended assignment, please respect the
deadline of November 26th 2018 AoE.
Please send your implementation via e-mail to the following address:
nswi004 at d3s.mff.cuni.cz
You should send your implementation as an archive (zip, tar.bz2, etc.)
in the attachment of the e-mail. Please make sure to include everything
necessary to run your implementation, to run the required unit tests and
to evaluate your source code. You can also use the `make dist' target
from the main Makefile to package your solution.
We will try to evaluate your submissions as they arrive, but we cannot
guarantee a specific reply latency. Therefore please avoid (in your own
interest) sending your implementation at the last moment, because we
might not be able to point you in time to some small issues in order for
you to fix them.
If you should have any questions (either specific to the assignment or
of a generic nature), please do not hesitate to send your query to this
mailing list.
Best regards,
- Vojtech Horky
-------------- next part --------------
========================================================================
Operating Systems Course
Semestral Task
Topic no. 3: Synchronization
Extended Assignment
========================================================================
Date of assignment: November 8th 2018
Submission deadline: November 26th 2018
------------------------------------------------------------------------
The goal of the 3rd semestral task is to implement a passive
synchronization primitive. The task is defined by a functional
programming interface that needs to be implemented and it is
accompanied by a set of unit tests that the implementation must
successfully pass.
Use the source code of Kalisto version 0.9.12 as the basis for your
implementation. i.e. start with the source code of Kalisto and extend
it by the required functionality. Kalisto 0.9.12 is available for
download from the following URL:
http://d3s.mff.cuni.cz/osy/download/kalisto-0.9.12.tar.bz2
If the assignment does not define an aspect of the required
implementation specifically or precisely, then the expected behavior
of the implementation is defined by the unit tests. If even the tests
do not define an aspect of the required implementation specifically or
precisely, then use your best knowledge and professional judgement to
implement the functionality in the most reasonable way and document
your decisions using comments in your source code.
Note on the Kernel Interface -------------------------------------------
Many parts of the Kalisto kernel are designed to follow one of the
following interface styles. These two interface styles define the way
objects (data structures) are created and accessed and they also
define two levels of encapsulation.
* The first interface style provides weaker encapsulation. Thus the
API exposes the internals of the objects and the object variables
are pointers. The objects of this interface style are usually static
(they are either allocated on the stack or as global variables). The
API provides the xxx_init() functions for initializing the objects
and the xxx_destroy() functions for cleanup.
It is possible to allocate such objects dynamically (i.e. on the
heap), but it is not common and the caller is responsible for the
allocation and disposal of the objects.
The API does not usually return an error value if an invalid pointer
is passed to it, because such an error is usually fatal for the
kernel. However, it is possible to include non-NULL assertions and
other integrity assertions in the routines that manipulate these
objects for debugging purposes. The integrity check is commonly
implemented using a "magic" field that must always have a constant
predefined value.
This interface style is used for synchronization primitives.
* The second interface style provides stronger encapsulation. Thus the
API does not expose the internals of the objects and the object
variables use opaque typedefs. These opaque types mask the fact that
the objects might be technically pointers or handles. The API
provides the xxx_create() functions that creates (including
allocation), initializes and activates new objects. The activation
might include inserting the new object into some internal
bookkeeping data structures.
The objects of this interface style are usually dynamic. Only very
rarely are these objects static, but this is nevertheless hidden
from the caller.
The API does return an error value if an invalid variable is passed
to it, because such an error is usually not fatal for the kernel.
This interface style is used for threads. For example, the
thread_create() function allocates and initializes the thread
control structure and the thread stack, but it also inserts the
thread into the scheduling queue.
General Recommendations for the Implementation -------------------------
The following recommendations capture the usual criteria of quality of
source code that is generally expected in critical system-level
software. While respecting these recommendations is slightly less
binding than the functional requirements of the assignment, severely
violating them might still lead to rejection of your implementation.
- Avoid using non-trivial hard-wired numerical constants in the source
code. Use properly named reusable macros.
- Use empty lines and block comments as visual delimiters to
consistently demark logical parts of the source code.
- Use consistent horizontal spacing to improve the readability and
comprehension of the source code. This includes both spaces in
expressions and proper indentation.
- Avoid creating overly long functions, functions with an excessive
level of block nesting and functions that implement an excessive
number of distinct logical operations. The function name should
adequately capture the summary of the function logical operation.
- Avoid creating source files that mix logically unrelated concerns or
functionality. Avoid placing source files into unrelated
directories.
- Use properly named macros or inline functions as replacements for
complex logical and arithmetic expressions.
- Use a consistent coding style (similar constructs should use similar
means). Match the coding style of the new code with the coding style
of the existing code.
- Use English for identifiers and comments. Use a consistent way of
naming things and a consistent way of commenting.
Task Assignment --------------------------------------------------------
Implement semaphores, a standard passive synchronization primitive.
The code that uses the semaphores to guard a critical section might
look as follows (an extremely simplified example):
struct semaphore sem;
sem_init(&sem, 100);
/* ... */
sem_down(&sem);
/* Critical section */
sem_up(&sem);
/* ... */
sem_destroy(&sem);
Note that a thread can be preempted at any time unless the interrupts
are disabled. This assignment mandates correct synchronization on a
single-CPU configuration only, thus disabling interrupts is sufficient
to prevent thread interleaving.
The semaphores are required to implement the following API:
* void sem_init(struct semaphore *sem, const int value)
This function initializes a semaphore @sem to the initial value
@value. The maximum value (see further) is set to infinity.
* void sem_init_limit(struct semaphore *sem, const int value,
const int limit)
This function initializes a semaphore @sem to the initial value
@value and also sets the maximum semaphore value to @limit. The
implementation must guarantee that the value of the semaphore
never exceeds the maximum value.
Setting the initial value and the maximum value of a semaphore to 1
turns the semaphore into a binary semaphore (also commonly referred
to as a non-recursive mutex or simply a lock).
* void sem_destroy(struct semaphore *sem)
This function disposes of the semaphore control structure @sem. If
there are threads still blocked on the disposed semaphore, the
function causes a kernel panic.
* int sem_get_value(struct semaphore *sem)
This function returns the current value of the semaphore @sem.
* void sem_up(struct semaphore *sem)
This function increments the value of the semaphore @sem by 1 and
potentially unblocks one of the threads that is blocked on the
semaphore (if the original value of the semaphore was 0). If the new
value of the semaphore is larger that the maximum limit of the
semaphore, then the value is set to the maximum limit.
* void sem_down(struct semaphore *sem)
This function decrements the value of the semaphore @sem by 1 if it
is possible (i.e. if the original value of the semaphore is > 0).
If the decrementation is not possible (i.e. if the original value of
the semaphore is == 0), then the calling thread is blocked.
Implement also the functionality of the non-recursive mutexes by
converting the following mutex calls to appropriate semaphore calls
(this can be achieved simply using preprocessor macros).
* mutex_init(struct mutex *mtx)
* mutex_lock(struct mutex *mtx)
* mutex_unlock(struct mutex *mtx)
* mutex_destroy(struct mutex *mtx)
Helper Routines --------------------------------------------------------
The correct implementation of the semaphores should make use of the
routines already present in the source code of Kalisto, potentially
extending them if needed. This is a brief summary of some of the most
relevant routines.
* ipl_t query_and_disable_interrupts(void)
This function returns the current state of interrupts on the current
CPU (as defined by a CP0 control register) and disables interrupts
on the current CPU.
* void conditionally_enable_interrupts(ipl_t state)
This function enables interrupts on the current CPU if the state
@state stored by a previous call of query_and_disable_interrupts()
indicates enabled interrupts.
* thread_t thread_get_current(void)
This function returns the identification of the current (calling)
thread.
* void thread_suspend(void)
This function blocks the current (calling) thread until it is
unblocked by a different thread by calling thread_wakeup().
* int thread_wakeup(thread_t thread)
This function unblocks the thread identified by the @thread
argument. The current (calling) thread continues in its execution,
it is not unscheduled only due to calling of this function. If the
thread identifier @thread is invalid, then the function returns
EINVAL. Otherwise the function returns EOK.
* void thread_yield(void)
The current (calling) thread relinquishes the CPU (it is forcefully
unscheduled). The thread eventually continues in its execution when
it is scheduled again.
Unit Tests -------------------------------------------------------------
The unit tests that validate the functionality of the implementation
can be found in the kernel/tests/sem subtree of the source tree of
Kalisto 0.9.12. The infrastructure for running and evaluating the
tests can be executed using the tests-sem.sh shell script. Your
implementation must successfully pass all the supplied tests in a
non-trivial way (i.e. the implementation must not use active waiting,
the tests must finish in a reasonable time, etc.). Modification of the
internal logic of the tests is forbidden.
Some of the tests from kernel/tests/mutex could be optionally adapted
to test the behavior of the mutex API implemented via the semaphores.
Delete the original binary implementation of semaphores and mutexes
(kernel/synch/sem.obj and kernel/synch/mutex.obj) from the source tree
of Kalisto to make sure that the tests validate your original
implementation.
To integrate your implementation with the tests, add necessary
#include directives to the kernel/api.h header file to make sure
all required declarations are available for the tests.
Recommended Literature -------------------------------------------------
[1] Operating Systems Course study material, Section 2.4. Process
Synchronization,
http://d3s.mff.cuni.cz/~ceres/sch/osy/text/ch02s04.html
[2] Wikipedia: Semaphore (programming),
https://en.wikipedia.org/wiki/Semaphore_(programming)
[3] Downey A. B.: The Little Book of Semaphores,
http://greenteapress.com/semaphores/
More information about the NSWI004
mailing list