Новости

Не беда, если вы чувствуете себя не у дел, когда другие программисты обсуждают аппроксимативный предел. Даже специалисты с опытом допускают ошибки из-за того, что подзабыли Computer Science. Расширенное издание бестселлера содержит все главные, а также продвинутые вопросы компьютерных наук: — типы и структуры данных; — алгоритмы; — графы; — теория сложности; — приемы эффективного решения задач; — безопасность; — железо и софт; — операционные системы; — сети; — базы данных и многое другое.

Операционные системы

Операционную систему можно рассматривать в качестве еще одного уровня абстракции, отделяющего пользователя (или программиста) от физической структуры компьютера. Вместо того чтобы напрямую управлять оборудованием, код приложения может просто обратиться к API ОС, чтобы задействовать те или иные системные функции.

Управление процессами

Как правило, пользователи предпочитают делать несколько дел одновременно. Подобно человеческому мозгу, процессор компьютера не может решать больше одной задачи за раз, но способен переключаться между разными задачами, чтобы создать видимость одновременного выполнения множества действий.

Это переключение позволяет нескольким задачам совместно использовать системные ресурсы (в том числе процессоры и память), но требует дополнительной работы, связанной с переключением контекстов и обеспечением того, чтобы разные процессы (выполнение задачи) не мешали друг другу.

Многозадачность

Многозадачная система работает в режиме разделения времени, при котором процессорное время распределяется между потоками различных процессов. Современные компьютеры обычно используют так называемую вытесняющую многозадачность, при которой ядро прерывает выполняющийся процесс по истечении некоего кванта времени или при получении сигнала от задачи с более высоким приоритетом. Поскольку распределение времени контролирует операционная система, каждый процесс в конечном итоге гарантированно получает квант времени ЦП. Тем не менее любой процесс может когда угодно потерять управление. Кроме того, может возникнуть ситуация взаимной блокировки, при которой несколько процессов находятся в состоянии ожидания ресурсов, занятых остальными, и ни один не может продолжить свое выполнение.

Пример
Для иллюстрации данной проблемы часто используется задача об обедающих философах, в которой пять безмолвных (то есть не разговаривающих друг с другом) философов сидят за круглым столом. Перед каждым из них стоит тарелка спагетти, и между каждой парой сидящих рядом философов лежит по одной вилке. Каждый из философов может либо есть, либо размышлять, причем есть он может, лишь взяв две вилки, лежащие с обеих сторон. Философ, у которого есть только одна вилка, не ест, а ждет, пока ему не достанется вторая вилка; таким образом, если каждый философ возьмет вилку слева от себя, все они будут голодать, ожидая возвращения второй вилки.

При использовании другого типа многозадачности, называемой совместной или кооперативной, каждый процесс сам контролирует свое выполнение и добровольно отдает процессорное время другим задачам либо периодически, либо при логической блокировке (например, при ожидании завершения ввода/вывода). Совместная многозадачность предполагает, что все процессы регулярно передают управление другим, и является непрактичной для большинства систем, поскольку существует вероятность того, что один из процессов не отдаст ресурсы, из-за чего остальные приложения не смогут продолжить работу. Тем не менее этот тип многозадачности часто применяется во встроенных системах.

Многопроцессорность и многопоточность

Если компьютер предусматривает несколько процессоров, то на нем могут одновременно выполняться несколько процессов. Кроме того, один процесс может состоять из нескольких потоков, выполняющихся на разных процессорах.

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

Многопоточность и состояния гонки

Состояния гонки возникают тогда, когда два или более потока пытаются одновременно изменить общие данные. Результат этого изменения зависит от порядка, в котором эти потоки обращаются к данным. Как правило, происходит нечто наподобие этого.

1. Поток A встречает оператор if и проверяет его условие.
2. Поток B выполняет код, который должен изменить результат условного выражения.
3. Поток A продолжает выполнение тела оператора if, даже если это уже неактуально.

Для того чтобы предотвратить возникновение этого гейзенбага, необходимо выполнить одно из следующих действий:

• заблокировать общие данные перед обращением к ним любого из потоков и тем самым предотвратить их изменение во время использования;
• превратить всю единицу работы (условное выражение и тело оператора if) в атомарную операцию, то есть в операцию, которую нельзя прервать.

Управление хранилищем

Ранее мы обсуждали, как происходит выделение памяти в стеке или в куче. Этим процессом управляет операционная система, распределяя память между процессами и решая, когда ее следует освободить.

Логические и физические адреса

Предположим, некоему вновь созданному процессу разрешено использовать 4 Гбайт памяти. Если мы предоставим этому процессу прямой доступ к памяти, то столкнемся с несколькими проблемами.

• Как мы можем гарантировать, что этот процесс не обратится к памяти за пределами выделенного блока?
• Если у нас нет непрерывного блока оперативной памяти размером 4 Гбайт, то как мы можем его создать?
• Если процесс приостановлен, а выделенная для него оперативная память используется другим процессом, то нужно ли нам ждать освобождения этого конкретного блока памяти перед возобновлением данного процесса?

Решение заключается в замене физической памяти логической. Вместо того чтобы предоставлять каждому процессу прямой доступ к диапазону физических адресов, мы назначаем ему блок логических адресов, которые ЦП может затем отобразить в физические. Благодаря такому подходу процессу не требуется знать о том, где в действительности хранятся используемые им данные. Их можно как угодно перемещать, не опасаясь того, что процесс (намеренно или случайно)получит доступ к памяти за пределами выделенного ему блока.

Редко используемые данные можно переместить в область подкачки, при этом процесс будет воспринимать их так, будто они находятся в оперативной памяти. Если нескольким процессам требуется копия одних и тех же инструкций, то одна и та же физическая память может отображаться в несколько логических адресов.

Пейджинг и свопинг

Объем данных растет так, чтобы заполнить все место на носителе.
Закон информации Паркинсона

Допустим, объем оперативной памяти системы не позволяет одновременно хранить данные для всех запущенных процессов, что тогда? Один из вариантов решения этой задачи — свопинг: процесс загружается в память целиком, выполняется до тех пор, пока управление не перейдет к другому процессу, а затем выгружается обратно на диск, чтобы освободить память для следующего процесса. В качестве альтернативы в память могут загружаться только те части программы, которые требуются в настоящий момент, а остальные при этом остаются на диске до тех пор, пока в них не возникнет необходимость.

Пейджинг, или подкачка страниц, предполагает разбиение виртуального адресного пространства на блоки фиксированного размера, называемые страницами, которые отображаются в страничные кадры или фреймы (того же размера) в памяти. Всякий раз, когда программа обращается к памяти, мы индексируем таблицу страниц, чтобы выяснить местоположение соответствующего страничного кадра. Если данная страница в настоящее время не загружена, то возникает ее отказ, после чего мы загружаем соответствующий кадр (при необходимости заменяя другую страницу, находящуюся в памяти в настоящее время).

Часто процесс работает с небольшим набором доступных ему страниц. Если это рабочее множество находится в памяти, то процесс может выполняться быстро, несмотря на небольшое количество загруженных страниц. Если же в каждый момент времени загруженной оказывается лишь часть рабочего множества, то результатом будут частые отказы страниц, поскольку процесс будет постоянно сталкиваться с отсутствием в памяти нужной ему страницы (такое состояние называется пробуксовкой). Чтобы этого избежать, мы можем разрешить запуск процесса только при загрузке в память всего рабочего множества.

Если памяти недостаточно для хранения рабочих множеств всех запущенных процессов, то некоторые процессы должны быть выгружены во избежание пробуксовки.