\documentstyle[11pt]{article}
% frob with the margins
\addtolength{\topmargin}{-1in}
\addtolength{\footskip}{-1in}
\addtolength{\textheight}{2in}
\addtolength{\oddsidemargin}{-.5in}
\addtolength{\evensidemargin}{-.5in}
\addtolength{\textwidth}{1in}
% no page numbers
\pagestyle{empty}
% counter for page numbers
\newcounter{pg}
\setcounter{pg}{2}

% DEFINE THE PROBLEM SET NUMBER
\def\psnum{9}

% title command
\newcommand{\mytitle}[1]{\begin{center} {\Large Computation Structures -- 
6.004 Problem Set \psnum \\ Juliet Bourne -- #1} \\ \vspace{-.1in} 
\rule{6in}{.5mm} \end{center}}
% problem command
\newcommand{\prob}[1]{\vspace{.1in}\noindent{\fbox{\large\bf Problem #1}}}
% subproblem command
\newcommand{\subprob}[1]{\vspace{.1in} \noindent{\large\bf #1.}}
% equations commands
\newcommand{\beq}{\vspace*{-.3in}\begin{eqnarray*}}
\newcommand{\eeq}{\end{eqnarray*}}
% newpage setup command 
\newcommand{\mynewpage}{\newpage\noindent
\begin{center}
{\Large 6.004 Problem Set \psnum -- Juliet Bourne -- {\bf Page \thepg}}
\rule{6in}{.5mm}
\end{center}
\addtocounter{pg}{1}}
% see-page command
\newcommand{\seepage}{\noindent See page \rule{.2in}{.1mm} for the
computer output.}

\begin{document}

\mytitle{11/28/90}

\vspace*{-.15in}
\prob{1: {\em Virtual Warm Up}}

A page-table entry is $A-P$ bits for the physical page number, plus $n$
status bits. The page table has $2^{V-P}$ entries. Thus the page table
will be $(A-P+n)2^{V-P}$ bits or $(A-P+n)2^{V-P-3}$ bytes.

\prob{2: {\em Page Fault}}

Problems with this strategy include the fact that nothing done to
correct what caused the page fault. Also, the instruction which caused
the page fault could have overwritten registers and/or modified
locations in main memory before the page fault occurred. Thus, the
machine will not be in the same state it was before the instruction was
run the first time.

\prob{3: {\em Translation Lookaside Buffer}}

\subprob{A} 14 bits for the physical page number plus 2 status bits,
which is 16 bits or 2 bytes per page map entry.

\subprob{B} The 2 bytes which hold the physical page number must be
fetched from the page map (which is in main memory) and 1 byte of data
must be fetched from main memory.

\subprob{C} Block size should be 2 bytes to hold the 2-byte page map
entry. 

\subprob{D} No, a ``page in memory'' bit is not required since the TLB
only has entries for which a successful translation has occurred. But
a ``page dirty'' bit is still needed to keep track of whether the page
has been written to or not.

\subprob{E} Assuming that B is the number of bits used to indicate the
offset into the block (which is $2^B$ bytes), the tags would be $14-B$
bits wide. A dirty bit would be necessary to indicate whether or not any
of the pages in the block had been written to. For example, let's say a
write was done to a certain page whose address is cached. Then the dirty
bit in the TLB page entry should be set to 0 to indicate this, and also
the dirty bit for the whole line should be set to 0. Thus, if that line
is about to be replaced, the correct data, indicating that a page has
been written to, will be written to the page map. Also, a valid bit for
a line in the TLB will be needed just in case a physical page which is
referred to in the TLB gets replaced in the page map. The total number
of bits for a line in the TLB will be $14-B$ for the tag, 2 for the TLD
status bits, 14 for the physical page number, and 1 for the page entry
dirty bit. Since there are T entries in the TLB, the TLB will require
$(30-B)T$ bits of storage.

\subprob{F} There will be 16 entries per set. This will require that 4
bits will indicate which line in a set to access, leaving $14-4=10$ bits
that will be the tag.

\subprob{G} If there is a TLB hit, only 1 byte needs to be read from
main memory. When there's a TLB miss, 2 bytes need to be read to get the
physical address from the virtual address and then the 1 byte of data
needs to be read. So:

\beq
t_h = 1 & \; \; & t_m = 3 \; \; \; \alpha = 0.95 \\
t_a & = & 0.95(1) + (1 - 0.95)(3) \\
\mbox{} & = & 0.95 + 0.15 \\
t_a & = & 1.10
\eeq

\noindent So, there will be, approximately, 1.1 million reference to the
main memory.

\end{document}
