Архитектура компьютерных систем

Программа курса

1. Управление памятью.

     1.1 Аллокация памяти: простые алгоритмы аллокации, Buddy аллокатор, SLAB аллокатор.

     1.2 Процесс: физическое и виртуальное адресные пространства, защита памяти, сегментация, paging и page fault.

2. Потоки исполнения

     2.1 Поток исполнения и диспетчеризация потоков исполнения.

     2.2 Планирование потоков исполнения: критерии планирования и простые алгоритмы планирования (SJF, RR), MLFQ, Ticket Scheduling, Linux CFS

3. Синхронизация потоков исполнения

     3.1 Конкурентное исполнение и состояние гонки

     3.2 Алгоритмы Петтерсона и Лэмпорта для взаимного исключения

     3.3 Барьеры компилятора, когерентность процессорных кешей, out-of-order исполнение и барьеры памяти.

     3.4 Атомарные инструкции. Взаимное исклчючение с использованием атомарных иснтрукций. Test-and-Set Lock, Ticket Lock, MCS Lock.

     3.5 Неблокирующая синхронизация. Проблема ABA и безопасное освобождение памяти.

     3.6. Per-CPU и Per-Thread память.

4. Межпроцессное взаимодействие: сигналы, pipe-ы, семафоры, сокеты, очереди сообщений.

5. Перманентное хранение

     5.1 Устройства хранения: HDD, SSD

     5.2 Файловые системы;

     5.3 Индексные структуры данных: B-деревья и их вариации, LSM деревья.

     5.4 Распределенные файловые системы. Протокол консенсуса, FLP, Paxos.

6. Виртуализация. Виды, назначение и применение виртуализации. Trap-and-Emulate, эффективная виртуализаци, критерий Попека и Голдберга.

 

Домашние задания

1. Прерывания.

2. Аллокация памяти.

3. Потоки исполнения, планирование и синхронизация.

4. Файловая система.

5. Пространство пользователя и системные вызовы.