Операционные системы
1. Проблема исключения одновременного доступа процессов (потоков) к ресурсу.
Понятия детерминированного набора последовательностей команд, состояния гонок, критического участка, взаимного исключения. Пример недетерминированного набора. Достаточное условие детерминированности Бернсайда. «Наивные» решения проблемы: запрет прерываний, использование флага.
Синхронизирующие объекты ОС: мьютексы, семафоры, операции с блокирующими переменными. Решение задачи производитель-потребитель с помощью семафоров. Условия ограниченного ожидания и прогресса. Примеры алгоритмов, реализующих взаимное исключение: строгого чередования, Петерсона, булочной.
2. Тупиковые ситуации, их обнаружение, устранение и предотвращение.
Понятие тупика. Примеры. Алгоритм обнаружения тупика. Восстановление после тупиков. Диаграммы захвата ресурсов, понятие безопасного состояния. Алгоритм банкира. Необходимые и достаточные условия возникновения тупика и их атака: организация очередей запросов, принцип двухфазной локализации, нумерация ресурсов.
3. Планирование процессов (потоков).
Понятие и критерии планирования. Приоритеты, квантование и вытесняющее планирование. Динамическое определение приоритета и длины кванта. Многоуровневые очереди. Планирование потоков на уровне ядра и на уровне приложения. Простейшие алгоритмы планирования
4. Организация памяти.
Понятия физической, внешней и логической памяти. Способы связывания логического адреса с физическим. Сегментная, страничная, сегментно-страничная и странично-сегментная модели. Понятия внутренней и внешней фрагментации. Алгоритм связывания при использовании страничной модели. Выбор размера страницы.
5. Виртуальная память.
Принцип локальности. Средства организации виртуальной памяти: оверлеи, свопинг, подкачка. Отказ страницы и его обработка операционной системой. Алгоритмы замещения страниц. Использование бита модификации для оптимизации процесса подкачки. Буфер TLB. Трешинг и способы борьбы с ним. Поддержка невыгружаемой памяти.
Сети и системы телекоммуникаций. Стандарты и протоколы интернета
1. Принципы и примеры числовой адресации.
Основные характеристики системы адресации: постоянная/переменная длина, плоская/иерархическая адресация, классы адресов. Адресация внутри хоста: номера протоколов и портов. Примеры. Адресация в сетях на основе IPv4: классы IPv4-адресов, специальные адреса, номера протоколов, порты протоколов UDP и TCP. Трансляция сетевого адреса (NAT).
2. Символьные имена и службы имен.
Причины использования символьных имен. Проблема определения числового адреса по символьному имени. Службы имен. Файл hosts. DNS: структура пространства имен, зоны и обслуживающие их серверы, делегирование, типы записей ресурсов DNS, итеративные и рекурсивные запросы, обратный поиск и зона in‑addr.arpa.
3. Предотвращение коллизий в сетях с множественным доступом.
Распределение канала в сетях с множественным доступом. Статический и динамический способы распределения канала, мультиплексирование на основе разделения времени и частотного уплотнения. Примеры алгоритмов распределения канала с конкуренцией и без. Алгоритмы CSMA/CD и MACAW. Оценки эффективности использования канала.
4. Маршрутизация и коммутация.
Методы маршрутизации: заливка, от источника, на основе таблиц. Связь адресов канального и сетевого уровней, протокол ARP. Статическое и динамическое формирование таблиц. Статическая маршрутизация на основе таблиц в сетях IPv4: выделение групп адресов с помощью масок, структура таблиц, технология CIDR. Маршрутизация и коммутация в сетях на основе виртуальных каналов.
5. Динамическая маршрутизация.
Алгоритмы динамического формирования таблиц маршрутизации: дистанционно-векторный и состояния связей. Иерархическая маршрутизация. Динамическая маршрутизация в Интернете: протоколы RIP, OSPF и BGP.
6. Управление потоком.
Понятие потока данных. Алгоритмы восстановления последовательности модулей: алгоритм с положительным подтверждением и повторной передачей, алгоритмы скользящего окна с возвратом на n и с выборочным повтором. Восстановление после сбоя получателя и отправителя. Борьба с дубликатами и потерями пакетов. Установка и разрыв соединения. Алгоритм тройного рукопожатия. Симметричное и асимметричное разъединение. Проблема двух армий. Борьба с полуоткрытыми соединениями.
7. Управление потоком в протоколе TCP.
Характеристики TCP-соединения. Основные поля заголовка TCP-сегмента. Установка и разрыв TCP-соединения. Определение максимального размера принимаемого сегмента и размера окна получателя. Зондирование пустым окном. Алгоритм Джекобсона определения времени ожидания подтверждения TCP-сегмента. Дополнение Карна.
8. Обеспечение требуемого качества обслуживания.
Проблема обеспечения качества обслуживания в сетях без резервирования ресурсов. Буферизация, дифференцированное обслуживание. Типы обслуживания в протоколе IP. Алгоритмы борьбы с перегрузкой: биты предупреждения, сдерживающие пакеты, сдерживающие пакеты для ретрансляционных участков, сброс нагрузки. Предотвращение перегрузки. Алгоритм случайного раннего обнаружения. Борьба с перегрузкой в TCP: алгоритм затяжного пуска, алгоритмы Кларка и Нагля.