[OSy] Fifth extended assignment
Vojtech Horky
horky at d3s.mff.cuni.cz
Thu Dec 6 07:41:07 CET 2018
Dear all,
please see attached the assignment of the 5th 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
device drivers 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 January 2nd 2019 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. 5: Device Drivers
Extended Assignment
========================================================================
Date of assignment: December 6th 2018
Submission deadline: January 2nd 2019
------------------------------------------------------------------------
The goal of the 5th semestral task is to implement an input/output
device driver. 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.13 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.13 is available for
download from the following URL:
http://d3s.mff.cuni.cz/osy/download/kalisto-0.9.13.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.
Device Drivers ---------------------------------------------------------
Device drivers provide access to peripheral input/output devices.
These peripheral devices (unlike the basic parts of the computer
architecture, such as the CPU and memory) are usually quite diverse
and highly configurable.
Device drivers also commonly provide some degree of abstraction and a
unifying API to the code that uses them. The abstraction encapsulates
both the implementation details of a specific device (how it is
technically controlled and what resources are required for that) and
the differences between various devices. The unifying API usually
covers larger classes of similar devices (e.g. block devices,
character devices, graphics devices, etc.). The specific way how are
these unifying APIs designed and which devices are grouped under which
classes of drivers is a prominent distinguishing factor among
real-world operating systems.
A device driver links two communicating parties: The rest of the
operating system and user space applications (software interface) and
the device itself (hardware interface). Both communicating parties can
send requests to the other party and the goal of the device driver is
to effectively and efficiently negotiate this communication,
especially when dealing with multiple (virtual) communicating
end-points, different degrees of parallelism, etc. The device driver
usually tries to limit active waiting (polling) that wastes time and
resources.
From the software architecture point of view, the two interfaces of a
device driver have the following properties:
* Software interface
The part of the device driver that implements the software interface
is also called the "top half". The software interface is usually a
synchronous API represented by a set of functions that are provided
to the rest of the operating system. These functions are used for
sending requests to the device (the function call blocks and returns
only after the processing of the request has finished) and for
querying the device state.
Sometimes the software interface also provides an asynchronous
API to the device. This means that the caller is not blocked until
the processing of a request has finished, but the function call
returns immediately and the client is notified after the processing
has finished via some asynchronous means (e.g. changing a flag,
sending a message, invoking a signal, etc.).
The "top half" implements the data structures and bookkeeping
algorithms for the proper request spooling/queuing, especially if
there are multiple software end-points. This bookkeeping can also
include request prioritization. The "top half" also ensures proper
synchronization of accesses to the hardware registers of the device
and maintains the "soft state" of the device (a software
representation of the actual hardware state).
* Hardware interface
The part of the device driver that implements the hardware interface
is also called the "bottom half". The hardware interface is an
asynchronous interface that is triggered by the changes of the
device state. The driver is usually notified about the changes of
the device state via hardware interrupts.
A common change of the device state is associated with the finishing
of processing of a request. When the interrupt handler implemented
in the "bottom half" handles an interrupt that signals the finishing
of processing of a request, it matches this information with the
data structure representing the original request in the "top half",
updates the "soft state" and notifies the "top half" about the
result of the processing (i.e. it unblocks the thread that waits on
the result).
Simple device drivers implement the entire "bottom half" business
logic directly within the hardware interrupt handler. Device drivers
that are designed to efficiently handle more concurrent requests
implement only the minimal necessary pricessing within the hardware
interrupt handler. This minimal processing just fetches the
necessary data from the hardware, but more complex routines
(especially the "soft state" update) is deferred for later
processing outside the interrupt handler using various means.
The deferred processing of interrupts is also preferred for devices
that can autonomously generate a lot of interrupts (e.g. networking
devices). Although the deferred processing causes some overhead, it
shortens the duration of the interrupt handler code and thus it also
lowers the overall latency of the entire operating system (since the
overall latency is bounded by the duration of the non-preemptible
interrupt handlers). Given enough CPUs, this also improves the
throughput of the "bottom half".
Some real-world operating systems even consider the "deferred
processing" as a separate part of the software architecture of
device drivers.
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 a simple ddisk [2] block device driver in Kalisto. The
device driver should provide a synchronous (blocking) API for reading
and writing disk blocks.
The ddisk device can physically handle only a single read/write
request at a time. However, the device driver should allow multiple
independent threads to issue multiple independent read/write requests
without active polling and the driver should be also designed in such
a way to support extending the ddisk capabilities in the future (i.e.
anticipating the capability to physically handle multiple read/write
requests at a time). This means that the driver should implement full
request spooling/queuing.
The hardware interface of the driver should be driven by the
interrupts generated by the ddisk device. The driver should also avoid
active polling whenever possible. However, it is sufficient to support
just a single ddisk device.
The driver is required to implement the following synchronous API:
* void disk_init(void)
This function initializes the data structures of the ddisk driver.
It is called from the bsp_main() function of the kernel that
initializes the kernel on the bootstrap CPU.
* int disk_get_nblocks(size_t *nblocks)
This function returns the number of blocks that are available on the
ddisk device in the @nblocks output argument. The size of a block in
bytes is defined by the DISK_BLOCK_SIZE constant (according to the
specification of the ddisk device, the current value is 512). The
function returns EOK if the number of blocks could be successfully
determined. If the operation fails, then the function returns an
appropriate error value.
* int disk_read(size_t block, void *data)
This function reads a block with the index @block from the ddisk
device (the indexing starts with 0) and stores the data into the
buffer determined by the virtual address @data. The caller is
expected to provide a buffer sufficiently large to store exactly
DISK_BLOCK_SIZE bytes of data. The function returns EOK if the
reading is successful and EINVAL if the requested block is not
available on the device. If the operation fails, then the function
returns an appropriate error value.
Active polling of the device should be avoided, the current
(calling) thread should be blocked until the request has been
processed. Each request should be enqueued to support extending the
ddisk capabilities in the future (i.e. physically handling multiple
requests at a time, including potential request prioritization and
media access strategies).
* int disk_write(size_t block, void *data)
This function writes DISK_BLOCK_SIZE bytes from the buffer
determined by the virtual address in the @data argument to the ddisk
block with the index @block (the indexing starts with 0). The
function returns EOK if the writing is successful and EINVAL if the
requested block is not available on the device. If the operation
fails, then the function returns an appropriate error value.
Active polling of the device should be avoided, the current
(calling) thread should be blocked until the request has been
processed. Each request should be enqueued to support extending the
ddisk capabilities in the future (i.e. physically handling multiple
requests at a time, including potential request prioritization and
media access strategies).
Unit Tests -------------------------------------------------------------
The unit tests that validate the functionality of the implementation
can be found in the kernel/tests/disk subtree of the source tree of
Kalisto 0.9.13. The infrastructure for running and evaluating the
tests can be executed using the tests-disk.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 polling,
it must enqueue requests, the tests must finish in a reasonable time,
etc.). Modification of the internal logic of the tests is forbidden.
Note: When the tests finish successfully, they revert the block device
to the original state. However, if the tests fail half-through their
execution, the block device could be left in a "broken" state not
suitable for running the tests again. Have a backup of the original
block device ready.
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, Chapter 4. Device
Management, http://d3s.mff.cuni.cz/~ceres/sch/osy/text/ch04.html
[2] MSIM ddisk device specification,
http://d3s.mff.cuni.cz/~holub/sw/msim/reference.html#ddisk
[3] Wikipedia: Device driver,
https://en.wikipedia.org/wiki/Device_driver
[4] Wikipedia: Interrupt handler,
https://en.wikipedia.org/wiki/Interrupt_handler
More information about the NSWI004
mailing list