Subversion Repositories shark

\documentclass[english]{report}

\usepackage[T1]{fontenc}

\usepackage[latin1]{inputenc}

\usepackage{a4wide}

\setcounter{secnumdepth}{3} \setcounter{tocdepth}{3}

\usepackage{graphicx}

\makeatletter

\usepackage{babel}

\makeatother

\begin{document}

\thispagestyle{empty}

\begin{center}{\LARGE S.Ha.R.K. User Manual}\end{center}{\LARGE \par} \vfill{}

\begin{center}{\large Volume VI}\end{center}

\begin{center}S.Ha.R.K. File System\end{center} \vfill{}

\begin{center}Written by\end{center}

\begin{center}Paolo Gai (pj at sssup.it)\end{center}

\begin{center}Tullio Facchinetti (tullio.facchinetti at unipv.it)\end{center}

\begin{center}Original italian version by\end{center}

\begin{center}Massimiliano Giorgi (massy at gandalf.sssup.it)\end{center}

\vfill{}

\begin{center}\includegraphics[width=2cm]{../common/sssup.ps}\end{center}

\begin{center}Scuola Superiore di Studi e Perfezionamento S. Anna\end{center}

\begin{center}RETIS Lab\end{center}

\begin{center}Via Carducci, 40 - 56100 Pisa\end{center}

\begin{center}\pagebreak\end{center}

\tableofcontents{}

\listoffigures

\listoftables

\begin{abstract}

This is the documentation about S.Ha.R.K. File system. The document gives an

insight on many data structures used internally by the file system. This is the

first step toward a \emph{true} file system user manual. If you carefully read

it, you will understand how it works, how can be initialized and used.

In any case, please send any comments to pj@sssup.it.

Enjoy,

Paolo

\end{abstract}

%----------------------------------------------------------------------------

\chapter{File system architecture}

\label{sec:arch}

%----------------------------------------------------------------------------

%----------------------------------------------------------------------------

\section{Features}

%----------------------------------------------------------------------------

\label{sec:arch:gen}The library is composed by two main layers:

\begin{description}

\item [File-system] The file system contains all the data structures used to

handle files.

\item [Blocks~devices]This part handles directly the hardware. They provide a

common interface that unifies the usage of all the block devices (i.e., the hard

disks).

\end{description}

The architecture of the library is modular, and it is described in

Figure \ref{fig:Filesystem-architecture}.

\begin{figure}

\begin{center}

\includegraphics[width=6cm]{images/arch2.eps}

\end{center}

\caption{File system architecture}

\label{fig:Filesystem-architecture}

\end{figure}

The library is connected to the Kernel via a \emph{glue} layer, to

the application via a \emph{wrapper} layer; the block devices and

the file system operations are separated by a cache, that may be

excluded.

\label{sec:arch:req}

The library needs a set of primitives that must be supported by

the underlying kernel, as memory handling, string handling, and

functions with a variable number of parameters. Moreover, the

kernel should support functions that implement:

\begin{itemize}

\item Mutual exclusion.

\item Allocation of low level resources (as I/O spaces and interrupts).

\item Memory protection (not needed in S.Ha.R.K.).

\end{itemize}

%----------------------------------------------------------------------------

\section{Low Level: Device Drivers}

%----------------------------------------------------------------------------

\begin{figure}

\begin{center}

\includegraphics[width=6cm]{images/archlow.eps}

\end{center}

\caption{Device Drivers}

\label{fig:archlow}

\end{figure}

The device drivers are divided in two main parts:

\begin{itemize}

\item A general part that exports the basic low level services. It

also gives a set of internal routines to the internal modules.

\item A set of internal modules that handle one or more

peripherals. The application can choose which module must be

linked, initialized and used at compile time.

\end{itemize}

\begin{figure}

\begin{center}

\includegraphics[width=6cm]{images/archlow2.eps}

\end{center}

\caption{Device Drivers - details}

\label{fig:archlow2}

\end{figure}

The general part is composed by four modules:

\begin{description}

\item [Block~device]The main part; it exports the interface to the upper layers,

inits the device driver subsystem and register all the drivers present in the

system.

\item [Logical~disk]This module provides functions that allow to inspect the

logical structure of an hard disk, like start, end, size and type of each

partition on the Hard Disk.

\item [Physical~disk]This module provide a small data base that contains

informations about all the hard disks in the system; these informations can be

useful for the module that must handle the low level pending request queues.

\item [Queue~policy]This module handles the low level policies for the pending

requests (SCAN, LOOK, EDF, ...).

\end{description}

%----------------------------------------------------------------------------

\section{High Level: File systems}

%----------------------------------------------------------------------------

\begin{figure}

\begin{center}

\includegraphics[width=10cm]{images/archhigh.eps}

\end{center}

\caption{High Level - File system details}

\label{fig:archhigh}

\end{figure}

The high level is divided in three parts:

\begin{itemize}

\item The first part handle the file systems, its initialization and its

interface to the internal modules.

\item A second part composed by a set of modules that implement a particular

file system (i.e., FAT16).

\item A cache module (whose policy can be easily changed).

\end{itemize}

The first part is composed by sub-modules (internal implementation

of a sub-module can be changed without affecting the rest of the

library):

\begin{description}

\item [Filesystems]It is responsible for the initialization and termination of

all the high level layer. It registers all the file systems, and it contains the

routines for mounting/unmounting the partitions.

\item [File]It handles the descriptor tables and the files; it defines the

\texttt{file} structure.

\item [Super]It handles the super blocks (that contains the global informations

about partitions on a disk).

\item [Inodes]It handles the inodes (informations about a file in the file

system).

\item [Dentry]It handles file names in a tree structure.

\item [Open,~read,~umask,~...]They implement the correspondent system

primitives.

\end{description}

%----------------------------------------------------------------------------

\chapter{Device drivers}

\label{sec:dd}

%----------------------------------------------------------------------------

%----------------------------------------------------------------------------

\section{Interface}

\label{sec:dd:interfaccia}

%----------------------------------------------------------------------------

%----------------------------------------------------------------------------

\subsection{Initialization}

\label{sec:dd:interfaccia:init}

%----------------------------------------------------------------------------

\begin{table}

\begin{verbatim}

typedef struct bdev_parms {

    __uint32_t showinfo;

    char *config;

    void *bmutexattr;

    __uint16_t dummy;

#ifdef IDE_BLOCK_DEVICE

    IDE_PARMS ideparms;

#endif

} BDEV_PARMS;

void bdev_def_showinfo (BDEV_PARMS s, int v);

void bdev_def_configstring(BDEV_PARMS s, char *v);

void bdev_def_mutexattrptr(BDEV_PARMS s,void *v);

\end{verbatim}

\caption{The BDEV\_PARMS structure}

\label{tab:BDEV_PARMS}

\end{table}

The bdev\_init() function (see Table \ref{tab:BDEV_PARMS}) must be

called to initialize a device driver, passing a pointer to a

BDEV\_PARMS structure. Use the provided macros to init that

structure.

The structure is composed by two parts: a generic part and a

specific part. The generic part is composed by the following

fields:

\begin{description}

\item [showinfo]If this flag is set, the initialization of the device will be

``verbose''. To set this flag, use the macro bdev\_def\_showinfo.

\item [config]It is a string that can have a particular meaning for the device

driver. The string is parsed by the device driver, that usually searches for

some initialization parameter (something like ``foo:[number]''). To set this

string, use the macro bdev\_def\_configstring.

\item [bmutexattr]This parameter can be used to tell the system which is the

kind of mutex to use to implement the mutual exclusion. To set this parameter,

use the macro \texttt{bdev\_def\_mutexattrptr}.

\item [dummy]Used to align the data structure (see the macro BASE\_DEV).

\end{description}

The specific part is directly specified by the device driver; the

bdev\_init function can be called can be called passing a pointer

to a BDEV\_PARMS structure initialized with a BASE\_BDEV value. If

NULL is specified, the default values are used.

%----------------------------------------------------------------------------

\subsubsection{How to create a new device driver}

%----------------------------------------------------------------------------

\begin{enumerate}

\item Add a new \emph{major} number in t the file include/fs/major.h (see

\ref{sec:dd:interfaccia:nomi});

\item Add a ``\#define'' into the file include/fs/bdevconf.h (to enable

selective compilation);

\item If needed, add fields to bdev\_parms, and modify the BASE\_BDEV macro with

the new default parameters;

\item Modify the function bdev\_init to call the init function of the new device

driver (into drivers/block/bdev.c).

\end{enumerate}

\begin{figure}

\begin{center}

\includegraphics[width=7cm]{images/ddinit.eps}

\end{center}

\caption{Device Drivers Initialization.}

\label{fig:ddinit}

\end{figure}

The device driver initialization function, after the

initialization of its internal part, does the following actions

(see Figure \ref{fig:ddinit}):

\begin{enumerate}

\item It registers itself calling bdev\_register(); That function must be called

for each device handled by the driver.

\item It registers every block device that it find into its interfaces to the

Physical Disk Module.

\item It registers every logical device found calling bdev\_register\_minor().

\end{enumerate}

Data structures and registration functions used in this phased are

described in Section \ref{sec:dd:interfaccia:det}.

%----------------------------------------------------------------------------

\subsection{Device serial number}

\label{sec:dd:interfaccia:nomi}

%----------------------------------------------------------------------------

\begin{figure}

\begin{center}

\includegraphics[width=7cm]{images/devtype.eps}

\end{center}

\caption{Device Serial Number}

\label{tab:devtype}

\end{figure}

Every logical device (i.e., a logical partition of a hard disk)

has a device serial number of type \_\_dev\_t, that must have a

unique value (see the POSIX standard).

The number has an internal structure (see Figure

\ref{tab:devtype}) composed by a \emph{major} \emph{number}, and

another number (whose number depends on the device implementation)

called \emph{minor} \emph{number}.

Three macro exists (see include/fs/sysmacro.h) to handle the

device numbers:

\begin{description}

\item [makedev]This macro creates a \_\_dev\_t number from the major and the

minor number.

\item [major]Returns the major number of a device.

\item [minor]Returns the minor number of a device.

\end{description}

The major number is used to decide which device driver will handle

a request (see Section \ref{sec:dd:interfaccia:det}). A device

driver can register more than on major number. Minor numbers are

device driver dependent, and the validity of a minor number is

checked only by the driver.

To simplify the search of a device, every device has a symbolic

name (see Section \ref{sec:dd:intercaccia:ext}). Symbolic names

are composed by two parts: a unique name for each major, and a

specific name assigned to each minor. For example, the major

MAJOR\_B\_IDE has a symbolic name ``ide''; a minor name for that

major can be ``hda2'', so the full name is ``ide/hda2'', that

identifies the second partition on the master hard disk on the

first IDE controller interface (see Section \ref{sec:dd:ide}).

%----------------------------------------------------------------------------

\subsection{Implementation details}

\label{sec:dd:interfaccia:det}

%----------------------------------------------------------------------------

\begin{table}

\begin{verbatim}

int bdev_register(__dev_t major, char *name, struct block_device *);

int bdev_register_minor(__dev_t device, char *name, __uint8_t fsind);

struct phdskinfo *phdsk_register( struct phdskinfo *disk);

\end{verbatim}

\caption{Block device registration functions}

\label{tab:Block_register}

\end{table}

These are the registration functions for the device drivers (see

Table \ref{tab:Block_register}):

\begin{description}

\item [bdev\_register]This function registers a device type (see Section

\ref{sec:dd:interfaccia:nomi}); the function receives as parameter the major

number, its symbolic name, and a pointer to a structure block\_device. The

function returns 0 in case of success, != 0 otherwise.

\item [bdev\_register\_minor]It registers a minor number, its symbolic name and

the file system type (see include/fs/fsind.h). This information is used by

bdev\_finddevice\_byname (see Section \ref{sec:dd:intercaccia:ext}). The

function returns 0 in case of success, != 0 otherwise.

\item [phdsk\_register]This function is used to register every physical device

found with parameters that can be used by the Disk Scheduling Algorithms (see

Section \ref{sec:dd:sched}). This function receives a pointer to a structure

phdiskinfo that contains the device parameters, and returns NULL in case of

error, or a pointer to the registered structure (that can be != from the

parameter) in case of success.

\end{description}

\begin{table}

\begin{verbatim}

struct dskgeometry {

    __uint16_t cyls;

    __uint16_t heads;

    __uint16_t sectors;

};

struct phdskinfo \{

    char pd_name[MAXPHDSKNAME];

    __dev_t pd_device;

    __blkcnt_t pd_size;

    int pd_sectsize;

    struct dskgeometry pd_phgeom;

    struct dskgeometry pd_logeom;

};

\end{verbatim}

\caption{The phdsk structure.}

\label{tab:structphdsk}

\end{table}

The phdskinfo structure contains the physical parameters of a

device. all the field must be filled before calling

phdsk\_register. The fields are:

\begin{description}

\item [pd\_name]device name, used only for debug purposes;

\item [pd\_device]device identificator;

\item [pd\_size]number of logical sectors of the device;

\item [pd\_sectsize]Dimension (bytes) of a logical sector;

\item [pd\_phgeom~e~pd\_logeom]geometry of the device (logical and phisical);

geometries are described using the struct dskgeometry (see Table

\ref{tab:structphdsk}):

\begin{description}

\item [cyls]number of cylinders (traces) of the device;

\item [heads]number of heads;

\item [sectors]number of sectors for each cylinder.

\end{description}

\end{description}

\begin{table}

\begin{verbatim}

struct block_device {

    char *bd_name;

    int bd_sectorsize;

    __uint32_t bd_flag_used:1;

    struct block_device_operations *bd_op;

};

\end{verbatim}

\caption{block\_device Structure}

\label{tab:structbdev}

\end{table}

The struct block\_device described in Table \ref{tab:structbdev}

is used to register the block devices:

\begin{description}

\item [bd\_name]Physical device name; for example, for the IDE device driver,

``ide''.

\item [bd\_sectorsize]logical sector dimension (bytes; redundant info but

useful).

\item [bd\_flag\_used]It should not modified by the device drivers. If set, the

corresponding device driver is present (a table of all the possible devices is

used to access the system in a fast way).

\item [bd\_op]Virtual device operations.

\end{description}

%----------------------------------------------------------------------------

\subsubsection{block\_device\_operation structure.}

\label{sec:dd:interfaccia:det:bdevop}

%----------------------------------------------------------------------------

\begin{table}

\begin{verbatim}

struct block_device_operations {

    int (*_trylock) (__dev_t device);

    int (*_tryunlock)(__dev_t device);

    int (*read) (__dev_t device, __blkcnt_t blocknum, __uint8_t *buffer);

    int (*seek) (__dev_t device, __blkcnt_t blocknum);

    int (*write) (__dev_t device, __blkcnt_t blocknum, __uint8_t *buffer);

};

\end{verbatim}

\caption{block\_device\_operations structure.}

\label{tab:structbdevop}

\end{table}

This structure contains the virtual operation that have to be

supplied by every device driver:

\begin{description}

\item [read]This function should read a logical pblock passed as parameter,

writing the result on the buffer. It returns 0 in case of success, != 0

otherwise.

\item [write]Similar to read, but it writes.

\item [seek]moves the head on the required block.

\item [\_trylock~e~\_tryunlock]Used to block/unblock a device. They return 0 in

case of success, != 0 otherwise; after initialization, and usually, every device

is in the unblocked state.

\end{description}

Why blocking/unblocking a device? The problem, described in

Section \ref{sec:dcache}, is that the data cache have to refer to

a logical block in an unique way. Since there are logical devices

that shares blocks (think at /dev/hda and /dev/hda2 in Linux), the

mount operation must be done in mutual exclusion, blocking the

device.

%----------------------------------------------------------------------------

\subsubsection{The ``lodsk'' module}

%----------------------------------------------------------------------------

\begin{table}

\begin{verbatim}

struct lodskinfo {

    __uint8_t fs_ind;

    __blkcnt_t start;

    __blkcnt_t size;

};

typedef int (*lodsk_callback_func)(int, struct lodskinfo*, void *);

int lodsk_scan(__dev_t device, lodsk_callback_func func, void *data, int

showinfo, char *lname);

\end{verbatim}

\caption{The lodsk module}

\label{tab:lodsk}

\end{table}

This module (see Table \ref{tab:lodsk}) offer a service to the

device drivers: It recognizes the logical structure (partitions)

of an HD as described into \cite{manual:DOS330} (part of the code

is derived from Linux).

before calling lodsk\_scan, the device driver must be already

registered; the function has five parameters:

\begin{enumerate}

\item The device ID where the search have to be done.

\item A callback function called for each partition found.

\item A generic pointer passed to the callback function.

\item A verbose flag.

\item The name of the logical device (i.e., ``hdb'', used if the verbose option

has been set.

\end{enumerate}

Each callback function is called passing as arguments:

\begin{enumerate}

\item The logical number of the partition (the Linux numbering scheme is used).

\item A structure with informations on the partition found. The structure has

the following fields:

\begin{description}

\item [fs\_ind]The file system number (see include/fs/fsind.h).

\item [start]The partition starting block.

\item [size]The partition size (number of blocks).

\end{description}

\item A the generic pointer passed to lodsk\_scan.

\end{enumerate}

The low\_level routines always check these values to avoid

read/write operations outside the partition.

%----------------------------------------------------------------------------

\subsubsection{Semaphores}

%----------------------------------------------------------------------------

The files include/fs/mutex.h and include/fs/semaph.h contain the

mutex/semaphore interface used by the file system.

\begin{table}

\begin{verbatim}

typedef internal_sem_t __sem_t;

#define __sem_init (ptr,val)

#define __sem_wait (ptr)

#define __sem_trywait (ptr)

#define __sem_signal (ptr)

\end{verbatim}

\caption{The semaphore interface}

\label{tab:semaph}

\end{table}

In particular, the semaphore interface (see Table

\ref{tab:semaph}) is simply a wrapper to the S.Ha.R.K. Internal

Semaphores.

\begin{table}

\begin{verbatim}

typedef internal_sem_t __mutex_t;

#define __mutex_init (ptr,attr)

#define __mutex_lock (ptr)

#define __mutex_trylock (ptr)

#define __mutex_unlock (ptr)

typedef SYS_FLAGS __fastmutex_t;

#define __fastmutex_init (ptr)

#define __fastmutex_lock (ptr)

#define __fastmutex_unlock (ptr)

\end{verbatim}

\caption{The mutex interface}

\label{tab:mutex}

\end{table}

The mutex interface requires two types of mutexes:

\begin{enumerate}

\item Fast mutexes: when only a few lines have to be protected (remapped to

kern\_fsave/kern\_frestore).

\item Normal mutexes: without any restriction (remapped again to the internal

semaphores).

\end{enumerate}

Please note that these functions are not directly used in the

code; instead, functions like \_\_b\_mutex\_lock and

\_\_fs\_mutex\_lock are used. This is done to make possible the

disabling of the mutual exclusion requirement when not needed

(i.e., if the file system runs as a process with its own address

space).

%----------------------------------------------------------------------------

\subsection{Exported interface}

\label{sec:dd:intercaccia:ext}

%----------------------------------------------------------------------------

\begin{table}

\begin{verbatim}

int bdev_read (__dev_t dev, __blkcnt_t blocknum, __uint8_t *buffer);

int bdev_write (__dev_t dev, __blkcnt_t blocknum, __uint8_t *buffer);

int bdev_seek (__dev_t dev, __blkcnt_t blocknum);

int bdev_trylock(__dev_t device); int bdev_tryunlock(__dev_t device);

__uint8_t bdev_getdeffs(__dev_t device);

__dev_t bdev_find_byname(char *name);

__dev_t bdev_find_byfs(__uint8_t fsind);

int bdev_findname(__dev_t device, char **majorname, char **minorname);

int bdev_scan_devices(int(*callback) (__dev_t,__uint8_t));

\end{verbatim}

\caption{Low level functions}

\label{tab:bdev}

\end{table}

The low level exports two kinds of functions: one to use the

devices, one to search/get the logical devices present on a

system.

The three main functions are:

\begin{description}

\item [bdev\_find\_byname]This function accepts a symbolic device name, as

described in Section \ref{sec:dd:interfaccia:nomi}, and returns 0 if the device

is not registered, or its number otherwise.

\item [bdev\_find\_byfs]This function accepts a file system ID (see

include/fs/fsind.h), and returns the first device that contains that file

system, or 0 if no one provides it.

\item [bdev\_scan\_device]This function can be used to get a list of all the

devices in the system; the user have to pass a callback that is called for each

device in the system. The function returns 0 in case of success, -1 if an error

occurred, or a value != 0 if the callback returns a value != 0. The callback is

called with a device serial number and a file system type that should be present

in the device.

\end{description}

These function are useful when at system startup the root file

system have to be mounted (see Section \ref{sec:fs:mount}).

The functions bdev\_getdeffs and bdev\textbackslash{}\_findname

are used for these purposes:

\begin{description}

\item [bdev\_getdeffs]to know a probable file system present on a logical

device.

\item [bdev\_findname]to know the logical name of a device. The function returns

!= 0 in case of error, and 0 in case of success. In the latter case, the two

buffers passed as parameter are filled with the major and minor names.

\end{description}

These functions simply check the parameter values and then they

calls the device drivers functions (see Section

\ref{sec:dd:interfaccia:det:bdevop}):

\begin{description}

\item [bdev\_read]Reads a block on the device.

\item [bdev\_write]Write a block on the device.

\item [bdev\_seek]Move the head in the position passed as parameter.

\item [bdev\_trylock~e~bdev\_tryunlock]Tries to block/unblock a device.

\end{description}

These functions can block the calling thread for an unspecified

amount of time. All the device drivers were thought to be used in

a multithreaded systems.

If a device driver is not multithread, proper mutual exclusion

must be ensured, because the file system high level functions will

call a low level service before the previous request has been

served. Note that if such a mutual exclusion is used, the access

to the device driver will be forced by the mutex policy, and so

all the disk scheduling algorithms will not work properly.

%----------------------------------------------------------------------------

\section{I/O requests scheduling}

\label{sec:dd:sched}

%----------------------------------------------------------------------------

Massy's thesis here inserts a dissertation on

the various disk scheduling algorithms that has been removed.

%----------------------------------------------------------------------------

\section{Disk scheduling algorithms implemented in S.Ha.R.K.}

\label{sec:dd:schedpres}

%----------------------------------------------------------------------------

The system currently support 5 different scheduling algorithms

that can be changed/increased simply modifying system

configuration.

\begin{table}

\begin{verbatim}

int bqueue_init (bqueue_t *);

int bqueue_numelements (bqueue_t *);

int bqueue_removerequest (bqueue_t *);

int bqueue_insertrequest (bqueue_t *, struct request_prologue *);

struct request_prologue *bqueue_getrequest(bqueue_t *);

\end{verbatim}

\caption{Queue handling functions}

\label{tab:bqueuefunc}

\end{table}

Only one algorithm can be active at a time. All the device drivers

should use the queuing interface listed in the bqueue.h file (see

Table \ref{tab:bqueuefunc}). The structure bqueue\_t is specific

for each scheduling algorithm. The semantic of each function in

the interface is the following:

\begin{description}

\item [bqueue\_init]Initialize the pending request queue; it returns 0 in case

of success, != 0 otherwise.

\item [bqueue\_numelements]Returns the number of elements in the queue.

\item [bqueue\_insertrequest]This function inserts a request in the queue,

following the specific algorithm behavior. The function returns 0 in case of

success, != 0 otherwise. Please note that requests are passed through a pointer

to the structrequest\_prologue\_t (see tab:structreqprolog). That is, every

algorithm should use a structure with a struct request\_prologue as first field,

passing a casted pointer to that structure.

\item [bqueue\_getrequest]Returns the first request in queue (without removing

it), and returns a pointer to that request, or NULL if there are not any pending

requests.

\item [bqueue\_removerequest]Removes the first request in queue, that is the

request that would have been returned by bqueue\_getrequest; it returns 0 in

case of success, != 0 in case of error.

\end{description}

\begin{table}

\begin{verbatim}

#define REQ_DUMMY 0

#define REQ_SEEK 1

#define REQ_READ 2

#define REQ_WRITE 3

struct request_prologue {

    unsigned sector;

    unsigned head;

    unsigned cylinder;

    unsigned nsectors;

    unsigned operation;

    struct request_specific x;

};

#define request_prologue_t struct request_prologue

\end{verbatim}

\caption{struct request\_prologue\_t}

\label{tab:structreqprolog}

\end{table}

before calling bdev\_insertrequest, all the fields of the struct

request\_prologue\_t must be filled (see Table

\ref{tab:structreqprolog}):

\begin{description}

\item [sector,~head,~cylinder]This is the starting position in the hard disk.

\item [nsectors]This is the number of sectors to transfer.

\item [operation]The operation that must be performed:

\begin{description}

\item [REQ\_DUMMY]request not specified.

\item [REQ\_SEEK]head seek to the specified position.

\item [REQ\_READ]read request.

\item [REQ\_WRITE]write request.

\end{description}

\end{description}

To add algorithm specific fields, you can use the method used for

the deadlines into Section \ref{sec:dd:sched:edf}.

struct request\_specific (see Table \ref{tab:structreqprolog})

must be defined by each algorithm, and contains algorithm-specific

fields.

struct bqueue\_t contains a scheduling queue. Its first field must

be a pointer to a struct phdiskinfo (see Section

\ref{sec:dd:interfaccia:det}, and Table \ref{tab:structphdsk}).

Here is a description about the implementation of various disk

scheduling algorithms.

%----------------------------------------------------------------------------

\subsection{FCFS}

\label{sec:dd:sched:fcfs}

%----------------------------------------------------------------------------

\begin{table}

\begin{verbatim}

typedef struct TAGfcfs_queue_t {

    struct phdskinfo *disk;

    __b_fastmutex_t mutex;