Int getc(file* fp);

Считав значение, из файла fp, она увеличивает значение текущей позиции на 1. Это может привести к ситуации выхода за границу существующего файла, такую ситуацию надо корректно обрабатывать. Поэтому getc имеет тип int, и если файл кончился, то она ничего из него не считывает, а возвращает некоторое значение, которое не может быть значением одного байта. Это значение представляет собой константу EOF, продекларированную в stdio. Следует помнить, что EOF не является значением, находящимся в файле и считываемым из него, это только результат обработки ошибки.

Определение конца файла

Не всегда удобно считывать значения из файла и проверять, не равно ли значение EOF. Поэтому существует функция feof:

int feof(FILE* fp);

Если из фала можно считывать, то она возвращает значение 0, а если достигнут конец файла, то ненулевое значение.

Побайтовый вывод

Для записи одного символа в файл используется функция putc:

int putc(int value, FILE* fp);

Эта функция записывает value в текущую позицию, а затем увеличивает её значение на 1, причём запись будет осуществлена, даже если достигнут конец файла: его размер будет автоматически увеличен. Она возвращает записанное значение, либо EOF, если записать не удалось.

Изменение позиции в файле

Для принудительного изменения значения текущей позиции служит функция fseek:

int fseek(FILE* fp, long int offset, int origin);

Она увеличивает значение текущей позиции файлового указателя fp на величину offset (в том числе и отрицательную), а origin определяет, откуда ведётся отсчёт. Этим аргументом могут быть три константы, определённые в stdio:

SEEK_SET – отсчёт ведётся от начала файла.

SEEK_CUR – отсчёт ведётся от текущей позиции.

SEEK_END – отсчёт ведётся от конца файла, причём в сторону увеличения размера: если указано положительное значение offset, то файл расширяется до необходимого размера, а пустые поля заполняются нулями.

Режимы "a" и "a+" при открытии файла устанавливают текущую позицию на конец файла, туда же она устанавливается при каждом вызове функции записи, в независимости от того, где она была до вызова функции.

Получение позиции

Функция int ftell(FILE* fp); возвращает текущую позицию файлового указателя.

Рекурсивные алгоритмы. Понятие рекурсии, возможности и эффективность, решаемые классы задач.

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

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

Рекурсивный алгоритм (процедура, функция):

Ш алгоритм называется рекурсивным, если в его определении содержится прямой или косвенный вызов этого же алгоритма;

Ш рекурсивная функция - одно из математических уточнений интуитивного понятия вычислимой функции.

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

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

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

Подпрограмма - все, что находится внутри рекурсивной функции.

Основное правило рекурсии: до рекурсивного вызова должна стоять проверка на возврат из рекурсии. Существуют следующие виды рекурсии:

В данном случае функция r1( ) вызывает саму себя.

#include <iostream>

using namespace std;

void r1 (int a);

void r2 (int a);

void r3 (int a);

void r1(int a)

{

cout << "function r1" << endl;

if (a < 6)

r1(a+1);

}

int main ( )

{

r1 (0);

return NULL;

}

Одна из самых больших опасностей рекурсии - бесконечный вызов функцией самой себя.

1.2 Общие принципы программной реализации рекурсии

В программировании рекурсия - вызов функции (процедуры) из неё же самой, непосредственно (простая рекурсия) или через другие функции (сложная рекурсия), например, функция A вызывает функцию B, а функция B - функцию A. Количество вложенных вызовов функции или процедуры называется глубиной рекурсии.

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

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

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

Имеется специальный тип рекурсии, называемый «хвостовой рекурсией». Интерпретаторы и компиляторы функциональных языков программирования, поддерживающие оптимизацию кода (исходного и/или исполняемого), автоматически преобразуют хвостовую рекурсию к итерации, благодаря чему обеспечивают выполнение алгоритмов с хвостовой рекурсией в ограниченном объёме памяти. Такие рекурсивные вычисления, даже если они формально бесконечны (например, когда с помощью рекурсии организуется работа командного интерпретатора, принимающего команды пользователя), никогда не приводят к исчерпанию памяти.

Нужно учитывать одну особенность, характерную для рекурсивных программ, подобных той, которую используют для генерации чисел Фибоначчи. Каждый уровень рекурсии в функции fibonacci удваивает количество вызовов, так что количество рекурсивных вызовов, которое должно быть выполнено для вычисления n - го числа Фибоначчи, оказывается порядка 2N.

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

может не быть очевидным.

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

параметрами. В современных системах программирования корректное функционирование подпрограмм, особенно рекурсивных, обеспечивается с помощью стека.

Программная обработка данных.

Программная обработка данных на компьютере

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

Данные — это информация, которая обрабатывается компьютером в двоичном компьютерном коде.

Программы. Для того чтобы компьютер «знал», что ему делать с данными, как их обрабатывать, он должен получить определенную команду (инструкцию). Например: «сложить два числа»; «заменить один символ в тексте на другой».

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

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

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

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

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

Обменная сортировка: идеи, преимущества и недостатки.

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

Алгоритм называют пузырьковой сортировкой, потому что на каждом шаге наибольший элемент не отсортированной части подобно пузырьку газа в воде всплывает вверх.

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

Для этого вводят логическую переменную Flag - признак совершения обмена на очередном проходе:

for k := N-1 downto 1 do

begin

Flag := false;

for j := 1 to k do

if a[j]>a[j+1] then

begin

Tmp := A[j]; A[j] := A[j+1]; A[j+1] := Tmp;

Flag := true;

end;

if not Flag then Break;

end;

Этот алгоритм имеет среднюю и максимальную временную эффективность O(n2) (два вложенных цикла, зависящих от n линейно) и не требует дополнительной памяти за исключением памяти для фиксированного числа переменных (i, j, Tmp, Flag).

Сортировка путём подсчётом: идеи, преимущества и недостатки.

Сортировка подсчётом — алгоритм сортировки, в котором используется диапазон чисел сортируемого массива (списка) для подсчёта совпадающих элементов. Применение сортировки подсчётом целесообразно лишь тогда, когда сортируемые числа имеют (или их можно отобразить в) диапазон возможных значений, который достаточно мал по сравнению с сортируемым множеством, например, миллион натуральных чисел меньших 1000. Эффективность алгоритма падает, если при попадании нескольких различных элементов в одну ячейку, их надо дополнительно сортировать. Необходимость сортировки внутри ячеек лишает алгоритм смысла[уточнить], так как каждый элемент придётся просматривать более одного раза.

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

Простой алгоритм[править]

Это простейший вариант алгоритма. Создать вспомогательный массив C[0..k - 1], состоящий из нулей, затем последовательно прочитать элементы входного массива A, для каждого A[i] увеличить C[A[i]] на единицу. Теперь достаточно пройти по массиву C, для каждого в массив A последовательно записать число j C[j] раз.

SimpleCountingSort

for i = 0 to k - 1

C[i] = 0;

for i = 0 to n - 1

C[A[i]] = C[A[i]] + 1;

b = 0;

for j = 0 to k - 1

for i = 0 to C[j] - 1

A[b] = j;

b = b + 1;

 

Сортировка методом Вставок: Идеи Преимущества и недостатки.

Сортировка вставками -- простой алгоритм сортировки. Хотя этот метод сортировки намного менее эффективен, чем более сложные алгоритмы (такие как быстрая сортировка), у него есть ряд преимуществ:

прост в реализации;

эффективен на небольших наборах данных, на наборах данных до десятков элементов может оказаться лучшим;

эффективен на наборах данных, которые уже частично отсортированы;

это устойчивый алгоритм сортировки (не меняет порядок элементов, которые уже отсортированы);

может сортировать список по мере его получения;

не требует временной памяти, даже под стек.

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

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

1.1 Простые вставки

1.2 Бинарные вставки

Когда при сортировке простыми вставками обрабатывается j-я запись, ее ключ сравнивается в среднем примерно с j/2 ранее отсортированными ключами; поэтому общее число сравнений равно приблизительно (1 +2+ ... +N) /2 ? 4 N2 , а это очень много, даже если N умеренно велико. Методы "бинарного поиска" указывают, куда вставлять j-й элемент после приблизительно j 2 log соответствующим образом выбранных сравнений.

Например, если вставляется 64-я запись, можно сначала сравнить ключ K64 с K32; затем, если он меньше, сравниваем его с K16, если больше.с K48 и т. д., так что место для R64 будет найдено после всего лишь шести сравнений. Общее число сравнений для N вставляемых элементов равно приблизительно N N 2 log , что существенно лучше, чем 4

Сортировка посредством выбора: идеи, преимущества и недостатки.

Сортировка посредством выбора

При сортировке посредством выбора[1] из массива выбирается элемент с наименьшим значением и обменивается с первым элементом. Затем из оставшихся n - 1 элементов снова выбирается элемент с наименьшим ключом и обменивается со вторым элементом, и т.д. Эти обмены продолжаются до двух последних элементов. Например, если применить метод выбора к массиву dcab, каждый проход будет выглядеть так, как показано ниже:

Начало d c a b

Проход 1 a c d b

Проход 2 a b d c

Проход 3 a b c d

Нижеследующий код демонстрирует простейшую сортировку посредством выбора:

/* Сортировка посредством выбора. */

void select(char *items, int count)

{

register int a, b, c;

int exchange;

char t;

for(a=0; a < count-1; ++a) {

exchange = 0;

c = a;

t = items[a];

for(b=a+1; b < count; ++b) {

if(items[b] < t) {

c = b;

t = items[b];

exchange = 1;

}

}

if(exchange) {

items[c] = items[a];

items[a] = t;

}

}

}

К сожалению, как и в пузырьковой сортировке, внешний цикл выполняется n - 1 раз, а внутренний — в среднем n/2 раз. Следовательно, сортировка посредством выбора требует

1/2(n2-n)

сравнений. Таким образом, это алгоритм порядка n2, из-за чего он считается слишком медленным для сортировки большого количества элементов. Несмотря на то, что количество сравнений в пузырьковой сортировке и сортировке посредством выбора одинаковое, в последней количество обменов в среднем случае намного меньше, чем в пузырьковой сортировке.

Верификация и отладка программы.

Верификацией и аттестацией называют процессы проверки и анализа, в ходе которых проверяется соответствие программного обеспечения своей спецификации и требованиям заказчиков. Верификация и аттестация охватывают полный жизненный цикл ПО — они начинаются на этапе анализа требований и завершаются проверкой программного кода на этапе тестирования готовой программной системы.

Верификация и аттестация не одно и то же, хотя их легко перепутать. Кратко различие между ними можно определить следующим образом:

Верификация ПО отвечает на вопрос, правильно ли создана система.

Аттестация ПО отвечает на вопрос, правильно ли работает система.

Процесс отладки включает:

 действия, направленные на выявление ошибок (тестирование);

 диагностику и локализацию ошибок (определение характера ошибок и их местонахождение);

 внесение исправлений в программу с целью устранения ошибок.

Из трех перечисленных видов работ самым трудоемким и дорогим является тестирование, затраты на которое приближаются к 45 % общих затрат на разработку ПС.

Технологии структурного и объектно-ориентированного программирования.

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

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

указание последовательности выполнения технологических операций;

перечисление условий, при которых выполняется та или иная операция;

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

Кроме набора операций и их последовательности, технология также определяет способ описания

проектируемой системы, точнее модели, используемой на конкретном этапе разработки.

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

Другим базовым принципом структурного программирования является использование при составлении программ только базовых алгоритмических структур (см. билет 4), запрет на использование оператора GOTO.

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

также специальный метод проектирования алгоритмов — метод пошаговой детализации.

Поддержка принципов структурного программирования была заложена в основу так называемых процедурных языков программирования. Как правило, они включали основные "структурные" операторы передачи управления, поддерживали вложение подпрограмм, локализацию и ограничение области "видимости" данных. Среди наиболее известных языков этой группы стоит назвать PL/1, ALGOL-68, Pascal, С.

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

Основным достоинством объектно-ориентированного программирования по сравнению с модульным программированием является "более естественная" декомпозиция программного обеспечения, которая существенно облегчает его разработку. Это приводит к более полной локализации данных и интегрированию их с подпрограммами обработки, что позволяет вести практически независимую разработку отдельных частей (объектов) программы. Кроме этого, объектный подход предлагает новые способы организации программ, основанные на механизмах наследования, полиморфизма, композиции, наполнения. Эти механизмы позволяют конструировать сложные объекты из сравнительно простых. В результате существенно увеличивается показатель повторного использования кодов и появляется возможность создания библиотек классов для различных применений.

Можно дать обобщающее определение: объект ООП — это совокупность переменных состояния и связанных с ними методов (операций). Упомянутые методы определяют, как объект взаимодействует с окружающим миром.

Жизненный цикл ПО. Виды процессов проектирования ПО.

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

1. анализ требований,

2. проектирование,

3. кодирование (программирование),

4. тестирование и отладка,

5. эксплуатация и сопровождение.

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

Эксплуатация включает работы по внедрению компонентов ПО в эксплуатацию, в том числе конфигурирование БД и рабочих мест пользователей, обеспечение эксплуатационной документацией, проведение обучения персонала и т.д., и непосредственно эксплуатацию, в том числе локализацию проблем и устранение причин их возникновения, модификацию ПО в рамках установленного регламента, подготовку предложений по совершенствованию, развитию и модернизации системы.

Управление проектом связано с вопросами планирования и организации работ, создания коллективов разработчиков; контроля за сроками и качеством выполняемых работ.

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

Обеспечение качества проекта связано с проблемами верификации, проверки и тестирования ПО.

Верификация – это процесс определения насколько текущее состояние разработки, достигнутое на данном этапе, отвечает требованиям этого этапа.

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

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

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

Управление конфигурацией – один из вспомогательных процессов, поддерживающих основные процессы жизненного цикла ПО, прежде всего процессы разработки и сопровождения ПО ИС.

Назначение процесса планирования ПО состоит в том, чтобы определить методы создания такого ПО, которое позволит реализовать системные требования и обеспечить уровень качества, соответствующий требованиям настоящего стандарта. Таблица А.1 содержит резюме целей и результатов процесса планирования ПО в зависимости от уровня ПО.

Цели процесса планирования ПО:

а) определить конкретные виды работ процессов разработки и интегральных процессов жизненного цикла, которые позволят реализовать системные требования и создать ПО требуемого уровня (6.2);

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

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

г) в случае необходимости рассмотреть дополнительные аспекты разработки, обсуждаемые в разделе 13;

д) определить стандарты разработки, позволяющие обеспечить требования по безопасности системы в части разрабатываемого ПО (6.5);

е) разработать документы процесса планирования ПО в соответствии с 6.3 и разделом 12;

ж) координировать разработку и изменение планов ПО (6.3).

Структурное и модульное программирование. Основные понятия.

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

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

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

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

Таким образом, для модуля должны быть определены

1) алгоритм решения задачи;

2) область допустимых входных значений;

3) область возможных выходных значений;

4) возможные побочные эффекты.

Технологии

Потоки программ. Создание и управление потоками.

Пото́к выполне́ния (тред; от англ. thread — нить) — наименьшая единица обработки, исполнение которой может быть назначено ядром операционной системы. Реализация потоков выполнения и процессов в разных операционных системах отличается друг от друга, но в большинстве случаев поток выполнения находится внутри процесса. Несколько потоков выполнения могут существовать в рамках одного и того же процесса и совместно использовать ресурсы, такие как память, тогда как процессы не разделяют этих ресурсов. В частности, потоки выполнения разделяют инструкции процесса (его код) и его контекст (значения переменных, которые они имеют в любой момент времени). В качестве аналогии потоки выполнения процесса можно уподобить нескольким вместе работающим поварам. Все они готовят одно блюдо, читают одну и ту же кулинарную книгу с одним и тем же рецептом и следуют его указаниям, причём не обязательно все они читают на одной и той же странице.

На одном процессоре многопоточность обычно происходит путём временного мультиплексирования (как и в случае многозадачности):процессор переключается между разными потоками выполнения. Это переключение контекста обычно происходит достаточно часто, чтобы пользователь воспринимал выполнение потоков или задач как одновременное. В многопроцессорных и многоядерных системах потоки или задачи могут реально выполняться одновременно, при этом каждый процессор или ядро обрабатывает отдельный поток или задачу.

Потоки выполнения отличаются от традиционных процессов многозадачной операционной системы тем, что:

1. процессы, как правило, независимы, тогда как потоки выполнения существуют как составные элементы процессов

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

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

4. процессы взаимодействуют только через предоставляемые системой механизмы связей между процессами

5. переключение контекста между потоками выполнения в одном процессе, как правило, быстрее, чем переключение контекста между процессами.

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

Функция getpid(2), возвращает значение идентификатора группы потока, независимо от того, из какого потока она вызвана. Функции kill() waitpid() и им подобные по умолчанию также используют идентификаторы групп потоков, а не отдельных процессов

#include <sys/types.h>

#include <linux/unistd.h>

...

_syscall0(pid_t,gettid);

...

pid_t my_tid;

my_tid = gettid();

Потоки создаются функцией pthread_create(3), определенной в заголовочном файле <pthread.h>. Первый параметр этой функции представляет собой указатель на переменную типа pthread_t, которая служит идентификатором создаваемого потока. Второй параметр, указатель на переменную типа pthread_attr_t, используется для передачи атрибутов потока. Третьим параметром функции pthread_create() должен быть адрес функции потока. Эта функция играет для потока ту же роль, что функция main() – для главной программы. Четвертый параметр функции pthread_create() имеет тип void *.

Функция потока должна иметь заголовок вида: