Commits

Weisi Dai committed 0c08629

added os_hw4

  • Participants
  • Parent commits ea9b249

Comments (0)

Files changed (1)

+% multiple1902 <multiple1902@gmail.com>
+% public on https://bitbucket.org/multiple1902/homework
+% licensed under cc by-sa 3.0
+% NOTE: needs pdfgantt package
+\documentclass[11pt]{article}
+\def\course{操作系统原理}
+\def\homeworkid{4}
+\usepackage{amsthm,amssymb,fullpage}
+\usepackage{enumerate}
+\usepackage[slantfont,boldfont,CJKnumber,CJKtextspaces,CJKmathspaces]{xeCJK}
+\usepackage{tabularx}
+\usepackage{booktabs}
+\usepackage{ulem}
+\usepackage{pgfgantt}
+\usepackage[
+    %colorlinks, %linkcolor=blue,anchorcolor=blue,citecolor=green,
+    pdfcreator={TeX}, pdftitle={\course 作业\homeworkid},
+    pdfauthor={multiple1902@gmail.com}
+    ]{hyperref}
+\def\UrlBreaks{\do-\do_}
+\setCJKmainfont{細明體}
+\setCJKsansfont{微軟正黑體}
+\newcommand{\problem}[1]{
+    \noindent \hskip 0.05\linewidth \fbox{\parbox{0.9\linewidth}{#1}} \\
+}
+
+\begin{document}
+
+\noindent\begin{tabularx}{\linewidth}{|X|}
+\hline \vskip -2mm
+{\sf \course} \hfill \today \\
+{\centering \sf \large
+Homework \homeworkid \\ }
+计算机92班 \hfill 戴唯思 09055029 \\ \hline
+\end{tabularx}
+
+\section*{习题一}
+
+\begin{enumerate}
+    \item 8:00, JOB1到达, 开始运行 \\
+        8:20, JOB2到达, 等待运行 \\
+        8:25, JOB3到达, 等待运行 \\
+        8:30, JOB4到达, 等待运行 \\
+        8:35, JOB5到达, 等待运行 \\
+        8:40, JOB6到达, 等待运行 \\
+        9:00, JOB1运行结束. 因为JOB5作业时间最短, 开始运行 \\
+        9:05, JOB5运行结束, JOB6运行 \\
+        9:15, JOB6运行结束, JOB3运行 \\
+        9:35, JOB3运行结束, JOB4运行 \\
+        10:00, JOB4运行结束, JOB2运行 \\
+        10:35, JOB2运行结束.
+
+    \item 如表所示
+        \begin{center}
+            \begin{tabular}[!h]{ccccc}\toprule
+                作业 & 提交时间 & 开始时刻 & 完成时刻 & 周转时间(min) \\ \midrule
+                JOB1 & 8:00 & 8:00 & 9:00 & 60 \\
+                JOB2 & 8:20 & 10:00 & 10:35 & 135 \\
+                JOB3 & 8:25 & 9:15 & 9:35 & 70 \\
+                JOB4 & 8:30 & 9:35 & 10:00 & 90 \\
+                JOB5 & 8:35 & 9:00 & 9:05 & 30 \\
+                JOB6 & 8:40 & 9:05 & 9:15 & 35 \\ \bottomrule
+            \end{tabular}
+        \end{center}
+
+        平均周转时间: $\frac{60+135+70+90+30+35}{6}=70$min
+\end{enumerate}
+
+\section*{习题三}
+\begin{enumerate}
+    \item 如表所示
+        \begin{center}
+            \begin{tabular}[h!]{cc}\toprule
+                时间(min) & 操作 \\ \midrule
+                0 & E运行 \\
+                10 & E结束, D运行 \\
+                18 & D结束, C运行 \\
+                24 & C结束, B运行 \\
+                28 & B结束, A运行 \\
+                30 & A结束 \\ \bottomrule
+            \end{tabular}
+        \end{center}
+
+        平均周转时间: $\frac{30+28+24+18+10}{5}=22$min
+    \item 如表所示
+        \begin{center}
+            \begin{tabular}[h!]{cc}\toprule
+                时间(min) & 操作 \\ \midrule
+                0 & A运行 \\
+                2 & A结束, B运行 \\
+                4 & C运行 \\
+                6 & D运行 \\
+                8 & E运行 \\
+                10 & B运行 \\
+                12 & B结束, C运行 \\
+                14 & D运行 \\
+                16 & E运行 \\
+                18 & C运行 \\
+                20 & C结束, D运行 \\
+                22 & E运行 \\
+                24 & D运行 \\
+                26 & D结束, E运行 \\
+                30 & E结束 \\ \bottomrule
+            \end{tabular}
+        \end{center}
+
+        平均周转时间: $\frac{2+12+20+26+30}{5}=18$min
+    \item 如表所示
+        \begin{center}
+            \begin{tabular}[h!]{cc}\toprule
+                时间(min) & 操作 \\ \midrule
+                0 & C运行 \\
+                6 & C结束, D运行 \\
+                14 & D结束, B运行 \\
+                18 & B结束, E运行 \\
+                28 & E结束, A运行 \\
+                30 & A结束 \\ \bottomrule
+            \end{tabular}
+        \end{center}
+
+        平均周转时间: $\frac{30+18+6+14+28}{5}=19.2$min
+    \item 如表所示
+        \begin{center}
+            \begin{tabular}[h!]{cc}\toprule
+                时间(min) & 操作 \\ \midrule
+                0 & A运行 \\
+                2 & A结束, B运行 \\
+                6 & B结束, C运行 \\
+                12 & C结束, D运行 \\
+                20 & D结束, E运行 \\
+                30 & E结束 \\ \bottomrule
+            \end{tabular}
+        \end{center}
+
+        平均周转时间: $\frac{2+6+12+20+30}{5}=18$min
+\end{enumerate}
+
+\section*{5.1}
+
+    \problem{Why is it important for the scheduler to distinguish I/O-bound programs from CPU-bound programs?}
+
+    \textsf{I/O-bound programs} consume a relatively small part of computing resources but a large amount of I/O operations, by which way they occupy much time as well. CPU resources are designed to perform computing, so principles for CPU scheduling is to maximize CPU usage. I/O-bound programs usually do not use up all their CPU quantum, thus make it possible to share CPU quantums with \textsf{CPU-bound programs} to improve the overall performance.
+
+\section*{5.4}
+
+    \problem{Consider the following set of processes, with the length of CPU burst given in milliseconds:
+
+    \begin{center}
+        \begin{tabular}[h!]{ccc}
+            \uline{Process} & \uline{Burst Time} & \uline{Priority} \\
+            $P_1$ & 10 & 3 \\
+            $P_2$ & 1 & 1 \\
+            $P_3$ & 2 & 3 \\
+            $P_4$ & 1 & 4 \\
+            $P_5$ & 5 & 2 
+        \end{tabular}
+    \end{center}
+
+    The processes are assumed to have arrived in the order $P_1$, $P_2$, $P_3$, $P_4$, $P_5$ all at time 0.
+
+    \begin{enumerate}[a.]
+        \item Draw four Gantt charts that illustrate the execution of these processes using the following scheduling algorithms: FCFS, SJF, nonpreemptive priority(a smaller priority number implies a higher priority), and RR(quantum$=1$).
+        \item What is the turnaround time of each process for each of the scheduling algorithms in part a?
+        \item What is the waiting time of each process for each of the scheduling algorithms in part a?
+        \item Which of the algorithms in part a results in the minimum average waiting time (over all processes)?
+    \end{enumerate}
+
+    }
+
+\begin{enumerate}[a.]
+    \item 
+    \begin{center}
+        \begin{tikzpicture}[x=.5cm, y=1cm]
+        \begin{ganttchart}[vgrid]{19}
+            \gantttitle{FCFS}{19} \\
+            \gantttitlelist{1,...,19}{1} \\
+            \ganttbar{$P_1$}{1}{10} \\
+            \ganttbar{$P_2$}{11}{11} \\
+            \ganttbar{$P_3$}{12}{13} \\
+            \ganttbar{$P_4$}{14}{14} \\
+            \ganttbar{$P_5$}{15}{19}
+        \end{ganttchart}
+        \end{tikzpicture}
+    \end{center}
+
+    \begin{center}
+        \begin{tikzpicture}[x=.5cm, y=1cm]
+        \begin{ganttchart}[vgrid]{19}
+            \gantttitle{SJF}{19} \\
+            \gantttitlelist{1,...,19}{1} \\
+            \ganttbar{$P_2$}{1}{1} \\
+            \ganttbar{$P_4$}{2}{2} \\
+            \ganttbar{$P_3$}{3}{4} \\
+            \ganttbar{$P_5$}{5}{9} \\
+            \ganttbar{$P_1$}{10}{19}
+        \end{ganttchart}
+        \end{tikzpicture}
+    \end{center} 
+
+    \begin{center}
+        \begin{tikzpicture}[x=.5cm, y=1cm]
+        \begin{ganttchart}[vgrid]{19}
+            \gantttitle{Priority}{19} \\
+            \gantttitlelist{1,...,19}{1} \\
+            \ganttbar{$P_2$}{1}{1} \\
+            \ganttbar{$P_5$}{2}{6} \\
+            \ganttbar{$P_1$}{7}{16} \\
+            \ganttbar{$P_3$}{17}{18} \\
+            \ganttbar{$P_4$}{19}{19}
+        \end{ganttchart}
+        \end{tikzpicture}
+    \end{center}
+    \begin{center}
+        \begin{tikzpicture}[x=.5cm, y=1cm]
+        \begin{ganttchart}[vgrid]{19}
+            \gantttitle{RR}{19} \\
+            \gantttitlelist{1,...,19}{1} \\
+            \ganttbar{$P_1$}{1}{1} \\
+            \ganttbar{$P_2$}{2}{2} \\
+            \ganttbar{$P_3$}{3}{3} \\
+            \ganttbar{$P_4$}{4}{4} \\
+            \ganttbar{$P_5$}{5}{5} \\
+            \ganttbar{$P_1$}{6}{6} \\
+            \ganttbar{$P_3$}{7}{7} \\
+            \ganttbar{$P_5$}{8}{8} \\
+            \ganttbar{$P_1$}{9}{9} \\
+            \ganttbar{$P_5$}{10}{10} \\
+            \ganttbar{$P_1$}{11}{11} \\
+            \ganttbar{$P_5$}{12}{12} \\
+            \ganttbar{$P_1$}{13}{13} \\
+            \ganttbar{$P_5$}{14}{14} \\
+            \ganttbar{$P_1$}{15}{19}
+        \end{ganttchart}
+        \end{tikzpicture}
+    \end{center}
+\item See Table \ref{tab:turnaroundtime}.
+
+    \begin{table}[h!]
+        \centering
+        \caption{Turnaround time}
+        \label{tab:turnaroundtime}
+        \begin{tabular}{ccccc} \toprule
+            Turnaround time & FCFS & SJF & Priority & RR \\ \midrule
+            $P_1$ & 10 & 19 & 16 & 19 \\
+            $P_2$ & 11 & 1 & 1 & 2 \\
+            $P_3$ & 13 & 4 & 18 & 7 \\
+            $P_4$ & 14 & 2 & 19 & 4 \\
+            $P_5$ & 19 & 9 & 6 & 14 \\ \bottomrule
+        \end{tabular}
+    \end{table}
+\item See Table \ref{tab:waitingtime}.
+
+    \begin{table}[h!]
+        \centering
+        \caption{Waiting time}
+        \label{tab:waitingtime}
+        \begin{tabular}{ccccc} \toprule
+            Waiting time & FCFS & SJF & Priority & RR \\ \midrule
+            $P_1$ & 0 & 9 & 6 & 9  \\
+            $P_2$ & 10 & 0 & 0 & 1 \\
+            $P_3$ & 11 & 2 & 16 & 5 \\
+            $P_4$ & 13 & 1 & 18 & 3 \\
+            $P_5$ & 14 & 4 & 1 & 9 \\ \bottomrule
+        \end{tabular}
+    \end{table}
+\item Shortest job first.
+\end{enumerate}
+
+\section*{5.5}
+
+    \problem{Which of the following scheduling algorithms could result in starvation?
+    
+    \begin{enumerate}[a.]
+        \item First-come, first served
+        \item Shortest job first
+        \item Round robin
+        \item Priority
+    \end{enumerate}
+    }
+
+    b. Shortest Job First and d. Priority.
+
+
+\end{document}