OMSCS: Перший семестр — організація навчання і Advanced Operating Systems

💡 Усі статті, обговорення, новини для початківців — в одному місці. Приєднуйтесь до Junior спільноти!

Вітаю, товариство! Мене звати Нікіта, я C++ розробник в Atto Trading, і це третій допис у серії про OMSCS. Перші можна знайти тут і тут.

У цьому пості я розкажу про те, як загалом влаштовано навчання, і про свій перший курс — Advanced Operating Systems. Я великий прокрастинатор, тому матеріалу накопичилось достатньо багато. Спершу я хотів у цьому пості розказати про всі предмети, які встиг узяти, але зрозумів, що це занадто за обсягом, тому ще про 3 предмети розповім у наступному дописі.

Організація навчання

Онбординг після зарахування

Усіх вступників автоматично зараховують на міні-курс, де директор програми Dr. Joyner коротко розповідає що до чого: які очікування від студентів, як проходить навчання, що важливо знати на старті. Тобто, у разі вступу, ви точно розумітимете, що від вас очікується.

Зарахування на курси і Time Ticket

Далі настає в чомусь найскладніша частина — зарахування на курси.

Студенти OMSCS використовують ту саму систему, що й усі інші студенти Georgia Tech, але для OMSCS доступні не всі курси. Студент може обрати курс для зарахування тільки після настання часу, записаного в його Time Ticket. Саме зарахування розбите на фази, усього їх 2. Вступники можуть реєструватися тільки в другій фазі, коли більшість місць уже зайнята. Час у Time Ticket доволі зручний у нашому часовому поясі, тому не треба буде вставати посеред ночі, щоб зареєструватися.

Ці Time Tickets видаються автоматично, а час у них залежить від того, скільки курсів студент уже пройшов. Чим довше навчаєшся — тим більше шансів потрапити на курс, якщо не провтикав настання часу в Time Ticket.

Місця, waitlist і FFF

У більшості курсів місця обмежені, але є кілька курсів з безлімітною кількістю місць, тому ситуація, що ви взагалі залишились без можливості зарахуватись на будь-що, практично неможлива.

Частина місць резервується під waitlist. Якщо ви не змогли зареєструватись на курс одразу, у вас є можливість додатись у цей список у порядку черги. Першій людині у списку дають обмежений час скористатись можливістю зарахуватись на курс. Якщо людина не скористалась — можливість передається далі по списку.

Перед початком навчання є «Free For all Friday», яку тепер називають «Free For all !Friday», бо проводиться в четвер. Під час FFAF спадають усі резервації, і тоді часто можна «залетіти» на курс в обхід черги у waitlist.

Через таку схему цілком можливий варіант, що ви не потрапите в першому семестрі на курс, який ви хочете, бо всі місця будуть зайняті. Треба бути до цього готовим і мати план Б.

Окремо є курс, на який майже нереально потрапити, якщо це не один з ваших останніх семестрів. Це Intro to Graduate Algorithms. Так стається, тому що цей курс обов’язковий для випуску, і майже всі місця в ньому зарезервовані для «випускників». Хоча я чув історії, як через FFAF туди потрапляли люди у свій перший семестр.

Canvas, Ed Discussion, лекції і завдання

Трохи про організацію навчального процесу.

Вас додають на курс у Canvas і на форум в Ed Discussion. Лекції часто доступні всі одразу і знаходяться в Canvas та/або в Ed. Також завжди є окремий список для читання із рекомендованих статей за темою.

В Ed Discussion відбувається основне спілкування викладачів і студентів та колаборація між студентами. Я багато разів бачив, як студенти постили якісь питання, на які отримували пояснення як від Teaching Assistants, так і від інших студентів. Якщо ви любите спілкуватись наживо, щотижня проводяться office hours, на яких можна поспілкуватись з професором і TA. Вони не завжди проводяться в зручний час, але вони записуються, тому їх можна подивитись потім. Якщо бути чесним, то я на це забив і ніколи на них не ходив, а переглядав тільки перший у першому семестрі. Суть у тому, що ситуація, коли ви повністю загубились і немає звідки отримати допомогу, дуже малоймовірна. За бажання та інвестиції часу можна отримати з курсу набагато більше, ніж просто переглянуті лекції.

На початку семестру завжди є пост, у якому всі представляються і знайомляться — це гарний спосіб збільшити собі кількість connections з усього світу в LinkedIn. З мого досвіду більшість студентів з англомовних країн, здебільшого США (оце так несподіванка).

Доступність лаб/завдань залежить від курсу, але зазвичай вони відкриваються поступово протягом семестру.

Кількість екзаменів залежить від курсу, але часто їх двоє: midterm і final.

До дедлайнів ставлення суворе: хтось взагалі не приймає завдання після дедлайну, а хтось дає коротке «розширення» з можливим штрафом по балах.

Десь трохи раніше середини семестру настає withdrawal deadline. До цього часу можна дропнутись з курсу, і в транскрипті навіть не буде запису, що ви цей курс брали. Після цієї дати у випадку покидання курсу в транскрипті стоятиме W.

Академічна доброчесність

Незвичним стало те, що тут ДУЖЕ відповідальне ставлення до академічної доброчесності. Про це постійно наголошують і за цим реально слідкують.

Я був свідком ситуацій, коли людей ловили на тому, що вони брали лаби з інтернету або ж генерували їх ллмкою. З LLM проблема не в тому, що було видно, що це згенерований код, а в тому, що LLM генерував код на основі доступного в інтернеті, і ловили саме за плагіат. Санкції виглядають приблизно так:

• 1 порушення: 0 за завдання/екзамен, неможливість отримати A за курс і неможливість дропнутись з курсу
• 2 порушення: відрахування з курсу
• 3 порушення: відрахування з програми

Може здатися дивним: чому неможливість дропнути курс — це взагалі покарання? Логіка в тому, що так студент не може просто вийти з курсу одразу після санкції й «обнулити» наслідки. Інакше перше порушення майже нічого б не коштувало, максимум довелося б узяти ще один семестр, щоб надолужити.

Такий підхід має свої плюси і мінуси. Очевидний плюс у тому, що підвищується цінність диплому. Бо більшість студентів дійсно пройшли програму, а не зчітирили собі шлях у ній. А ось мінус у тому, що одне і те ж завдання, яке може бути доволі обмежене і специфіковане, дається великій кількості людей протягом декількох років. Я люблю себе накручувати, а накручування тут в тому, що, як я розумію, завжди існує шанс, що в когось перетнеться з тобою хід думок і стиль вирішення проблеми, тому є шанс false positive потрапляння на плагіат. На щастя, такого зі мною не було, але якщо зайти на сабредіт, можна побачити купу постів, де люди божаться, що їх безпідставно звинуватили в плагіаті.

Незважаючи на вищесказане, ситуація не настільки погана, бо завжди є процес розгляду, де дають студентам довести свою невинуватість.

Як проходять екзамени (прокторинг)

Екзамени організовані схожим чином з IELTS.

Зазвичай на проходження екзамену дається тиждень або, наприклад, п’ятниця + вихідні. Тобто можна обрати зручний для себе час. Екзамен треба проходити в тихій кімнаті наодинці.

У випадку closed-notes перед екзаменом треба просканувати кімнату, щоб показати, що ти дійсно там один, і що в кімнаті немає нічого, що може допомогти. Також треба просканувати свій паспорт, щоб за вас не могла написати роботу інша людина.

Під час екзамену записується звук з мікрофона, відео з камери та екран. У прямому ефірі за вами зазвичай ніхто не дивиться, але система відмічає підозрілі моменти, які потім може переглянути хтось із викладачів. Сам екзамен може тривати 2.5 години, що є неймовірним челенджем для любителів коротких смішних відосів в інтернеті.

Саме навчання

Fall 2024 — Advanced Operating Systems (AOS)

Мені пощастило зарахуватись на курс, який я хотів. Я обрав Advanced Operating Systems, тому що:

1. Мені хочеться вірити, що я шарю в ОС, і це легкий спосіб втягнутись у навчання через тему, в якій я вже розбираюсь.
2. Зазвичай багато людей беруть цей курс після Graduate Introduction to Operating Systems, тому відносно мало фрешменів конкурує за місця в AOS.

Можна подумати, що цей предмет про ОС, але це тільки частково правда) Я б його назвав Introduction to Distributed Systems. Ось що взагалі викладається в курсі:

Курс починається з короткого рефрешеру про базові речі — що таке ОС, як працює віртуальна пам’ять, кеш, багатопоточність і так далі. Загалом усе, що викладається на ОС під час бакалаврату. Після цього йшла домашня робота, де треба було відповісти на декілька питань, і простенька лаба про багатопоточність на C, щоб люди розуміли, чи взагалі готові вони проходити цей курс. Питання здебільшого базові, типу:

Explain all the actions from the time a process incurs a page fault to the time it resumes execution. Assume that this is the only runnable process in the entire system.

але були й цікаві, наприклад:

Explain page coloring and how it may be used in memory management by an operating system.

Поняття page coloring було для мене новим. Виявилось, що єдине більш-менш живе ядро, яке його використовує — це FreeBSD.

Далі йде перша серйозна тема — OS Structures. Тут розглядають три підходи до структури ядра: SPIN, Exokernel і L3 Microkernel. Загалом доволі цікаво, особливо враховуючи, що microkernel архітектура ядра досі жива і використовується в QNX, що є одним з основних виборів за потреби в RTOS. Ще згадувалась дуже повчальна історія про вплив оптимізації на софт: до якогось моменту вважалося, що мікроядра повільні, бо в Mach від Carnegie Mellon border crossing займав десь 900 циклів процесора, але в якийсь момент за справу взявся дядько Лідтке і оптимізував це в своїй ОС L3 до 123 циклів. Хоча здавалося б, Mach писали далеко не дурні люди. Після цього мікроядра повільними вже не вважали)

Наступна тема — Virtualization. Тут розповідається про CPU, Memory і Device Virtualization. Порівнюються Full Virtualization (VMware) та Paravirtualization (Xen). Цьому модулю відповідає перша лаба на С з використанням libvirt. Вона складається з 2 частин: vCPU scheduler і memory coordinator для guest OSes. Мені лаба дуже сподобалась, бо немає якогось явного кращого детерміністичного рішення. Треба придумати евристику, щоб рішення працювало достатньо добре в декількох різних сценаріях.

Після цього Parallel Systems — найбільший модуль курсу. Тут дуже багато чого. Починається з Symmetric Multiprocessor (SMP) і того, як імплементовано memory consistency та cache coherence. Потім про різні можливі способи імплементації спінлоків і бар’єрів на UMA і NUMA. Наступною підтемою йде імплементація і оптимізація Remote Procedure Call (RPC), після чого викладаються різні підходи до scheduling. Ця велика тема закінчується обговоренням того, як можна оптимізувати ОС конкретно для Shared Memory Multiprocessor з великою кількістю CPU на прикладі Tornado. Основна ідея в тому, щоб мінімізувати кількість глобальних об’єктів у ядрі, захищених м’ютексом, замінивши їх локальними репліками.

Далі йде Distributed Systems. Тут треба сказати про дядька Лампорта. Це людина, яка придумала LaTeX, Paxos, TLA+ і отримала премію Тюрінга в 2013 році за внесок у distributed computing. Його стаття «Time, Clocks, and the Ordering of Events in a Distributed System» з 1978 року — це основа всього модуля. Головна ідея: у розподіленій системі немає глобального часу, тому потрібен інший спосіб визначити, що сталося раніше, а що пізніше. Звідси happened-before relationship і logical clocks. Це все існує для того, щоб можна було досягти розподіленого консенсусу. Бонусом ще розказується про distributed mutual exclusion. Fun fact: в алгоритмі Лампорта для цього треба мінімум 3(N-1) повідомлень на 1 lock, де N — це кількість процесів. Після цього розповідається про Active Networks, що є концепцією з 90-х, де роутери не просто пересилають пакети, а можуть виконувати код. 90-ті були давно, але Active Networks можна вважати одним з концептуальних попередників SDN, хоча архітектурно вони суттєво відрізняються. Взагалі зараз майже все Software Defined, навіть машини.

Цим двом темам відповідає друга лаба. У ній треба імплементувати декілька SMP бар’єрів на OpenMP і декілька Distributed Memory бар’єрів на MPI. Усе це треба додатково заміряти і написати звіт з поясненням результатів. Крутість цієї лаби полягає в тому, що вам дають доступ до PACE — кластера GaTech, де ви через SLURM запускаєте джоби одразу на багатьох машинах усередині кластера.

Потім трохи археології під назвою Distributed Objects and Middleware: Spring OS (не плутати зі Spring Framework), Java RMI, Enterprise JavaBeans. Не дуже корисний модуль, як на мене, бо це все вже мертве.

Після цього Distributed Subsystems — застосування distributed systems. Тут 3 сабмодулі. Перший про Global Memory Systems. Якщо коротко, ідея в тому, щоб робити swap не в локальному накопичувачі, а в RAM іншої машини, з’єднаної по LAN. Як можна зрозуміти, це було придумано задовго до SSD. Можна подумати, що це давно мертва ідея, але я загуглив, і ця ідея лягла в основу disaggregated memory, що зараз використовується в HPC кластерах. Наступний сабмодуль називається Distributed Shared Memory, про те, як можна неявно для програми представити фізичну пам’ять на різних нодах як один логічний адресний простір, приховуючи явну комунікацію. Плюси, я думаю, очевидні. З мінусів — це те, можна на зверненні до адреси зависнути, чекаючи на пам’ять з іншого кінця кластера. Ну і останній сабмодуль про імплементацію distributed filesystem.

Десь тут треба було зробити третю лабу. У ній треба імплементувати щось на кшталт магазину на gRPC з тредпулом. Загалом лаба цікава і фактично є підготовкою до останньої лаби. Ще з цікавого: на момент, як я її писав, не підтримувались останні версії gRPC, тому асинхронну комунікацію не можна було імплементувати через колбеки, через це довелося використовувати CompletionQueue. І підхід тут дуже цікавий. У кожної операції є void* тег. Так ось у цей тег у більшості випадків треба передавати якийсь динамічно створений через new об’єкт, щоб у наступних операціях звернутись до нього по тегу як по вказівнику, бо в ньому зазвичай треба зберігати якусь асоційовану з цим ланцюгом викликів інформацію. Виходить така собі state machine з ручним керуванням пам’яттю.

Далі йде Failures and Recovery: LRVM, RioVista, QuickSilver. Цей модуль про те, як робити транзакції і recovery віртуальної пам’яті на рівні ОС з відносно малим оверхедом.

Після цього Internet Scale Computing, який розбитий на 3 сабмодулі. Перший загальний про те, як менеджити ресурси великого сервісу і про replication vs partitioning. Другий модуль про легендарний гуглівський MapReduce. Я не знаю, що тут додати, тому якщо не знаєте, що це, то краще погуглити. Третій сабмодуль про Content Delivery Networks (CDN) на Coral DHT. Це теж дуже прикольна і досі актуальна технологія, яку активно використовують, наприклад, стримінгові сервіси.

Цьому модулю відповідає остання четверта лаба. У ній треба імплементувати спрощену версію MapReduce на основі gRPC. Спрощення полягає в тому, що workers запущені на одному хості і можуть юзати спільну файлову систему. Оригінальна імплементація MapReduce використовує Google File System (GFS), що сама собою є гарним екземпляром програмної інженерії.

Потім коротке повернення до операційних систем під назвою Real-Time and Multimedia. У цьому модулі розглядається TS-Linux та Persistent Temporal Streams, але фактично більшість теми зводиться до ідей імплементації real-time scheduling.

І наостанок трохи Security — Saltzer and Schroeder’s design principles і Andrew File System.

На цьому з лекціями все. Пару слів про тести. Курс має 3 closed-notes тести: Test 1 (Lessons 1-4), Test 2 (Lessons 5-7), Test 3/Final (Lessons 8-11). На кожен тест відводиться 3 дні (п’ятниця + вихідні). Особливість полягає в тому, що в п’ятницю викладають 80% питань, і тому за бажання можна гарно підготуватись.

Окрема особливість курсу — це reading list із ~30 академічних статей. Читати все не обов’язково, але за двома статтями треба написати summary. Особисто я прочитав усього 3: MapReduce — бо треба було для лаби, і 2 для summary:

1. Using Processor-Cache Affinity Information in Shared-Memory Multiprocessor Scheduling (1993) — тут назва говорить сама за себе)
2. The Multikernel: A New OS Architecture for Scalable Multicore Systems (2009). Тут уже цікавіше. Тут описується реально існуюча ОС Barrelfish, розроблена в ETH Zürich, ідея якої в тому, щоб мати можливість працювати на гетерогенних ядрах. Уявіть: у вас є кластер, де і x86, і ARM, і RISC-V, а ви зверху накатуєте одну ОС.

Що можу сказати про цей курс. Мені було цікаво, а це, я думаю, головне) Особливо цікавими для мене були лаби. Якщо захочете подивитись лекції, то вони є у вільному доступі в інтернеті. З мінусів я можу виділити розгляд неактуальних технологій, але, як кажуть, університет — це не ПТУ. Інколи корисно розглянути щось суто з академічної/теоретичної точки зору, особливо враховуючи, як деякі технології можуть отримувати друге життя — як, наприклад, Global Memory Systems переродилась у disaggregated memory з попитом на навчання LLM.

Я дуже хотів отримати A, бо це дає доступ до предмету Systems Design for Cloud Computing (SDCC). SDCC — це логічне продовження AOS, з тим самим професором. Основний топік цього предмету — це імплементувати MapReduce, але вже в повному вигляді. Врешті я отримав A, але SDCC я так поки і не взяв, бо він вимагає відвідування мітингів, які за київським часом проводяться вночі. Це єдиний не повністю асинхронний курс, про який я знаю в OMSCS.

Підсумки

Перший семестр вийшов насиченим. AOS виявився гарним вибором для старту — достатньо challenging, щоб було цікаво, але не настільки, щоб паралельно з full-time роботою це було нереально. На OMSCentral AOS оцінений студентами за складністю в середньому як 4/5.

Через те, що в мене дуже погано з time management, я все відкладав на останній момент. Оскільки дедлайни на тести були десь о 8 ранку в понеділок, я декілька разів складав їх о 1 ночі під кінськими дозами кофеїну. З лабами була приблизно така ж проблема. Я хочу зауважити, що це не через те, що навантаження надзвичайно велике, а суто через моє невміння розподіляти час (були тижні, в які я взагалі нічого не робив із навчання). Тобто якщо ви стабільно декілька разів на тиждень будете щось робити, без довгих перерв — проблем із поєднанням з full-time взагалі не буде.

Що далі?

У наступній частині розкажу про ще три курси: Software Analysis and Testing, High Performance Computing і High Performance Computer Architecture. Stay tuned! Я сподіваюсь, цього разу перерва між частинами буде менша ніж рік)