\documentclass[oneside,a4paper]{article}
%\usepackage[margin=2cm]{geometry}
\usepackage{fancyhdr}
\usepackage{amsmath,amsthm,amssymb}
\usepackage{graphicx}
\usepackage{hyperref}

\usepackage{mathtext}
\usepackage[T1,T2A]{fontenc}
\usepackage[utf8]{inputenc}
\usepackage[english,bulgarian]{babel}
\usepackage{setspace}

%\usepackage{array}

%\usepackage[chapter]{algorithm}
%\usepackage[noend]{algpseudocode}
%\usepackage{float}
%\floatname{algorithm}{Алгоритъм}

%\usepackage{myalg}

%\setlength{\parindent}{10pt} 
%\setlength{\parskip}{1ex}

\title{Операционни системи, лекции}
\author{Георги Георгиев (Скелета)}

\begin{document}


\maketitle

Този документ не е учебник.
Това са бележки на автора, част от подготовката за лекции.
Целта е да ми помагат, когато се скъса тънката нишка на мисълта.

\section{Въведение}

\paragraph{Дефиниция} Няма точна дефиниция на ОС.

Неформални дефиниции:

ОС осигурява удобства за агентите, ползващи изчислителната система (хора, други ИС, вътрешни компоненти на ИС).

ОС осигурява абстракции и изолация.

[Таненбаум] providing application programmers (and application programs, naturally) a clean
abstract set of resources instead of the messy hardware ones and managing these
hardware resources.

[http://www.toves.org/books/os/]
ОС осигурява удобни абстракции за сложните компютърни ресурси, хардуерна съвместимост, сигурност.

[http://www.linfo.org/operating\_system.html] An operating system is a collection of programs that manages all the other programs (i.e, application programs) in a computer as well as the allocation and use of hardware resources such as the CPU (central processing unit), memory and the hard disk drive (HDD). 

\paragraph{Основни понятия} (абстракции):

периферни устройства, драйвери (хардуерна съвместимост)

файлове, имена (разделяне на пространството, идентификация на ресурсите)

процес, комуникационен канал (обработка и обмен на информацията, многозадачност, времеделене)

права за достъп, изолация (защита на данните и информационните процеси)

\paragraph{Структура, интерфейси:} \mbox{}

Потребителски интерфейс: GUI, shell

Програмен интерфейс: API

ОС в тесен смисъл: kernel -- осигурява основните абстракции и съвместната им работа

ОС в широк смисъл: kernel + обвивки -- осигурява стандартни инструменти за работа

\paragraph{Литература:} \mbox{}

The Mythical Man-Month 

Essays on Software Engineering 

Frederick P. Brooks, Jr. 

University of North Carolina, Chapel Hill 

\vspace{10pt}
The Unix-HATERS Handbook

Published by IDG Books Worldwide, Inc.



\section{Увод в Unix}

\paragraph{Стил Unix} 
Основни принципи за програмите и интерфейса:

Doug McIlroy (изобретил pipeline през 1973, реализиран от Ken Thompson):

Write programs that do one thing and do it well. 

Write programs to work together. 

Write programs to handle text streams, because that is a universal interface.

\vspace{5pt}

Ортогоналност на инструментите (и на системните извиквания). 

Предпочитане на текстов формат --
вход-изхода е чист от съобщения и няма интерактивна работа (диалог с потребителя).
Съобщенията са в stderr, а ако правим диалог, добавяме опции или пишем програма-обвивка.

Ранна философия на Unix – малки и прости инструменти, които се комбинират.

Използване на абстракциите на ОС – процеси, комуникационни канали, файлове.

Изграждане на технологични решения и програми за фиксирането им.

Средство за този инженерен подход – Unix shell. 


\paragraph{Сравнение GUI -- shell} \mbox{} %\\

GUI e потребителски – приложения, документи, скриване на абстракциите.

shell е програмистки – достъп до абстракциите и ресурсите, нужда от квалификация.
Улеснява комбинирането на инструменти, конструиране, тестване и поддръжка на сложни решения.


\subsection{Въведение в shell} (Linux dash/bash).\mbox{}

Разглеждане на ресурсите (coreutils):

(1) файлова система (Unix name space), структура, монтиране, mount, df, du, ls, mkdir, mv, cp, rm

(2) процеси, наследяване, ps, top

(3) документация -- man

\vspace{5pt}

Прости инструменти: cat echo cut grep find sort wc tar

Пример: find /etc -name *.sh|wc -l

Учебник: /usr/share/doc/bash/bash*.pdf

\paragraph{Литература:} \mbox{}

https://en.wikipedia.org/wiki/Unix

https://en.wikipedia.org/wiki/Unix\_philosophy

https://en.wikipedia.org/wiki/Pipeline\_(Unix)

%http://www.bradleymonk.com/File:The\_truth\_about\_Unix\_Don\_Norman.pdf
критика на интерфейса на Unix: 

Norman, Don (1981). "The truth about Unix: The user interface is horrid"

\subsection{Процеси и наследяване в Unix} %\mbox{}\\

Процесите в Unix са представени чрез дърво с ребра родител--наследник.

Процесът работи в обкръжение, стартираната програма наследява от родителя няколко неща:\\
(1) обкръжение (вижда се с команда env) -- списък от низове от вида name=value.\\
(2) аргументи -- името на извиканата програма, аргументи и опции.\\
(3) отворени файлови дескриптори (комуникационните канали на родителя). 

Системни извиквания за пораждане на процеси:\\
fork() -- създава точно копие на процеса.\\
execve(filename, argv[], envp[]) -- заменя процеса с нов.

Файлов дескриптор -- указател към единия край на комуникационен канал (stream, поток от байтове).
Основни видове канали в Unix:\\
pipe -- еднопосочна тръба, свързваща процеси.\\
file\_stream -- тръба между процес и обикновен файл или периферно устройство.\\
connection -- двупосочна тръба, свързваща процеси.\\
socket -- крайна точка за изграждане на конекции, генератор на конекции.

Не е много ясно ако няколко процеса ползват общ край на канал, кои атрибути на канала са общи и кои локални (man open, dup).

\subsection{Управление на процесите в bash} %\mbox{}\\

Няколко специални символа в bash управляват изпълнението на процеси --
>, <, \verb|>>|, |, \& и ;.

\paragraph{Изпълнение на команда:}  \mbox{}\\

Примерна програма на C, имитираща изпълнение на команда:

\begin{verbatim}
int pid;
pid=fork();
if (pid>0) waitpid(pid,...);
if (pid==0) execvp(args[0], args);
if (pid<0) perror("fork");
\end{verbatim}

\paragraph{Пренасочване на вход/изхода} \mbox{}\\

\verb|cmd > filename| пренасочва изхода.

\verb|cmd < filename| пренасочва входа.

\verb|cmd >> filename| пренасочва изхода, като дописва във файла (\verb|O_APPEND|).

\vspace{5pt}

Пример на C за пренасочване на изхода към файл "demo.txt":

\begin{verbatim}
int fd, pid;
pid=fork();
if (pid>0) waitpid(pid,...);
if (pid==0) { 
 fd=open("demo.txt",O_WRONLY|O_CREAT,...);
 close(STDOUT_FILENO);
 dup(fd);
 close(fd);
 execvp(args[0], args);
}
if (pid<0) perror("fork");
\end{verbatim}

\paragraph{Конвейри:} \mbox{}\\

\verb|cmd1| | \verb|cmd2| | \verb|cmd3| ... изпълнява паралелно няколко команди, 
като подава изхода на всяка като вход на следващата.

\vspace{5pt}

Пример на C за изпълнение на конвейр "\verb|cmd1| | \verb|cmd2|":

\begin{verbatim}
int fd[2], pid, pid1;
pid=fork();
if (pid>0) waitpid(pid,...);
if (pid==0) {   /* Child shell */
 pipe(fd);      /* Create pipe */
 pid1=fork(); 
 if (pid1==0) { /* process for cmd1 */
  close(fd[0]);  /* Close unused read end */
  dup2(fd[1],STDOUT_FILENO);
  close(fd[1]);  /* Close duplicated write end */
  execvp("cmd1", args_cmd1);
 }
 if (pid1>0) { /* process for cmd2 */
  close(fd[1]);  /* Close unused write end */
  dup2(fd[0],STDIN_FILENO);
  close(fd[0]);  /* Close duplicated read end */
  execvp("cmd2", args_cmd2);
 }
}
if (pid<0) perror("fork");
\end{verbatim}

\paragraph{Изпълнение на команда във фонов режим (background):} \mbox{}\\

\verb|cmd1 &| стартира команда за паралелно изпълнение с bash. 

\paragraph{Литература:} \mbox{}

https://brennan.io/2015/01/16/write-a-shell-in-c/

http://www.teach.cs.toronto.edu/~ajr/209/notes/procfiles/pipe-example.c
 
\subsection{bash като език}

bash е интерпретатор, чете от 3 възможни източника -- 
конзола, файл или низ, ако се вика с 'bash -c'.

bash прави синтактически анализ на интерпретирания текст.
Разделя го на команди, всяка команда е поредица от думи.
За всяка дума се прави оценка (заместване), след това се правят пренасочванията и командата се изпълнява.

\paragraph{Подтискане на оценяването (quoting)} \mbox{}

Символът $\backslash$ подтиска оценяването на следващия го символ.
Ако е в края на реда, изтрива от входния поток символа за нов ред, все едно залепя текущия и следващия ред.

Простите кавички 'текст' подтискат напълно оценяването в оградения текст.

Двойните кавички "текст" $\;$ подтискат частично оценяването в оградения текст.
Не се подтиска оценяването на '\$' и '`'.

\emph{Примери:}
\begin{verbatim}
$ echo 123\&45
123&45
$ x=123
$ echo 'x=$x'
x=$x
$ echo "x=$x"
x=123
$ echo "`whoami`"
skelet
\end{verbatim}

\paragraph{Оценяване на думите, заместване (shell expansions)} \mbox{}

При оценяването една дума може да се замести с няколко нови.
Оценяването се предизвиква от специален символ или синтактична конструкция.

Има няколко вида оценяване, те се извършват в определен ред, 
като резултатът от всяко оценяване се подлага на следващото:

\begin{itemize}
   \item Заместване на списък в големи скоби:\\
      \verb|$ echo L3{a,b,c}456|\\
      \verb|L3a456 L3b456 L3c456|
   \item Заместване на \verb|~|  с домашната директория.
   \item Изчисляване на стойност. Започва с \$ и има няколко форми:
   \begin{itemize}
       \item \$name или \$\{name\} връща стойността на променливата name.
       
       Втората форма е удобна когато променливата е потопена в текст.
       Стойността може да бъде модифицирана. \emph{Пример:} 
\begin{verbatim}       
$ x=my_video.webm
$ echo $x
my_video.webm
$ echo ${x%.webm}.ogg
my_video.ogg
\end{verbatim}
       \item \$(command) или `command` изпълнява команда и връща текста, който тя поражда.
\emph{Пример:} 
\begin{verbatim}              
$ echo $(date +%d.%m.%Y)
19.03.2018      
\end{verbatim}
       \item \$((expr)) изчислява аритметичен израз.
\emph{Пример:} 
\begin{verbatim}              
$ echo $((2+3*5))
17   
\end{verbatim}
    \end{itemize}  
    \item Разширяване на имената на файлове.
    Ако дума съдържа *, ? или [list], тя се интерпретира като образец
    и се замества със списък от файлови имена, съответни на образеца.
    
    Образецът е частен случай на регулярен израз в смисъл на Клини:\\
    (1) обикновен символ съответства на себе си.\\
    (2) ? съответства на кой да е символ.\\
    (3) * съответства на кой да е низ.\\
    (4) [x-y] съответства на символите от x до y.\\
    (5) [$c_1\ldots c_k$] съответства на изброените символи.\\
    (6) [!list] съответства на всички символи освен тези, описани в list.
\emph{Пример:} 
\begin{verbatim}              
$ echo *
counting.sh demo1.sh demo2.sh problem1.txt vi_demo.txt
$ echo *.sh
counting.sh demo1.sh demo2.sh
$ echo demo?.sh
demo1.sh demo2.sh
$ echo demo[2-5].sh
demo2.sh
$ echo demo[!2-5].sh
demo1.sh
\end{verbatim}
\end{itemize} 
 
\paragraph{Специални променливи:} \mbox{}

\$0 -- име на изпълняваната програма

\$1 ... \$n -- аргументи на изпълняваната програма

\$\# -- брой на аргументите

\$* \$@ -- списък от всички аргументи

\$? -- код на грешка от последната изпълнена програма

\$\$ -- PID на изпълняваната програма



\section{Синхронизация}

Когато няколко изчислителни ресурса работят паралелно, необходимо е да синхронизират своята работа.

Терминът \emph{синхронизация} следва да се разбира като съгласуване на общата работа, 
изчакване във времето -- процес или хардуер, който използва резултат от друг процес или хардуер, трябва да изчака завършването на предходните задачи, за да ползва резултата.

\paragraph{Прекъсвания} \mbox{}

Паралелизъм на хардуера, сигнализация между устройствата.

Превключване на процесите от входно-изходни събития.

Времеделене -- timer interrupt.

\paragraph{Race condition, spinlock:} \mbox{}

състезание за ресурси (\emph{race condition})

пример, критична секция

анализ на проблема – инварианта на структура данни

\vspace{5pt}

Взаимно изключване (\emph{mutual exclusion, mutex}) -- механизъм, 
забраняващ два процеса едновременно да изпълняват код, 
който променя данни в споделената структура (ресурс). 
Прилагането му е достатъчно условие да няма race condition, но не е необходимо (може да пипаме едновременно различни инварианти в случай, че промените по тях са независими).

Решения за защита на критичната секция (ниско ниво):\\
(1) алгоритми на Декер и Петерсон\\
(2) еднопроцесорна система -- временна забрана на прекъсванията\\
(3) хардуерни механизми -- test and set, atomic swap.\\
(4) многопроцесорни системи -- memory barrier, подреждат във времето конвейри на различни процесори, за да се извърши атомарното заключване.

Всички тези механизми осигуряват взаимно изключване, като чакат в цикъл ресурса да се освободи
(Tanenbaum: Mutual Exclusion with Busy Waiting).
За тях ползваме термина \emph{spinlock}. 

Предимства на spinlock: \\
(1) няма смяна на контекста, ако критичната секция е кратък код това е оптималното решение.\\
(2) това е първичен инструмент, всеки друг разчита на него за да осигури атомарни операции.

Недостатъци на spinlock: \\
(1) не пести CPU-ресурс, когато няколко процеса чакат lock-а, всички те ползват CPU.\\
(2) не може пряко да реализира абстракция на хардуерното прекъсване и естествения паралелизъм на хардуера.\\
(3) spinlock следва да е непрекъсваем, иначе се получават големи забавяния.

Когато spinlock е неудобен, се ползват инструменти за синхронизация от високо ниво.

\paragraph{Семафор} \mbox{}

\paragraph{Concurrent programming:} \mbox{}



\paragraph{Литература:} \mbox{}

%\vspace{5pt}

Tanenbaum, Boss. "Modern Operating Systems". 4-th edition:\\
1.3.4 I/O Devices\\
2.3.1 Race Conditions\\
2.3.2 Critical Regions\\
2.3.3 Mutual Exclusion with Busy Waiting



%\vspace{10pt}
%The Unix-HATERS Handbook

%Published by IDG Books Worldwide, Inc.

\newpage
\subsection*{Литература:} \mbox{}\\

Tanenbaum, Boss. "Modern Operating Systems". 4-th edition:\\

POSIX, последна версия: http://pubs.opengroup.org/onlinepubs/9699919799/

\end{document}
