Откройте браузер, музыкальный плеер и игру. У вас один процессор — возможно, несколько ядер — но всё это кажется работающим одновременно. И вместе они требуют больше…
English narration · English + 中文 subtitles burned in · Английское озвучивание · Английский + китайские субтитры (встроенные)
16.1
How an OS maximises use of resources · Как ОС максимизирует использование ресурсов
Syllabus · Программа
English
Candidates should be able to:
Notes and guidance
Show understanding of how an OS can maximise the use of resources
Describe the ways in which the user interface hides the complexities of the hardware from the user
Show understanding of process management
The concept of multi-tasking and a process The process states: running, ready and blocked The need for scheduling and the function and benefits of different scheduling routines (including round robin, shortest job first, first come first served, shortest remaining time) How the kernel of the OS acts as an interrupt handler and how interrupt handling is used to manage low-level scheduling
Show understanding of virtual memory, paging and segmentation for memory management
The concepts of paging, virtual memory and segmentation The difference between paging and segmentation How pages can be replaced How disk thrashing can occur
Русский
Кандидаты должны уметь:
Примечания и рекомендации
Показать понимание того, как ОС может максимизировать использование ресурсов
Описать способы, которыми пользовательский интерфейс скрывает от пользователя сложность аппаратного обеспечения
Показать понимание управления процессами
Концепция многозадачности и процесса Состояния процесса: выполнение, ожидание и блокировка Необходимость планирования и функции, а также преимущества различных алгоритмов планирования (включая по циклическому принципу, наиболее короткая задача, первый пришёл — первый обслужен, наиболее короткое оставшееся время) Как ядро ОС действует как обработчик прерываний и как обработка прерываний используется для управления низкоуровневым планированием
Показать понимание виртуальной памяти, постраничного и сегментного адресования для управления памятью
Концепции постраничного адресования, виртуальной памяти и сегментации Различие между постраничным адресованием и сегментацией Как страницы могут быть заменены Как может возникнуть thrashing диска
Source: Cambridge International syllabus · Источник: Программа Cambridge International
English
A computer has many resources (CPU time, memory, disk, I/O) and many programs competing for them. The OS shares them fairly and efficiently so each is well used and the system stays responsive:
multi-tasking 多任务 — switch the CPU quickly between processes so several seem to run at once.
memory management — give each process the memory it needs; use disk paging 分页 when RAM runs out.
spooling 假脱机 and buffering — print jobs queue on disk so the CPU never waits for the printer.
caching — keep recently-used disk data in cache 高速缓存 / RAM.
Русский
Компьютер имеет множество ресурсов (процессорное время, память, диск, ввод/вывод) и множество программ, конкурирующих за них. ОС справедливо и эффективно разделяет их, чтобы каждый ресурс использовался хорошо, а система оставалась отзывчивой:
ОС разделяет процессор, память, диск и ввод/вывод между программами
многозадачность — быстрое переключение процессора между процессами, чтобы несколько казались запущенными одновременно.
управление памятью — предоставление каждому процессу нужной ему памяти; использование дискового pagging (перемещения страниц), когда RAM заканчивается.
spooling (пулинг) и буферизация — задания печати очереди на диске, чтобы процессор никогда не ждал принтера.
кэширование — хранение недавно использованных данных диска в кэше / RAM.
Процессор — ключевой ресурс, который ОС разделяет между конкурирующими задачамиОС также управляет памятью (RAM), решая, что оставить в ней, а что переместить на диск
The user interface hides the hardware behind friendly abstractions: the user sees windows, menus and folders, not addresses or sectors. One click on an icon makes the OS find the program on disk, allocate memory, load it and start it. A CLI (command line) is powerful and scriptable for experts; a GUI (graphical) is easier to learn. Most systems offer both.
"Describe two ways in which the complexities of the hardware are hidden from the user." (1) The user works with files and folders by name, and the OS translates them into the tracks, sectors and blocks of the disk; (2) the user runs a program with a click or a command, and the OS loads it, allocates memory and schedules it without the user knowing any addresses; (3) device drivers let the user print or save without knowing how the printer or disk is controlled; (4) a graphical interface replaces machine-level commands with icons, windows and menus. The benefit to a student, with an example: the OS makes the hardware usable without technical knowledge, for instance saving a document to a USB drive by dragging its icon.
"Show how an OS maximises the use of resources." It schedules the processor so that it is never idle while a process is ready; it manages memory, allocating it to processes, reclaiming it and extending it with virtual memory; it manages input and output, using buffers and spooling so that fast and slow devices overlap their work; and it manages storage, keeping track of free space and files. Each point names a resource and what the OS does with it.
Русский
Пользовательский интерфейс скрывает аппаратное обеспечение за понятными абстракциями: пользователь видит окна, меню и папки, а не адреса или секторы. Один клик по значку заставляет ОС найти программу на диске, выделить память, загрузить её и запустить. CLI (командная строка) мощна и поддается автоматизации для опытных пользователей; GUI (графический интерфейс) легче освоить. Большинство систем предлагают оба варианта.
"Опишите два способа, которыми сложность аппаратного обеспечения скрывается от пользователя." (1) Пользователь работает с файлами и папками по имени, а ОС преобразует их в дорожки, сектора и блоки диска; (2) пользователь запускает программу кликом мыши или командой, а ОС загружает её, выделяет память и планирует выполнение без знания пользователем каких-либо адресов; (3) драйверы устройств позволяют печатать или сохранять файлы, не зная, как управляются принтер или диск; (4) графический интерфейс заменяет машинные команды иконками, окнами и меню. Польза для студента с примером: ОС делает оборудование используемым без технических знаний, например, сохранение документа на USB-накопитель перетаскиванием его иконки.
"Покажите, как ОС максимизирует использование ресурсов." Она планирует процессор, чтобы он никогда не простаивал, пока готов к выполнению какой-либо процесс; она управляет памятью, выделяя её процессам, освобождая обратно и расширяя с помощью виртуальной памяти; она управляет вводом и выводом, используя буферы и спуллинг, чтобы быстрые и медленные устройства перекрывали друг друга по времени выполнения задач; и она управляет хранилищем, отслеживая свободное пространство и файлы. Каждый пункт называет ресурс и то, что ОС делает с ним.
16.1
Process management · Управление процессами
English
A process 进程 is a program in execution — its code, current state, memory and open files.
Scheduling
The scheduler 调度器 chooses which ready process runs next, and for how long:
round robin 轮转 — each process gets a fixed time slice 时间片, then goes to the back of the queue.
first-come-first-served; shortest job first; shortest remaining time (run the job with the least work left); priority; multilevel feedback queues.
The trade-off is responsiveness vs throughput vs fairness.
"Describe what is meant by multi-tasking and how it benefits process management."Several processes are held in memory at the same time and the processor switches between them so quickly that they appear to run simultaneously, each given a share of processor time in turn. The benefit: the processor is never left idle while one process waits for input or output, so throughput is higher and the user can work on several programs at once. "Explain the need for scheduling." There are more processes than processors, so a decision must be made about which process runs next and for how long; scheduling makes sure every process makes progress, that the processor is fully used, that response times are acceptable, and that priorities can be respected.
The scheduling routines, as the exam wants them described.
Routine
Function
Benefit
Drawback
first come first served (FCFS)
processes run in the order in which they arrive in the ready queue, each to completion
simple; every process is dealt with in turn, none is starved
a long process holds up all the short ones behind it; poor response
shortest job first (SJF)
the ready process with the shortest estimated run time runs next, to completion
minimises the average waiting time; many short jobs finish quickly
run times must be known in advance; a long job may never run (starvation)
shortest remaining time (SRT)
pre-emptive 抢占式 version of SJF: if a new process arrives with less time left than the running one, it takes over
short processes are served even faster; good throughput
more context switches; a long job can be interrupted repeatedly and starve
round robin (RR)
each ready process gets a fixed time slice in turn; when it expires the process goes to the back of the queue
fair; every process responds within a bounded time, good for interactive use
context-switch overhead; a very short slice wastes time, a long one delays others
priority
the ready process with the highest priority runs first
important or time-critical work is done first
low-priority processes may starve unless priorities age
Worked example. Three processes arrive together with CPU times of 8, 4 and 2 ms. Compare the average waiting time under FCFS (in arrival order A, B, C) and under shortest job first.
FCFS: A waits 0, B waits 8, C waits 12; average $(0 + 8 + 12)/3 = 6.7\ \text{ms}$. SJF runs C, B, A: C waits 0, B waits 2, A waits 6; average $2.7\ \text{ms}$. The total work is the same 14 ms either way; the order decides who waits. Round robin with a 2 ms slice would give A, B and C each a turn in the first 6 ms, so C finishes at 6 ms, B at 12 ms and A at 14 ms: the most responsive, not the fastest on average.
Process states
A process is new, ready (waiting for the CPU), running, blocked 阻塞 (waiting for I/O or a lock), or terminated. When its time slice ends it goes running → ready; when it requests I/O it goes running → blocked; when the I/O finishes it goes blocked → ready.
The three states and why a process moves.Running: the process has the processor. Ready: it could run but is waiting for the processor. Blocked: it cannot run until something else happens. Reasons for each transition, which the exam asks for one at a time: running to ready when its time slice ends, or when a higher-priority process becomes ready and pre-empts it (an interrupt); running to blocked when it requests input or output or waits for a resource or another process; blocked to ready when the I/O it was waiting for completes (signalled by an interrupt); ready to running when the scheduler dispatches it. A blocked process can never go straight to running: it must become ready first.
Process control block and context switch
For each process the OS keeps a process control block 进程控制块 (PCB) — the saved program counter, registers, state and memory info.
a context switch 上下文切换 suspends one process and starts another: it saves the state into one PCB and restores it from another. This small cost is paid on every switch.
the kernel 内核 (the core of the OS) acts as an interrupt handler 中断处理程序. When a device or the timer raises an interrupt, interrupt handling 中断处理 saves the running process and runs the right routine — this is what drives low-level scheduling.
"Outline how the kernel acts as an interrupt handler" (two marks). When an interrupt is raised, the kernel saves the state of the running process (its registers and program counter, in its process control block), identifies the source and priority of the interrupt, runs the appropriate interrupt service routine, and then restores the interrupted process (or a higher-priority one) so that execution continues. This is how the timer ends a time slice and how a completed I/O operation unblocks a process.
Inter-process communication
Processes are isolated, so the OS provides inter-process communication 进程间通信: pipes 管道 (one program's output feeds another's input), shared memory 共享内存 (a region several processes can use), and message passing.
Русский
Процесс — это выполняемая программа: её код, текущее состояние, выделенная память и открытые файлы.
Планирование
Планировщик выбирает, какой готовый процесс будет выполнен следующим и в течение какого времени:
циклическое планирование — каждому процессу выделяется фиксированный тайм-слайс (квант времени), после чего он ставится в конец очереди.
план по порядку поступления; кратчайшая задача первой; кратчайшее оставшееся время (выполнять задачу с наименьшим объемом оставшейся работы); приоритеты; многоуровневые очереди с обратной связью.
Компромисс заключается в балансе между отзывчивостью, пропускной способностью и справедливостью.
"Опишите, что подразумевается под многозадачностью и как она помогает управлению процессами."Несколько процессов удерживаются в памяти одновременно, а процессор переключается между ними настолько быстро, что кажется, будто они выполняются параллельно, каждый получает свою долю процессорного времени по очереди. Выгода: процессор никогда не простаивает, когда один процесс ожидает ввода или вывода, поэтому пропускная способность выше, и пользователь может работать с несколькими программами одновременно. "Объясните необходимость планирования." Существует больше процессов, чем процессоров, поэтому необходимо принимать решение о каком процессе выполнять следующим и в течение какого времени; планирование обеспечивает, чтобы каждый процесс продвигался вперед, чтобы процессор был полностью загружен, чтобы время отклика было приемлемым, и чтобы можно было соблюдать приоритеты.
Та же работа в другом порядке: план «кратчайшая задача первой» убирает короткие задания, поэтому большинство заданий ждет меньше, но есть риск, что длинное задание будет ждать вечно
Рутины планирования так, как этого требует экзамен.
Рутина
Функция
Преимущество
Недостаток
план по порядку поступления (FCFS)
процессы выполняются в порядке их поступления в очередь готовых, каждый до завершения
простота; каждый процесс обрабатывается по очереди, никто не голодает
длинный процесс задерживает все короткие задачи, следующие за ним; плохая отзывчивость
кратчайшая задача первой (SJF)
следующий выполняется готовый процесс с кратчайшей оценочной продолжительностью, до завершения
минимизирует среднее время ожидания; многие короткие задачи завершаются быстро
продолжительность должна быть известна заранее; длинная задача может никогда не выполниться (голодание)
кратчайшее оставшееся время (SRT)
прерываемая версия SJF: если новый процесс прибывает с меньшим временем выполнения, чем у текущего, он захватывает управление
короткие процессы обслуживаются еще быстрее; высокая пропускная способность
больше переключений контекста; длинная задача может прерываться снова и снова и голодать
циклическое планирование (RR)
каждый готовый процесс получает фиксированный квант времени по очереди; когда он истекает, процесс ставится в конец очереди
справедливость; каждый процесс реагирует в пределах ограниченного времени, хорошо подходит для интерактивного использования
накладные расходы на переключение контекста; очень короткий квант тратит время впустую, длинный задерживает другие
приоритет
готовый процесс с наивысшим приоритетом выполняется первым
важные или критичные по времени задачи выполняются первыми
процессы с низким приоритетом могут голодать, если приоритеты не стареют (не повышаются со временем)
Разобранный пример. Три процесса прибывают одновременно с потребностями в CPU 8, 4 и 2 мс. Сравните среднее время ожидания при FCFS (в порядке прибытия A, B, C) и при плане «кратчайшая задача первой».
FCFS: A ждет 0, B ждет 8, C ждет 12; среднее $(0 + 8 + 12)/3 = 6.7\ \text{ms}$. SJF выполняет C, B, A: C ждет 0, B ждет 2, A ждет 6; среднее $2.7\ \text{ms}$. Общий объем работы одинаков — 14 мс в обоих случаях; порядок решает, кто ждет. Циклическое планирование с квантом 2 мс обеспечило бы A, B и C по очереди в первые 6 мс, так что C завершится на 6 мс, B на 12 мс, а A на 14 мс: это наиболее отзывчивый вариант, но не самый быстрый в среднем.
Планирование по порядку поступления четырех процессовЦиклическое планирование: каждый процесс получает фиксированный квант времени по очереди, затем выполняет следующий (в отличие от плана по порядку поступления)
Состояния процессов
Процесс может находиться в состоянии нов (new), готов (ready, ожидает процессор), выполнения (running), ожидания (blocked, ожидает ввод-вывод или блокировку) или завершения (terminated). Когда заканчивается его временной слайс, он переходит из выполнения в готовность; когда он запрашивает ввод-вывод — из выполнения в ожидание; когда ввод-вывод завершается, он переходит из ожидания в готовность.
Процесс перемещается между состояниями нового, готового, выполнения, ожидания и завершения
Три состояния и причины перехода процесса.Выполнение: процесс использует процессор. Готовность: он мог бы выполняться, но ждет процессор. Ожидание: он не может выполняться, пока не произойдет другое событие. Причины каждого перехода, которые на экзамене спрашивают по одному: выполнение → готовность, когда заканчивается его временной слайс, или когда становится готовым процесс более высокого приоритета и прерывает его (прерывание); выполнение → ожидание, когда он запрашивает ввод или вывод или ждет ресурса или другого процесса; ожидание → готовность, когда завершается ожидаемый им ввод-вывод (сигнализируется прерыванием); готовность → выполнение, когда планировщик диспетчерирует его. Ожидающий процесс никогда не может сразу перейти в выполнение: сначала он должен стать готовым.
Блок управления процессом и переключение контекста
Для каждого процесса операционная система хранит блок управления процессом (PCB) — сохраненный счетчик команд, регистры, состояние и информацию о памяти.
Переключение контекста сохраняет состояние одного процесса и загружает состояние другого
переключение контекста приостанавливает один процесс и запускает другой: оно сохраняет состояние в один PCB и восстанавливает его из другого. Этот небольшой расход происходит при каждом переключении.
ядро (основа ОС) действует как обработчик прерываний. Когда устройство или таймер вызывает прерывание, обработка прерываний сохраняет выполняющийся процесс и запускает нужную подпрограмму — именно так управляется низкоуровневое планирование.
"Опишите, как ядро действует как обработчик прерываний (два балла)." При возникновении прерывания ядро сохраняет состояние выполняемого процесса (его регистры и счетчик команд в блоке управления процессом), определяет источник и приоритет прерывания, запускает соответствующую подпрограмму обработки прерываний, а затем восстанавливает прерванный процесс (или процесс более высокого приоритета), чтобы выполнение продолжилось. Именно так таймаут завершает временной слайс, а завершенная операция ввода-вывода разблокирует процесс.
Межпроцессное взаимодействие
Процессы изолированы, поэтому ОС предоставляет межпроцессное взаимодействие: каналы (pipe — вывод одной программы питает ввод другой), общая память (область, которую могут использовать несколько процессов) и передача сообщений.
Explore · Исследовать
The life of a process · Жизненный цикл процесса
Tap round the loop a process travels. It only runs when the scheduler picks it; needing I/O sends it to blocked, and finishing its time slice sends it back to ready — round and round until it's done. · Процесс движется по кругу цикла. Он выполняется только тогда, когда планировщик выбирает его; необходимость ввода/вывода переводит его в состояние ожидания (blocked), а истечение временного кванта возвращает обратно в готовность (ready) — снова и снова, пока он не завершится.
Each process gets its own virtual address space 虚拟地址空间 — a clean, contiguous range of addresses the OS maps to physical memory. This gives each process a simple space, protects processes from each other, and lets the total memory exceed physical RAM.
In paging, the virtual space is split into fixed-size pages 页 and physical memory into same-sized frames 页框. A page table maps each page to a frame. If an accessed page is not in RAM — a page fault 缺页 — the OS reads it from the swap file 交换文件 into a frame, evicting another page if RAM is full. Frequent faults cause thrashing 抖动 (disk thrashing), where the OS spends most of its time swapping pages instead of doing useful work.
In segmentation 分段, memory is split into variable-sized logical segments (code, stack, heap), each with its own permissions. Many systems use paging within segments.
"Explain what is meant by virtual memory" (three marks).Secondary storage (disk) is used to extend the RAM, so that the available memory appears larger than the physical memory; the address space of a process is divided into pages, and only the pages currently needed are held in RAM while the rest wait on disk; pages are swapped between RAM and disk as required, and the OS translates each virtual address into a physical one. Why an OS needs it: the programs running may need more memory than the RAM installed; it lets more (or larger) programs run at once; a program can be larger than the physical memory; memory is used efficiently because only the active parts of programs occupy RAM.
Paging against segmentation: the difference the exam wants.Paging divides memory into blocks of fixed size (pages and frames) chosen by the hardware, with no regard to the program's structure, and the mapping is invisible to the programmer; segmentation divides a program into variable-sized logical units (a procedure, an array, the stack) whose sizes and boundaries follow the program, so a segment can be protected or shared as a unit. "Describe the process of segmentation": the program is split into segments of different sizes, each given a segment number; a segment table records where each segment starts in memory and how long it is; a logical address is a segment number plus an offset, and the OS adds the offset to the segment's base address to find the physical location.
"Explain what is meant by disk thrashing" and when it occurs.Disk thrashing 磁盘抖动 is the state in which pages are swapped in and out of RAM so frequently that the processor spends more time moving pages than executing instructions, and the system slows almost to a halt. It occurs when the RAM is too small for the pages the running processes need (their working sets): a page just moved out is needed again almost at once, so it is fetched back, which pushes out another page that is soon needed, and so on. Too many processes, or a program that accesses memory unpredictably, brings it on; more RAM or fewer processes cure it.
Русский
Каждому процессу выделяется собственное пространство виртуальных адресов — чистый, непрерывный диапазон адресов, который ОС отображает на физическую память. Это дает каждому процессу простое пространство, защищает процессы друг от друга и позволяет суммарному объему памяти превышать объем физической ОЗУ.
При страничной организации виртуальное пространство делится на фиксированные по размеру страницы, а физическая память — на рамки такого же размера. Таблица страниц отображает каждую страницу на рамку. Если нужная страница отсутствует в ОЗУ — возникает ошибка обращения к странице (page fault), и ОС считывает ее из файла подкачки в рамку, вытесняя другую страницу, если ОЗУ заполнена. Частые ошибки вызывают thrashing (thrashing диска), когда ОС проводит большую часть времени в обмене страницами вместо полезной работы.
Страничная организация отображает каждую страницу логической памяти на рамку физической памяти
При сегментации память делится на логические сегменты переменного размера (код, стек, куча), каждый со своими правами доступа. Во многих системах используется страничная организация внутри сегментов.
Сегментация отображает сегменты переменного размера с помощью таблицы карт сегментов
"Объясните, что понимается под виртуальной памятью (три балла)." Для расширения ОЗУ используется вторичное хранилище (диск), благодаря чему доступная память кажется больше физической; адресное пространство процесса делится на страницы, и только необходимые в данный момент страницы находятся в ОЗУ, остальные ждут на диске; страницы подкачиваются между ОЗУ и диском по мере необходимости, а ОС преобразует каждый виртуальный адрес в физический. Почему ОС нужна эта технология: работающие программы могут требовать больше памяти, чем установлено в ОЗУ; она позволяет одновременно запустить больше (или более крупных) программ; программа может быть больше физической памяти; память используется эффективно, поскольку в ОЗУ занимают только активные части программ.
Страничная организация против сегментации: разница, которую хочет видеть экзаменатор.Страничная организация делит память на блоки фиксированного размера (страницы и рамки), выбираемые аппаратным обеспечением, без учета структуры программы, и отображение скрыто от программиста; сегментация делит программу на логические единицы переменного размера (процедура, массив, стек), размеры и границы которых следуют за программой, поэтому сегмент можно защитить или сделать общим как единое целое. "Опишите процесс сегментации: программа разделяется на сегменты разного размера, каждому присваивается номер сегмента; таблица сегментов фиксирует, где начинается каждый сегмент в памяти и какова его длина; логический адрес состоит из номера сегмента и смещения, а ОС добавляет смещение к базовому адресу сегмента, чтобы найти физическое местоположение.
«Объясните, что подразумевается под «thrashing» (трэш-эффектом) и когда он возникает». «Thrashing» — это состояние, при котором страницы перемещаются в оперативную память и выгружаются из неё настолько часто, что процессор тратит больше времени на перемещение страниц, чем на выполнение инструкций, и система замедляется почти до полной остановки. Оно возникает, когда оперативная память слишком мала для наборов рабочих страниц запущенных процессов: страница, только что выгруженная, требуется снова почти немедленно, поэтому она загружается обратно, что вытесняет другую страницу, которая soon тоже понадобится, и так далее. Слишком много процессов или программа с непредсказуемым доступом к памяти вызывают его; решение — добавить больше RAM или сократить количество процессов.
Explore · Исследовать
What happens on a page fault · Что происходит при ошибке обращения к странице (page fault)?
Step through a page fault. When the program touches a page that isn't in RAM, the OS quietly fetches it from disk and updates the page table — so the program sees more memory than physically exists. · Пройдите через ошибку страницы. Когда программа обращается к странице, которой нет в ОЗУ, ОС тихо подгружает её с диска и обновляет таблицу страниц — так программа видит больше памяти, чем физически существует.
How an interpreter runs a program · Как интерпретатор выполняет программу
Syllabus · Программа
English
Candidates should be able to:
Notes and guidance
Show understanding of how an interpreter can execute programs without producing a translated version
Show understanding of the various stages in the compilation of a program
Including lexical analysis, syntax analysis, code generation and optimisation
Show understanding of how the grammar of a language can be expressed using syntax diagrams or Backus-Naur Form (BNF) notation
Show understanding of how Reverse Polish Notation (RPN) can be used to carry out the evaluation of expressions
Русский
Кандидаты должны уметь:
Примечания и рекомендации
Показать понимание того, как интерпретатор может выполнять программы без создания переведённой версии
Показать понимание различных этапов компиляции программы
Включая лексический анализ, синтаксический анализ, генерацию кода и оптимизацию
Показать понимание того, как грамматика языка может быть выражена с помощью диаграмм синтаксиса или нотации Бэкуса-Наура (BNF)
Показать понимание того, как обратная польская нотация (RPN) может использоваться для вычисления выражений
Source: Cambridge International syllabus · Источник: Программа Cambridge International
English
An interpreter 解释器 translates and runs the source at the same time. For each statement it reads the line, does lexical and syntax analysis, checks types, then executes the action, and moves on. Errors are reported immediately and it usually stops; no executable is produced. The translation is redone every run (slower), but it gives fast development feedback and is portable.
"Explain how an interpreter executes a program without producing a translated version" (three marks). The interpreter takes one statement (line) at a time, translates (analyses) it, and executes it immediately, before moving to the next; no translated version of the whole program is created or stored, so every statement is translated every time it is executed, including each pass through a loop; if a statement contains an error, execution stops there and the error is reported. This is what makes an interpreter good for developing and testing (errors are found as they are reached, and a change can be tried at once) but slower for running finished programs.
Русский
Интерпретатор переводит и выполняет исходный код одновременно. Для каждой команды он считывает строку, проводит лексический и синтаксический анализ, проверяет типы, затем выполняет действие и переходит дальше. Ошибки сообщаются немедленно, и обычно выполнение останавливается; исполняемый файл не создается. Перевод выполняется заново при каждом запуске (медленнее), но это обеспечивает быструю обратную связь при разработке и является портативным.
«Объясните, как интерпретатор выполняет программу без создания переведенной версии» (три балла). Интерпретатор берет одно выражение (строку) за раз, переводит (анализирует) его и выполняет немедленно, прежде чем перейти к следующему; переведенная версия всей программы не создается и не хранится, поэтому каждое выражение переводится каждый раз при выполнении, включая каждый проход через цикл; если выражение содержит ошибку, выполнение останавливается на этом месте, и ошибка сообщается. Именно это делает интерпретатор хорошим инструментом для разработки и тестирования (ошибки находятся по мере их достижения, а изменения можно попробовать сразу), но более медленным для выполнения готовых программ.
A compiler 编译器 turns source into machine code 机器码 in phases:
lexical analysis 词法分析 — the lexer groups characters into tokens 词法单元 (keywords, identifiers, operators, literals), discarding whitespace and comments.
syntax analysis (parsing) 语法分析 — check the tokens fit the grammar and build an abstract syntax tree 抽象语法树. A missing bracket gives a syntax error 语法错误.
semantic analysis 语义分析 — check the program makes sense (variables declared, types match).
code generation 代码生成 — walk the tree and emit target code, choosing registers and layouts.
code optimisation 代码优化 — remove redundant work, fold constants, reorder for the pipeline.
The output is an executable.
The purpose of each stage, in the words that score.Lexical analysis: removes white space and comments; converts the characters of the source code into tokens (keywords, identifiers, operators, constants), checking that each is valid in the language; enters identifiers into the symbol table 符号表. Syntax analysis: checks that the sequence of tokens obeys the grammar (syntax rules) of the language; builds a parse tree (abstract syntax tree); reports syntax errors; type checking and the checking of variable declarations are sometimes counted here as semantic analysis. Code generation: converts the checked tree into object code or machine code (possibly via an intermediate code), allocating memory and registers. Optimisation: makes the code run faster or use less memory, by removing redundant instructions, combining or simplifying calculations, and reorganising loops, without changing what the program does. The matching question pairs each stage with one of these descriptions.
Русский
Компилятор преобразует исходный код в машинный код поэтапно:
Лексический анализ — лексер группирует символы в токены (ключевые слова, идентификаторы, операторы, литералы), отбрасывая пробельные символы и комментарии.
Синтаксический анализ (парсинг) — проверка соответствия токенов грамматике и построение абстрактного синтаксического дерева. Отсутствующая скобка вызывает синтаксическую ошибку.
Семантический анализ — проверка осмысленности программы (объявление переменных, соответствие типов).
Генерация кода — обход дерева и выдача целевого кода, выбор регистров и разметки.
Этапы компиляции от исходного кода до оптимизированного исполняемого файла
Цель каждого этапа, словами, которые дают баллы.Лексический анализ: удаляет пробельные символы и комментарии; преобразует символы исходного кода в токены (ключевые слова, идентификаторы, операторы, константы), проверяя, что каждый из них допустим в языке; вносит идентификаторы в таблицу символов. Синтаксический анализ: проверяет, что последовательность токенов соответствует грамматике (синтаксическим правилам) языка; строит разборное дерево (абстрактное синтаксическое дерево); сообщает о синтаксических ошибках; проверка типов и проверка объявлений переменных иногда относятся сюда как семантический анализ. Генерация кода: преобразует проверенное дерево в объектный код или машинный код (возможно, через промежуточный код), выделяя память и регистры. Оптимизация: делает код более быстрым или требующим меньше памяти, путем удаления избыточных инструкций, объединения или упрощения вычислений и реорганизации циклов, не изменяя того, что делает программа. Задание на сопоставление связывает каждый этап с одним из этих описаний.
Explore · Исследовать
The phases of compilation · Этапы компиляции
Step through what a compiler does to your source. Each phase hands its output to the next — characters become tokens, tokens become a tree, the tree becomes optimised machine code. · Продемонстрируйте, что делает компилятор с вашим исходным кодом. Каждый этап передает свой результат следующему — символы становятся токенами, токены превращаются в дерево, дерево становится оптимизированным машинным кодом.
16.2
Grammar: BNF and syntax diagrams · Грамматика: BNF и диаграммы синтаксиса
English
A grammar 文法 says which token sequences are valid programs.
Backus-Naur Form 巴科斯-诺尔范式 (BNF) is textual. A production rule 产生式 has the form:
Each alternative is a sequence of terminal 终结符 symbols (literal text) and non-terminal 非终结符 symbols (other rule names):
The recursive third rule expresses "a letter followed by any number of letters or digits". An IF statement:
A syntax diagram 语法图 (railroad diagram) shows the same thing graphically: boxes for non-terminals, rounded boxes for terminals, arrows for valid paths, loops for repetition. The two notations are equivalent. The parser uses the grammar to decide whether a program is valid.
Reading the exam's diagrams. Each diagram defines one non-terminal; follow the arrows from the entry to the exit, and every path you can trace is a valid string. A choice of boxes side by side is a set of alternatives; a loop back is "repeat as many times as you like"; a box for another non-terminal means "insert anything that rule allows". "State why the string is invalid" wants the rule it breaks, in words: 9K is invalid as a variable because the first character must be a letter, not a digit; JJ90 is an invalid passcode if the rule allows only one letter before the digits, or if J is not in the set of letters listed. Always check the string against the set of characters the diagram actually allows, not against what a real language would accept.
Writing BNF from a diagram. Each diagram becomes one rule <name> ::= ...; alternatives are separated by |; a sequence is written one symbol after another; and repetition is written with recursion, because BNF has no loop symbol: "one or more letters" is <word> ::= <letter> | <letter><word>, and "zero or more digits after a letter" is <variable> ::= <letter> | <letter><digits> with <digits> ::= <digit> | <digit><digits>.
Worked example. Complete the BNF for a vehicle registration that must begin with two letters (from A B C) followed by one, two or three digits (from 0 1 2).
AB12 is valid; A12 is not (only one letter); AB1234 is not (four digits); AD1 is not (D is not a listed letter). Asked to add a constraint such as "the third character may also be a symbol", add the extra alternative to the rule for that position only, and define <symbol> with its own rule.
Worked example. Write BNF for an expression that is a variable, followed by an operator, followed by either a variable or a number, where a variable is a single lower-case letter from a b c and an operator is + or -.
The recursive <number> rule allows any number of digits; the two alternatives of <expression> cover both cases named in the definition. Keep every non-terminal in angle brackets and every terminal without them.
Русский
Грамматика определяет, какие последовательности токенов являются допустимыми программами.
Форма Бэкуса-Наура (BNF) текстовая. Правило вывода имеет вид:
<symbol> ::= alternative1 | alternative2 | ...
Каждая альтернатива представляет собой последовательность терминальных символов (буквального текста) и нетерминальных символов (имен других правил):
Рекурсивное третье правило выражает «буква, за которой следует любое количество букв или цифр». Утверждение IF:
<if-statement> ::= IF <condition> THEN <statement> ENDIF
| IF <condition> THEN <statement> ELSE <statement> ENDIF
Диаграмма синтаксиса (диаграмма железной дороги) показывает то же самое графически: прямоугольники для нетерминалов, скругленные прямоугольники для терминалов, стрелки для допустимых путей, петли для повторений. Обе нотации эквивалентны. Парсер использует грамматику, чтобы определить, является ли программа корректной.
Диаграмма синтаксиса (железнодорожная) для оператора присваиванияДиаграмма синтаксиса и правило BNF говорят одно и то же: выбор становится альтернативами, разделенными чертами, а цикл — правилом, ссылающимся на самого себя
Чтение диаграмм экзамена. Каждая диаграмма определяет один нетерминал; следуйте по стрелкам от входа к выходу, и каждый путь, который можно пройти, является допустимой строкой. Выбор прямоугольников, расположенных рядом, представляет собой набор альтернатив; петля назад означает «повторить столько раз, сколько нужно»; прямоугольник для другого нетерминала означает «вставить всё, что разрешает правило». «Объясните, почему строка недействительна» требует указать нарушенное правило словами: 9K является недопустимым идентификатором, потому что первый символ должен быть буквой, а не цифрой; JJ90 является недопустимым паролем, если правило допускает только одну букву перед цифрами, или если J не входит в перечень допустимых букв. Всегда проверяйте строку на соответствие множеству символов, которые диаграмма фактически позволяет, а не тому, что было бы принято в реальном языке программирования.
Составление BNF по диаграмме. Каждая диаграмма превращается в одно правило <name> ::= ...; альтернативы разделяются знаком |; последовательность записывается символ за символом; а повторение записывается через рекурсию, поскольку в BNF нет символа цикла: «одна или более букв» записывается как <word> ::= <letter> | <letter><word>, а «ноль или более цифр после буквы» — как <variable> ::= <letter> | <letter><digits> с использованием <digits> ::= <digit> | <digit><digits>.
Разбор примера. Заполните BNF для регистрационного номера транспортного средства, который должен начинаться с двух букв (из A B C), за которыми следуют одна, две или три цифры (из 0 1 2).
<letter> ::= A | B | C
<digit> ::= 0 | 1 | 2
<digits> ::= <digit> | <digit><digit> | <digit><digit><digit>
<registration> ::= <letter><letter><digits>
AB12 является валидным; A12 — нет (только одна буква); AB1234 — нет (четыре цифры); AD1 — нет (D не является перечисленной буквой). Если требуется добавить ограничение, например «третий символ также может быть символом», добавьте дополнительную альтернативу только к правилу для этой позиции и определите <symbol> собственным правилом.
Разбор примера. Напишите BNF для выражения, которое представляет собой переменную, за которой следует оператор, за которым следует либо переменная, либо число, где переменная — это одна строчная буква из a b c, а оператор — это + или -.
<variable> ::= a | b | c
<operator> ::= + | -
<number> ::= <digit> | <digit><number>
<expression> ::= <variable><operator><variable> | <variable><operator><number>
Рекурсивное правило <number> позволяет любое количество цифр; две альтернативы правила <expression> охватывают оба случая, названных в определении. Сохраняйте все нетерминалы в угловых скобках, а все терминалы — без них.
Reverse Polish Notation (RPN) · Обратная польская запись (RPN)
English
In infix 中缀 notation the operator sits between its operands (3 + 4 * 2), needing brackets and precedence rules. In Reverse Polish Notation 逆波兰表示法 (RPN, postfix 后缀) the operator follows its operands (3 4 2 * +), needing no brackets.
Converting infix to RPN
Use an operator stack 栈. Scan left to right: output an operand; for an operator, first pop any stacked operators of higher or equalprecedence 优先级 to the output, then push it; push (; on ) pop to output until the matching (. At the end, pop all operators. Example: (3 + 4) * 2 → 3 4 + 2 *.
Evaluating RPN
Use a stack of operands. Scan left to right: push each operand; on an operator, pop the top two, apply it, and push the result. Evaluating 3 4 2 * +:
Token
Stack
3
3
4
3, 4
2
3, 4, 2
*
3, 8
+
11
Result: 11. RPN needs no brackets at evaluation time and suits a stack machine — which is how the JVM and many bytecode 字节码 interpreters work.
"Explain why RPN is used to evaluate expressions" (two marks). In RPN the operators appear in the order in which they are applied, so an expression can be evaluated in a single left-to-right pass with no brackets and no precedence rules; it is therefore simpler and faster for the compiler or interpreter to process. "Identify, with reasons, a suitable data structure": a stack, because evaluation needs the most recently pushed operands first (last in, first out): each operand is pushed, and each operator pops the top two, applies itself, and pushes the result. Show the stack contents after every token when asked.
Converting infix to RPN by hand. (1) Fully bracket the expression using the precedence rules; (2) move each operator to just after the closing bracket of its own pair; (3) remove the brackets. So $(a - b) * (a + c) / 7$ becomes $((a - b) * (a + c)) / 7$, then a b - a c + * 7 /. Note that * and / are applied left to right, so the division is the last operator, not the multiplication. More conversions: $((7 + 3) - (2 * 8)) / 6$ is 7 3 + 2 8 * - 6 /; $(7 - 2 + 8) / (9 - 5)$ is 7 2 - 8 + 9 5 - /; $a * b + b - d + 15$ is a b * b + d - 15 +; $(2 - 6) * (13 + 7) / 5$ is 2 6 - 13 7 + * 5 /.
Converting RPN back to infix. Work through the RPN with a stack of expressions: push each operand; for each operator pop two, write them either side of it in brackets, and push the result. So a b / 4 * a b + - is $((a / b) * 4) - (a + b)$; 5 2 + 9 3 - / 3 * is $((5 + 2) / (9 - 3)) * 3$; b a c - + d b + * c / is $((b + (a - c)) * (d + b)) / c$; a b - c + c a - * d / is $(((a - b) + c) * (c - a)) / d$. Keep the brackets: dropping them can change the meaning.
Worked example. Evaluate a b - c d + * e / when $a = 17$, $b = 5$, $c = 7$, $d = 3$ and $e = 10$, showing the stack.
token
action
stack (top on the right)
a
push 17
17
b
push 5
17, 5
-
pop 5 and 17, push $17 - 5$
12
c
push 7
12, 7
d
push 3
12, 7, 3
+
pop 3 and 7, push $7 + 3$
12, 10
*
pop 10 and 12, push $12 \times 10$
120
e
push 10
120, 10
/
pop 10 and 120, push $120 / 10$
12
Result 12. The order of the pops matters for - and /: the value popped second is the left operand, so a b - is $a - b$, not $b - a$. Two more, in the same way: d a b + * c a - / with $a = 6, b = 12, c = 15, d = 5$ gives $5 \times (6 + 12) / (15 - 6) = 90 / 9 = 10$; c a - b d + * b c + / with $a = 4, b = 12, c = 24, d = 6$ gives $(24 - 4) \times (12 + 6) / (12 + 24) = 360 / 36 = 10$.
Worked example. Convert $(A + B) \times (C - D)$ to RPN, then evaluate $(3 + 4) \times (5 - 2)$. Scan left to right using an operator stack. Push (; output A; push +; output B; on ) pop back to the matching (, giving A B + so far. Push ×, and the second bracket behaves the same way, giving C D -. At the end pop the ×. Result: A B + C D - ×. To evaluate the numbers, use a stack of operands: push 3, push 4; + pops both and pushes 7; push 5, push 2; - pops both and pushes 3; × pops 7 and 3 and pushes 21. Two things make these reliable: the operands keep their original order through the conversion (only the operators move), and every operator acts on the two values immediately below it on the stack.
Русский
В инфиксной записи оператор находится между своими операндами (3 + 4 * 2), требуя скобок и правил приоритета. В Обратной польской записи (RPN, постфиксная) оператор следует за своими операндами (3 4 2 * +), скобки не требуются.
Преобразование инфиксной записи в RPN
Используйте стек операторов. Сканируйте слева направо: выводите операнд; для оператора сначала извлеките (pop) из стека все операторы с более высоким или равнымприоритетом в выходную последовательность, затем поместите (push) текущий оператор; помещайте ⟨(⟩; при encountering ⟨)⟩ извлекайте в выход до встречного совпадающего ⟨(⟩. В конце извлеките все операторы. Пример: (3 + 4) * 2 → 3 4 + 2 *.
Вычисление RPN
Используйте стек операндов. Сканируйте слева направо: помещайте каждый операнд; при遇到 операторе извлеките два верхних элемента, примените оператор и поместите результат. Вычисление 3 4 2 * +:
Токен
Стек
3
3
4
3, 4
2
3, 4, 2
*
3, 8
+
11
Результат: 11. RPN не требует скобок во время вычисления и подходит для стеговой машины — так работают JVM и многие интерпретаторы байт-кода.
«Объясните, почему RPN используется для вычисления выражений» (два балла). В RPN операторы появляются в порядке их применения, поэтому выражение может быть вычислено за один проход слева направо с отсутствием скобок и отсутствием правил приоритета; поэтому компилятору или интерпретатору проще и быстрее его обрабатывать. «Определите, с обоснованием, подходящую структуру данных»:стек, потому что при вычислении нужны в первую очередь последние помещенные операнды (последним пришел — первым ушел): каждый операнд помещается в стек, а каждый оператор извлекает два верхних, применяет себя и помещает результат. Показывайте содержимое стека после каждого токена, если этого требуется.
Преобразование инфиксной записи в RPN вручную. (1) Полностью обведите выражение скобками, используя правила приоритета; (2) переместите каждый оператор непосредственно после закрывающей скобки своей пары; (3) удалите скобки. Таким образом, $(a - b) * (a + c) / 7$ превращается в $((a - b) * (a + c)) / 7$, затем в a b - a c + * 7 /. Обратите внимание, что * и / применяются слева направо, поэтому деление является последним оператором, а не умножением. Дополнительные преобразования: $((7 + 3) - (2 * 8)) / 6$ это 7 3 + 2 8 * - 6 /; $(7 - 2 + 8) / (9 - 5)$ это 7 2 - 8 + 9 5 - /; $a * b + b - d + 15$ это a b * b + d - 15 +; $(2 - 6) * (13 + 7) / 5$ это 2 6 - 13 7 + * 5 /.
Преобразование RPN обратно в инфиксную запись. Пройдитесь по RPN со стеком выражений: помещайте каждый операнд; для каждого оператора извлеките два, запишите их по обе стороны от него в скобках и поместите результат. Таким образом, a b / 4 * a b + - это $((a / b) * 4) - (a + b)$; 5 2 + 9 3 - / 3 * это $((5 + 2) / (9 - 3)) * 3$; b a c - + d b + * c / это $((b + (a - c)) * (d + b)) / c$; a b - c + c a - * d / это $(((a - b) + c) * (c - a)) / d$. Сохраняйте скобки: их удаление может изменить смысл.
Разбор примера. Вычислите a b - c d + * e / при значениях $a = 17$, $b = 5$, $c = 7$, $d = 3$ и $e = 10$, показывая стек.
Токен
Действие
Стек (верхний справа)
a
push 17
17
b
push 5
17, 5
-
pop 5 and 17, push $17 - 5$
12
c
push 7
12, 7
d
push 3
12, 7, 3
+
pop 3 and 7, push $7 + 3$
12, 10
*
pop 10 and 12, push $12 \times 10$
120
e
push 10
120, 10
/
pop 10 and 120, push $120 / 10$
12
Результат 12. Порядок извлечения важен для操作- и /: значение, извлеченное вторым, является левым операндом, поэтому a b - это $a - b$, а не $b - a$. Еще два, аналогичным образом: d a b + * c a - / с $a = 6, b = 12, c = 15, d = 5$ дает $5 \times (6 + 12) / (15 - 6) = 90 / 9 = 10$; c a - b d + * b c + / с $a = 4, b = 12, c = 24, d = 6$ дает $(24 - 4) \times (12 + 6) / (12 + 24) = 360 / 36 = 10$.
Разбор примера. Преобразуйте $(A + B) \times (C - D)$ в обратную польскую нотацию (RPN), затем вычислите $(3 + 4) \times (5 - 2)$. Сканируйте слева направо, используя стек операторов. Поместите (; выведите A; поместите +; выведите B; на ) извлеките обратно к соответствующей скобке (, получив пока что A B +. Поместите ×, и вторая скобка ведёт себя аналогично, давая C D -. В конце извлеките ×. Результат: A B + C D - ×. Для вычисления чисел используйте стек операндов: поместите 3, поместите 4; + извлекает оба значения и помещает 7; поместите 5, поместите 2; - извлекает оба значения и помещает 3; × извлекает 7 и 3 и помещает 21. Две вещи делают эти процессы надёжными: операнды сохраняют свой первоначальный порядок при преобразовании (двигаются только операторы), и каждый оператор действует над двумя значениями непосредственно под ним в стеке.
Explore · Исследовать
Operator precedence — what RPN removes · Приоритет операторов — то, что убирает обратная польская нотация
In ordinary infix maths × and ÷ bind tighter than + and −, so you must apply rules in the right order. Reverse Polish Notation writes the operands first (3 4 2 × + 1 −), fixing the order so no precedence rules are needed. · В обычной инфиксной математике × и ÷ имеют более высокий приоритет, чем + и −, поэтому правила применяются в правильном порядке. Обратная польская нотация записывает операнды сначала (3 4 2 × + 1 −), фиксируя порядок так, что правила приоритета не нужны.
16.2
Definitions the examiner accepts · Определения, принимаемые экзаменатором
English
A definition question is marked against fixed wording. Learn these exactly, and give one answer only.
Term
Definition
multi-tasking
several processes held in memory at once, the processor switching between them so that they appear to run simultaneously
process
a program that has been loaded into memory and is being executed (or is ready to be)
running / ready / blocked
has the processor / waiting for the processor / cannot continue until an event such as I/O completes
scheduling
deciding which ready process gets the processor next, and for how long
pre-emptive scheduling
the running process can be interrupted and moved to ready so that another process runs
virtual memory
using secondary storage to extend RAM, holding only the pages currently needed in physical memory
paging
dividing memory and programs into fixed-size pages that are moved between disk and RAM as needed
segmentation
dividing a program into variable-sized logical segments, each mapped to memory by a segment table
disk thrashing
pages being swapped between RAM and disk so often that little useful processing is done
interpreter
translates and executes a program one statement at a time, without producing a translated version
compiler
translates a whole high-level program into machine (object) code before it is run
lexical analysis
converts the source code into tokens, removing white space and comments, and builds the symbol table
syntax analysis
checks that the tokens obey the grammar of the language and builds a parse tree
Backus–Naur Form
a notation for the grammar of a language: rules of the form <name> ::= alternatives built from terminals and non-terminals
Reverse Polish Notation
a way of writing expressions with each operator after its operands, so they can be evaluated with a stack and without brackets
Русский
Вопросы на определение оцениваются по фиксированной формулировке. Выучите их точно и дайте только один ответ.
Термин
Определение
многозадачность
несколько процессов удерживается в памяти одновременно, процессор переключается между ними, создавая впечатление одновременного выполнения
процесс
программа, загруженная в память и выполняемая (или готовая к выполнению)
работающий / готовый / заблокированный
имеет процессор / ожидает процессор / не может продолжать до завершения события, такого как ввод-вывод
планирование
решение о том, какой готовый процесс получит процессор следующим и на какой период
прерываемое планирование
работающий процесс может быть прерван и перемещён в состояние «готов», чтобы другой процесс мог выполняться
виртуальная память
использование вторичного хранилища для расширения ОЗУ, хранение в физической памяти только необходимых в данный момент страниц
страничная организация
разделение памяти и программ на страницы фиксированного размера, которые перемещаются между диском и ОЗУ по мере необходимости
сегментация
разделение программы на логические сегменты переменного размера, каждый из которых отображается в памяти с помощью таблицы сегментов
трэш (thrashing)
частая подмена страниц между ОЗУ и диском, в результате которой практически бесполезная обработка не выполняется
интерпретатор
переводит и выполняет программу по одной команде за разом, не создавая переведённой версии
компилятор
переводит всю высокоуровневую программу в машинный (объектный) код до её запуска
лексический анализ
преобразует исходный код в токены, удаляя пробельные символы и комментарии, и строит таблицу символов
синтаксический анализ
проверяет соответствие токенов грамматике языка и строит дерево разбора
форма Бэкуса–Наура
нотация для грамматики языка: правила вида <name> ::= alternatives, построенные из терминальных и нетерминальных символов
обратная польская нотация
способ записи выражений, где каждый оператор следует за своими операндами, что позволяет вычислять их со стеком и без скобок
16.2
Exam tips · Советы для экзамена
English
The OS questions are marked on named mechanisms: scheduling, memory management, I/O buffering and spooling, file management; for the interface, file names not addresses, clicks not commands, drivers, GUI.
Process states with their transitions and the reason for each; scheduling routines as function plus benefit plus drawback; the kernel saves state, identifies the interrupt, services it, restores.
Virtual memory: disk extends RAM, pages swapped, address translation; paging is fixed-size and invisible, segmentation is variable-size and logical; thrashing is swapping instead of working.
Interpreter: one statement at a time, translated then executed, nothing stored. Compiler stages: tokens and symbol table, grammar and parse tree, code, optimisation.
BNF: a rule per diagram, | for choice, recursion for repetition, terminals bare and non-terminals in angle brackets. Say which rule a string breaks.
RPN: operators after operands, evaluate with a stack, show every step; convert by fully bracketing; when converting back, keep the brackets.
Common mistakes
Describing multi-tasking as "running several programs at the same time" without saying the processor switches between them.
Sending a blocked process straight to running, or giving "time slice ended" as the reason for running to blocked.
Confusing shortest job first (non-pre-emptive) with shortest remaining time (pre-emptive), or round robin with priority.
Defining virtual memory as "using the hard disk as RAM" with no mention of pages being swapped.
Saying an interpreter "converts the program to machine code and then runs it"; that is a compiler.
Putting syntax checking in lexical analysis, or optimisation before code generation in the matching question.
Writing BNF repetition as <letter>* or with an ellipsis; use recursion. Leaving angle brackets off non-terminals.
Reversing the operands of - or / when evaluating RPN, or writing the RPN of $a * b + c$ as a b c + *.
Русский
Вопросы об ОС оцениваются по названным механизмам: планирование, управление памятью, буферизация и спуллинг ввода-вывода, файловое управление; по интерфейсу: имена файлов вместо адресов, клики вместо команд, драйверы, графический интерфейс.
Состояния процессов с их переходами и причинами каждого; routines планирования как функция плюс преимущество плюс недостаток; ядро сохраняет состояние, определяет прерывание, обслуживает его, восстанавливает.
Виртуальная память: диск расширяет ОЗУ, страницы подменяются, преобразование адресов; страничная организация — фиксированный размер и невидима, сегментация — переменный размер и логична; трэш — это подмена вместо работы.
Интерпретатор: одна команда за разом, переводится затем выполняется, ничего не сохраняется. Этапы компилятора: токены и таблица символов, грамматика и дерево разбора, код, оптимизация.
BNF: одно правило на диаграмму, | для выбора, рекурсия для повторения, терминалы без скобок, нетерминалы в угловых скобках. Укажите, какое правило нарушает строка.
RPN: операторы следуют за операндами, вычисление со стеком, показ каждого шага; преобразование через полное раскрытие скобок; при обратном преобразовании сохраняйте скобки.
Распространенные ошибки
Описание многозадачности как «выполнения нескольких программ одновременно» без упоминания переключения процессора между ними.
Отправка заблокированного процесса сразу в состояние «работающий» или указание «истёк временной слайс» как причины перехода из состояния «работающий» в «заблокированный».
Путаница между алгоритмом кратчайшей задачи первой (непрерываемым) и кратчайшего оставшегося времени (прерываемым), или round robin и приоритетным планированием.
Определение виртуальной памяти как «использования жёсткого диска как ОЗУ» без упоминания подмены страниц.
Утверждение, что интерпретатор «преобразует программу в машинный код, а затем выполняет её»; это описание компилятора.
Размещение проверки синтаксиса в лексическом анализе или оптимизации перед генерацией кода в сопоставлении понятий.
Запись повторения в BNF как <letter>* или с многоточием; следует использовать рекурсию. Пропуск угловых скобок вокруг нетерминалов.
Перестановка операндов - или / при вычислении RPN, или запись RPN для $a * b + c$ как a b c + *.
Interactive lessons on this topic · Интерактивные уроки по этой теме
Work through it step by step, with instant-check exercises. · Пройдите его шаг за шагом с упражнениями мгновенной проверки.
Pick one and the site follows you — notes, papers, videos and practice all open on it. · Выберите один, и сайт будет вести вас — конспекты, работы, видео и практика откроются там.
Type to search notes, lessons, code, vocabulary and past-paper questions across every subject. · Введите запрос для поиска заметок, уроков, кода, словаря и вопросов с реальных экзаменов по всем предметам.
