\documentclass{ictlab}

\RCS $Revision: 1.0 $

\usepackage{alltt,key,biganswerbox}
%\usepackage[hang,bf,nooneline]{caption2}
\usepackage[flushleft]{caption2}

\ifx\pdftexversion\undefined \usepackage{url} \else
  \usepackage[pdfpagemode=None,pdfauthor={Nick Urbanik}]{hyperref}
\fi

\newcommand*{\screenwidth}{0.4\textwidth}
\newcommand*{\labTitle}{Tutorial: Process Control Blocks}
\renewcommand*{\subject}{Operating Systems and Systems Integration}

\includeversion{questionsonly}
\begin{solution}
  \excludeversion{questionsonly}
\end{solution}

\providecommand*{\EMPH}[1]{\textmd{\textnormal{\emph{\uppercase{#1}}}}}
\providecommand*{\ONE}{\EMPH{ONE}\xspace}
\providecommand*{\TWO}{\EMPH{TWO}\xspace}
\providecommand*{\THREE}{\EMPH{THREE}\xspace}
\providecommand*{\FOUR}{\EMPH{FOUR}\xspace}
\providecommand*{\FIVE}{\EMPH{FIVE}\xspace}
\providecommand*{\SIX}{\EMPH{SIX}\xspace}

\newlength{\oneline}
\setlength{\oneline}{7mm}
\newlength{\boxht}
\setlength{\boxht}{9mm}

\begin{document}
\begin{enumerate}
\item What is a \emph{process control block} (\PCB)?
  \begin{biganswerbox}[\boxht]%
    \begin{solution}%
      A process control block is a \emph{data structure} used by an
      operating system to manage processes.
    \end{solution}
  \end{biganswerbox}

\item Is a \PCB only found in a Linux or \POSIX \OS or is it found in
  all operating systems?
  \begin{biganswerbox}[\oneline]%
    \begin{solution}%
      As I mentioned in the notes, process control blocks are found in
      all modern operating systems.  The structure of \PCB{}s will be
      different on each operating system though.
    \end{solution}
  \end{biganswerbox}
  
\item Give \ONE other name for a \PCB.
  \begin{biganswerbox}[\oneline]%
    \begin{solution}%
      It is sometimes called a \emph{process descriptor}, or a
      \emph{task descriptor}.  In the 2.6 source code of Linux, the
      data type is a structure called \texttt{task\_struct}
    \end{solution}
  \end{biganswerbox}
  
\item Give \ONE name for the data structure that holds the \PCB{}s.
  \begin{biganswerbox}[\oneline]%
    \begin{solution}%
      The \emph{process table}.  The \PCB{}s may be put into a number of
      lists at the same time.  The process table describes the system
      by which the operating system finds a \PCB by its process \ID.
    \end{solution}
  \end{biganswerbox}

\item Briefly define the term \emph{program counter}.
  \begin{biganswerbox}[3\oneline]%
    \begin{solution}%
      The \emph{program counter} is a \CPU register that holds the
      address of the next instruction that will be fetched.  As the
      \CPU fetches each instruction, the \PC is automatically
      incremented to point to the next instruction.
      
      You might like to play with the simple Macromedia Flash model of
      a simple computer consisting of a \CPU and \RAM connected by a
      4-bit data bus, 3-bit address bus, and 2-line control bus.  You
      can find it at
      \url{http://ictlab.tyict.vtc.edu.hk/ossi/lectures/processes/fetching.swf}.
      The \RAM contains three instructions, each occupies two 4-bit
      memory locations.
    \end{solution}
  \end{biganswerbox}

\item What data is held in the \emph{program counter}?
  \begin{biganswerbox}[3\oneline]%
    \begin{solution}%
      The address of the next machine instruction that will be fetched
      and executed.
    \end{solution}
  \end{biganswerbox}

\end{enumerate}


\paragraph{Process Control Blocks:}


In figure~\vref{fig:process-control-blocks} we see three processes,
P1, P2 and P3\@.  There are seven moments in time where the main
values of the \PCB{}s of the three processes are shown.  The time
intervals are not equal; they are just where the scheduler changed the
process.  The size of all \IO instructions is \emph{three bytes}.  In
each \PCB I have shown the program counter value, and the process
state.  The process state can be running (i.e., executing on the
\CPU), ready (i.e., ready to run), and sleeping (i.e., blocked).
There are two queues shown: a wait queue for processes that are
blocked waiting for \IO, and a ready queue, for processes that are in
the ready to run state.

\begin{figure}[ht]
  \centering%
  \includegraphics[width=\linewidth]{process-control-blocks-figure}
  \caption{An example of three processes executing, showing their process control blocks.}
  \label{fig:process-control-blocks}
\end{figure}

\begin{enumerate}
\item State the technical term for what the scheduler does at each of
  the times $t_0$, $t_1$, $t_2$, $t_3$, $t_4$, $t_5$ and $t_6$.
  \begin{biganswerbox}[\oneline]%
    \begin{solution}%
      Context switch.
    \end{solution}
  \end{biganswerbox}

  
\item Does  process P1  perform \IO?  If so, at what address is the
  \IO instruction?
  \begin{biganswerbox}[4\oneline]%
    \begin{solution}%
      Yes, you can see that it does, because the state of that process
      is sleeping after $t_1$, and you can see that it appears in the
      \emph{wait queue}, where it waits for the input or output to
      finish.
      
      We are told that the \IO instructions are \emph{three bytes
        long} in \emph{this particular example}, as specified in the
      question.  At $t_1$, the \CPU has already executed the \IO
      instruction.  This is what caused the \OS to put the process
      onto the wait queue, since \IO devices are typically much slower
      than the rate at which the \CPU can execute instructions.

      The \OS put the process into the sleeping state when the program
      counter was pointing to the \emph{next instruction to be
      fetched} that comes immediately \emph{after} the \IO
      instruction.
      
      So we know that the address of the instruction after the \IO
      instruction is at address C0DE\hex.  The size of the \IO
      instruction is three bytes, i.e., it is three address locations
      before C0DE\hex, so its address is $\C0\D\E\hex - 3 =
      \C0\D\B\hex$.
    \end{solution}
  \end{biganswerbox}

\item Does  process P2  perform \IO?  If so, at what address is the
  \IO instruction?
  \begin{biganswerbox}[4\oneline]%
    \begin{solution}%
      Yes, we can see that P2 moves to the sleeping state at time
      $t_2$, where we see that it is also on the wait queue.

      Using the same reasoning as before, we can see that the address
      of the \IO instruction is $\F\E\E\D\hex - 3 = \F\E\E\A\hex$.
    \end{solution}
  \end{biganswerbox}

\item Does  process P3  perform \IO?  If so, at what address is the
  \IO instruction?
  \begin{biganswerbox}[4\oneline]%
    \begin{solution}%
      Yes, P3 is blocked for \IO at time $t_3$.  The address of the
      \IO instruction is $\D1\C\E\hex - 3 = \D1\C\B\hex$.
    \end{solution}
  \end{biganswerbox}

\item List at least \FIVE other kinds of data that will be stored in a
  \PCB that is not shown in figure~\vref{fig:process-control-blocks}.
  \begin{biganswerbox}[4\oneline]%
    \begin{solution}%
      If you look at the definition of the data type
      \texttt{task\_struct} in the header file
      \path{/usr/src/linux-2.4.22-1.2188.nptl/include/linux/sched.h}
      and also see the definition of \texttt{thread\_struct} in
      \path{/usr/src/linux-2.4.22-1.2188.nptl/include/asm/processor.h},
      you will see that the \PCB contains a great deal of information
      about the process, including:
      \begin{itemize}
      \item The process \ID
      \item the process state (for example, whether it is executing,
        ready to run, or sleeping)
      \item program counter (stored in \texttt{thread\_struct})
      \item the scheduling priority
      \item information about the user and groups associated with this
        process
      \item pointer to the parent process \PCB
      \item pointer to a list of child process \PCB{}s
      \item pointers to the process's data and machine code in memory
      \item pointers to open files and other resources held by the process
      \end{itemize}
    \end{solution}
  \end{biganswerbox}
\end{enumerate}
\end{document}