diff options
author | Ben Burwell <ben@benburwell.com> | 2015-04-01 20:47:40 -0400 |
---|---|---|
committer | Ben Burwell <ben@benburwell.com> | 2015-04-01 20:47:40 -0400 |
commit | 4a04db9470cc0492a4bfb9752de14d8e12209177 (patch) | |
tree | 52ea5efdefb181ed9b76d3e749766f2924b69044 /docs/tech/data_structures.tex | |
parent | d8463e5ebbf8805c30ee6402e6667eb5f78446cc (diff) |
add docs
Diffstat (limited to 'docs/tech/data_structures.tex')
-rw-r--r-- | docs/tech/data_structures.tex | 95 |
1 files changed, 95 insertions, 0 deletions
diff --git a/docs/tech/data_structures.tex b/docs/tech/data_structures.tex new file mode 100644 index 0000000..0805caf --- /dev/null +++ b/docs/tech/data_structures.tex @@ -0,0 +1,95 @@ +\chapter{Data Structures} +\label{data_structures} + +\section{Process Control Block} +\label{process_control_block} + +The operating system stores information about processes in a Process Control Block\index{Process Control Block} (PCB)\index{PCB}. Defined in {\tt mpx.h}, the PCB stores the following information: +\begin{enumerate} + \item A pointer to the next PCB in the chain. + \item A pointer to the previous PCB in the queue. + \item A pointer to the next PCB in the queue. + \item A 9-character array to store the process name.\footnote{Note that thus, the maximum length of a process name is 8 characters, since character 9 will be {\tt 0x0}.} + \item A type (application or system). + \item A state (ready, running, or blocked). + \item A ``suspended'' flag. + \item A stack pointer for the process's stack. + \item An array of size {\tt STACK\_SIZE} to store the stack. + \item The address at which the process is loaded in memory. + \item The amount of memory allocated for the process. + \item A pointer to a parameter structure, storing the operation number and operation type for the process's current IO operation (if any). +\end{enumerate} + +The actual code for the structure is listed here: + +\begin{lstlisting} +struct pcbstruct { + struct pcbstruct * chain; + struct pcbstruct * next; + struct pcbstruct * prev; + char name[9]; + short type; + short priority; + short state; + short suspend; + unsigned stack_ptr; + unsigned stack[STACK_SIZE]; + unsigned loadaddr; + parm *parm_add; + int mem_size; +}; +\end{lstlisting} + +Each process control block is linked to the next one (except for the last one, whose next PCB is {\tt NULL}) by a pointer for iteration purposes. Process control blocks can reside in at most one of several system-wide queues at any given time. + +\subsection{Ready Queue} + +The ready queue is maintained as a priority-ordered list of processes that are ready to be run. This way, the dispatcher knows which process to start next. Queue operations stored in {\tt pcb.c} use the {\tt next} and {\tt prev} fields of the PCB to create a doubly-linked list and is prioritized using the PCB's {\tt priority} field. By definition, the priority of an application process must be greater than the minimum priority and smaller than the maxiumum priority of a system process. In this way, we can assign the idle process to have the lowest possible priority and the command handler to have the highest possible priority. + +\subsection{I/O Queue} + +The I/O queue stores queue of processes involved in I/O operations. This queue is a normal FIFO queue, contrasted with the Ready Queue. + +\section{Device Control Block} +\label{device_control_block} + +In order to manage I/O devices, MPX-OS uses Device Control Blocks,\index{Device Control Block} or DCBs. The {\tt struct} for the DCB is defined in {\tt mpx.h}, and is accessible to all component programs. + +The following information is stored: +\begin{enumerate} + \item The current operation. + \item A pointer to the event flag used to signal completion. + \item A pointer to the PCB currently using the device. + \item A pointer to the head of the queue of PCBs waiting to use the device. + \item A far pointer to an int to store the length of the device buffer. The far pointer allows it to point to a different section of memory, since the variable will be declared in a user program. + \item A far pointer to a char array to store the I/O buffer. + \item A count of the number of characters in the buffer. + \item A char array to act as the ring buffer, implemented as a circular queue (see below). + \item The index of the front element of the ring buffer. + \item The index of the rear element of the ring buffer. + \item The number of characters in the ring buffer. + \item The maximum size of the ring buffer. +\end{enumerate} + +The code for the DCB structure is listed below: +\begin{lstlisting} +struct dcb_struct { + unsigned current_op; + unsigned * event_flag; + pcb * current_pcb; + pcb * pcb_head; + far int * length; + far char * buffer; + int count; + far char * c_buffer; + char ring[INPUT_BUFFER_MAX]; + int ring_front; + int ring_rear; + int ring_count; + int ring_size; +}; +\end{lstlisting} + +\subsection{Ring Buffer} + +The ring buffer is used to implement type-ahead; that is, inputted characters are stored by the DCB when there is no current read operation and inserted into the buffer when a read request is made. There are several variables in the DCB structure used to implement the circular queue, whose logic is located in {\tt dcb.c} |