\documentclass[answers]{exam}
% \documentclass[addpoints,answers]{exam}
\usepackage{color}
\usepackage[utf8]{inputenc}

\title{Computer Architecture Homework 8}
\date{Spring 2022, May}

\usepackage{natbib}
\usepackage{graphicx}

\begin{document}



\maketitle

\section*{Problem 1 (10 points) }
Choose True / False:\\
\\1.A virtual memory system that uses paging is vulnerable to external fragmentation.\underline{\hbox to 10mm{}}
\\2.One way to solve Compulsory miss is to increase the block size.\underline{\hbox to 10mm{}}
\\3.In a bare system, addresses issued with loads/stores are real physical addresses other than virtual address.\underline{\hbox to 10mm{}}
\\4.The size of the virtual address space accessible to the program cannot be larger than the size of the physical address space.\underline{\hbox to 10mm{}}\\

\section*{Problem 2 (10 points)}
This question refers to an architecture using segmentation with paging. In this architecture, the 32-bit virtual address is divided into fields as follows:
\begin{table}[h!]
  \begin{center}
    \begin{tabular}{|c|c|c|} 
      \hline
      3 bit segment number &	13 bit page number 	& 16 bit offset\\
      \hline
    \end{tabular}
  \end{center}
\end{table}
\\Here is the relevant table (all values in hexadecimal):
\begin{table}[h!]
  \begin{center}
    \begin{tabular}{|c|c|c|c|c|c|}
        \hline
        \multicolumn{2}{|c|}{Segment Table}& \multicolumn{2}{c|}{Page Table A}&\multicolumn{2}{c|}{Page Table B}\\
         \hline
        0&   Page Table A&  0&	CAEF&	0&	C001\\
         \hline
        1& 	 Page Table B&	1&	DEAB&	1&	D5AA\\
         \hline
        X&	(rest invalid)&	2&	BFFE&	2&	A000\\
         \hline
		&                 & 3&	AF11&	3&	BA09\\
		 \hline
	    &	              & X&	(rest invalid)&	X&	(rest invalid)\\
	     \hline
    \end{tabular}
  \end{center}
\end{table}
\\Find the physical address corresponding to each of the following virtual addresses (answer "bad virtual address" if the virtual address is invalid):\\
\begin{center}
\\1.0x00000000  \underline{\hbox to 40mm{}}
\\2.0x20032003  \underline{\hbox to 40mm{}}
\\3.0x100205BD  \underline{\hbox to 40mm{}}
\end{center}
\\

\vspace{12mm}

\section*{Problem 3 (30 points)}
In a 34-bit machine we subdivide the virtual address into 4 segments as follows:\\
\begin{table}[h!]
  \begin{center}
  \setlength{\tabcolsep}{7mm}
    \begin{tabular}{|c|c|c|c|} 
      \hline
      8 bit &	7 bit &	7 bit &	12 bit\\
      \hline
    \end{tabular}
  \end{center}
\end{table}
\\We use a 3-level page table, such that the first 8-bit are for the first level and so on. Assume the size of each page table is equal to one page size. (Ignore the fragments and treat it roughly as one page)
\\
\\\textbf{Question 1.}What is the page size in such a system? 
\\
\\\textbf{Question 2.}What is the size of a page table for a process that has 256K of memory starting at address 0? 
\\
\\\textbf{Question 3.}What is the size of a page table for a process that has a code segment of 48K starting at address 0x1000000, a data segment of 600K starting at address 0x80000000 and a stack segment of 64K starting at address 0xf0000000 and growing upward ? 

\newpage
\section*{Problem 4 (20 points)}
A processor has 16-bit addresses, 256 byte pages, and an 8-entry fully associative TLB with LRU replacement (the LRU field is 3 bits and encodes the order in which pages were accessed, 0 being the most recent). At some time instant, the TLB for the current process is the initial state given in the table below. Assume that all current page table entries are in the initial TLB. Assume also that all pages can be read from and written to. Fill in the final state of the TLB according to the access pattern below. Free physical pages: 0x17, 0x18, 0x19.

\begin{table}[h!]
  \begin{center}
  \setlength{\tabcolsep}{7mm}
    \begin{tabular}{|c|c|} 
      \hline
      1&write 0x776e\\
      \hline
      2&read 0x9796\\
      \hline
      3&write 0x9a0f\\
      \hline
      4&read 0x5a82\\
      \hline
      5&write 0x035b\\
      \hline
      6&read 0x0365\\
      \hline
    \end{tabular}
  \end{center}
\end{table}

\begin{minipage}{\textwidth}
 \begin{minipage}[t]{0.45\textwidth}
  \centering
     \makeatletter\def\@captype{table}\makeatother
       \begin{tabular}{|c|c|c|c|c|} 
      \hline
        \textbf{VPN} &\textbf{PPN} &\textbf{Valid} &\textbf{Dirty} &\textbf{LRU}\\
         \hline
        0x6f & 0x48 & 1 & 0 & 0\\
         \hline
        0x03 & 0x97 & 1 & 1 & 5\\
         \hline
        0x77 & 0x56 & 1 & 0 & 6\\
         \hline
        0x1f & 0x2d & 1 & 1 & 1\\
         \hline
        0x9a & 0x9a & 1 & 0 & 3\\
         \hline
        0x00 & 0x00 & 0 & 0 & 7\\
         \hline
        0xea & 0x6d & 1 & 1 & 2\\
         \hline
        0xc8 & 0x21 & 1 & 0 & 4\\
         \hline
    \end{tabular}
  \end{minipage}
  \begin{minipage}[t]{0.45\textwidth}
   \centering
        \makeatletter\def\@captype{table}\makeatother
         \begin{tabular}{|c|c|c|c|c|} 
      \hline
        \textbf{VPN} &\textbf{PPN} &\textbf{Valid} &\textbf{Dirty} &\textbf{LRU}\\
         \hline
         &  &  &  & \\
         \hline
        &  &  &  & \\
         \hline
         &  &  &  & \\
         \hline
        &  &  &  & \\
         \hline
        &  &  &  & \\
         \hline
         &  &  &  & \\
         \hline
         &  &  &  & \\
         \hline
        &  &  &  & \\
         \hline
    \end{tabular}
   \end{minipage}
\end{minipage}



\section*{Problem 5 (30 points)}
Assume a computer has 32-bit addresses, 4KB pages, and the physical memory space is 4GB. The computer uses two-level paging, each page table entry consists of a next-level address index and seven additional control bits.
\\\textbf{Question 1.}What is the minimum number of bits per secondary page table entry? And justify your ans..\\
\\\textbf{Question 2.}What is the minimum number of bits per level 1 page table entry? And justify your ans..\\
\\\textbf{Question 3.}Assuming that each page table entry is 8 bytes in size (In addition to the next level address index and seven additional control bits, we have added some new things to expand its size to 8 bytes) and each page table is exactly 1 page in size, how many bits of virtual address does the program actually use?
(Hint: It means that not all 32 bits are valid virtual addresses, and some bits may be useless.)\\
\\\textbf{Question 4.}According to question 3, how many bytes is the virtual address space of an application?\\
\vspace{20cm}


\end{document}
 