\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}