3) Примеры

Независимый выбор пары соседей для первой парты в классе из n учеников можно осуществить n(n-1) способами. Если предстоит рассмотреть все варианты для выбора наиболее приемлемого в некотором заданном смысле, то трудоемкость алгоритма, очевидно, оценивается как O(n²), или квадратичная. Согласно свойству (b) O-операций, собственно константа, определяющая трудоемкость каждого отдельного шага оценки "приемлемости", скрыта внутри обозначения, и даже может быть нам неизвестна.

23 Билет

1.Ядро операционной системы

Ядро - это базовая часть любой современной операционной системы (ОС), работающее в защищенном режиме и отделяющее пользовательские процессы от прямого доступа к ресурсам компьютера. Оно включает в себя драйверы устройств, механизм распределения памяти, управление процессами, связями и т.д. Разработчики ядра стараются следовать рекомендациям стандарта «IEEEStd1003.1-1988 (POSIX.1)» для обеспечения переносимости программного обеспечения с одной операционной системы на другую.

2.Системные вызовы

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

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

Все основные системные вызовы доступны посредством стандартной библиотеки libc, однако часто реализация включает в себя макрос, который в конце концов вызывает системный вызов. Для архитектуры i386 системные вызовы ограничены 5-ю аргументами, не считая номера вызова, из-за аппаратного числа регистров.

3.Примеры

К примеру, в программе можно

переопределить свой системный вызов close.

#include <syscall.h>

extern int syscall(int,...);

int my_close(int filedescriptor)

{

return syscall(SYS_close, filedescriptor);

}

В библиотеке для определения системного вызова пользуются

специальными макросами. Например, системный вызов close записывается следующим образом:

#include <syscall.h>

_syscall1 (int, close, int, filedescriptor);

Возвращаемое значение syscall может быть равным -1, если вызов неудачен, 0 или больше в случае успеха. В случае неудачи ошибку можно определить по глобальной переменной errno.

24 Билет.

1. Системный вызов dup. int dup( int oldfd );

Несмотря на то, что старый и новый дескрипторы взаимозаменяемы, мы будем сначала закрывать один из стандартных потоков. Системный вызов dup использует наименьший по номеру неиспользуемый дескриптор.

2. Системный вызов dup2. Существует другой системный вызов dup2. int dup2( int oldfd, int newfd );

Благодаря этому особенному вызову, мы имеем закрытую операцию идействующую копию за один системный вызов. Он гарантированно [неделим], т.е. никогда не будет прерван поступающим сигналом. С первым системным вызовом dup программисты были вынуждены предварительно выполнять операцию close, что приводило к наличию двух системных вызовов с малой степенью защищенности в краткий промежуток времени между ними. Если бы сигнал поступил в течение этого интервала времени, копия дескриптора не состоялась бы; dup2 разрешает эту проблему.

3. Пример: childpid = fork(); if(childpid == 0) {/* Закрываем стандартный ввод потомка */ close(0);/* Дублируем вход канала на stdin */ dup(fd[0]);execlp("sort", "sort", NULL);