text:
<repo_name>din982/CSE-450<file_sep>/homework_3/homework_3.tex
\documentclass{article}

\usepackage{fancyhdr}
\usepackage{extramarks}
\usepackage{minted}
\usepackage[T1]{fontenc}
\usepackage{graphicx}
\usepackage{inconsolata}
\usepackage{multicol}
\usepackage{enumitem}
\usepackage{tikz}
\usetikzlibrary{positioning}

\tikzset{
  gray box/.style={
    fill=gray!20,
    draw=gray,
    minimum width={2*#1ex},
    minimum height={2em},
  },
  annotation/.style={
    anchor=north,
  }
}

%
% Basic Document Settings
%

\topmargin=-0.45in
\evensidemargin=0in
\oddsidemargin=0in
\textwidth=6.5in
\textheight=9.0in
\headsep=0.25in

\linespread{1.1}

\pagestyle{fancy}
\lhead{\hmwkAuthorName}
\chead{\hmwkClass: \hmwkTitle}
\rhead{\firstxmark}
\lfoot{\lastxmark}
\cfoot{\thepage}

\renewcommand\headrulewidth{0.4pt}
\renewcommand\footrulewidth{0.4pt}

\setlength\parindent{0pt}

%
% Create Problem Sections
%

\newcommand{\enterProblemHeader}[1]{
\nobreak\extramarks{}{Problem \arabic{#1} continued on next page\ldots}\nobreak{}
\nobreak\extramarks{Problem \arabic{#1} (continued)}{Problem \arabic{#1} continued on next page\ldots}\nobreak{}
}

\newcommand{\exitProblemHeader}[1]{
\nobreak\extramarks{Problem \arabic{#1} (continued)}{Problem \arabic{#1} continued on next page\ldots}\nobreak{}
\stepcounter{#1}
\nobreak\extramarks{Problem \arabic{#1}}{}\nobreak{}
}

\setcounter{secnumdepth}{0}
\newcounter{partCounter}
\newcounter{homeworkProblemCounter}
\setcounter{homeworkProblemCounter}{1}
\nobreak\extramarks{Problem \arabic{homeworkProblemCounter}}{}\nobreak{}

%
% Homework Problem Environment
%
% This environment takes an optional argument. When given, it will adjust the
% problem counter. This is useful for when the problems given for your
% assignment aren't sequential. See the last 3 problems of this template for an
% example.
%
\newenvironment{homeworkProblem}[1][-1]{
\ifnum#1>0
\setcounter{homeworkProblemCounter}{#1}
\fi
\section{Problem \arabic{homeworkProblemCounter}}
\setcounter{partCounter}{1}
\enterProblemHeader{homeworkProblemCounter}
}{
\exitProblemHeader{homeworkProblemCounter}
}

%
% Homework Details
%   - Title
%   - Due date
%   - Class
%   - Section/Time
%   - Instructor
%   - Author
%

\newcommand{\hmwkTitle}{Homework\ \#3}
\newcommand{\hmwkDueDate}{March 1, 2016}
\newcommand{\hmwkClass}{Operating Systems}
\newcommand{\hmwkClassTime}{Monday \& Wednesday 3:30pm --- 5:17pm}
\newcommand{\hmwkClassInstructor}{Professor Qu}
\newcommand{\hmwkAuthorName}{<NAME>}

%
% Title Page
%

\title{
\vspace{2in}
\textmd{\textbf{\hmwkClass:\ \hmwkTitle}}\\
\normalsize\vspace{0.1in}\small{Due\ on\ \hmwkDueDate\ at 11:59pm}\\
\vspace{0.1in}\large{\textit{\hmwkClassInstructor\ \\ \hmwkClassTime}}
\vspace{3in}
}

\author{\textbf{\hmwkAuthorName}}
\date{}

\renewcommand{\part}[1]{\textbf{\large Part \Alph{partCounter}}\stepcounter{partCounter}\\}

%
% Various Helper Commands
%

% Alias for the Solution section header
\newcommand{\solution}{\textsc{\textbf Solution}\\}

% Alias for bold small caps
\newcommand{\smallcaps}[1]{\textsc{\textbf #1}\\}

\begin{document}

  \maketitle

  \pagebreak

  \begin{homeworkProblem}

    Consider the following process arrival list:

    \begin{center}
      \begin{tabular}{c c c}
        \underline{Name} & \underline{Arrival time} & \underline{Service time} \\
        A & $0$ & $4$ \\
        B & $3$ & $9$ \\
        C & $5$ & $2$ \\
        D & $7$ & $5$ \\
        E & $11$ & $3$ \\
        F & $13$ & $1$ \\
        G & $21$ & $4$ \\
      \end{tabular}
    \end{center}

    Consider the following scheduling methods:

    \begin{multicols}{2}
      \begin{enumerate}[label=(\alph*)]
        \item First-come first-served (FCFS)
        \item Shortest-job first (SJF)
        \vfill
        \columnbreak
        \item Shortest remaining time first (SRTF)
        \item Round-robin (RR), Quantum = 5
      \end{enumerate}
    \end{multicols}

    Draw a Gantt chart (time line) showing which process is executing over time and calculate the average waiting time and average completion time. \\

    Notes : (1) In SRTF, if a process arrives with service time equal to the remaining service time of the process currently being served, the current process is not interrupted. (2) In RR, if a process arrives at the same time a quantum finishes, the running process is preempted and the new arrival executes.  The preempted process goes to the end of the ready queue. (3) Waiting time and completion time is defined as in the slides. \\

    \solution

    \begin{center}
      \smallcaps{(a) First-come first-served (FCFS)}
      \begin{tikzpicture}[node distance=-0.5pt]
        \node [gray box=4] (p1) {\(P_{A}\)};
        \node [gray box=9, right=of p1] (p2) {\(P_{B}\)};
        \node [gray box=2, right=of p2] (p3) {\(P_{C}\)};
        \node [gray box=5, right=of p3] (p4) {\(P_{D}\)};
        \node [gray box=3, right=of p4] (p5) {\(P_{E}\)};
        \node [gray box=1, right=of p5] (p6) {\(P_{F}\)};
        \node [gray box=4, right=of p6] (p7) {\(P_{G}\)};

        \node [annotation] at (p1.south west) {0};
        \node [annotation] at (p1.south east) {4};
        \node [annotation] at (p2.south east) {13};
        \node [annotation] at (p3.south east) {15};
        \node [annotation] at (p4.south east) {20};
        \node [annotation] at (p5.south east) {23};
        \node [annotation] at (p6.south east) {24};
        \node [annotation] at (p7.south east) {28};
      \end{tikzpicture}

      \textbf{Average waiting time:} $(0 + 1 + 8 + 8 + 9 + 10 + 3) \div 7 = 5.6$ \\
      \textbf{Average completion time:} $(4 + 10 + 10 + 13 + 12 + 11 + 7) \div 7 = 9.6$
    \end{center}

    \begin{center}
      \smallcaps{(b) Shortest-job first (SJF)}
      \begin{tikzpicture}[node distance=-0.5pt]
        \node [gray box=4] (p1) {\(P_{A}\)};
        \node [gray box=9, right=of p1] (p2) {\(P_{B}\)};
        \node [gray box=1, right=of p2] (p3) {\(P_{F}\)};
        \node [gray box=2, right=of p3] (p4) {\(P_{C}\)};
        \node [gray box=3, right=of p4] (p5) {\(P_{E}\)};
        \node [gray box=5, right=of p5] (p6) {\(P_{D}\)};
        \node [gray box=4, right=of p6] (p7) {\(P_{G}\)};

        \node [annotation] at (p1.south west) {0};
        \node [annotation] at (p1.south east) {4};
        \node [annotation] at (p2.south east) {13};
        \node [annotation] at (p3.south east) {14};
        \node [annotation] at (p4.south east) {16};
        \node [annotation] at (p5.south east) {19};
        \node [annotation] at (p6.south east) {24};
        \node [annotation] at (p7.south east) {28};
      \end{tikzpicture}

      \textbf{Average waiting time:} $(0 + 1 + 9 + 12 + 5 + 0 + 3)
      \div 7 = 4.2$ \\
      \textbf{Average completion time:} $(4 + 10 + 11 + 17 + 8 + 1 + 7) \div 7 = 8.3$
    \end{center}

    \begin{center}
      \smallcaps{(c) Shortest remaining time first {SRTF}}
      \begin{tikzpicture}[node distance=-0.5pt]
        \node [gray box=4] (p1) {\(P_{A}\)};
        \node [gray box=1, right=of p1] (p2) {\(P_{B}\)};
        \node [gray box=2, right=of p2] (p3) {\(P_{C}\)};
        \node [gray box=5, right=of p3] (p4) {\(P_{D}\)};
        \node [gray box=1, right=of p4] (p5) {\(P_{E}\)};
        \node [gray box=1, right=of p5] (p6) {\(P_{F}\)};
        \node [gray box=4, right=of p6] (p7) {\(P_{E}\)};
        \node [gray box=8, right=of p7] (p8) {\(P_{B}\)};
        \node [gray box=4, right=of p8] (p9) {\(P_{G}\)};

        \node [annotation] at (p1.south west) {0};
        \node [annotation] at (p1.south east) {4};
        \node [annotation] at (p2.south east) {5};
        \node [annotation] at (p3.south east) {7};
        \node [annotation] at (p4.south east) {12};
        \node [annotation] at (p5.south east) {13};
        \node [annotation] at (p6.south east) {14};
        \node [annotation] at (p7.south east) {16};
        \node [annotation] at (p8.south east) {24};
        \node [annotation] at (p9.south east) {28};
      \end{tikzpicture}

      \textbf{Average waiting time:} $(0 + 12 + 0 + 0 + 2 + 0 + 3) \div 7 = 2.4$ \\
      \textbf{Average completion time:} $(4 + 21 + 2 + 5 + 5 + 1 + 7) \div 7 = 6.4$
    \end{center}

    \begin{center}
      \smallcaps{(d) Round-robin, Quantum = 5}
      \begin{tikzpicture}[node distance=-0.5pt]
        \node [gray box=4] (p1) {\(P_{A}\)};
        \node [gray box=5, right=of p1] (p2) {\(P_{B}\)};
        \node [gray box=2, right=of p2] (p3) {\(P_{C}\)};
        \node [gray box=5, right=of p3] (p4) {\(P_{D}\)};
        \node [gray box=4, right=of p4] (p5) {\(P_{B}\)};
        \node [gray box=3, right=of p5] (p6) {\(P_{E}\)};
        \node [gray box=1, right=of p6] (p7) {\(P_{F}\)};
        \node [gray box=4, right=of p7] (p8) {\(P_{G}\)};

        \node [annotation] at (p1.south west) {0};
        \node [annotation] at (p1.south east) {4};
        \node [annotation] at (p2.south east) {9};
        \node [annotation] at (p3.south east) {11};
        \node [annotation] at (p4.south east) {16};
        \node [annotation] at (p5.south east) {20};
        \node [annotation] at (p6.south east) {23};
        \node [annotation] at (p7.south east) {24};
        \node [annotation] at (p8.south east) {28};
      \end{tikzpicture}

      \textbf{Average waiting time:} $(0 + 8 + 4 + 4 + 9 + 10 + 3) \div 7 = 5.4$ \\
      \textbf{Average completion time:} $(4 + 17 + 6 + 9 + 12 + 11 + 7) \div 7 = 9.4$
    \end{center}
  \end{homeworkProblem}

  \begin{homeworkProblem}
    A Multilevel feedback queues are shown in the diagram below. The scheduler first executes all processes in Q0. Only when Q0 is empty will it execute processes in Q1, and only when Q0 and Q1 are empty will it execute processes in Q2. A process arriving for Q0 will preempt a process in Q1 or Q2, and a process arriving for Q1 will preempt a process in Q2; a process preempted in this case is put back to the head of the same queue; when this process is scheduled to run next time it will execute for the remaining of its allocated time quantum. A new process entering the system is put in Q0 and is given a time quantum of 8 milliseconds. If it does not finish within this time, it is preempted and moved to the tail of Q1. If Q0 is empty, the process at the head of Q1 is scheduled to run with a time quantum of 16 milliseconds. If it does not finish within this time, it is preempted and moved to the tail of Q2. Processes in Q2 are run on an FCFS basis. \\

    \begin{center}
      \includegraphics[scale=0.5]{image.png} \\
    \end{center}

    Given the following arrival time and CPU burst of processes A, B, C, D, and E as shown in table below.

    \begin{center}
      \begin{tabular}{ | c | c | c |}
        \hline
        Task & Arrival Time & Service Time \\
        \hline
        A & 0 & 25 \\
        \hline
        B & 5 & 28 \\
        \hline
        C & 19 & 11 \\
        \hline
        D & 25 & 19 \\
        \hline
        E & 36 & 33 \\
        \hline
      \end{tabular}
    \end{center}

    \begin{enumerate}[label=\alph*)]
      \item Show the status of each queue along the time line during the running of the system. You only need to show the status of the system when either 1) a new process arrives, or 2) a process is preempted, or 3) a process terminates. The status includes time stamp, the name of the process and its remaining time in each queue. For example, at time 0, process A is in $Q_0$ and it has 25 time units toward finishing. $Q_1$ and $Q_2$ are empty. You are asked to complete the table with time moment and status of each queue. Moreover, B(x) A(y) shows A is at the head of the queue with x remaining time and B is at the tail of the queue with remaining time of y. You can add new rows to the table if you think the table is not enough to accommodate all the events.
    \end{enumerate}

    \solution

    \begin{center}
      \begin{tabular}{| c | c | c | c |}
        \hline
        \textbf{Time} & $Q_0$ & $Q_1$ & $Q_2$ \\
        \hline
        0 & A(25) & &  \\
        \hline
        5 & B(28) A(20) & & \\
        \hline
        8 & B(28) & A(17) & \\
        \hline
        16 & & A(17) B(20) & \\
        \hline
        19 & C(11) & A(14) B(20) & \\
        \hline
        25 & C(5) D(19) & A(14) B(20) & \\
        \hline
        27 & D(19) & A(14) B(20) C(3) & \\
        \hline
        35 & & A(14) B(20) C(3) D(11) & \\
        \hline
        36 & E(33) & A(13) B(20) C(3) D(11) & \\
        \hline
        44 & & A(13) B(20) C(3) D(11) E(25) & \\
        \hline
        56 & & B(20) C(3) D(11) E(25) & A(1) \\
        \hline
        72 & & C(3) D(11) E(25) & A(1) B(4) \\
        \hline
        75 & & Process C terminates D(11) E(25) & A(1) B(4) \\
        \hline
        86 & & Process D terminates E(25) & A(1) B(4) \\
        \hline
        102 & & & A(1) B(4) E(9) \\
        \hline
        103 & & & Process A terminates B(4) E(9) \\
        \hline
        107 & & & Process B terminates E(9) \\
        \hline
        116 & & & Process E terminates \\
        \hline
      \end{tabular}
    \end{center}
  \end{homeworkProblem}

\end{document}
<file_sep>/homework_prereq/homework_prereq.tex
\documentclass{article}

\usepackage{fancyhdr}
\usepackage{extramarks}
\usepackage{minted}

%
% Basic Document Settings
%

\topmargin=-0.45in
\evensidemargin=0in
\oddsidemargin=0in
\textwidth=6.5in
\textheight=9.0in
\headsep=0.25in

\linespread{1.1}

\pagestyle{fancy}
\lhead{\hmwkAuthorName}
\chead{\hmwkClass: \hmwkTitle}
\rhead{\firstxmark}
\lfoot{\lastxmark}
\cfoot{\thepage}

\renewcommand\headrulewidth{0.4pt}
\renewcommand\footrulewidth{0.4pt}

\setlength\parindent{0pt}

%
% Create Problem Sections
%

\newcommand{\enterProblemHeader}[1]{
    \nobreak\extramarks{}{Problem \arabic{#1} continued on next page\ldots}\nobreak{}
    \nobreak\extramarks{Problem \arabic{#1} (continued)}{Problem \arabic{#1} continued on next page\ldots}\nobreak{}
}

\newcommand{\exitProblemHeader}[1]{
    \nobreak\extramarks{Problem \arabic{#1} (continued)}{Problem \arabic{#1} continued on next page\ldots}\nobreak{}
    \stepcounter{#1}
    \nobreak\extramarks{Problem \arabic{#1}}{}\nobreak{}
}

\setcounter{secnumdepth}{0}
\newcounter{partCounter}
\newcounter{homeworkProblemCounter}
\setcounter{homeworkProblemCounter}{1}
\nobreak\extramarks{Problem \arabic{homeworkProblemCounter}}{}\nobreak{}

%
% Homework Problem Environment
%
% This environment takes an optional argument. When given, it will adjust the
% problem counter. This is useful for when the problems given for your
% assignment aren't sequential. See the last 3 problems of this template for an
% example.
%
\newenvironment{homeworkProblem}[1][-1]{
    \ifnum#1>0
        \setcounter{homeworkProblemCounter}{#1}
    \fi
    \section{Problem \arabic{homeworkProblemCounter}}
    \setcounter{partCounter}{1}
    \enterProblemHeader{homeworkProblemCounter}
}{
    \exitProblemHeader{homeworkProblemCounter}
}

%
% Homework Details
%   - Title
%   - Due date
%   - Class
%   - Section/Time
%   - Instructor
%   - Author
%

\newcommand{\hmwkTitle}{Homework\ Prereq}
\newcommand{\hmwkDueDate}{January 18, 2016}
\newcommand{\hmwkClass}{Operating Systems}
\newcommand{\hmwkClassTime}{Monday \& Wednesday 3:30pm --- 5:17pm}
\newcommand{\hmwkClassInstructor}{Professor Qu}
\newcommand{\hmwkAuthorName}{<NAME>}

%
% Title Page
%

\title{
    \vspace{2in}
    \textmd{\textbf{\hmwkClass:\ \hmwkTitle}}\\
    \normalsize\vspace{0.1in}\small{Due\ on\ \hmwkDueDate\ at 11:59pm}\\
    \vspace{0.1in}\large{\textit{\hmwkClassInstructor\ \\ \hmwkClassTime}}
    \vspace{3in}
}

\author{\textbf{\hmwkAuthorName}}
\date{}

\renewcommand{\part}[1]{\textbf{\large Part \Alph{partCounter}}\stepcounter{partCounter}\\}

%
% Various Helper Commands
%

% Useful for algorithms
\newcommand{\alg}[1]{\textsc{\bfseries \footnotesize #1}}

% For derivatives
\newcommand{\deriv}[1]{\frac{\mathrm{d}}{\mathrm{d}x} (#1)}

% For partial derivatives
\newcommand{\pderiv}[2]{\frac{\partial}{\partial #1} (#2)}

% Integral dx
\newcommand{\dx}{\mathrm{d}x}

% Alias for the Solution section header
\newcommand{\solution}{\textbf{\large Solution}}

% Probability commands: Expectation, Variance, Covariance, Bias
\newcommand{\E}{\mathrm{E}}
\newcommand{\Var}{\mathrm{Var}}
\newcommand{\Cov}{\mathrm{Cov}}
\newcommand{\Bias}{\mathrm{Bias}}

\begin{document}

\maketitle

\pagebreak

\begin{homeworkProblem}
  A computer is built that uses 15 bits for integers and for addresses.

    \begin{enumerate}
        \item How many bytes of memory can be addressed?
        \item What is the range of values for signed (two's complement) integers.
        We want the largest magnitude negative number, and the largest magnitude
        positive number.
    \end{enumerate}

    \textbf{Solution}

    \begin{enumerate}
      \item $2^{15} = 32,768$ bits can be addressed, which is $\frac{32768}{8} = 4,096$ bytes.
      \item $-2^{14} = -16,384$ is the samllest negative integer \& $2^{14} - 1
      = 16,383$ is the largest integer.
    \end{enumerate}

\end{homeworkProblem}

\begin{homeworkProblem}
  Describe two of the primary motivations for having Virtual Memory in the computer system. \\

  \textbf{Solution}

  \begin{enumerate}
    \item To allow efficient and safe sharing of memory among multiple programs.
    \item To allow a user to exceed the size of primary memory.
  \end{enumerate}
\end{homeworkProblem}

\begin{homeworkProblem}
  Explain why virtual memory in a system without Translation Lookaside Buffer will be much slower than physical memory. \\

  \textbf{Solution} \\

  If a system did not contain a Translation Lookaside Buffer it would be much slower than physical memory because there would be an extra step involved in looking a page address up. Because on every reference the virtual page number is looked up in TLB, and without a TLB, it would result in a miss. A TLB miss takes about 13 clock cycles.
\end{homeworkProblem}

\begin{homeworkProblem}
  Describe what is wrong with the following function and propose modifications to fix it, submit with a test program and test results.
  \begin{minted}[linenos]{C++}
char *string_duplicator(char *s) {
        char *cpy;
        for (int i = 0; i <= strlen(s); i++) {
                cpy[i] = s[i];
        }
        return(cpy);
}
\end{minted}

  \textbf{Solution} \\

  The problem with the previous function was two fold; the first issue was `strlen` was part of a library that was not imported. The second issue was that the variable 'i' was not declared. \\

  \textbf{Proposed Solution}

  \begin{minted}[linenos]{C++}
#include <iostream>

// Prototype so that the main function can call
// string_duplicator
char *string_duplicator(char *s);

int main(int argc, char const *argv[]) {
        char testString[] = "hello";
        printf("%s\n", string_duplicator(testString));
}

char *string_duplicator(char *s) {
        char *cpy = new char;
        for (int i = 0; i <= strlen(s); i++) {
                cpy[i] = s[i];
        }
        return(cpy);
}
  \end{minted}

  This produces a result of \textbf{Hello}.
\end{homeworkProblem}

\begin{homeworkProblem}
  Please submit a testing program and test results together with a brief readme file describing what the main function of the function test.

  \begin{minted}[linenos]{C++}
int test(char *s) {
        int x = 0;
        unsigned char c; while (*s) {
                c = *s; while (c) {
                        if (c & 1) x++;
                        c = c >>1;
                }
                s++;
        }
        return x;
}
  \end{minted}

  \textbf{Explanation of test function} \\

  The above function loops through each character of 's' and checks to see if there is a '1' stored in the address of that character. If there is a one, it increments x by 1, if there is no one, it bitshifts right by 1. \\

  \pagebreak

  \textbf{Proposed Solution}

  \begin{minted}[linenos]{C++}
#include <iostream>

int test(char *s) {
        int x = 0;
        unsigned char c; while (*s) {
                c = *s; while (c) {
                        if (c & 1) x++;
                        c = c >>1;
                }
                s++;
        }
        return x;
}

int main(int argc, char const *argv[]) {
        char testString[] = "Hello, World";
        printf("%d\n", test(testString));
}
  \end{minted}

This produces a result of \textbf{46}.
\end{homeworkProblem}

\end{document}
<file_sep>/notes/exam_cheatsheet/exam_cheatsheet.tex
\documentclass{article}

\usepackage[margin=0.5in]{geometry}
\usepackage{multicol}
\usepackage[T1]{fontenc}
\usepackage{lipsum}
\usepackage{color}
\usepackage{tikz}
\usepackage[usenames, dvipsnames]{color}
\usepackage[linesnumbered,boxed,commentsnumbered,lined]{algorithm2e}
\usetikzlibrary{positioning}

\tikzset{
  gray box/.style={
    fill=gray!20,
    draw=gray,
    minimum width={2*#1ex},
    minimum height={2em},
  },
  annotation/.style={
    anchor=north,
  }
}

\setlength\parindent{0pt}

% Alias for bold small caps
\newcommand{\smallcaps}[1]{\textsc{\textbf #1}\\}

\begin{document}

    \section*{CPU Efficiency}
    Measurements of a certain computer system have shown that the average process time runs for a time T before blocking on I/O. A process switch requires a time S, which is effectively wasted (overhead). For round-robin scheduling with quantum Q, give a formula for the CPU efficiency (defined as the percentage of CPU time used for useful work) for each of the following:

    \begin{center}
      When $T > Q$ Then the formula is $\frac{Q}{Q+S}$ \\
      When $T < Q$ Then the formula is $\frac{T}{T+S}$ \\
      When $Q = S$ Then the formula is $\frac{Q}{Q+Q}$ or $\frac{Q}{Q+S} \to \frac{1}{2}$\\
      When $Q \approx 0$ $\to$ $Q$ $\to$ $\lim_{Q\to0} \to 0$\\
      When $Q \approx \infty$ $\to$ $T$ is used \\
    \end{center}

    \section*{CPU Scheduling}

    \begin{itemize}
      \item \textbf{{\color{blue} CPU Utilization}} -- keep the CPU as busy as possible
      \item \textbf{{\color{blue} Throughput}} -- Number of processes that complete their execution per time unit
      \item \textbf{{\color{blue} Turnaround time}} -- Amount of time to execute a particular process, from submission until completion (completion time)
      \item \textbf{{\color{blue} Waiting time}} -- Amount of time a process has been waiting in the ready queue
      \item \textbf{{\color{blue} Response time}} -- Amount of time it takes from when a request was submitted until the first response is procduced, \textbf{not} output (for time-sharing environment)
    \end{itemize}

    \smallcaps{Example}

    Five tasks A through E, arrive at a computer system at almost the same time.
    They have estimated running times of 10, 6, 2, 4 and 8. For each of the following scheduling algorithms, determine the \textsc{\textbf{average waiting time.}} Ignore process-switching overhead, you need to draw the gantt chart to show the schedule/running behavior of the five tasks.

    \begin{itemize}
      \item First-come, first-served (run in order 10, 6, 2, 4, 8).
      \item Shortest job first.
      \item Longest job first: the runnable process with the longest estimated running time (CPU burst) will be scheduled to run.
      \item Priority scheduling: each process is assigned a priority, and the runnable process with the highest priority is allowed to run. In this question, the five tasks' priorities are 3, 5, 2, 1 and 4, respectively, with 5 being the highest priority.
    \end{itemize}

    \begin{center}
      \smallcaps{(a) First-come first-served (FCFS)}
      \begin{tikzpicture}[node distance=-0.5pt]
        \node [gray box=10] (p1) {\(P_{A}\)};
        \node [gray box=6, right=of p1] (p2) {\(P_{B}\)};
        \node [gray box=2, right=of p2] (p3) {\(P_{C}\)};
        \node [gray box=4, right=of p3] (p4) {\(P_{D}\)};
        \node [gray box=8, right=of p4] (p5) {\(P_{E}\)};

        \node [annotation] at (p1.south west) {0};
        \node [annotation] at (p1.south east) {10};
        \node [annotation] at (p2.south east) {16};
        \node [annotation] at (p3.south east) {18};
        \node [annotation] at (p4.south east) {22};
        \node [annotation] at (p5.south east) {30};
      \end{tikzpicture}

      \textbf{Average waiting time:} $(0 + \{10 - 0\} + \{16 - 0\} + \{18 - 0\} + \{22 - 0\}) \div 5 = 13.2$ \\
    \end{center}

    \begin{center}
      \smallcaps{(b) Shortest Job First (SJF)}
      \begin{tikzpicture}[node distance=-0.5pt]
        \node [gray box=2] (p1) {\(P_{C}\)};
        \node [gray box=4, right=of p1] (p2) {\(P_{D}\)};
        \node [gray box=6, right=of p2] (p3) {\(P_{B}\)};
        \node [gray box=8, right=of p3] (p4) {\(P_{E}\)};
        \node [gray box=10, right=of p4] (p5) {\(P_{A}\)};

        \node [annotation] at (p1.south west) {0};
        \node [annotation] at (p1.south east) {2};
        \node [annotation] at (p2.south east) {6};
        \node [annotation] at (p3.south east) {12};
        \node [annotation] at (p4.south east) {20};
        \node [annotation] at (p5.south east) {30};
      \end{tikzpicture}

      \textbf{Average waiting time:} $(\{20 - 0\} + \{6 - 0\} + 0 + \{2 - 0\} + \{12 - 0\}) \div 5 = 8$ \\
    \end{center}

    \begin{center}
      \smallcaps{(c) Longest Job First (SJF)}
      \begin{tikzpicture}[node distance=-0.5pt]
        \node [gray box=10] (p1) {\(P_{A}\)};
        \node [gray box=8, right=of p1] (p2) {\(P_{E}\)};
        \node [gray box=6, right=of p2] (p3) {\(P_{B}\)};
        \node [gray box=4, right=of p3] (p4) {\(P_{D}\)};
        \node [gray box=2, right=of p4] (p5) {\(P_{C}\)};

        \node [annotation] at (p1.south west) {0};
        \node [annotation] at (p1.south east) {10};
        \node [annotation] at (p2.south east) {18};
        \node [annotation] at (p3.south east) {24};
        \node [annotation] at (p4.south east) {28};
        \node [annotation] at (p5.south east) {30};
      \end{tikzpicture}

      \textbf{Average waiting time:} $(0 + \{18 - 0\} + \{28 - 0\} + \{24 - 0\} + \{10 - 0\}) \div 5 = 16$ \\
    \end{center}

    \begin{center}
      \smallcaps{(d) Priority Scheduling $\to$ 3,5,2,1,4}
      \begin{tikzpicture}[node distance=-0.5pt]
        \node [gray box=6] (p1) {\(P_{B}\)};
        \node [gray box=8, right=of p1] (p2) {\(P_{E}\)};
        \node [gray box=10, right=of p2] (p3) {\(P_{A}\)};
        \node [gray box=2, right=of p3] (p4) {\(P_{C}\)};
        \node [gray box=4, right=of p4] (p5) {\(P_{D}\)};

        \node [annotation] at (p1.south west) {0};
        \node [annotation] at (p1.south east) {6};
        \node [annotation] at (p2.south east) {14};
        \node [annotation] at (p3.south east) {24};
        \node [annotation] at (p4.south east) {26};
        \node [annotation] at (p5.south east) {30};
      \end{tikzpicture}

      \textbf{Average waiting time:} $(\{14 - 0\} + 0 + \{24 - 0\} + \{26 - 0\} + \{6 - 0\}) \div 5 = 14$ \\
    \end{center}

    \pagebreak

    \section*{Synchronization}

    \begin{itemize}
      \item {\color{blue} Synchronization} -- Using atomic operations to ensure cooperation between threads
      \begin{itemize}
        \item {\color{orange} Atomic} -- Non-interruptible
      \end{itemize}
      \item {\color{blue} Critical Section} -- piece of code that only one thread can execute at once. Only on thread at a time will get into this section of code.
      \begin{itemize}
        \item {\color{orange} Mutual Exclusion} -- ensuring that only one thread does a particular thing at a time
        \item {\color{orange} Progress} -- selecting a thread to enter cannot postpone indefinitely
        \item {\color{orange} Bounded Waiting} -- before entering the critical section
      \end{itemize}
    \end{itemize}

    \begin{center}
      {\color{red} \textbf{!!All synchronization involves waiting!!}}
    \end{center}

    \begin{multicols}{2}
      \begin{algorithm}[H]
        \While{true}{
          wait(rw\_mutex)\;
          \tcp{writing is performed}\label{cmt}
          signal(rw\_mutex)\;
        }
      \caption{Writer}
      \end{algorithm}

      \vfill
      \columnbreak

      \begin{algorithm}[H]
        \While{true} {
          wait(mutex)\;
          readCount$++$\;
          \If{readCount == 1} {
            wait(rw\_mutex)\;
          }
          signal(mutex)\;
          \tcp{reading is performed}\label{cmt}
          wait(mutex)\;
          readCount$--$\;
          \If{readCount == 0} {
            signal(rw\_mutex)\;
          }
          signal(mutex)\;
        }
      \caption{Reader}
      \end{algorithm}
    \end{multicols}

    The reader \& writer share three data structures:

    \begin{itemize}
      \item semaphore rw\_mutex
      \begin{itemize}
        \item this is to ensure mutual exclusion between readers and writers
      \end{itemize}
      \item semaphore mutex
      \begin{itemize}
        \item this is to ensure mutual exclusion when the variable readCount is updated
      \end{itemize}
      \item int readCount
      \begin{itemize}
        \item this is to keep track of how many processes are currently reading the object
      \end{itemize}
    \end{itemize}

    Since we have semaphores rw\_mutex \& mutex, we know that no two processes can execute {\color{blue}\texttt{wait()}} and {\color{blue}\texttt{signal()}} on the same semaphore at the same time. Because of this, we can see how \textbf{Algorithm 1} \& \textbf{Algorithm 2} adhere to mutual exclusion. \\

    Two operations for semaphores:

    \begin{itemize}
      \item {\color{blue} \textbf{block}} -- place the process invoking the operation on the appropriate waiting queue
      \item {\color{blue} \textbf{wakeup}} -- remove one of the processes in the waiting queue and place it in the ready queue
    \end{itemize}

    \section*{Schedulers}

    \textbf{Long-term} - selects which processes should be brought into ready queue \\
    \textbf{Short-term} - selects which processes get executed next \\
    \textbf{Mid-term} - partially executed \\

\end{document}
<file_sep>/homework_4/homework_4.tex
\documentclass{article}

\usepackage{fancyhdr}
\usepackage{extramarks}
\usepackage{minted}
\usepackage[T1]{fontenc}
\usepackage{graphicx}
\usepackage{inconsolata}
\usepackage{multicol}
\usepackage{enumitem}

%
% Basic Document Settings
%

\topmargin=-0.45in
\evensidemargin=0in
\oddsidemargin=0in
\textwidth=6.5in
\textheight=9.0in
\headsep=0.25in

\linespread{1.1}

\pagestyle{fancy}
\lhead{\hmwkAuthorName}
\chead{\hmwkClass: \hmwkTitle}
\rhead{\firstxmark}
\lfoot{\lastxmark}
\cfoot{\thepage}

\renewcommand\headrulewidth{0.4pt}
\renewcommand\footrulewidth{0.4pt}

\setlength\parindent{0pt}

%
% Create Problem Sections
%

\newcommand{\enterProblemHeader}[1]{
\nobreak\extramarks{}{Problem \arabic{#1} continued on next page\ldots}\nobreak{}
\nobreak\extramarks{Problem \arabic{#1} (continued)}{Problem \arabic{#1} continued on next page\ldots}\nobreak{}
}

\newcommand{\exitProblemHeader}[1]{
\nobreak\extramarks{Problem \arabic{#1} (continued)}{Problem \arabic{#1} continued on next page\ldots}\nobreak{}
\stepcounter{#1}
\nobreak\extramarks{Problem \arabic{#1}}{}\nobreak{}
}

\setcounter{secnumdepth}{0}
\newcounter{partCounter}
\newcounter{homeworkProblemCounter}
\setcounter{homeworkProblemCounter}{1}
\nobreak\extramarks{Problem \arabic{homeworkProblemCounter}}{}\nobreak{}

%
% Homework Problem Environment
%
% This environment takes an optional argument. When given, it will adjust the
% problem counter. This is useful for when the problems given for your
% assignment aren't sequential. See the last 3 problems of this template for an
% example.
%
\newenvironment{homeworkProblem}[1][-1]{
\ifnum#1>0
\setcounter{homeworkProblemCounter}{#1}
\fi
\section{Problem \arabic{homeworkProblemCounter}}
\setcounter{partCounter}{1}
\enterProblemHeader{homeworkProblemCounter}
}{
\exitProblemHeader{homeworkProblemCounter}
}

%
% Homework Details
%   - Title
%   - Due date
%   - Class
%   - Section/Time
%   - Instructor
%   - Author
%

\newcommand{\hmwkTitle}{Homework\ \#4}
\newcommand{\hmwkDueDate}{March 23, 2016}
\newcommand{\hmwkClass}{Operating Systems}
\newcommand{\hmwkClassTime}{Monday \& Wednesday 3:30pm --- 5:17pm}
\newcommand{\hmwkClassInstructor}{Professor Qu}
\newcommand{\hmwkAuthorName}{<NAME>}

%
% Title Page
%

\title{
\vspace{2in}
\textmd{\textbf{\hmwkClass:\ \hmwkTitle}}\\
\normalsize\vspace{0.1in}\small{Due\ on\ \hmwkDueDate\ at 11:59pm}\\
\vspace{0.1in}\large{\textit{\hmwkClassInstructor\ \\ \hmwkClassTime}}
\vspace{3in}
}

\author{\textbf{\hmwkAuthorName}}
\date{}

\renewcommand{\part}[1]{\textbf{\large Part \Alph{partCounter}}\stepcounter{partCounter}\\}

%
% Various Helper Commands
%

% Alias for the Solution section header
\newcommand{\solution}{\textsc{\textbf Solution}\\}

% Alias for bold small caps
\newcommand{\smallcaps}[1]{\textsc{\textbf #1}\\}

\begin{document}

  \maketitle
  \pagebreak

  \begin{homeworkProblem}
    Answer the following questions

    \begin{enumerate}[label=(\alph*)]
      \item Describe a real-life deadlock situation. Explain why it satisfies the four necessary conditions (mutual exclusion, hold-and-wait, non-preemption, circular wait). How do people recover from that situation? \\
      Upon recovery, which condition becomes false?
      \item Give an example, where the system is not in a safe state, but if the processes of the system are allowed to be executed, then they will be successfully completed.
    \end{enumerate}

    \solution

    \begin{enumerate}[label=(\alph*)]
      \item An example of a real life deadlock would be something like a person trying to get a professional job, but are unable to because they lack the experience to get the job. However, to get the experience, they need to have a job. This satisfies the four condtions of deadlock as follows:
      \begin{itemize}
        \item \smallcaps{Mutual Exclusion} One of the things (get a professional job) is unable to occur because it is dependent on the other (experience), and visa-versa.
        \item \smallcaps{Hold and Wait} This is essentially the same as the previous bullet point.
        \item \smallcaps{No Preemption} This holds because you can't get one without the other. As a result, none of the two 'proceeses` could preempt one another.
        \item \smallcaps{Circular Wait} This condition is satisfied because if you want the job, you need the experience, if you want the expirenece, you need the job. That is a continuous cycle.
      \end{itemize}
      People are able to recover from such deadlock by getting an internship, or an apprenticeship which will give them the experience that they need to get the job. The condition that becomes false is the circular wait. Now, the person has experience and is able to obtain the professional job.

      \item Like in the previous example I provided, if the user were able to obtain an internship, then the processes could execute as normal, and all four condtions of deadlock would be satisfied. In this case deadlock would not occur.
    \end{enumerate}
  \end{homeworkProblem}

  \begin{homeworkProblem}
    Consider the following snapshot of a system (P=Process, R=Resource) :

    \begin{center}
      \begin{tabular}{|c|c|c|c|}
        \hline
        \multicolumn{4}{|c|}{Available} \\
        \hline
        $R_a$ & $R_b$ & $R_c$ & $R_d$ \\
        \hline
        1 & 5 & 2 & 0 \\
        \hline
      \end{tabular}
    \end{center}

    \pagebreak

    \begin{center}
      \begin{multicols}{2}
        \begin{tabular}{|c|c|c|c|c|}
          \hline
          \multicolumn{5}{|c|}{Maximum Demand} \\
          \hline
          & $R_a$ & $R_b$ & $R_c$ & $R_d$ \\
          \hline
          $P_0$ & 0 & 3 & 1 & 2 \\
          \hline
          $P_1$ & 1 & 7 & 5 & 0 \\
          \hline
          $P_2$ & 2 & 3 & 5 & 6 \\
          \hline
          $P_3$ & 0 & 6 & 5 & 2 \\
          \hline
          $P_4$ & 0 & 6 & 5 & 6 \\
          \hline
        \end{tabular}

        \begin{tabular}{|c|c|c|c|c|}
          \hline
          \multicolumn{5}{|c|}{Current Allocation} \\
          \hline
          & $R_a$ & $R_b$ & $R_c$ & $R_d$ \\
          \hline
          $P_0$ & 0 & 0 & 1 & 2 \\
          \hline
          $P_1$ & 1 & 0 & 0 & 0 \\
          \hline
          $P_2$ & 1 & 3 & 5 & 4 \\
          \hline
          $P_3$ & 0 & 6 & 3 & 2 \\
          \hline
          $P_4$ & 0 & 0 & 1 & 4 \\
          \hline
        \end{tabular}
      \end{multicols}
    \end{center}

    Answer the following questions using banker's algorithm:

    \begin{enumerate}[label=\alph*)]
      \item Calcualtes the \textit{Needs} matrix:
      \begin{center}
        \begin{tabular}{|c|c|c|c|c|}
          \hline
          \multicolumn{5}{|c|}{Needs} \\
          \hline
          & $R_a$ & $R_b$ & $R_c$ & $R_d$ \\
          \hline
          $P_0$ & & & & \\
          \hline
          $P_1$ & & & & \\
          \hline
          $P_2$ & & & & \\
          \hline
          $P_3$ & & & & \\
          \hline
          $P_4$ & & & & \\
          \hline
        \end{tabular}
      \end{center}

      \item Is the system in a safe state?  If so, show how you derive a safe order with Safety Algorithm in which the processes can run. Show the different values of the work vector after each iteration. What is the sequence of processes that the algorithm implicitly created?

      \item If a request from process $P_0$ arrives for (0, 3, 0, 0), can the request be granted immediately? Justify your answer, using only the knowledge of the sequence you found at sub-question (b).
    \end{enumerate}

    \solution

    \begin{enumerate}[label=\alph*)]
      \item Needs Matrix:
      \begin{center}
        \begin{tabular}{|c|c|c|c|c|}
          \hline
          \multicolumn{5}{|c|}{Needs} \\
          \hline
          & $R_a$ & $R_b$ & $R_c$ & $R_d$ \\
          \hline
          $P_0$ & 0 & 3 & 0 & 0 \\
          \hline
          $P_1$ & 0 & 7 & 5 & 0 \\
          \hline
          $P_2$ & 1 & 0 & 0 & 2 \\
          \hline
          $P_3$ & 0 & 0 & 2 & 0 \\
          \hline
          $P_4$ & 0 & 6 & 4 & 2 \\
          \hline
        \end{tabular}
      \end{center}

      \item Derived safe state: \\
      Initial Work:
      \begin{center}
        \begin{tabular}{|c|c|c|c|}
          \hline
          \multicolumn{4}{|c|}{Work} \\
          \hline
          $R_a$ & $R_b$ & $R_c$ & $R_d$ \\
          \hline
          1 & 5 & 2 & 0 \\
          \hline
        \end{tabular}
      \end{center}
      \textbf{Derived safe order}: \\
      <$P_0$>
      \begin{center}
        \begin{tabular}{|c|c|c|c|}
          \hline
          \multicolumn{4}{|c|}{Work} \\
          \hline
          $R_a$ & $R_b$ & $R_c$ & $R_d$ \\
          \hline
          1 & 5 & 3 & 2 \\
          \hline
        \end{tabular}
      \end{center}

      \pagebreak

      \textbf{Derived safe order}: \\
      <$P_0$, $P_2$>
      \begin{center}
        \begin{tabular}{|c|c|c|c|}
          \hline
          \multicolumn{4}{|c|}{Work} \\
          \hline
          $R_a$ & $R_b$ & $R_c$ & $R_d$ \\
          \hline
          2 & 8 & 8 & 6 \\
          \hline
        \end{tabular}
      \end{center}

      \textbf{Derived safe order}: \\
      <$P_0$, $P_2$, $P_3$>
      \begin{center}
        \begin{tabular}{|c|c|c|c|}
          \hline
          \multicolumn{4}{|c|}{Work} \\
          \hline
          $R_a$ & $R_b$ & $R_c$ & $R_d$ \\
          \hline
          2 & 14 & 11 & 8 \\
          \hline
        \end{tabular}
      \end{center}

      \textbf{Derived safe order}: \\
      <$P_0$, $P_2$, $P_3$, $P_4$>
      \begin{center}
        \begin{tabular}{|c|c|c|c|}
          \hline
          \multicolumn{4}{|c|}{Work} \\
          \hline
          $R_a$ & $R_b$ & $R_c$ & $R_d$ \\
          \hline
          2 & 14 & 12 & 12 \\
          \hline
        \end{tabular}
      \end{center}

      \textbf{Derived safe order}: \\
      <$P_0$, $P_2$, $P_3$, $P_4$, $P_1$>
      \begin{center}
        \begin{tabular}{|c|c|c|c|}
          \hline
          \multicolumn{4}{|c|}{Work} \\
          \hline
          $R_a$ & $R_b$ & $R_c$ & $R_d$ \\
          \hline
          3 & 14 & 12 & 12 \\
          \hline
        \end{tabular}
      \end{center}

      \item The request for $P_0$ can be granted immediately. This is possible because we know that the initial work is:
      \begin{center}
        \begin{tabular}{|c|c|c|c|}
          \hline
          \multicolumn{4}{|c|}{Work} \\
          \hline
          $R_a$ & $R_b$ & $R_c$ & $R_d$ \\
          \hline
          1 & 5 & 2 & 0 \\
          \hline
        \end{tabular}
      \end{center}

      The request of (0,3,0,0) does not exceed the available work of (1,5,2,0). As stated in the previous answer, $P_0$ is the first process in the derived safe order.
    \end{enumerate}
  \end{homeworkProblem}
\end{document}
<file_sep>/homework_prereq/cpp_programming/problem_5.cpp
#include <iostream>

int test(char *s) {
        int x = 0;
        unsigned char c; while (*s) {
                c = *s; while (c) {
                        if (c & 1) x++;
                        c = c >>1;
                }
                s++;
        }
        return x;
}

int main(int argc, char const *argv[]) {
        char testString[] = "Hello, World";
        printf("%d\n", test(testString));
}
<file_sep>/homework_1/homework_1.tex
\documentclass{article}

\usepackage{fancyhdr}
\usepackage{extramarks}
\usepackage{minted}
\usepackage[T1]{fontenc}
\usepackage{graphicx}
\usepackage{inconsolata}

%
% Basic Document Settings
%

\topmargin=-0.45in
\evensidemargin=0in
\oddsidemargin=0in
\textwidth=6.5in
\textheight=9.0in
\headsep=0.25in

\linespread{1.1}

\pagestyle{fancy}
\lhead{\hmwkAuthorName}
\chead{\hmwkClass: \hmwkTitle}
\rhead{\firstxmark}
\lfoot{\lastxmark}
\cfoot{\thepage}

\renewcommand\headrulewidth{0.4pt}
\renewcommand\footrulewidth{0.4pt}

\setlength\parindent{0pt}

%
% Create Problem Sections
%

\newcommand{\enterProblemHeader}[1]{
\nobreak\extramarks{}{Problem \arabic{#1} continued on next page\ldots}\nobreak{}
\nobreak\extramarks{Problem \arabic{#1} (continued)}{Problem \arabic{#1} continued on next page\ldots}\nobreak{}
}

\newcommand{\exitProblemHeader}[1]{
\nobreak\extramarks{Problem \arabic{#1} (continued)}{Problem \arabic{#1} continued on next page\ldots}\nobreak{}
\stepcounter{#1}
\nobreak\extramarks{Problem \arabic{#1}}{}\nobreak{}
}

\setcounter{secnumdepth}{0}
\newcounter{partCounter}
\newcounter{homeworkProblemCounter}
\setcounter{homeworkProblemCounter}{1}
\nobreak\extramarks{Problem \arabic{homeworkProblemCounter}}{}\nobreak{}

%
% Homework Problem Environment
%
% This environment takes an optional argument. When given, it will adjust the
% problem counter. This is useful for when the problems given for your
% assignment aren't sequential. See the last 3 problems of this template for an
% example.
%
\newenvironment{homeworkProblem}[1][-1]{
\ifnum#1>0
\setcounter{homeworkProblemCounter}{#1}
\fi
\section{Problem \arabic{homeworkProblemCounter}}
\setcounter{partCounter}{1}
\enterProblemHeader{homeworkProblemCounter}
}{
\exitProblemHeader{homeworkProblemCounter}
}

%
% Homework Details
%   - Title
%   - Due date
%   - Class
%   - Section/Time
%   - Instructor
%   - Author
%

\newcommand{\hmwkTitle}{Homework\ \#1}
\newcommand{\hmwkDueDate}{February 10, 2016}
\newcommand{\hmwkClass}{Operating Systems}
\newcommand{\hmwkClassTime}{Monday \& Wednesday 3:30pm --- 5:17pm}
\newcommand{\hmwkClassInstructor}{Professor Qu}
\newcommand{\hmwkAuthorName}{<NAME>}

%
% Title Page
%

\title{
\vspace{2in}
\textmd{\textbf{\hmwkClass:\ \hmwkTitle}}\\
\normalsize\vspace{0.1in}\small{Due\ on\ \hmwkDueDate\ at 11:59pm}\\
\vspace{0.1in}\large{\textit{\hmwkClassInstructor\ \\ \hmwkClassTime}}
\vspace{3in}
}

\author{\textbf{\hmwkAuthorName}}
\date{}

\renewcommand{\part}[1]{\textbf{\large Part \Alph{partCounter}}\stepcounter{partCounter}\\}

%
% Various Helper Commands
%

% Useful for algorithms
\newcommand{\alg}[1]{\textsc{\bfseries \footnotesize #1}}

% For derivatives
\newcommand{\deriv}[1]{\frac{\mathrm{d}}{\mathrm{d}x} (#1)}

% For partial derivatives
\newcommand{\pderiv}[2]{\frac{\partial}{\partial #1} (#2)}

% Integral dx
\newcommand{\dx}{\mathrm{d}x}

% Alias for the Solution section header
\newcommand{\solution}{\textbf{\large Solution}}

% Probability commands: Expectation, Variance, Covariance, Bias
\newcommand{\E}{\mathrm{E}}
\newcommand{\Var}{\mathrm{Var}}
\newcommand{\Cov}{\mathrm{Cov}}
\newcommand{\Bias}{\mathrm{Bias}}

\begin{document}

  \maketitle

  \pagebreak

  \begin{homeworkProblem}
    Briefly explaining \textsc{what conditions} cause a process to move between each of the following 3 states indicated by each arrow (from 1 to 6). Label it N/A if it doesn't happen. \\

    \textbf{\textsc{Solution}}

    From running $\Rightarrow$ ready \textit{1} : Interupt
    \begin{itemize}
      \item An interupt is a signal to the processor emitted by hardware or software indicating an event that needs immediate attention.
    \end{itemize}
    From ready $\Rightarrow$ running \textit{2} : Scheduler Dispatch
    \begin{itemize}
      \item A process that is dispatched is a process that is scheduled to execute.
    \end{itemize}
    From ready $\Rightarrow$ waiting \textit{3} : N/A \\
    From waiting $\Rightarrow$ ready \textit{4} : I/O or event completion
    \begin{itemize}
      \item An I/O-bound process is a process that spends more time doing I/O than    it does computations. Event completion is when the process has finished executing.
    \end{itemize}
    From waiting $\Rightarrow$ running \textit{5} : N/A \\
    From running $\Rightarrow$ waiting \textit{6} : I/O or event wait
    \begin{itemize}
      \item Event wait is a process that is waiting for some event to occur (such as an I/O completion or reception of a signal).
    \end{itemize}
  \end{homeworkProblem}

  \begin{homeworkProblem}
    Question 2.  In this question, events are given during the execution of a grading program. You are supposed to understand the process state transition and fill out those blanks and choose the right options. Hint: state transition occurs when some particular events happen. Please use one of ready, running, blocked states as the possible state for the process. When you need to determine the running mode, please use either user or kernel. [Please check and understand these concepts through reading either from the slides or textbook] [19 points: one for each cell in the answer table] \\

    \textbf{\textsc{Solution}}

    \textit{Q1} : Ready State \\
    \textit{Q2} : Running State \\
    \textit{Q3} : User Mode \\
    \textit{Q4} : Blocked State \\
    \textit{Q5} : Kernel Mode \\
    \textit{Q6} : Yes \\
    \textit{Q7} : Ready State \\
    \textit{Q8} : Blocked State \\
    \textit{Q9} : Ready State \\
    \textit{Q10} : Running State \& User Mode \\
    \textit{Q11} : Running State to Blocked State \\
    \textit{Q12} : Ready State to Running State \\
    \textit{Q13} : Kernel Mode \\
    \textit{Q14} : Ready State \\
    \textit{Q15} : User Mode \\
    \textit{Q16} : Ready \\
  \end{homeworkProblem}

  \pagebreak

  \begin{homeworkProblem}
    Question 3.  Case study, in this task, you need to study a process state transition for any real system (linux, wondows, mac, android, ios, etc.). What you need to do is draw (or copy paste) the process state transition diagram and describe the conditions for every transition. \\

    \textbf{\textsc{Solution}} \\

    \begin{center}
      \write18{wget http://i.stack.imgur.com/2CP6n.png}
      \includegraphics[scale=0.5]{2CP6n.png} \\
    \end{center}

    \begin{itemize}
      \item When the \texttt{onCreate()} method is called the process is created and moves into the \texttt{New} process state.
      \item When the \texttt{onStart()} method is called the process moves from \texttt{Ready} to \texttt{Running}.
      \item When the \texttt{onResume()} method is called the process moves from    \texttt{Waiting} to \texttt{Running}.
      \item When the \texttt{onPause()} method is called the process moves from \texttt{Running} to \texttt{Waiting}.
      \item When the \texttt{onStop()} method is called the process moves into the \texttt{Waiting} state.
      \item When the \texttt{onDestroy()} method is called the process moves from \texttt{Waiting} to \texttt{Terminated} state.
    \end{itemize}

  \end{homeworkProblem}

\end{document}
<file_sep>/homework_5/homework_5.tex
\documentclass{article}

\usepackage{fancyhdr}
\usepackage{extramarks}
\usepackage{minted}
\usepackage[T1]{fontenc}
\usepackage{graphicx}
\usepackage{inconsolata}
\usepackage{multicol}
\usepackage{enumitem}
\usepackage{amsmath}
\usepackage{amssymb}

%
% Basic Document Settings
%

\topmargin=-0.45in
\evensidemargin=0in
\oddsidemargin=0in
\textwidth=6.5in
\textheight=9.0in
\headsep=0.25in

\linespread{1.1}

\pagestyle{fancy}
\lhead{\hmwkAuthorName}
\chead{\hmwkClass: \hmwkTitle}
\rhead{\firstxmark}
\lfoot{\lastxmark}
\cfoot{\thepage}

\renewcommand\headrulewidth{0.4pt}
\renewcommand\footrulewidth{0.4pt}

\setlength\parindent{0pt}

%
% Create Problem Sections
%

\newcommand{\enterProblemHeader}[1]{
\nobreak\extramarks{}{Problem \arabic{#1} continued on next page\ldots}\nobreak{}
\nobreak\extramarks{Problem \arabic{#1} (continued)}{Problem \arabic{#1} continued on next page\ldots}\nobreak{}
}

\newcommand{\exitProblemHeader}[1]{
\nobreak\extramarks{Problem \arabic{#1} (continued)}{Problem \arabic{#1} continued on next page\ldots}\nobreak{}
\stepcounter{#1}
\nobreak\extramarks{Problem \arabic{#1}}{}\nobreak{}
}

\setcounter{secnumdepth}{0}
\newcounter{partCounter}
\newcounter{homeworkProblemCounter}
\setcounter{homeworkProblemCounter}{1}
\nobreak\extramarks{Problem \arabic{homeworkProblemCounter}}{}\nobreak{}

%
% Homework Problem Environment
%
% This environment takes an optional argument. When given, it will adjust the
% problem counter. This is useful for when the problems given for your
% assignment aren't sequential. See the last 3 problems of this template for an
% example.
%
\newenvironment{homeworkProblem}[1][-1]{
\ifnum#1>0
\setcounter{homeworkProblemCounter}{#1}
\fi
\section{Problem \arabic{homeworkProblemCounter}}
\setcounter{partCounter}{1}
\enterProblemHeader{homeworkProblemCounter}
}{
\exitProblemHeader{homeworkProblemCounter}
}

%
% Homework Details
%   - Title
%   - Due date
%   - Class
%   - Section/Time
%   - Instructor
%   - Author
%

\newcommand{\hmwkTitle}{Homework\ \#5}
\newcommand{\hmwkDueDate}{March 30, 2016}
\newcommand{\hmwkClass}{Operating Systems}
\newcommand{\hmwkClassTime}{Monday \& Wednesday 3:30pm --- 5:17pm}
\newcommand{\hmwkClassInstructor}{Professor Qu}
\newcommand{\hmwkAuthorName}{<NAME>}

%
% Title Page
%

\title{
\vspace{2in}
\textmd{\textbf{\hmwkClass:\ \hmwkTitle}}\\
\normalsize\vspace{0.1in}\small{Due\ on\ \hmwkDueDate\ at 11:59pm}\\
\vspace{0.1in}\large{\textit{\hmwkClassInstructor\ \\ \hmwkClassTime}}
\vspace{3in}
}

\author{\textbf{\hmwkAuthorName}}
\date{}

\renewcommand{\part}[1]{\textbf{\large Part \Alph{partCounter}}\stepcounter{partCounter}\\}

%
% Various Helper Commands
%

% Alias for the Solution section header
\newcommand{\solution}{\textsc{\textbf Solution}\\}

% Alias for bold small caps
\newcommand{\smallcaps}[1]{\textsc{\textbf #1}\\}

\begin{document}

  \maketitle
  \pagebreak

  \begin{homeworkProblem}
    Why is the protection of processes' memory space important? Describe a scenario where absence of memory protection leads to problems. \\

    \solution

    Protection of processes' memory space is important because it prevents processes from accessing memory that have not yet been allocated. A scenario in which could cause problems with the absence of memeory protection would be when a process attempts to access memory that hasn't been allocated yet will cause the program to crash.
  \end{homeworkProblem}

  \begin{homeworkProblem}
    Consider a system where the virtual memory page size is 1KB (1024 bytes), and main memory consists of 4 page frames, which are empty initially. Now consider a process, which requires 8 pages of storage.  At some point during its execution, the page table is as shown below:

    \begin{center}
      \begin{tabular}{|c|c|c|}
        \hline
        Virtual Page \# & Physical Page \# & Valid Flag \\
        \hline
        0 &  & No \\
        \hline
        1 &  & No \\
        \hline
        2 & 2 & Yes \\
        \hline
        3 & 3 & Yes \\
        \hline
        4 &  & No \\
        \hline
        5 &  & No \\
        \hline
        6 & 0 & Yes \\
        \hline
        7 & 1 & Yes \\
        \hline
      \end{tabular}
    \end{center}

    \begin{enumerate}
      \item List the virtual address ranges that will result in a page fault.
      \item Give the following ordered references to the virtual addresses (i) 4500, (ii) 8000, (iii) 3000, (iv) 1100, please calculate the main memory (physical) addresses. If there is a page fault, please use LRU based page replacement to replace the page. How which page will be affected and compute the physical addresses after the page fault. We assume the reference string is \ldots 2 4 7 3 0 4 3 0 7 5 0 7 6 0 2 3 6 4 7 6 3 2 before the new reference.
    \end{enumerate}

    \solution

    \begin{enumerate}
      \item The virtual address ranges that will result in page fault are: \\
      Page 0: 0 -- 1023 \\
      Page 1: 1024 -- 2047 \\
      % Page 2: 2048 -- 3071 \\
      Page 4: 4096 -- 5119 \\
      Page 5: 5020 -- 6143 \\

      \pagebreak

      \item References as follows:
      \begin{enumerate}[label=(\roman*)]
        \item 4500 is a page fault. Reference string is: \\
        \begin{center}
          \begin{tabular}{ccccccccccccccccccccccc}
            2 & 4 & 7 & 3 & 0 & 4 & 3 & 0 & 7 & 5 & 0 & 7 & 6 & 0 & 2 & 3 & 6 & 4 & 7 & 6 & 3 & 2 & 4 \\
            2 & 2 & 2 & 2 & 0 & & & & & 0 & & & 0 & & 0 & 0 & & 4 & 4 & & & 2 & 2 \\
            & 4 & 4 & 4 & 4 & & & & & 5 & & & 5 & & 2 & 2 & & 2 & 7 & & & 7 & 4 \\
            & & 7 & 7 & 7 & & & & & 7 & & & 7 & & 7 & 3 & & 3 & 3 & & & 3 & 3 \\
            & & & 3 & 3 & & & & & 3 & & & 6 & & 6 & 6 & & 6 & 6 & & & 6 & 6 \\
          \end{tabular}
        \end{center}

        \begin{center}
          \begin{tabular}{|c|c|c|}
            \hline
            Virtual Page \# & Physical Page \# & Valid Flag \\
            \hline
            0 &  & No \\
            \hline
            1 &  & No \\
            \hline
            2 & 2 & Yes \\
            \hline
            3 & 3 & Yes \\
            \hline
            4 & 1 & Yes \\
            \hline
            5 &  & No \\
            \hline
            6 & 0 & Yes \\
            \hline
            7 & & No \\
            \hline
          \end{tabular}
        \end{center}

        \textit{Page \#} $*$ \textit{Page Size} $+$ \textit{Offset} $=$ \textit{Virtual Address}\\
        Offset is found by $4500 - (4 * 1024) = 404$ \\

        $\therefore 4500 = 4 * 1024 + 404$ \\
        So \ldots virtual page \#4 points to physcial page \#1, so the physical address is $1 * 1024 + 404 = 1428$.

        \item After the page replacement, 8000 is a page fault. Reference string is:

        \begin{center}
          \begin{tabular}{cccccccccccccccccccccccc}
            2 & 4 & 7 & 3 & 0 & 4 & 3 & 0 & 7 & 5 & 0 & 7 & 6 & 0 & 2 & 3 & 6 & 4 & 7 & 6 & 3 & 2 & 4 & 7 \\
            2 & 2 & 2 & 2 & 0 & & & & & 0 & & & 0 & & 0 & 0 & & 4 & 4 & & & 2 & 2 & 2\\
            & 4 & 4 & 4 & 4 & & & & & 5 & & & 5 & & 2 & 2 & & 2 & 7 & & & 7 & 4 & 4 \\
            & & 7 & 7 & 7 & & & & & 7 & & & 7 & & 7 & 3 & & 3 & 3 & & & 3 & 3 & 3 \\
            & & & 3 & 3 & & & & & 3 & & & 6 & & 6 & 6 & & 6 & 6 & & & 6 & 6 & 7 \\
          \end{tabular}
        \end{center}

        \begin{center}
          \begin{tabular}{|c|c|c|}
            \hline
            Virtual Page \# & Physical Page \# & Valid Flag \\
            \hline
            0 &  & No \\
            \hline
            1 & & No \\
            \hline
            2 & 2 & Yes \\
            \hline
            3 & 3 & Yes \\
            \hline
            4 & 1 & Yes \\
            \hline
            5 &  & No \\
            \hline
            6 & & No \\
            \hline
            7 & 0 & Yes \\
            \hline
          \end{tabular}
        \end{center}

        Offset is found by $8000 - (7 * 1024) = 832$ \\
        $\therefore 8000 = 7 * 1024 + 832$ \\
        So \ldots virtual page \#7 points to physcial page \#0, so the physical address is $0 * 1024 + 832 = 832$.

        \pagebreak

        \item There is no page fault on 3000 so reference string \& page table remain the same.

        \begin{center}
          \begin{tabular}{cccccccccccccccccccccccc}
            2 & 4 & 7 & 3 & 0 & 4 & 3 & 0 & 7 & 5 & 0 & 7 & 6 & 0 & 2 & 3 & 6 & 4 & 7 & 6 & 3 & 2 & 4 & 7 \\
            2 & 2 & 2 & 2 & 0 & & & & & 0 & & & 0 & & 0 & 0 & & 4 & 4 & & & 2 & 2 & 2\\
            & 4 & 4 & 4 & 4 & & & & & 5 & & & 5 & & 2 & 2 & & 2 & 7 & & & 7 & 4 & 4 \\
            & & 7 & 7 & 7 & & & & & 7 & & & 7 & & 7 & 3 & & 3 & 3 & & & 3 & 3 & 3 \\
            & & & 3 & 3 & & & & & 3 & & & 6 & & 6 & 6 & & 6 & 6 & & & 6 & 6 & 7 \\
          \end{tabular}
        \end{center}

        \begin{center}
          \begin{tabular}{|c|c|c|}
            \hline
            Virtual Page \# & Physical Page \# & Valid Flag \\
            \hline
            0 &  & No \\
            \hline
            1 &  & No \\
            \hline
            2 & 2 & Yes \\
            \hline
            3 & 3 & Yes \\
            \hline
            4 & 1 & Yes \\
            \hline
            5 &  & No \\
            \hline
            6 & & No \\
            \hline
            7 & 0 & Yes \\
            \hline
          \end{tabular}
        \end{center}

        Offset is found by $3000 - (2* 1024) = 952$ \\
        $\therefore 3000 = 2 * 1024 + 952$ \\
        So \ldots virtual page \#2 points to physcial page \#2, so the physical address is $2 * 1024 + 952 = 3000$.

        \item 1100 results in a page fault, reference string is:

        \begin{center}
          \begin{tabular}{ccccccccccccccccccccccccc}
            2 & 4 & 7 & 3 & 0 & 4 & 3 & 0 & 7 & 5 & 0 & 7 & 6 & 0 & 2 & 3 & 6 & 4 & 7 & 6 & 3 & 2 & 4 & 7 & 1 \\
            2 & 2 & 2 & 2 & 0 & & & & & 0 & & & 0 & & 0 & 0 & & 4 & 4 & & & 2 & 2 & 2 & 2 \\
            & 4 & 4 & 4 & 4 & & & & & 5 & & & 5 & & 2 & 2 & & 2 & 7 & & & 7 & 4 & 4 & 4 \\
            & & 7 & 7 & 7 & & & & & 7 & & & 7 & & 7 & 3 & & 3 & 3 & & & 3 & 3 & 3 & 1 \\
            & & & 3 & 3 & & & & & 3 & & & 6 & & 6 & 6 & & 6 & 6 & & & 6 & 6 & 7 & 7 \\
          \end{tabular}
        \end{center}

        \begin{center}
          \begin{tabular}{|c|c|c|}
            \hline
            Virtual Page \# & Physical Page \# & Valid Flag \\
            \hline
            0 &  & No \\
            \hline
            1 & 3 & Yes \\
            \hline
            2 & 2 & Yes \\
            \hline
            3 & & No \\
            \hline
            4 & 1 & Yes \\
            \hline
            5 &  & No \\
            \hline
            6 & & No \\
            \hline
            7 & 0 & Yes \\
            \hline
          \end{tabular}
        \end{center}

        Offset is found by $1100 - (1 * 1024) = 76$ \\
        $\therefore 1100 = 1 * 1024 + 76$ \\
        So \ldots virtual page \#1 points to physcial page \#3, so the physical address is $3 * 1024 + 76 = 3148$.
      \end{enumerate}
    \end{enumerate}
  \end{homeworkProblem}

  \pagebreak

  \begin{homeworkProblem}
    Given a computer system with the following paging based addressing for virtual addresses. Please answer the following questions:

    \begin{center}
      \begin{tabular}{|c|c|c|c|c|}
        \hline
        2 bits & 5 bits & 5 bits & 5 bits & 7 bits \\
        \hline
      \end{tabular}
    \end{center}

    \begin{enumerate}
      \item What is the size of the virtual address space?
      \item What is the page size?
      \item What is the maximum number of pages for a process?
      \item Given the system has a TLB hit ratio of 99\% and page fault rate of 1\%. Please formulate the effective memory access time.
    \end{enumerate}

    \solution

    \begin{enumerate}
      \item The virtual address space is: $2 + 5 + 5 + 5 + 7 = 24 \implies 2^{24} = 16,777,216$ bytes or 16 MB.
      \item The page offset field is $7$ $\therefore$ $2^7 = 128$ bytes.
      \item The number of pages for each process is $2^{24}$\big/ $2^{7} = 2^{17} \implies 131,072$
      \item Effective memory access time is: \\
      $(\mbox{TLB Lookup} + \mbox{Memory Access Time}) * .99 + (\mbox{TLB Lookup} + 2 (\mbox{Memory Access Time})) * .01$
    \end{enumerate}
  \end{homeworkProblem}

  \begin{homeworkProblem}
    Consider a system with 1MB of available memory and requests for 42KB, 396KB, 10KB, and 28KB. The system is using Buddy Allocation Algorithm.

    \begin{enumerate}[label=\alph*)]
      \item Show the amount of memory allocated for each request and the state of memory after each request. Assume there is no memory release.
      \item Why does internal fragmentation occur with buddy allocation? How much internal fragmentation exists in this scenario?
      \item Why does external fragmentation occur with buddy allocation? How much external fragmentation exists in this scenario?
    \end{enumerate}

    \pagebreak

    \solution

    \begin{enumerate}[label=\alph*)]
      \item 42KB $\implies$ 64KB : \textbf{64KB} 64KB 128KB 256KB 512KB \\
            396KB $\implies$ 512KB : \textbf{64KB} 64KB 128KB 256KB \textbf{512KB} \\
            10KB $\implies$ 16KB : \textbf{64KB} \textbf{16KB} 16KB 32KB 64KB 128KB 256KB \textbf{512KB} \\
            28KB $\implies$ 32KB : \textbf{64KB} \textbf{16KB} 16KB \textbf{32KB} 64KB 128KB 256KB \textbf{512KB} \\

            Key: \textbf{Bold} font denotes allocated memory.
      \item Internal fragmentation is wasted memory visible only to the process making the memory request. Internal fragmentation occurs in buddy allocation because memory requests must be rounded up to the nearest power of 2. \\
      Amount of internal fragmentation: $(64-42) + (512-396) + (16-10) + (32 - 28) = 148KB$
      \item External fragmentation is wasted memory visible to the system outside of the requesting processes. External fragmentation occurs because not all requests (even after they've been rounded up to the nearest power of two) are the same size; therefore, it is possible that a memory request will not be able to satisfied, even when there is enough total free memory in the system. \\
      Amount of external fragmentation: $16 + 128 + 256 = 400KB$
    \end{enumerate}
  \end{homeworkProblem}
\end{document}
<file_sep>/notes/final_exam/final_exam_cheatsheet.tex
\documentclass{article}

\usepackage[margin=0.3in]{geometry}
\usepackage{multicol}
\usepackage[T1]{fontenc}
\usepackage{lipsum}
\usepackage{color}
\usepackage{tikz}
\usepackage{amsmath}
\usepackage{graphicx}
\usepackage[usenames, dvipsnames]{color}
\usepackage[linesnumbered,boxed,commentsnumbered,lined]{algorithm2e}
\usetikzlibrary{positioning}

\tikzset{
  gray box/.style={
    fill=gray!20,
    draw=gray,
    minimum width={2*#1ex},
    minimum height={2em},
  },
  annotation/.style={
    anchor=north,
  }
}

\setlength\parindent{0pt}

% Alias for bold small caps
\newcommand{\smallcaps}[1]{\textsc{\textbf #1}\\}

\begin{document}
  \begin{multicols}{2}
    A computer whose processes have 1024 pages in their address spaces keeps
    its page tables in memory. The overhead required for reading a word from
    the page table is 500 nsec.  To reduce this  overhead, the computer has an
    associative  memory  which holds 32 (virtual  page,  physical  page frame)
    pairs and can do look up in 100 nsec.  What hit rate is needed  to reduce
    the mean overhead to 200 nsec?

    \smallcaps{Solution}

    The effective instruction time is $100h + 500(1-h)$, where h is the
    hit rate. $100$ is the look up time \& $500$ is the overhead. Set the
    expression equal to 200 and solve for h. We get h must be 0.75 (or greater).

    \begin{align*}
      100h + 500(1-h) &= 200 \\
      100h + 500 - 500h &= 200 \\
      -400h + 500 &= 200 \\
      -400h &= -300 \\
      h &= \frac{-300}{-400} \\
      h &= \frac{3}{4} \implies 75\%
    \end{align*}

    \section*{Address Translation}
    \begin{tabular}{|c|c|c|}
      \hline
      Frame Number & Process ID & Page Number \\
      \hline
      0 & 1 & 2 \\
      \hline
      1 & 1 & 1 \\
      \hline
      2 & 2 & 1 \\
      \hline
      3 & 3 & 0 \\
      \hline
      4 & 1 & 3 \\
      \hline
    \end{tabular}

    Using the table above, translate the following:

    \begin{enumerate}
      \item To which physical address does virtual address 130 of process 1 map to?
        If this virtual address does not map to any physical address, write `does not map'.
      \item To which physical address does virtual address 17 of process 2 map to?
        If this virtual address does not map to any physical address, write `does not map'.
      \item Which virtual address of which process maps to physical address 50?
    \end{enumerate}

    \smallcaps{Solution}

    \begin{enumerate}
      \item logical $= (1 \times 100) + 30 \implies 130$ \\
        Physical $=$ frame\# $= 1 \implies (1 \times 100) + 30 = 130$
      \item Virtual address 17 does not map
      \item Physical address $= (0 \times 100) + 50 = 50$ Where $0$ is the frame\# \\
        So, logical address $= (2 \times 100) + 50 = 250$ Where $2$ is the page\#
    \end{enumerate}

    \section*{File system implementation}
    Consider a File system that maintains unique index node for each
    file in the system. Each index node includes 10 direct pointers, a single indirect pointer,
    and a double indirect pointer. The file system block size is 1024 bytes, and a block pointer
    occupies 4 bytes.

    \begin{enumerate}
      \item What is the maximum file size that can be supported by the index node?
      \item How many disk operations will be required if a process read data from the $N^{th}$ block
        of a file? Assume that the file is already open, the buffer cache is empty, and each disk
        operation read a single file block. Your answer should be given in terms of $N$.
    \end{enumerate}

    \smallcaps{Solution}

    \begin{enumerate}
      \item $1024 * (10 + 2^8 + 2^8 * 2^8)$ \\
        $\implies 2^{10} * (2^3 + 2 + 2^8 + 2^{16})$ \\
        $\implies 2^{13} + 2^{11} + 2^{18} + 2^{26}$ \\
      \item $0 \le N < 10$, One operation \\
        $10 \le N < 256 + 10$, Two operations \\
        $256 + 10 \le N < 2^{13} + 2^{11} + 2^{18} + 2^{26}$, Three operations
    \end{enumerate}

    \# 6 part c:
    \begin{itemize}
      \item $1 \le N < 10$, One operation
      \item $10 \le N$, $1 + ceiling(\frac{n - 10}{255})$
    \end{itemize}

    Allocations

    \begin{itemize}
      \item Contiguous Allocation : Each file occupies a set of contiguous blocks on the disk.
      \item Linked Allocation : Each file is a linked list of disk blocks: blocks may be scattered
        anywhere on the disk.
      \item Indexed Allocation : Brings all pointers together into the index block.
    \end{itemize}

    \section*{Disk Scheduling}

    \begin{itemize}
      \item First-come, First-served: the requests are processed in the order they were received.
      \item Shortest Seek Time First: Process the request that is closest to the arms current
        position.
      \item SCAN: Process all the requests going in one direction until they are complete, and then
        change the direction of the arm and process the rest of the requests.
      \item C-SCAN: Process all the requests going in one direction. When arm reaches the end, start
        back at the beginning and finish out the rest of the requests.
      \item C-LOOK: Process all the requests in one direction, when the last request in that direction
        is completed, change the direction of the arm and process the rest of the requests in the
        other direction.
    \end{itemize}

    \section*{Page Replacement Algorithms}

    \begin{itemize}
      \item First-in First-out (FIFO): when a page must be replaced, the oldest page is chosen.
      \item Optimal: Replace page that will not be used for the longest period of time.
      \item LRU: Replace the page that has not been used for the longest period of time.
    \end{itemize}

    \section*{Deadlock}

    Four conditions for deadlock:
    \begin{itemize}
      \item Mutual Exclusion
      \item Hold and Wait
      \item No Preemption
      \item Circular Wait
    \end{itemize}

    For calculating the needs matrix, we take maximum $-$ current. To derive the safe order, We
    start with the initial work, and we check the current allocation and if that is less than the
    current work, that process is added to safe state \& then we add the current allocation to the
    work available.

    \section*{Segmentation}

    A virtual memory system supports 12 bits length virtual addresses. It uses pure segmentation
    with a maximum segment size of $2^{10}$ (1024) bytes. Suppose that the segment table for the
    currently running process looks as follows:

    \begin{tabular}{|c|c|c|c|c|}
      \hline
      Segment \# & V & P & Start & Length \\
      \hline
      0 & 1 & 1 & 0 & 200 \\
      \hline
      1 & 1 & 0 & 1000 & 160 \\
      \hline
      2 & 0 & 0 & 0 & 0 \\
      \hline
      3 & 1 & 0 & 200 & 300 \\
      \hline
    \end{tabular}

    In the table above V and P are the segment `valid' and `protection' bits, `start' represents the
    physical address of the start of the segment and `Length' is the segments's length. $P = 1$
    indicates that a segment is read-only.

    Consider the following read and write operations. If the specified operation would succeed given
    the segment table shown above, give the physical address to which the specified virtual address
    would translate. If it would not succeed, state the reason that it would fail.

    \begin{enumerate}
      \item A write to virtual address 150
      \item A read from virtual address 1025
      \item A write to virtual address 400
    \end{enumerate}

    \smallcaps{Solution}

    \begin{enumerate}
      \item
        $150 = (0 \times 1024) + 150$ \\
        $150 < 200$ \\
        This would fail because there is a protection bit $\implies$ read-only.
      \item
        $1025 = (1 \times 1024) + 1$ \\
        $1 < 1160$ \\
        Physical address $= 1001$.
      \item
        $4000 = (3 \times 1024) + 928$ \\
        $928 > 500$ \\
        This would fail because of a trap: Addressing error.
    \end{enumerate}

    \section*{Buddy Algorithm}
    \begin{center}
      \includegraphics[scale=0.4]{buddy_algorithm.png} \\
    \end{center}

    This would represent a request for $<$ 4KB. In the example above one of the 4KB blocks would be
    allocated to the current request.

    Internal fragmentation is wasted memory visible only to the process making the memory request.
    Internal fragmentation occurs in buddy allocation because memory requests must be rounded up to
    the nearest power of 2.

    So, for example if we had a request of 2KB, then the internal fragmentation would be $4KB - 2KB
    = 2KB$

    External fragmentation is wasted memory visible to the system outside of the requesting
    processes. External fragmentation occurs because not all requests (even after they've been
    rounded up to the nearest power of two) are the same size; therefore, it is possible that a
    memory request will not be able to satisfied, even when there is enough total free memory in the
    system.

    Basically: External fragmentation is because it's not contiguous.
  \end{multicols}
\end{document}
<file_sep>/notes/jan_25/2016_01_25_lecture_notes.tex
\documentclass[titlepage]{article}
\usepackage{fancyhdr}
\usepackage{datetime}
\usepackage{color}
\fancyhf{}

\topmargin=-0.45in
\evensidemargin=0in
\oddsidemargin=0in
\textwidth=6.5in
\textheight=9.0in
\headsep=0.25in

\newcommand{\noteTitle}{\formatdate{25}{1}{2016} --- Notes}
\newcommand{\professor}{<NAME>}
\newcommand{\class}{CSE 450 Operating Systems}
\newcommand{\classTime}{Monday \& Wednesday 3:30 --- 5:17 pm}
\newcommand{\notesAuthor}{<NAME>}

\pagestyle{fancy}
\lhead{\notesAuthor}
\chead{\class}
\rhead{\noteTitle}
\lfoot{}
\cfoot{\thepage}
\rfoot{}
\renewcommand{\headrulewidth}{0.4pt}
\renewcommand{\footrulewidth}{0.4pt}

\title{
  \textmd{\LARGE{\textbf{\noteTitle}}}\\
  \textmd{\Large{\textit{\class}}}\\
  \textmd{\Large{\textit{Professor\ \professor}}}\\
  \textmd{\normalsize{\classTime}}\\
  \vspace{3.5in}
  \textmd{\LARGE{\textbf{\notesAuthor}}}\\
  \date{}
}

\begin{document}
  \maketitle

  \section*{What Computer System Structure}
  \begin{itemize}
    \item Computer system can be divided into four components
    \begin{itemize}
      \item Hardware --- provides basic computing resources
      \begin{itemize}
        \item CPU, memory, I/O devices
      \end{itemize}
      \item Operating System
      \begin{itemize}
        \item Controls and coordinates use of hardware among various applications and users
      \end{itemize}
      \item Application programs ---  define the ways in which the system resources are used to solve the computing problems of the users
      \begin{itemize}
        \item Word processors, compilers, web browsers, database systems, \& video games
      \end{itemize}
      \item Users
      \begin{itemize}
        \item People, machines, \& other computers
      \end{itemize}
    \end{itemize}
  \end{itemize}

  \section*{What is an Operating System?}
  \begin{itemize}
    \item An operating system (OS) is a collection of software that manages computer hardware resources and provides common services for computer programs.
    \begin{itemize}
      \item The OS is a vital component of the system software in a computer system.
      \item Application Programs usually require an OS to function
      \item A program that acts as an intermediary between a user of a computer and sthe computer hardware.
    \end{itemize}
    \item Operating System {\color{red} \textbf{goals}}:
    \begin{itemize}
      \item Execute user programs and make solving problems easier.
      \item Make the computer system convient to user.
      \item Use the computer hardware in an efficient manner.
    \end{itemize}
  \end{itemize}

  \section*{Computer-System Operation}
  \begin{itemize}
    \item I/O devices and the computer execute concurrently
    \item Each device controller is in charge of a particular device type
    \item Each device controller has a local buffer
    \item CPU moves data from/to main memory to/from local buffers
    \item I/O is from the device to local buffer of controller
    \item Device controller informs CPU that is has finished its operation by causing an \textit{interrupt}
  \end{itemize}

\end{document}
<file_sep>/homework_2/homework_2.tex
\documentclass{article}

\usepackage{fancyhdr}
\usepackage{extramarks}
\usepackage{minted}
\usepackage[T1]{fontenc}
\usepackage{graphicx}
\usepackage{inconsolata}
\usepackage{multicol}
\usepackage{enumitem}

%
% Basic Document Settings
%

\topmargin=-0.45in
\evensidemargin=0in
\oddsidemargin=0in
\textwidth=6.5in
\textheight=9.0in
\headsep=0.25in

\linespread{1.1}

\pagestyle{fancy}
\lhead{\hmwkAuthorName}
\chead{\hmwkClass: \hmwkTitle}
\rhead{\firstxmark}
\lfoot{\lastxmark}
\cfoot{\thepage}

\renewcommand\headrulewidth{0.4pt}
\renewcommand\footrulewidth{0.4pt}

\setlength\parindent{0pt}

%
% Create Problem Sections
%

\newcommand{\enterProblemHeader}[1]{
\nobreak\extramarks{}{Problem \arabic{#1} continued on next page\ldots}\nobreak{}
\nobreak\extramarks{Problem \arabic{#1} (continued)}{Problem \arabic{#1} continued on next page\ldots}\nobreak{}
}

\newcommand{\exitProblemHeader}[1]{
\nobreak\extramarks{Problem \arabic{#1} (continued)}{Problem \arabic{#1} continued on next page\ldots}\nobreak{}
\stepcounter{#1}
\nobreak\extramarks{Problem \arabic{#1}}{}\nobreak{}
}

\setcounter{secnumdepth}{0}
\newcounter{partCounter}
\newcounter{homeworkProblemCounter}
\setcounter{homeworkProblemCounter}{1}
\nobreak\extramarks{Problem \arabic{homeworkProblemCounter}}{}\nobreak{}

%
% Homework Problem Environment
%
% This environment takes an optional argument. When given, it will adjust the
% problem counter. This is useful for when the problems given for your
% assignment aren't sequential. See the last 3 problems of this template for an
% example.
%
\newenvironment{homeworkProblem}[1][-1]{
\ifnum#1>0
\setcounter{homeworkProblemCounter}{#1}
\fi
\section{Problem \arabic{homeworkProblemCounter}}
\setcounter{partCounter}{1}
\enterProblemHeader{homeworkProblemCounter}
}{
\exitProblemHeader{homeworkProblemCounter}
}

%
% Homework Details
%   - Title
%   - Due date
%   - Class
%   - Section/Time
%   - Instructor
%   - Author
%

\newcommand{\hmwkTitle}{Homework\ \#2}
\newcommand{\hmwkDueDate}{February 19, 2016}
\newcommand{\hmwkClass}{Operating Systems}
\newcommand{\hmwkClassTime}{Monday \& Wednesday 3:30pm --- 5:17pm}
\newcommand{\hmwkClassInstructor}{Professor Qu}
\newcommand{\hmwkAuthorName}{<NAME>}

%
% Title Page
%

\title{
\vspace{2in}
\textmd{\textbf{\hmwkClass:\ \hmwkTitle}}\\
\normalsize\vspace{0.1in}\small{Due\ on\ \hmwkDueDate\ at 11:59pm}\\
\vspace{0.1in}\large{\textit{\hmwkClassInstructor\ \\ \hmwkClassTime}}
\vspace{3in}
}

\author{\textbf{\hmwkAuthorName}}
\date{}

\renewcommand{\part}[1]{\textbf{\large Part \Alph{partCounter}}\stepcounter{partCounter}\\}

%
% Various Helper Commands
%

% Useful for algorithms
\newcommand{\alg}[1]{\textsc{\bfseries \footnotesize #1}}

% For derivatives
\newcommand{\deriv}[1]{\frac{\mathrm{d}}{\mathrm{d}x} (#1)}

% For partial derivatives
\newcommand{\pderiv}[2]{\frac{\partial}{\partial #1} (#2)}

% Integral dx
\newcommand{\dx}{\mathrm{d}x}

% Alias for the Solution section header
\newcommand{\solution}{\textbf{\large Solution}}

% Probability commands: Expectation, Variance, Covariance, Bias
\newcommand{\E}{\mathrm{E}}
\newcommand{\Var}{\mathrm{Var}}
\newcommand{\Cov}{\mathrm{Cov}}
\newcommand{\Bias}{\mathrm{Bias}}

\begin{document}

  \maketitle

  \pagebreak

  \begin{homeworkProblem}
    \begin{itemize}
      \item Can there be a thread blocked on a semaphore with non-negative value?
      \item Can a semaphore have a negative value without having any threads blocked on it?
    \end{itemize}

    \textbf{\textsc{Solution}} \\

    Yes, because a thread is blocked on 0, and 0 is non-negative. If the value is negative, there are no more resources allocate to use the semaphore. \\

    Yes, because if there are no threads are requesting it than it can have a negative value.
  \end{homeworkProblem}

  \begin{homeworkProblem}
    In the following code, four processes produce output using the routine `printf' and synchronize using three semaphores `R', `S' and `T.' \underline{We assume function `printf' wont cause context switch.}

    \begin{minted}{C++}
      Semaphore R=1, S=3, T=0; /* Initialization */
    \end{minted}

    \begin{multicols}{4}
      \begin{minted}{C++}
        /* Process 1 */
        while(true) {
          P(S);
          printf('A');
        }
      \end{minted}

      \vfill
      \columnbreak

      \begin{minted}{C++}
        /* Process 2 */
        while(true) {
          P(T);
          printf('B');
          printf('C');
          V(T);
        }
      \end{minted}

      \vfill
      \columnbreak

      \begin{minted}{C++}
        /* Process 3 */
        while(true) {
          P(T);
          printf('D');
          V(R);
        }
      \end{minted}

      \vfill
      \columnbreak

      \begin{minted}{C++}
        /* Process 4 */
        while(true) {
          P(R);
          printf('E');
          V(T);
        }
      \end{minted}
    \end{multicols}

    \begin{enumerate}[label=\alph*)]
      \item How many \textbf{A}\textquotesingle s and \textbf{B}\textquotesingle s are printed when this set of processes runs?

      \item What is the smallest number of \textbf{D}\textquotesingle s that might be printed when this set of processes runs?

      \item Is \textbf{AEBCBCDAA} a possible output sequence when this set of processes runs? Clarify your answer.
    \end{enumerate}

    \textbf{\textsc{Solution}}

    \begin{enumerate}[label=\alph*)]
      \item Three \textbf{A}\textquotesingle s are printed because S is decremented, but it is never incremented.

      B can be printed 0, 1, or \{B\}* times. It is possible that be could be infinite. However, It is also possible that process 3 and process 4 could be in an infinite loop, and in that case B would not be printed. It could also be that B could get printed only one time, and then process 3 and 4 are in an infinite loop. B could be printed \{B\}* times if process 2 was in an infinite loop.

      \item 0 times. If process 4 is run, it is possible that process 2 could run, and then go between process 2 and 4 infinitely so long as there is no waiting queue.

      If there is a waiting queue then D can be printed infinitely many times.

      \item Yes, because processes 1 could run, then process 4, then process 2, then process 2, then process 2, then process 2, then process 2, then process 3, then process 1, and finally process 1 if there is a waiting queue.

      If there is a waiting queue then this would not be a possible output, because then process 2 is not able to be in the waiting queue when it is being executed. So the output BCBC would be unable to complete.
    \end{enumerate}
  \end{homeworkProblem}

  \pagebreak

  \begin{homeworkProblem}
    Consider the following two processes $P[i]$ and $P[j]$. Initially, flag[i] = flag [j] = false.

    \begin{multicols}{2}

      \begin{minted}{C++}
        Do {
          flag[i]=true;
          While(flag[j]);

          critical section

          flag[i] = false;

          remainder section
        } while(1);
      \end{minted}

      \vfill
      \columnbreak

      \begin{minted}{C++}
        Do {
          flag[j]=true;
          While(flag[i]);

          critical section

          flag[j] = false;

          remainder section
        } while(1);
      \end{minted}
    \end{multicols}

    \begin{enumerate}[label=\alph*)]
      \item Does the above program satisfy the `progress' requirement? Justify your answer with an informal proof or counterexample. [Simple `Yes' or `No' without explanation]
      \item Is mutual exclusion assured? Justify your answer with an informal proof or counterexample.
    \end{enumerate}

    \textbf{\textsc{Solution}}

    \begin{enumerate}[label=\alph*)]
      \item Yes, this follows the `progress' requirement. According to the `progress' requirement, if no process is executing in it\textquotesingle s critical section, and some process wishes to enter their critical section, then so long as that process is not in the remainder section it will enter the critical section. In the example above once $p[i]$ starts then it sets $p[j]$ to true. Once $p[j]$ begins then it will enter the critical section, but while that happens, $p[i]$ is also set to true. Being that $p[j]$ is in the critical section, that means that $p[i]$ will also be able to enter the critical section being that it is not currently in the remainder section. Therefore, satisfying the `progress' requirement.

      \item Mutual exclusion is assured. In either case each process $p[i]$ \& $p[j]$ can only do one thing at a time. Even if one process starts a little bit before another one, we\textquotesingle ll assume that the while() loop will still be executed before the other process finishes the critical section and turns flag[] to false. Because of this, we can be assured that mutual exclusion is achieved.
    \end{enumerate}
  \end{homeworkProblem}

\end{document}
<file_sep>/homework_6/homework_6.tex
\documentclass{article}

\usepackage{fancyhdr}
\usepackage{extramarks}
\usepackage{minted}
\usepackage[T1]{fontenc}
\usepackage{graphicx}
\usepackage{inconsolata}
\usepackage{multicol}
\usepackage{enumitem}
\usepackage{amsmath}
\usepackage{amssymb}

%
% Basic Document Settings
%

\topmargin=-0.45in
\evensidemargin=0in
\oddsidemargin=0in
\textwidth=6.5in
\textheight=9.0in
\headsep=0.25in

\linespread{1.1}

\pagestyle{fancy}
\lhead{\hmwkAuthorName}
\chead{\hmwkClass: \hmwkTitle}
\rhead{\firstxmark}
\lfoot{\lastxmark}
\cfoot{\thepage}

\renewcommand\headrulewidth{0.4pt}
\renewcommand\footrulewidth{0.4pt}

\setlength\parindent{0pt}

%
% Create Problem Sections
%

\newcommand{\enterProblemHeader}[1]{
\nobreak\extramarks{}{Problem \arabic{#1} continued on next page\ldots}\nobreak{}
\nobreak\extramarks{Problem \arabic{#1} (continued)}{Problem \arabic{#1} continued on next page\ldots}\nobreak{}
}

\newcommand{\exitProblemHeader}[1]{
\nobreak\extramarks{Problem \arabic{#1} (continued)}{Problem \arabic{#1} continued on next page\ldots}\nobreak{}
\stepcounter{#1}
\nobreak\extramarks{Problem \arabic{#1}}{}\nobreak{}
}

\setcounter{secnumdepth}{0}
\newcounter{partCounter}
\newcounter{homeworkProblemCounter}
\setcounter{homeworkProblemCounter}{1}
\nobreak\extramarks{Problem \arabic{homeworkProblemCounter}}{}\nobreak{}

%
% Homework Problem Environment
%
% This environment takes an optional argument. When given, it will adjust the
% problem counter. This is useful for when the problems given for your
% assignment aren't sequential. See the last 3 problems of this template for an
% example.
%
\newenvironment{homeworkProblem}[1][-1]{
\ifnum#1>0
\setcounter{homeworkProblemCounter}{#1}
\fi
\section{Problem \arabic{homeworkProblemCounter}}
\setcounter{partCounter}{1}
\enterProblemHeader{homeworkProblemCounter}
}{
\exitProblemHeader{homeworkProblemCounter}
}

%
% Homework Details
%   - Title
%   - Due date
%   - Class
%   - Section/Time
%   - Instructor
%   - Author
%

\newcommand{\hmwkTitle}{Homework\ \#6}
\newcommand{\hmwkDueDate}{April 11, 2016}
\newcommand{\hmwkClass}{Operating Systems}
\newcommand{\hmwkClassTime}{Monday \& Wednesday 3:30pm --- 5:17pm}
\newcommand{\hmwkClassInstructor}{Professor Qu}
\newcommand{\hmwkAuthorName}{<NAME>}

%
% Title Page
%

\title{
\vspace{2in}
\textmd{\textbf{\hmwkClass:\ \hmwkTitle}}\\
\normalsize\vspace{0.1in}\small{Due\ on\ \hmwkDueDate\ at 11:59pm}\\
\vspace{0.1in}\large{\textit{\hmwkClassInstructor\ \\ \hmwkClassTime}}
\vspace{3in}
}

\author{\textbf{\hmwkAuthorName}}
\date{}

\renewcommand{\part}[1]{\textbf{\large Part \Alph{partCounter}}\stepcounter{partCounter}\\}

%
% Various Helper Commands
%

% Alias for the Solution section header
\newcommand{\solution}{\textsc{\textbf Solution}\\}

% Alias for bold small caps
\newcommand{\smallcaps}[1]{\textsc{\textbf #1}\\}

\begin{document}

  \maketitle
  \pagebreak

  \begin{homeworkProblem}
    For each part of this question, assume that the disk has a total of 100 cylinders.

    \begin{enumerate}[label=\alph*)]
      \item Suppose that the disk head scheduling policy is shortest seek time first (SSTF). The disk heads are currently positioned over cylinder 42 and requests are queue for data on cylinders
      \begin{center}
        27, 40, 90, 37, 15, 67
      \end{center}
      What will be the total distance (in cylinders) traveled by the disk heads to serve the six queued requests?
      \item Suppose instead that the disk head scheduling policy is SCAN (elevator). The disk heads are initially positioned over cylinder 42 and the current direction of travel of the heads is `up', i.e., towards higher numbered cylinders. For the same set of queued requests given in part (a), what will be the total distance (in cylinders) traveled by the disk heads to service the requests?
    \end{enumerate}

    \solution

    \begin{enumerate}[label=\alph*)]
      \item SSTF
      \begin{tabbing}
        \textbf{Read order:} \= 40, 37, 27, 15, 67, 90 \\
        \textbf{distance:} \> $2 + 3 + 10 + 12 + 52 + 23 = 102$
      \end{tabbing}

      \item SCAN
      \begin{tabbing}
        \textbf{Read order:} \= 90, 67, 40, 37, 27, 15 \\
        \textbf{distance:} \> $48 + 23 + 27 + 3 + 10 + 12 = 123$
      \end{tabbing}
    \end{enumerate}
  \end{homeworkProblem}

  \begin{homeworkProblem}
    Consider a File system that maintains unique index node for each file in the system. Each index node includes 8 direct pointers, a single indirect pointer, and a double indirect pointer. The file system block size is 1024 bytes, and a block pointer occupies 4 bytes.

    \begin{enumerate}[label=\alph*)]
      \item What is the maximum file size that can be supported by the index node?
      \item How many disk operation will be required if a process read data from the Nth block of a file? Assume that the file is already open, the buffer cache is empty, and each disk operation read a single file block. Your answer should be given in terms of N.
      \item How much space (including overhead) does a file that is 1025 bytes long?
      \item How much space (including overhead) does a file that is 65536 (64KB) bytes long?
    \end{enumerate}

    \pagebreak

    \solution

    \begin{enumerate}[label=\alph*)]
      \item $2^{13} + 2^{18} + 2^{26}$
      \item
      \begin{itemize}
        \item If $0 \le N < 8$ One operation is needed
        \item If $8 \le N < 256 + 8$ Two operations are needed
        \item If $256 + 8 \le N < 2^{13} + 2^{18} + 2^{26}$ Three operations are needed
      \end{itemize}
      \item $128 + 1024 = 1152$ bytes
      \item $128 + 65536 = 66688$ bytes
    \end{enumerate}
  \end{homeworkProblem}

  \begin{homeworkProblem}
    Suppose a file system can have three disk allocation strategies, contiguous, linked, and indexed. We have just read the information for a file from its parent directory. For contiguous and linked allocation, this gives the address of the first block, and for indexed allocation this gives the address of the index block. Now we want to read the 10th data block into the memory. How many disk blocks (N) do we have to read for each of the allocation strategies? \textit{For partial credit, explicitly list which block(s) you have to read.} \\

    \solution

    Contiguous allocation : 1 block \\
    Linked allocation : 10 blocks \\
    Indexed allocation : 2 blocks
  \end{homeworkProblem}
\end{document}
<file_sep>/homework_prereq/cpp_programming/problem_4.cpp
#include <iostream>

// Prototype so that the main function can call
// string_duplicator
char *string_duplicator(char *s);

int main(int argc, char const *argv[]) {
        char testString[] = "hello";
        printf("%s\n", string_duplicator(testString));
}

char *string_duplicator(char *s) {
        char *cpy = new char;
        for (int i = 0; i <= strlen(s); i++) {
                cpy[i] = s[i];
        }
        return(cpy);
}
<file_sep>/notes/exam_notes/exam_notes.tex
\documentclass[titlepage]{article}
\usepackage{datetime}
\usepackage[usenames, dvipsnames]{color}
\usepackage{algorithm2e}

\newcommand*{\redbold}[1]{\textbf{{\color{red} #1}}}
\newcommand*{\redit}[1]{\textit{{\color{red} #1}}}
\newcommand*{\bluebold}[1]{\textbf{{\color{blue} #1}}}
\newcommand*{\orangebold}[1]{\textbf{{\color{Orange} #1}}}

\title{Exam Notes}
\author{<NAME>}
\date{\formatdate{23}{02}{2016}}

\begin{document}
  \maketitle

  \centering{\section*{Processes}}

  \centering{\section*{Process \& Thread Synchronization}}

  \paragraph{Background}

  \begin{itemize}
    \item Parallelism can provide a distinct way of conceptualizing problems
    \item Concurrent access to shared data may result in data inconsistency
    \item Maintaining data consistency requires mechanisms to ensure that the orderly exectution of cooperating processes
    \item Suppose that we wanted to provide a solution to the consumer-producer problem that fills \redbold{all} the buffers

    \begin{itemize}
      \item We can do so by having an integer \redit{count} that keeps track of the number of full buffers
      \item Initially the \redbold{count} is set to $0$
      \item It is incremented by the producer after it produces a new buffer
      \item It is decremented by the consumer after it consumers a buffer
    \end{itemize}
  \end{itemize}

  \paragraph{Race Condition}

  Race conditions can occur when two operations on shared variables are not \textbf{atomic}

  \paragraph{Definitions}

  \begin{itemize}
    \item \bluebold{Synchronization} using atomic operations to ensure cooperation between threads
    \item \bluebold{Critical Section} piece of code that only one thread can execute at once. Only one thread at a time will get into this section of code
    \begin{itemize}
      \item \orangebold{Mutual Exclusion} ensuring that only one thread does a particular thing at a time
      \item \orangebold{Progress} selecting a thread to enter cannot postpone indefinitely
      \item \orangebold{Bounded Waiting} before entering the critical section
    \end{itemize}
  \end{itemize}

  {\color{blue} Important idea: all synchronization involves waiting}

  \paragraph{Peterson's Solution}

  \begin{itemize}
    \item A solution for two processes
    \item Assum that the LOAD and STORE instructions are atomic
    \begin{itemize}
      \item \textbf{Atomic} == cannot be interrupted
    \end{itemize}
    \item The two processes share two variables
    \begin{itemize}
      \item int {\color{red} turn}
      \item Boolean {\color{red} flag[2]}
    \end{itemize}
    \item The variable {\color{red} turn} indicates whos turn it is to enter the critical section
    \item the {\color{red} flag} array is used to indicate if a process is ready to enter the critical section
    \begin{itemize}
      \item {\color{red} flag[i] = true} implies that {\color{blue} $P_1$} is ready
    \end{itemize}
  \end{itemize}

  \paragraph{Alogrithm for Process {\color{blue} $P_1$}}

  \begin{center}
    \begin{algorithm}
      \SetAlgoLined
      \While{true}{
        flag[i] = TRUE\;
        turn = j\;
        \While{flag[j] \&\& turn == j}{
          \vdots
          CRITICAL SECTION\;
          flag[i] = FALSE\;
          REMAINDER SECTION\;
        }
      }
      \caption{Peterson's Solution}
    \end{algorithm}
  \end{center}

  \paragraph{Semaphore}

  \begin{itemize}
    \item Synchronization tool that does not require busy waiting
    \begin{itemize}
      \item integer variable
      \item Two standard operations
      \begin{itemize}
        \item {\color{blue} S.wait()} $\Rightarrow$ P()
        \item {\color{blue} S.signal()} $\Rightarrow$ V()
      \end{itemize}
      \item Less complicated
    \end{itemize}
    \item Can only be accessed via two indivisible (atomic) operations
  \end{itemize}

  \paragraph{Semaphore as General Synchronization Tool}

  \begin{itemize}
    \item {\color{red} Counting} semaphore -- integer value can range over unrestricted domain
    \item {\color{red} Binary} semaphore -- integer value that can range only between 0 \& 1; can be simpler to implement
    \begin{itemize}
      \item Also known as {\color{red} mutex locks}
    \end{itemize}
    \item Can implement a counting semaphore {\color{blue} S} as a binary semaphore
    \item Provides mutual exclusion
  \end{itemize}

\end{document}
<file_sep>/notes/jan_27/2016_01_27_lecture_notes.tex
\documentclass[titlepage]{article}
\usepackage{fancyhdr}
\usepackage{color}
\usepackage{datetime}

\fancyhf{}

\topmargin=-0.45in
\evensidemargin=0in
\oddsidemargin=0in
\textwidth=6.5in
\textheight=9.0in
\headsep=0.25in

\newcommand{\noteTitle}{\formatdate{27}{1}{2016} --- Notes}
\newcommand{\professor}{<NAME>}
\newcommand{\class}{CSE 450 Operating Systems}
\newcommand{\classTime}{Monday \& Wednesday 3:30 --- 5:17 pm}
\newcommand{\notesAuthor}{<NAME>}

\pagestyle{fancy}
\lhead{\notesAuthor}
\chead{\class}
\rhead{\noteTitle}
\lfoot{}
\cfoot{\thepage}
\rfoot{}
\renewcommand{\headrulewidth}{0.4pt}
\renewcommand{\footrulewidth}{0.4pt}

\title{
  \textmd{\LARGE{\textbf{\noteTitle}}}\\
  \textmd{\Large{\textit{\class}}}\\
  \textmd{\Large{\textit{Professor\ \professor}}}\\
  \textmd{\normalsize{\classTime}}\\
  \vspace{3.5in}
  \textmd{\LARGE{\textbf{\notesAuthor}}}\\
  \date{}
}

\begin{document}
  \maketitle
  \section*{Process State}
  \begin{itemize}
    \item As a process executes, it changes \textit{state}

    \begin{itemize}
      \item \textbf{new} The process is being created
      \item \textbf{ready} The process is waiting to run
      \item \textbf{running} Instructions are being executed
      \item \textbf{waiting} Process waiting for some event to occur
      \item \textbf{terminatied} The process has finished execution
    \end{itemize}
  \end{itemize}

  \begin{itemize}
    \item {\color{blue} \textbf{Job queue}} --- set of all processes in the system
    \item {\color{blue} \textbf{Ready queue}} --- set of all processes residing in main memory, ready and waiting to be exectued
    \item {\color{blue} \textbf{Device queues}} --- set of processes waiting for an I/O device
    \item {\color{blue} \textbf{Scheduling}} --- Processes (PCBs) migrate among the various queues
    \item {\color{blue} \textbf{Long-term scheduler}} (or job scheduler) --- selects processes should be brought into the ready queue
    \begin{itemize}
      \item Long-term scheduler is invoced very infrequently
      \item The long-term scheduler controls the \textit{degree of multiprogramming}
    \end{itemize}
    \item {\color{blue} \textbf{Short-term scheduler}} (or CPU scheduler) --- selects which processes should be next and allocates the CPU
    \begin{itemize}
      \item Short-term scheduler is invoced very frequently (milliseconds) $\Rightarrow$ (must be fast)
    \end{itemize}
    \item Praent processes create children processes, which, in turn create other processes, forming a tree of processes
    \item Must construct new PCB
    \item Resource sharing strategies
    \begin{itemize}
      \item Parant and children share all resources (I/O states, address space information)
      \item Children share a subset of parent's resources
      \item Parent and child share no resources (UNIX exec())
    \end{itemize}
    \item Execution
    \begin{itemize}
      \item Parant and child execute concurrently
      \item Parent waits until the children terminate
    \end{itemize}
  \end{itemize}
\end{document}

languages: TeX C++

repo_language: TeX


text:
<repo_name>tibernardinelli/socket-chat-client<file_sep>/src/br/com/usp/redes/ep/Main.java
package br.com.usp.redes.ep;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.net.Socket;
import java.net.UnknownHostException;
import java.util.Scanner;

public class Main {

	private static Scanner scanner;
	private static Socket socket;
	private static BufferedReader bufferedReader;
	private static PrintWriter printWriter;

	public static void main(String[] args) throws UnknownHostException, IOException {
		scanner = new Scanner(System.in);

		socket = new Socket("localhost", 2020);
		printWriter = new PrintWriter(socket.getOutputStream(), true);
		bufferedReader = new BufferedReader(new InputStreamReader(socket.getInputStream()));

		System.out.println("Nome do usuário: ");
		String usuario = scanner.nextLine();
		printWriter.println(usuario);
		System.out.println(receiveMessage());

		new Thread(() -> {
			printWriter.println("keepAlive");
		});

	}

	private static String receiveMessage() throws IOException{
		String s = "";
		String x = null;
		while (!(x = bufferedReader.readLine()).equals("$$D")){
			s += x;
		}
		return s;
	}

}

branch_name: refs/heads/master

repo_language: Java

repo_name: tibernardinelli/socket-chat-client