#include<stdio.h>
void main()
{
printf("Hello World\n");
exit(0);
}
Текстовый — наименьший "inpedance mismatch", следовательно наиболее простая разработка.
Shell есть в любой ОС. Даже в стандарте POSIX: Shell Command Language
Окружение — это контекст текущего процесса Shell. В Unix оно определяется переменными окружения. Вообще говоря, у любого процесса есть определенные ресурсы: общие (разделяемые) и индивидуальные. Окружение относится к индивидуальным, в то время как файловая система — к разделяемым.
$ env ... $ echo $PATH ... $ PATH=/tmp ... $ env bash: env: command not found $ export PATH=/tmp ... $ source PATH=/tmp ...
<цель>: <другие цели, от которых зависит эта>
<набор shell-команд>
Всеволод Дёмкин <vseloved@gmail.com>
Лицензия на использование: Creative Commons Attribution-Noncommercial-Share Alike 3.0 Unported License
Базовая оценка: 1 балл
Написать на любом языке программирования (подсказка: проще всего на языке со скриптинговыми возможностями) скрипт, который выдаст отчет по текстовому лог-файлу log.txt с таким содержанием:
Хит — это одна загрузка веб-страницы по данному адресу.
Пример записи в лог-файле:host-24-225-218-245.patmedia.net - - [01/Oct/2006:06:33:45 -0700] "GET /example/example.atom HTTP/1.1" 304 - "-" "NetNewsWire/2.0b37 (Mac OS X; Lite; http://ranchero.com/netnewswire/)"
Формат записи: <DNS клиента> - - [<Штамп времени>] <Строка HTTP-запроса (тип, URL, версия)> <Код HTTP-ответа> <Количество переданных байт> <Строка реферера> <Название клиента>
С помощью GNU Assembler (GAS) или Netwide Assembler (NASM) в ОС Linux создать утилиту обработки файлов, которая реализует один из перечисленных ниже алгоритмов:
Для минимальной оценки — XOR-шифрование. Запускаться она должна так:Шифрование: $ ./xorc -e <входной файл> <зашифрованный файл> Расшифровка: $ ./xorc -d <зашифрованный файл> <расшифрованный файл> В результате содержимое входного и расшифрованного файлов должно быть идентичным.
Иначе — по вариантам:
Шифрование: $ ./tea -e <исходный файл> <зашифрованный файл> Расшифровка: $ ./tea -d <зашифрованный файл> <расшифрованный файл> В результате содержимое исходного и расшифрованного файлов должно быть идентичным.
Получение дельта-файла: $ ./deltac <исходный файл> <измененный файл> <дельта-файл> Наложение дельта-файла: $ ./deltac -d <исходный файл> <дельта-файл> <результирующий файл> В результате содержимое измененного и результирующего файлов должно быть идентичным.
Вычисление суммы: $ ./bsdsum <исходный файл> <файл с сумой> Проверка суммы: $ ./bsdsum -c <файл с сумой> <файл> - результат (true или false) выводится на экран
Вычисление суммы: $ ./crc32sum <исходный файл> <файл с сумой> Проверка суммы: $ ./crc32sum -c <файл с сумой> <файл> - результат (true или false) выводится на экран
Вычисление суммы: $ ./adler32sum <исходный файл> <файл с сумой> Проверка суммы: $ ./adler32sum -c <файл с сумой> <файл> - результат (true или false) выводится на экран
Писать на АСМе сейчас практически не нужно. Но ВСЕГДА рано или поздно сталкивался с тем, что нужно уметь читать АСМ. Либо для того, чтобы сделать действительно оптимальный код, либо — что гораздо чаще — чтобы суметь правильно прочитать stack trace и поймать эту самую чертову ошибку. Мне довольно часто приходилось видеть этот "кошмар прикладного программиста", когда большая и сложная программа валится на невнятном сообщении "выполнена недопустимая операция". И без знания АСМа понять, что случилось, невозможно.
Языки ассемблеров были первыми "высокоуровневыми" языками по сравнению с программированием непосредственно в адресных кодах. В них появились:
mov, push, ...) вместо кодов операций
55
89 E5
83 EC 08
C7 45 FC 01 00 00 00
83 EC 0C
6A 00
E8 D1 FE FF FF
push %ebp
mov %esp, %ebp
sub $0x8, %esp
movl $0x1, -4(%ebp)
sub $0xc, %esp
push $0x0
call 8048348
int main()
{
int i = 1;
exit(0);
}
Еще один пример — классический Hello World
#include <stdio.h>
int main()
{
printf("hello, world");
return 0;
};
преобразованный в ассемблер компилятором MSVC (cl 1.cpp /Fa1.asm):
CONST SEGMENT
$SG3830 DB 'hello, world', 00H
CONST ENDS
PUBLIC _main
EXTRN _printf:PROC
; Function compile flags: /Odtp
_TEXT SEGMENT
_main PROC
; File c:\...\1.cpp
; Line 4
push ebp
mov ebp, esp
; Line 5
push OFFSET $SG3830
call _printf
add esp, 4
; Line 6
xor eax, eax
; Line 7
pop ebp
ret 0
_main ENDP
_TEXT ENDS
и компилятором GCC:
.file “ctest.c”
.version “01.01”
gcc2_compiled.:
.section .rodata
.LC0:
.string “Hello, world!\n”
.text
.align 16
.globl main
.type main,@function
main:
pushl %ebp
movl %esp, %ebp
subl $8, %esp
subl $12, %esp
pushl $.LC0
call printf
addl $16, %esp
subl $12, %esp
pushl $0
call exit
.Lfe1:
.size main,.Lfe1-main
.ident “GCC: (GNU) 2.96 20000731 (Linux-Mandrake 8.0 2.96-0.48mdk)”
Это частично определяемый аппаратной архитектурой и частично конкретной средой исполнения механизм вызова подпрограмм. Соглашения включают ответы на вопросы: как передаются/возвращаются аргументы, как распределяется работа при вызове/завершении подпрограммы.
Конкретные примеры реализации:
push eAX ; последний аргумент — содержимое регистра eAX push byte[eBP+20] ; предпоследний аргумент — содержимое ячейки памяти по адресу = адрес в eBP + 20 байт push 3 ; первый аргумент — константа 3 call calc ; вызов подпрограммы calc, возвращаемое значение будет в eAXТипичная структура подпрограммы:
calc: push eBP ; сохранить указатель на стек mov eBP,eSP ; получить новый указатель на стек sub eSP,4*3 ; выделить место для локальных переменных ... ; произвести вычисления, в конце концов результат записать в eAX mov eSP,eBP ; "освободить" место, занимаемое локальными переменными pop eBP ; восстановить указатель на стек ret 0 ; вернуться в место вызова
Не используя клиентские библиотеки, а работая напрямую с HTTP-протоколом, связаться с сервером хранения/обработки данных и выполнить простую последовательность команд.
Базовые варианты:
Продвинутые варианты:
Не используя клиентские библиотеки, а работая напрямую с сокетными соединениями, связаться с сервером хранения/обработки данных и выполнить определенную простую последовательность команд (в зависимости от варианта). Сами команды и их результат отображать на экране.
Базовые варианты:
Продвинутые варианты:
Последовательность команд:
Изначальное определение: это эффективный изолированный дупликат реальной машины.
С точки зрения целевого предназначения:
Типы:
На минимальную оценку: на любом языке программирования реализовать задачу Производитель-потребитель с помощью классической синхронизации и передачи сообщений.
Иначе — по вариантам:http://en.wikipedia.org/wiki/Producer-consumer_problem
Есть буффер ограниченного размера N, к которому имеют доступ 2 нити: производитель и потребитель. Производитель в бесконечном цикле генерирует пакет данных в течение случайного интервала времени и записывает их в буфер в течение какого-то времени t1, если в нем есть свободное место. Потребитель в бесконечном цикле считывает и удаляет данные из буфера (если они там есть) по 1 пакету в течение времени t2, а затем случайный интервал времени обрабатывает их.
Задание: Необходимо смоделировать эту ситуацию в программе в виде 2 нитей исполнения (производителя и потребителя). Работа нитей должна фиксироваться в виде журнала и отображаться на экране. Например (размер буфера: 20):12:01:10.353 Производитель создал новый пакет данных. В буфере: 19 12:01:11.353 Производитель записал пакет в буфер. В буфере: 20 12:01:11.700 Производитель создал новый пакет данных. В буфере: 20 12:01:11.701 Производитель ожидает. В буфере: 20 12:01:11.910 Потребитель считал пакет из буфера. В буфере: 19 12:01:13.011 Потребитель обработал данные. В буфере: 19 12:01:14.005 Потребитель считал пакет из буфера. В буфере: 18 12:01:14.243 Производитель записал пакет в буфер. В буфере: 19 ...
http://en.wikipedia.org/wiki/Readers-writers_problem
Есть общий участок памяти, N нитей исполнения, которые только читают из него (читатели), и M нитей, которые только пишут в него (писатели). Когда какая-то из нитей производит запись, остальные нити не должны иметь доступа к памяти.
Задание: Необходимо обеспечить, чтобы чтение могло происходить несколькими нитями одновременно. Необходимо обеспечить, чтобы каждый писатель ждал возможности записи не больше необходимого (т.е. если писатель запросил запись в то время, как какие-то нити читали, он должен ожидать права записи только до того момента, как эти нити закончат чтение, но не до того момента, как его закончат другие, которые могли бы начать чтение позже, чем писатель запросил запись).
Отображение работы программы должно быть подобно задаче Производитель-потребитель.
http://en.wikipedia.org/wiki/Sleeping_barber_problem
В парикмахерской работает 1 парикмахер, у которого есть 1 кресло для стрижки, и N кресел для ожидания клиентов. Клиенты приходят к парикмахеру через случайные промежутки времени. Когда клиентов нет, парикмахер спит в кресле. Когда приходит клиент он будит парикмахера и начинается стрижка. Если парикмахер стрижет кого-то, клиент садится в одно из свободных кресел. Если все кресла заняты, клиент уходит. Когда парикмахер освобождается, он начинает стричь клиента, который ждет дольше всего, или засыпает, если в очереди нет клиентов. Время стрижки клиента также является случайной величиной.
Задание: Смоделировать эту ситуацию, избежав появления возможностей создания ситуаций deadlock и голодание. Результаты работы программы должны отображаться также, как и в предыдущих задачах, например:12:01:10.353 Парикмахер спит. 12:01:11.412 Клиент 1 пришел в парикмахерску. Очередь: 0 12:01:11.700 Клиент 1 будит парикмахера. 12:01:11.701 Клиент 1 садится на стрижку. Очередь: 0 12:01:11.910 Клиент 2 пришел в парикмахерскую. Очередь: 0 12:01:11.815 Клиент 2 садится в кресло для ожидания. Очередь: 1 12:01:14.810 Клиент 3 пришел в парикмахерскую. Очередь: 1 12:01:14.951 Клиент 1 постригся и уходит из парикмахерской. 12:01:15.115 Клиент 3 садится в кресло для ожидания. Очередь: 2 12:01:15.222 Клиент 1 садится на стрижку. Очередь: 1 ...
http://en.wikipedia.org/wiki/Dining_philosophers_problem
5 философов сидят за столом. Они могут быть в 2-х взаимоисключающих состояниях: думать и есть. Между каждым философом лежит 1 вилка, а перед каждым -- тарелка. Для того чтобы начать есть, философу нужно взять 2 вилки (левую и правую). Сначала философ берет левую, а затем правую.
Задание: Необходимо смоделировать эту ситуацию в программе в виде 5 нитей исполнения (для каждого философа). Работа нитей должна фиксироваться в виде журнала и отображаться на экране. Например:12:01:10.353 Философ 1 думает. Состояни вилок: 01100 12:01:10.389 Философ 5 взял левую вилку (№5). Состояни вилок: 01101 12:01:10.390 Философ 5 взял правую вилку (№1). Состояни вилок: 11101 12:01:10.391 Философ 5 начал есть. 12:01:11.800 Философ 3 закончил есть. 12:01:11.812 Философ 4 взял левую вилку (№4). Состояни вилок: 11111 12:01:11.813 Философ 4 не смог взять правую вилку (№5). Состояни вилок: 11111 12:01:11.815 Философ 2 положил левую вилку (№2). Состояни вилок: 10111 ...
При этом не должно возникать ситуаций deadlock, когда каждый философ взял по одной вилке и ожидает вторую вилку.
По мотивам проекта Wide Finder 2
Имеется текстовый файл log.txt, сожержащий записи access log сервера Apache.
Формат записи:<DNS клиента> - - [<Штамп времени с временной зоной>] <Строка HTTP-запроса (тип, URL, версия)> <Код HTTP-ответа> <Количество переданных байт или '-', если ответ не имеет тела> <Строка реферера ('-' означает прямой запрос без реферера)> <Название клиента>
Пример записи:host-24-225-218-245.patmedia.net - - [01/Oct/2006:06:33:45 -0700] "GET /example/example.atom HTTP/1.1" 304 - "-" "NetNewsWire/2.0b37 (Mac OS X; Lite; http://ranchero.com/netnewswire/)"
Написать Shell-скрипт, который по этому файлу расчитает и выдаст в консоль такие величины:
Оценка за каждый пункт — 2 балла.
Подсказка: команды Shell, которые могут пригодиться: grep, cut, sort и uniq, awk
Литература:
Сроки сдачи: 5.10.2011
С помощью GNU Assembler (GAS) или Netwide Assembler (NASM) в ОС Linux создать утилиту обработки файлов, которая реализует алгоритм подсчета Контрольной суммы CRC по одному из модулей (ниже). В программе не использовать библиотечные функции (только системные вызовы и операции ассемблера).
Программа должна запускаться так:Печать ФИО, номера зачетки и модуля: ./crc -v Результат (строка вида "Vasya Pupkin IS-8201 CRC-4-ITU x4 + x + 1") выводится в STDOUT Вычисление суммы: ./crc <имя файла> Результат (число) выводится в STDOUT Проверка суммы: ./crc -c <сумма> <имя файла> Результат (true или false) выводится в STDOUTМодуль в зависимости от последних двух цифр номера зачетки:
01 - CRC-4-ITU 02 - CRC-5-EPC 03 - CRC-5-ITU 04 - CRC-5-USB 05 - CRC-6-ITU 06 - CRC-7 07 - CRC-8-CCITT 08 - CRC-8-Dallas/Maxim 09 - CRC-8 10 - CRC-8-SAE J1850 11 - CRC-8-WCDMA 12 - CRC-10 13 - CRC-11 14 - CRC-12 15 - CRC-15-CAN 16 - CRC-16-IBM 17 - CRC-16-CCITT 18 - CRC-16-T10-DIF 19 - CRC-16-DNP 20 - CRC-16-DECT 21 - CRC-16-Fletcher 22 - CRC-24 23 - CRC-24-Radix-64 24 - CRC-30 25 - CRC-32 26 - CRC-32C 27 - CRC-32K 28 - CRC-32Q 29 - CRC-40-GSM 30 - CRC-64-ISO
Оценка — 10 баллов.
Литература:
Сроки сдачи: 19.10.2011 (перненосится на 26.10.2011)
Написать на языке С 2 программы, которые, симулируют некоторые функции bash (запуск процессов, перенаправление ввода-вывода) с помощью системных вызовов (fork, exec, kill, signal, wait, waitpid, dup2, open, sleep, pipe,...). Программы должны работать следующим образом:
prog1:
[0] echo 'tail -f $1' > /tmp/rtail
[1] /tmp/rtail ~/.bash_history >> /tmp/1.txt &
PID процесса [1] должен быть сохранен.
[2] Ожидает завершения команды, запущенной на шаге [1]. После завершения выводит: "Program 1 terminated."
prog2:
[3] Выводит на экран: "Program 2 started."
[4] устанавливает обработчики следующих сигналов:
на экране должен быть вывод соответствующей команды
[5] sleep 30
[6] kill PID
PID — это PID процесса, запущенного в строчке [1].
[7] После завершения выводит: "Program 2 terminated."
Т.е. в задании все вызовы cat, sleep, kill, а также конструкции |, >, >>, & должны быть заменены на соответствующие системые вызовы (и/или последовательность вызова функций в С).
./prog1 & ./prog2
Оценка: 10 баллов
Литература:
Срок сдачи: 2.11.2011
Необходимо на языке C средствами библиотеки PThreads смоделировать одну из классических задач синхронизации.
Есть общий ресурс, N нитей исполнения, которые только читают из него (читатели), и M нитей, которые только пишут в него (писатели). Когда какая-то из нитей производит запись, остальные нити не должны иметь доступа к ресурсу.
12:01:10.353 Читатель 1 хочет читать данные. Ресурс не занят. 12:01:10.354 Читатель 1 начал чтение. 12:01:10.453 Читатель 2 хочет читать данные. Читатель 1 читает ресурс. 12:01:10.456 Читатель 2 начал чтение. 12:01:11.000 Писатель 1 хочет писать данные. Читатели 1, 2 читают ресурс. 12:01:11.001 Писатель 1 ожидает. 12:01:11.100 Читатель 1 закончил чтение. Читатель 2 читает ресурс. Писатель 1 ожидает. 12:03:08.500 Читатель 3 хочет читать данные. Читатель 2 читает ресурс. Писатель 1 ожидает. 12:03:08.501 Читатель 3 ожидает. Читатель 2 читает ресурс. Писатель 1 ожидает. 12:05:11.100 Читатель 2 закончил чтение. Ресурс свободен. Писатель 1 ожидает. Читатель 3 ожидает. 12:05:11.105 Писатель 1 начал запись. Писатель 1 пишет. Читатель 3 ожидает. ...
В парикмахерской работает 1 парикмахер, у которого есть 1 кресло для стрижки, и N кресел для ожидания клиентов. Клиенты приходят к парикмахеру через случайные промежутки времени. Когда клиентов нет, парикмахер спит в кресле. Когда приходит клиент он будит парикмахера и начинается стрижка. Если парикмахер стрижет кого-то, клиент садится в одно из свободных кресел. Если все кресла заняты, клиент уходит. Когда парикмахер освобождается, он начинает стричь клиента, который ждет дольше всего, или засыпает, если в очереди нет клиентов. Время стрижки клиента также является случайной величиной.
В этой задаче необходимо избежать появления ситуаций deadlock или голодание.
Результаты работы программы должны отображаться по мере их появления следующим образом:12:01:10.353 Парикмахер спит. 12:01:11.412 Клиент 1 пришел в парикмахерску. Очередь: 0 12:01:11.700 Клиент 1 будит парикмахера. 12:01:11.701 Клиент 1 садится на стрижку. Очередь: 0 12:01:11.910 Клиент 2 пришел в парикмахерскую. Очередь: 0 12:01:11.815 Клиент 2 садится в кресло для ожидания. Очередь: 1 12:01:14.810 Клиент 3 пришел в парикмахерскую. Очередь: 1 12:01:14.951 Клиент 1 постригся и уходит из парикмахерской. 12:01:15.115 Клиент 3 садится в кресло для ожидания. Очередь: 2 12:01:15.222 Клиент 1 садится на стрижку. Очередь: 1 ...
5 философов сидят за столом. Они могут быть в 2-х взаимоисключающих состояниях: думать и есть. Между каждым философом лежит 1 вилка, а перед каждым — тарелка. Для того чтобы начать есть, философу нужно взять 2 вилки (левую и правую). Сначала философ берет левую, а затем правую.
Необходимо избежать ситуаций deadlock или голодание.
Результаты работы программы должны отображаться по мере их появления следующим образом:12:01:10.353 Философ 1 думает. Состояние вилок: 01100 12:01:10.389 Философ 5 взял левую вилку (№5). Состояние вилок: 01101 12:01:10.390 Философ 5 взял правую вилку (№1). Состояние вилок: 11101 12:01:10.391 Философ 5 начал есть. 12:01:11.800 Философ 3 закончил есть. 12:01:11.812 Философ 4 взял левую вилку (№4). Состояние вилок: 11111 12:01:11.813 Философ 4 не смог взять правую вилку (№5). Состояние вилок: 11111 12:01:11.813 Философ 4 положил левую вилку. Состояние вилок: 11101 12:01:11.815 Философ 2 положил левую вилку (№2). Состояние вилок: 10101 ...
Задания по вариантам (номер варианта — остаток от деления номера зачетки на 3 плюс 1):
Литература:
Оценка: 10 баллов.
Дополнительно можно решить любую из 3х задач методом передачи сообщений на языке Erlang или с помощью STM на языке Clojure — +10 баллов.
Срок сдачи: 16.11.2011
На языке С/C++, не используя клиентские библиотеки, а работая напрямую с сокетными соединениями, связаться с сервером хранения/обработки данных и выполнить определенную простую последовательность команд (в зависимости от варианта). Сами команды и их результат отображать на экране.
Базовые варианты (номер варианта равен остатку от деления номера зачетки на 3, увеличенному на 1 ) — оценка 10 баллов:
Продвинутые варианты - можно выбрать любой (оценка 20 баллов):
Последовательность команд:
Сроки сдачи: 30.11.2011
С помощью библиотеки FUSE создать виртуальную файловую систему, дерево которой задано в файле заданий. Номер варианта — последняя цифра номера зачетки. Файловая должна монтироваться в режиме только чтение, после чего должна быть возможность осуществить листинг ее директорий и просмотр содержимого виртуальных файлов. При обращении к файловой системе должны проверяться права доступа (маска прав указана в файле задания). Владельцем всех файлов должен быть текущий пользователь, который выполняет монтирование системы.
Файловая система содержит 4 директории: bin, test, txt и zdir. А также 4 файла, из которых 3 — текстовые файлы: example, readme.txt, test,— и 1 бинарный файл по варианту (содержимое бинарного файла должно быть взято из соответствующей стандартной системной утилиты: ls, grep, pwd,...) Содержимое остальных файлов:
Оценка: 10 баллов
Срок сдачи: 31.12.2011
Дополнительно реализовать следующие операции:
Императивный подход — исторически первый подход к программированию компьютеров, который применялся с момента их появления. Его суть в том, чтобы дать компьютеру точную команду, что и как нужно сделать, например переместить содержимое ячейки памяти по такому-то адресу в такой-то регистр. Таким образом происходило программирование в адресных кодах, затем в ассемблере, затем в первом "высокоуровневом" языке Fortran, затем в C и т.д. до наших дней. Иными словами, этот подход постепенно эволюцтонировал по мере развития мейнстрим инструментов и языков разработки. Эта эволюция постепенно прошла через стадии: "наивного" (без четко определенных правил и парадигм) программирования, структурного, затем объектно-ориентированного и скриптингового, которые являются основными на сегодняшний день.
Если первым "высокоуровневым" языком программирования был Fortran, то вторым — Lisp — первый представитель совсем другой модели вычислений. Декларативный подход ставит своей целью описать не детали выполнения, а требуемый результат каких-то операций.
Лямбда исчисление Черча является основой большинства (хотя и не всех) декларативных парадигм.
Хороший кейс дл сравнения императивного и декларативного подходов — это навигационные и реляционные БД и использующиеся для запросов к ним языки: FoxPro и SQL.
Основанно на модели формальной логики предикатов I порядка. В рамках него появились такие подходы к вычислениям как:
Обобщение операций над скалярными данными на матричные операции. Основные идеи:
Лабораторная работа может быть прислана на email <vseloved@gmail.com> в виде zip-архива, содержащего файлы исходного кода в сопровождении краткого описания (файл README) и файлов, необходимых для сборки (как правило, файл Makefile). Названия всех файлов на английском языке. Либо сдана лично на занятии. Программа должна выполняться в среде Linux.
Если работа сдана до крайнего срока, то оценка выставляется за точность, качество и полноту выполнения заданий (количество баллов указано в задании к каждой работе). При сдаче работы после установленного срока оценка за работу снижается на 1 балл каждую неделю.
Работа будет проверена на плагиат путем сравнения с помощью утилиты diff с другими уже сданными работами.
Для работ присланных по email:
Таблица результатов будет опубликована в Интернет.
Необходимо выбрать Open-source проект, связанный с системным программированием, и реализовать в нем какую-то новую функцию. Эта функция должна быть принята мейнтенером проекта.
Кроме того, необходимо обосновать выбор способа решения, сравнить его с другими. Также необходимо создать автоматические тесты, подтверждающие надежность решения и документацию по его установке и использованию.
Найти подходящие проекты можно здесь:
Задание выполняется в группе 2-3 человека.
Синхронизация процессов — одна из важных проблем, возникающих в параллельном программировании. Часто требуется реализовать эксклюзивный доступ к неким данным. Для решения этой проблемы были разработаны несколько подходов, некоторые из которых будут рассмотрены здесь.
Семафоры являются одной из первых концепций синхронизации процессов. Они придуманы в 1965–м году Эдсгером Вайбом Дейкстрой.
Семафор представляет из себя целую неотрицательную переменную, доступ процессов к которой (за исключением момента инициализации) осуществляется с помощью двух атомарных операций: P (от датского слова proberen — проверять) и V (от verhogen – увеличивать).
Традиционно данные операции определяются следующим образом:P(S): пока S == 0 процесс блокируется;
S = S – 1;
V(S): S = S + 1;semaphores.h) содержит функции sem_init(), sem_wait(), sem_post(), sem_getvalue() и sem_destroy(), а также специальный тип sem_t, позволяющие использовать семафоры в ваших программах.
Мониторы были придуманы Хоаром (C. A. R. Hoare) как более безопасный примитив синхронизации. Они проще в использовании, так как не требуют столь высокого внимания, как семафоры.
Монитор представляет собой объект, содержащий один или несколько методов. Примечательной особенностью является то, что в один конкретный момент времени только одна нить может находиться в мониторе, то есть исполнять один из его методов. Ещё одним важным свойством является то, что нити могут на время лишаться эксклюзивного доступа в ожидании некоего события (это реализуется с помощью условных переменных — conditional variables).
Некоторые языки (например, Java) имеют встроенные реализации мониторов. Впрочем, их несложно реализовать и самим, используя, например, библиотеку POSIX Threads (pthread) с её эксклюзивными замќами (mutal lock, mutex — тип pthread_mutex_t) и условными переменными (тип pthread_cond_t).
Передача сообщений является интуитивно понятным методом синхронизации процессов, объединяющем в себе и синхронизацию, и межпроцессное взаимодействие — IPC (InterProcess Communication). Он базируется на понятии очереди сообщений и двух методах — send(), позволяющем отсылать сообщения, и receive(), позволяющем их принимать. В стандарте POSIX существует собственный интерфейс для работы с очередями, рассматриваемый, например, в mq_overview(7)
STM является самым высокоуровнёвым и современным методом синхронизации. Идея впервые появилась в 1986 и окончательно трансформировалась в современный STM в 1995–м.
Суть метода транзакций заключается в том, что изменения данных не станут видны другим нитям до тех пор, пока не будет выполнен коммит (commit). После коммита система пытается применить сделанные изменения к общему участку памяти. Если сделать это не удаётся (например, если кто–то другой тоже сделал коммит), производится откат до начального состояния и повторная попытка (retry).
На данный момент поддержка STM во многих языках программирования реализуется с помощью сторонних библиотек. Следует также отметить, что STM лучше показывает себя в больших системах, так как при малом количестве нитей слишком много времени тратится на повторные попытки коммита.
Уровень консенсуса:
∞ — memory-to-memory move and swap, augmented queue, compare-and-swap, fetch-and-cons, sticky byte, Load-Link/Store-Conditional1
2n-2 — n-register assignment
2 — test-and-set, swap, fetch-and-add, queue, stack
1 — atomic read and atomic write
Невозможно реализовать операцию, которая имеет больше участников, чем уровень консенсуса атомарной инструкции.
Запись в память и возврат предыдущего значения по этому адресу.
Создание замка на основе TSL:
#define LOCKED 1
int TestAndSet(int* lockPtr) {
int initial = *lock;
*lock = LOCKED;
return initial;
}
volatile int lock = 0;
void Critical() {
while (TestAndSet(&lock) == 1) /* busy waiting */;
/* critical section */
lock = 0; //release lock when finished with the critical section
}
Запись в память, при условии, что значение в ней совпадает с заданным.
int compare_and_swap (int* register, int oldval, int newval) {
int old_reg_val = *register;
if (old_reg_val == oldval) *register = newval;
return old_reg_val;
}
void acquire_mutex(int *mutex) {
while (cas(mutex, 1, 0)) /* busy waiting */;
}
void release_mutex(int *mutex) {
*mutex = 1;
}
В x86 архитекуре — инструкция CMPXCHG.
Пара инструкций, в которой вторая не выполниться, если после прочтени данных (LL) произошли их изменения (даже в случае их последующего восстановления).
Особенность: проблематичная реализация.
Формула для определения итоговой оценки: S + E
S — оценка за семестр
S = L + C + T
L — оценка за лабораторные
L = ∑Li, Li — оценка за лабораторную i
Li = bLi + round(4−(accept_date−start_date)/7)
bLi — базовая оценка за лабораторную i (указывается в задании), bLi ∈ [1,3]
accept_date — дата сдачи л/р
start_date — дата проведения реальной л/р (индивидуальная для каждой группы)
C — оценка за курсовую работу, С ∈ [0,17]
С = С1 + С2 + round(4−(accept_date−`2010/11/26`)/7)
C1 — оценка программы, C2 ∈ [0,10]
С2 — оценка тестов, примеров, интеграционной части, документации, C3 ∈ [0,3]
T — оценка за контрольную работу, T ∈ [0,18]
T = q1 + q2 + q3
qi — оценка за вопрос i, qi = 2×(q−2), q ∈ [2,5]
E — оценка за экзамен, E ∈ [0,30]
E = Q1 + Q2
Qi — оценка за вопрос i, Qi = 5×(Q−2), Q ∈ [2,5]
Требуемые баллы:
A - 91..100
B - 81..90
C - 71..80
D - 61..70
E - 51..60
Литература:
Процесс – это адресное пространство и единая нить управления — Э. Танненбаум
Понятие процесса включает в себя:
Нить управления (thread) — это одна логическая цепочка выполнения команд. На самом деле, в одном процессе может быть несколько одновременно запущенных таких цепочек, т.е. нитей. В таком случае имеет место многопоточность (multi-threading).
Дилемма:
Волокна (fibers) — аналогичны нитям, но используют кооперативную многозадачность (см. Планирование процессов)
Со-процедуры (co-routines) — особый вид процедур с несколькими точками входа. Реализует кооперативную многозадачность.
Простейший пример использования со-процедур: допустим, у вас имеется отношение производитель-потребитель. Первый добавляет в очередь некие предметы, второй их удаляет. Для повышения производительности предметы добавляются и удаляются по нескольку за раз, пока очередь не заполнится. В таком случае код (на неком абстрактном языке) будет выглядеть так:var q := new queue
coroutine produce
loop
while q is not full
create some new items
add the items to q
yield to consume
coroutine consume
loop
while q is not empty
remove some items from q
use the items
yield to produce
produce очередь будет заполняться, пока не закончится место. После этого управление будет передано (команда yield) со-процедуре consume. Она будет удалять элементы очереди до тех пор, пока та не опустеет, после чего снова будет вызвана со-процедура produce.
Структура для хранения информации о процессе (Process control block) содержит, как правило:
Пример реальной структуры (из Linux): attachment:pcb.txt
fork())exec() — execl, execlp, execle, execv, execvp). Впрочем, никто не запрещает клону продолжать выполнение главной программы. 1 #include <sys/types.h>
2 #include <unistd.h>
3 #include <stdio.h>
4 #include <stdlib.h>
5
6 int main() {
7 /* Клонируем текущий процесс */
8 pid_t childpid = fork();
9
10 /* Обратите внимание на то, что переменная childpid будет существовать и в
11 * оригинальном процессе, и в его клоне, но во втором случае будет равна
12 * нулю. Именно этот факт используется в следующей конструкции */
13 if(childpid == 0) {
14 /* Это клон. С помощью стандартной команды echo выведем приветствие и завершимся */
15
16 char* command[3] = {"/bin/echo", "Hello, world!", NULL};
17
18 execvp(command[0], command);
19
20 /* Если не произошло никаких ошибок, execvp() не завершается и мы
21 * никогда не достигнем этого участка кода. Если же мы всё-таки сюда
22 * добрались, клону следует завершиться с кодом возврата,
23 * сигнализирующем об ошибке */
24 exit(EXIT_FAILURE);
25 } else if(childpid == -1) {
26 /* fork() возвращает -1 в случае ошибки */
27 fprintf(stderr, "Can't fork, exiting...\n");
28 exit(EXIT_FAILURE);
29 } else {
30 /* Это родительский процесс. Просто завершимся с кодом возврата 0 */
31 exit(EXIT_SUCCESS);
32 }
33
34 return 0;
35 }
wait() (wait(), waitpid()), один процесс может ожидать завершения другого. Это часто используется в родительских процессах, которые хотят получить информацию о завершении их потомков. Вызовы wait() являются блокирующими — функция не завершится, пока не завершится процесс, который она ждёт.Если потомок завершается, но родительский процесс не вызывает wait(), потомок становится зомби. Таким образом, процессы-зобми — это завершившиеся процессы, информация о завершении которых никем не запрошена (т.е. никто не вызывал для этого процесса wait()). Впрочем, после завершения родительского процесса все его потомки переходят к процессу с PID 1, т.е. init. Он самостоятельно очищает информацию, оставшуюся после зомби.
Вытесняющая многозадачность (англ. «preemptive multitasking») — в системе работает планировщик (англ. «scheduler»), который имеет право в любой момент приостановить выполняющийся процесс и передать управление другому. Такое переключение между процессами носит имя «переключение контекста» (англ. «context switch»). Вытесняющая многозадачность даёт некоторые гарантии того, что каждый процесс получит некое количество процессорного времени.
Кооперативная многозадачность (англ. «cooperative multitasking») — каждый процесс должен самостоятельно передавать управление. За примером кооперативной многозадачности см. определение со-процессов в разделе о нитях.
Написать Shell-скрипт, который по текстовому файлу log.txt расчитает и выдаст такие параметры:
Базовый вариант: TOP 10 URL по количеству обращений
Иначе:
host-24-225-218-245.patmedia.net - - [01/Oct/2006:06:33:45 -0700] "GET /example/example.atom HTTP/1.1" 304 - "-" "NetNewsWire/2.0b37 (Mac OS X; Lite; http://ranchero.com/netnewswire/)"Формат записи:
<DNS клиента> - - [<Штамп времени>] <Строка HTTP-запроса (тип, URL, версия)> <Код HTTP-ответа> <Количество переданных байт> <Строка реферера> <Название клиента>
С помощью библиотеки FUSE создать виртуальную файловую систему, дерево файлов для которой закодированно в одном из форматов данных.
Эта файловая система должна монтироваться в режиме только чтение, после чего можно будет осуществить листинг виртуальных директорий и просмотр содержимого виртуальных файлов (содержимое файлов будет находится в соответствующем fuse-файле описания).
Абстрактное представление этой файловой системы (которое можно получить с помощью командыtree):/ |--docs | |--pdfs | | |--article.pdf | | |--example.pdf | | `--example.pdf~ | `--spreadsheets | |--.hidden | `--test |--etc | `--fuse | `--fuse.conf `--forbidden dir `--test
Базовые варианты:
Продвинутые варианты (для этих вариантов таже необходимо обеспечить проверку прав доступа при обращении к директориям и файлам):
Systems Software Research is Irrelevant
— Роб Пайк, http://doc.cat-v.org/bell_labs/utah2000
Системное программирование (СП) — это вершина пирамиды изучения программирования. Это вовсе не обучение программированию на Ассемблере, а совокупность знаний о создании больших программных систем, состоящих из взаимодействующих компонентов, которая опирается на:
Операционные системы (ОС) являются эталонными примерами для изучения, но принципы СП применимы и используются в любых крупных программных системах: виртуальных машинах (ВМ), СУБД, серверах, системах распределенных вычислений и т.д.
Платформа — это аппаратная архитектура и/или программная основа, которая позволяет исполняться "пользовательским" программам. Приложение — это собственно программа, которая выполняет какаое-то полезное действие.
Это внешнее представление, абстракция какого-то информационного объекта. Интерфейс разделяет методы внешнего взаимодействия и внутренней работы. Один объект может иметь несколько интерфейсов для разных "потребителей". Интерфейс — это средства трансляции между сущностями внешней и внутренней для объекта среды. Интерфейс — это форма косвенного взаимодействия. Связанно с концепцией кибернетики "черный ящик".
Это набор правил взаимодействия между объектами. Эти правила определяют синтаксис, семантику и синхронизацию взаимодействия. Протокол может существовать в форме конвенции (неформального) или стандарта (формального набора правил).
Вопрос: какая взаимосвязь между протоколом и интерфейсом?
Основные составные части большинства протоколов:
Протокол и диллема узника
Закон Постела (принцип робастности): будьте консервативны в том, что отправляете, и либеральны в том, что принимаете
Это нормативная спецификация технологиии или методологии.
Открытые стандарты — это стандарты, которые публикуются в открытых источниках и, как правило, имеют одну или несколько (например, W3C требует как минимум двух) эталонных реализаций (reference implementation). Также, как правило, такие стандарты разрабатываются в четко определенном процессе.
Вопрос: какие ещё?
Особенностью теории СП является то, что это практическая дисциплина, поэтому кроме установленных научным путем фактов она включает также большое количество эвристик и накопленного опыта разработки, которые не является всегда истинными, однако дают важные подсказки и указывают направление развития для тех, кто работает в этой области. Такие законы — как из разряда доказанных фактов, так и просто обобщений — составляют концептальную основу СП.
В распределенных системах из 3х качеств: целостность (consistency), доступность (availability) и терпимость к разделению (partition tolerance) одновременно могут быть достигнуты только 2.
Следствие: определенные подходы к разработке распределенных систем и движение NoSQL.
См. Amazon Dynamo
Любая программа пытается расшириться до тех пор, пока не научиться читать почту. Те программы, которые не могут так расшириться, заменяются теми, которые могут
Мораль:
"Любая достаточно сложная программа на C или Fortran содержит ad hoc, неформально специфицированную, переполненную багами, медленную реализацию половину Common Lisp"
Примечание: Common Lisp — динамический ЯП, который имеет наибольшие возможности расширения и абстракции.
Что отличает Lisp? (Питер Норвиг, PAIP, 1992)
- Встроенная поддержка списков
- Автоматическое управление памятью
- Динамическая типизация
- Функции — первоклассные объекты
- Единообразный синтаксис
- Интерактивная среда
- Расширяемость
- Итсория
Мораль:
Тенденция вслед за относительно небольшой, элегантной и успешной системой спроектировать систему следующего поколения как слонопотамного, переполненного функциями монстра. (Которого часто так и не удается довести до полноценной реализации) [из книги Фреда Брукса Мифический человеко-месяц]
Мораль:
Принципы:
Вопрос: Почему важны открытые системы?
Вопрос: в чем разница между масштабруемостью и производительностью?
Масштабируемость бывает вертикальной и горизонтальной. Вертикальная масштабируемость — способность справляться с большей нагрузкой с помощью улучшения внутренних характеристик (например: добавить больше памяти в компьютер). Горизонтальная — путем добавления типичных компонент. У каждого подхода есть свой предел.
Экономический аспект: коммодитизация
Уровни:
Писать на АСМе сейчас практически не нужно. Но ВСЕГДА рано или поздно сталкивался с тем, что нужно уметь читать АСМ. Либо для того, чтобы сделать действительно оптимальный код, либо — что гораздо чаще — чтобы суметь правильно прочитать stack trace и поймать эту самую чертову ошибку. Мне довольно часто приходилось видеть этот "кошмар прикладного программиста", когда большая и сложная программа валится на невнятном сообщении "выполнена недопустимая операция". И без знания АСМа понять, что случилось, невозможно.
Языки ассемблеров были первыми "высокоуровневыми" языками по сравнению с программированием непосредственно в адресных кодах. В них появились:
mov, push, ...) вместо кодов операций
55
89 E5
83 EC 08
C7 45 FC 01 00 00 00
83 EC 0C
6A 00
E8 D1 FE FF FF
push %ebp
mov %esp, %ebp
sub $0x8, %esp
movl $0x1, -4(%ebp)
sub $0xc, %esp
push $0x0
call 8048348
int main()
{
int i = 1;
exit(0);
}
Еще один пример — классический Hello World
#include <stdio.h>
int main()
{
printf("hello, world");
return 0;
};
преобразованный в ассемблер компилятором MSVC (cl 1.cpp /Fa1.asm):
CONST SEGMENT
$SG3830 DB 'hello, world', 00H
CONST ENDS
PUBLIC _main
EXTRN _printf:PROC
; Function compile flags: /Odtp
_TEXT SEGMENT
_main PROC
; File c:\...\1.cpp
; Line 4
push ebp
mov ebp, esp
; Line 5
push OFFSET $SG3830
call _printf
add esp, 4
; Line 6
xor eax, eax
; Line 7
pop ebp
ret 0
_main ENDP
_TEXT ENDS
и компилятором GCC:
.file “ctest.c”
.version “01.01”
gcc2_compiled.:
.section .rodata
.LC0:
.string “Hello, world!\n”
.text
.align 16
.globl main
.type main,@function
main:
pushl %ebp
movl %esp, %ebp
subl $8, %esp
subl $12, %esp
pushl $.LC0
call printf
addl $16, %esp
subl $12, %esp
pushl $0
call exit
.Lfe1:
.size main,.Lfe1-main
.ident “GCC: (GNU) 2.96 20000731 (Linux-Mandrake 8.0 2.96-0.48mdk)”
Это частично определяемый аппаратной архитектурой и частично конкретной средой исполнения механизм вызова подпрограмм. Соглашения включают ответы на вопросы: как передаются/возвращаются аргументы, как распределяется работа при вызове/завершении подпрограммы.
Конкретные примеры реализации:
push eAX ; последний аргумент — содержимое регистра eAX push byte[eBP+20] ; предпоследний аргумент — содержимое ячейки памяти по адресу = адрес в eBP + 20 байт push 3 ; первый аргумент — константа 3 call calc ; вызов подпрограммы calc, возвращаемое значение будет в eAXТипичная структура подпрограммы:
calc: push eBP ; сохранить указатель на стек mov eBP,eSP ; получить новый указатель на стек sub eSP,4*3 ; выделить место для локальных переменных ... ; произвести вычисления, в конце концов результат записать в eAX mov eSP,eBP ; "освободить" место, занимаемое локальными переменными pop eBP ; восстановить указатель на стек ret 0 ; вернуться в место вызова
Писать на АСМе сейчас практически не нужно. Но ВСЕГДА рано или поздно сталкивался с тем, что нужно уметь читать АСМ. Либо для того, чтобы сделать действительно оптимальный код, либо — что гораздо чаще — чтобы суметь правильно прочитать stack trace и поймать эту самую чертову ошибку. Мне довольно часто приходилось видеть этот "кошмар прикладного программиста", когда большая и сложная программа валится на невнятном сообщении "выполнена недопустимая операция". И без знания АСМа понять, что случилось, невозможно.
Языки ассемблеров были первыми "высокоуровневыми" языками по сравнению с программированием непосредственно в адресных кодах. В них появились:
mov, push, ...) вместо кодов операций
55
89 E5
83 EC 08
C7 45 FC 01 00 00 00
83 EC 0C
6A 00
E8 D1 FE FF FF
push %ebp
mov %esp, %ebp
sub $0x8, %esp
movl $0x1, -4(%ebp)
sub $0xc, %esp
push $0x0
call 8048348
int main()
{
int i = 1;
exit(0);
}
Еще один пример — классический Hello World
#include <stdio.h>
int main()
{
printf("hello, world");
return 0;
};
преобразованный в ассемблер компилятором MSVC (cl 1.cpp /Fa1.asm):
CONST SEGMENT
$SG3830 DB 'hello, world', 00H
CONST ENDS
PUBLIC _main
EXTRN _printf:PROC
; Function compile flags: /Odtp
_TEXT SEGMENT
_main PROC
; File c:\...\1.cpp
; Line 4
push ebp
mov ebp, esp
; Line 5
push OFFSET $SG3830
call _printf
add esp, 4
; Line 6
xor eax, eax
; Line 7
pop ebp
ret 0
_main ENDP
_TEXT ENDS
и компилятором GCC:
.file “ctest.c”
.version “01.01”
gcc2_compiled.:
.section .rodata
.LC0:
.string “Hello, world!\n”
.text
.align 16
.globl main
.type main,@function
main:
pushl %ebp
movl %esp, %ebp
subl $8, %esp
subl $12, %esp
pushl $.LC0
call printf
addl $16, %esp
subl $12, %esp
pushl $0
call exit
.Lfe1:
.size main,.Lfe1-main
.ident “GCC: (GNU) 2.96 20000731 (Linux-Mandrake 8.0 2.96-0.48mdk)”
Это частично определяемый аппаратной архитектурой и частично конкретной средой исполнения механизм вызова подпрограмм. Соглашения включают ответы на вопросы: как передаются/возвращаются аргументы, как распределяется работа при вызове/завершении подпрограммы.
Конкретные примеры реализации:
push eAX ; последний аргумент — содержимое регистра eAX push byte[eBP+20] ; предпоследний аргумент — содержимое ячейки памяти по адресу = адрес в eBP + 20 байт push 3 ; первый аргумент — константа 3 call calc ; вызов подпрограммы calc, возвращаемое значение будет в eAXТипичная структура подпрограммы:
calc: push eBP ; сохранить указатель на стек mov eBP,eSP ; получить новый указатель на стек sub eSP,4*3 ; выделить место для локальных переменных ... ; произвести вычисления, в конце концов результат записать в eAX mov eSP,eBP ; "освободить" место, занимаемое локальными переменными pop eBP ; восстановить указатель на стек ret 0 ; вернуться в место вызова