Закон Амдала. Трудоемкость алгоритма и ее оценка. Оценка трудоемкости алгоритмов матричных операций.
Закон Амдала. Трудоемкость алгоритма и ее оценка. Оценка трудоемкости алгоритмов матричных операций. - раздел Образование, Ответы на вопросы к экзамену по ОС
Закон Амдала — Иллюстрирует Ограничение Роста Производительно...
Закон Амдала — иллюстрирует ограничение роста производительности вычислительной системы с увеличением количества вычислителей. Джин Амдал сформулировал закон в 1967 году, обнаружив простое по существу, но непреодолимое по содержанию ограничение на рост производительности при распараллеливании вычислений: «В случае, когда задача разделяется на несколько частей, суммарное время её выполнения на параллельной системе не может быть меньше времени выполнения самого длинного фрагмента». Согласно этому закону, ускорение выполнения программы за счёт распараллеливания её инструкций на множестве вычислителей ограничено временем, необходимым для выполнения её последовательных инструкций.
По сути трудоёмкость - это оценка функции роста количества итераций при линейном приращении объема данных.
Например, если при увеличении размера входного массива в 2 раза количество итераций алгоритма по его обработке возрастёт в 4 раза, то это - квадратичная зависимость .
Можно эту функцию получить и экспериментально - нужно просто замерить время работы алгоритма на различных объёмах входных данных и построить график.
Может оказаться, что алгоритм с большей трудоёмкостью будет более эффективен на небольших объемах данных, поскольку коэффициенты при её расчёте обычно опускаются и считается предельная оценка при . Например, алгоритм будет явно эффективнее на небольших объемах, чем . Поэтому Вам, возможно, будет интереснее замерить реальную производительность и получить графическую зависимость экспериментально.
Оценка трудоемкости алгоритмов матричных операций. – оценка производится в зависимости от программы, тоесть если у нас например простое присваивание без цикла то здесь трудоемкость малая, а если у нас цикл а в нём большие функции вычисляются то это уже более трудоемкий алгоритм.
20 Понятия «процесс» и «поток». Необходимость использования потоков. Свойства (параметры) процессов и потоков.
• ПРОЦЕСС – понятие, используемое для учета ресурсов – единица планирования ресурсов
• Процесс – выполнение программы с ее исходными данными
• Процессы делятся на системные (решение задач ОС)- службы, демоны и пользовательские – создаются из выполняемых файлов
• Системные процессы – ДЕМОНЫ (Linux), службы (Windows). СП не связаны с терминалом - Linux, не имеют окон - Windows
• Процесс может породить один или несколько дочерних процессов (потомков) – например, проводник Windows
• Процесс имеет: виртуальное адресное пространство, имя, PID, ACL, приоритет, описатель (handle) Windows, открытые файлы, модули, объекты синхронизации, память - рабочее множество страниц, время работы на ЦП в режиме пользователя и ядра, привязку к ЦП и т.д. ( около 50 параметров в PowerShell)
• Для выполнения вычислительных работ каждый ПРОЦЕСС имеет один или несколько ПОТОКОВ – важно для многоядерных процессоров
• ПОТОК –последовательность выполняющихся команд ЦП.
• Поток имеет приоритет, согласно которому он получает КВАНТЫ времени ЦП, идентификатор TID, стек
Критерии классификации ОС Классификация ОС Примеры ОС Области применения ОС различных типов... По количеству одновременно решаемых задач... По количеству пользователей...
Назначение и функции операционной системы (ОС).
Операционная система – комплекс управляющих и обрабатывающих программ, предназначенный для:
Управления ресурсами вычислительной системы (ВС) Создания интерфейсов
MS Windows 95
• вытесняющая многозадачность (квантование времени)
• графический интерфейс пользователя 1024*840 пик
• 32 - разрядный код ОС
• файловые системы FAT12, FAT16 и FAT32
MS Windows 98
• вытесняющая многозадачность (квантование времени)
• графический интерфейс пользователя 1024*840 пик
• 32 - разрядный код ОС
• файловые системы FAT12, FAT16 и FAT32
MS Windows me
• вытесняющая многозадачность (квантование времени)
• графический интерфейс пользователя 1200*1024 пик
• 32 - разрядный код ОС
• файловые системы FAT12, FAT16 и FAT32
MS Windows NT4
• вытесняющая многозадачность (квантование времени)
• графический интерфейс пользователя 1024*840 пикcел
• 32 - разрядный код ОС
• файловые системы FAT12, FAT16 и NTFS4
MS Windows 2000
• вытесняющая многозадачность (квантование времени)
• графический интерфейс пользователя 1024*840 пикcел
• 32 - разрядный код и частично 64- разрядный код ОС
• файловые с
MS Windows XP
• вытесняющая многозадачность (квантование времени)
• графический интерфейс пользователя 1024*840 пикcел
• 32 - разрядный код и частично 64- разрядный код ОС
• файловые с
MS Windows Vista
• улучшенная вытесняющая многозадачность
• 32 - разрядный код и 64- разрядный код ОС
• файловые системы FAT16, FAT32, NTFS5, extFAT
• необходимый объем ОП 1 Гб – 2 Гб
MS Windows 7
• улучшенная вытесняющая многозадачность
• 32 - х и 64 – х разрядный код ОС
• файловые системы FAT16, FAT32, NTFS5 и extFAT
• необходимый объем ОП 1 Гб – 2 Гб
•
MS Windows 8 и Windows RT
• новый плиточный интерфейс пользователя
• ориентация на мобильные платформы
• новая энергосберегающая организация управления ресурсами
• 32 - х и 64 – х разрядный код ОС
Ядро и вспомогательные модули ОС.
Наиболее общим подходом к структуризации операционной системы является разделение всех ее модулей на две группы:
ядро — модули, выполняющие основные функции ОС;
мо
Архитектура ОС с ядром в привилегированном режиме.
Для надежного управления ходом выполнения приложений операционная система должна иметь по отношению к приложениям определенные привилегии. Иначе некорректно работающее приложение мо
Многослойная структура ядра ОС.
Вычислительную систему, работающую под управлением ОС на основе ядра, можно рассматривать как систему, состоящую из трех иерархически расположенных слоев: нижний слой образует аппар
Типовые средства аппаратной поддержки ОС.
Четкой границы между программной и аппаратной реализацией функций ОС не существует — решение о том, какие функции ОС будут выполняться программно, а какие аппаратно, принимается раз
Создание процессов (действия, выполняемые ОС).
• Создание виртуального адресного пространства процесса (ВАП)
• Загрузка образа процесса в ВАП
• Загрузка (части) модулей, используемых процессом, в ВАП
• Добавление инфо
Вытесняющие и невытесняющие алгоритмы планирования
невытесняющая многозадачность - это способ планирования процессов, при котором активный процесс выполняется до тех пор, пока он сам, по собственной инициативе, не отдаст управление
Задача обедающих философов.
Пять безмолвных философов сидят вокруг круглого стола, перед каждым философом стоит тарелка спагетти. Вилки лежат на столе между каждой парой ближайших философов.
Каждый фи
Официант
Относительно простое решение задачи достигается путём добавления официанта возле стола. Философы должны дожидаться разрешения официанта перед тем, как взять вилку. Поскольку официант знает, сколько
Иерархия ресурсов
Другое простое решение достигается путём присвоения частичного порядка ресурсам (в данном случае вилкам) и установления соглашения, что ресурсы запрашиваются в указанном порядке, а возвращаются в о
Страничное распределение
При страничном распределении виртуальная память делится на части одинакового и фиксированного для данной системы размера, называемымивиртуальными страницами. Вся оперативная память такж
Сегментное распределение
При страничном распределении виртуальное адресное пространство делится на равные части механически, без учета смыслового значения данных. В одной странице могут одновременно оказаться код прог
Сегментное - страничное распределение
Данный метод представляет собой комбинацию страничного и сегментного механизмов управления памятью и направлен на реализацию достоинств обоих подходов.
Виртуальная память делится на се
Виртуальная память
Виртуальная память (virtual memory) организуется операционной системой за счет использования дополнительно к оперативной памяти некоторого количества памяти на внешнем запомина
Хотите получать на электронную почту самые свежие новости?
Подпишитесь на Нашу рассылку
Наша политика приватности обеспечивает 100% безопасность и анонимность Ваших E-Mail
Новости и инфо для студентов