Частотный анализ текстового файла

Контрольная работа №2

Задание №1: Теоретический вопрос

 

1. Управлению памятью, как часть подсистемы управления процессами. Концепция виртуальной памяти.

2. Физическая память и ее адресация: сегментный и страничный механизмы.

3. Страничное замещение основной памяти. Свопинг (swapping) страниц и процессов.

4. Аппаратная поддержка многозадачности и виртуальной памяти в архитектуре CPU Intel x86.

5. Управление процессами и нитями. Структуры данных процесса: контекст (user) и дескриптор (proc).

6. Создание и завершение процессов (системные вызовы fork, exec, wait, exit). Состояния процесса и переходы между ними.

7. Понятие потоков (нитей) и многопоточность процессов в OC UNIX. Планирование выполнения процессов, принципы организации многопользовательского режима, прерывание по таймеру.

8. Выполнение в режиме ядра. Системные вызовы. Начальный процесс init.

9. Драйверы устройств. Типы и базовая архитектура драйверов. Блочные и символьные драйверы. Псевдоустройства.

10. Взаимодействие процессов. Сигналы

11. Взаимодействие процессов. программные каналы

12. Взаимодействие процессов. разделяемая память

13. Взаимодействие процессов. семафоры

14. Взаимодействие процессов. очереди сообщений

15. Взаимодействие процессов. программные гнезда (sockets).

16. Запуск и останов системы. Конфигурирование системы. Обзор командных файлов запуска (инициализации) UNIX.

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

18. Сетевые интерфейсы UNIX и их драйверы. Базовый сетевой демон услуг Internet – inetd.

19. Сетевые порты и их связь с сетевыми сервисами UNIX. Демоны маршрутизации routed, gated.

20. Утилиты для конфигурирования и проверки состояния сети (ifconfig, etherfind, netstat, ping, traceroute, tcpshow, trafshow, tcpdump).

21. Удаленный доступ. Сервисные сетевые протоколы: FTP, Telnet, Ssh, Rlogin.

22. Система защиты и безопасности. Принципы защиты ОС и данных. Пароли и аутентификация пользователей.

23. Привилегии и права доступа, наследование прав (SetUID, SetGID). Контроль прав доступа.

24. Фильтрация пакетов на сетевом уровне (iptables, ipfw). Фильтрация трафика приложений.

25. Контроль системных регистрационных журналов. Резервное копирование и восстановление данных.

26. Шифрование данных (crypt, DES, bdes). Система сетевой защиты Kerberos.

27. Возможности и особенности работы OC Unix в качестве серверной платформы.

 

 

 

Задание №2: Практическое задание

Общая информация

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

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

В состав программы должен входить файл README с информацией о авторстве, функциях программы, краткой инструкцией по использованию и установке. Также необходимо указать необходимые нестандартные (не поставляемые вместе в ОС) библиотеки и модули. Текст должен быть либо на английском языке, либо на русском в кодировке koi8-r.

К реферативным работам предъявляются стандартные требования по оформлению. Выполнение реферата равносильно заданию повышенной сложности.

 

Задания малой сложности.

Частотный анализ текстового файла

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

Вывести первые 20 записей в порядке убывания количества символов в виде:

“A” 65 123

где A – символ (для непечатываемых символов – не выводить), 65 – код символа, 123 – количество символов “A” в файле.

Для решения задачи использовать mmap().

 

Список строк

Написать программу, которая вставляет строки, введенные с клавиатуры, в список. Память под узлы списка выделяется динамически с использование malloc(3).

Ввод завершается строкой “.”. Затем все строки из списка выводятся на экран.

 

Таблица поиска строк в текстовом файле

Написать программу, которая анализирует текстовый файл. После запроса, который предлагает ввести номер строки, с использованием printf(3) программа печатает соответствующую строку текста. Ввод нулевого номера завершает работу программы. Используйте open(2), read(2), lseek(2) и close(2) для ввода/вывода. Постройте таблицу отступов в файле и длин строк для каждой строки файла. Как только эта таблица построена, позиционируйтесь на начало заданной строки и прочтите точную длину строки. Предполагайте, что файл не длиннее сотни строк

 

Таблица поиска строк в текстовом файле (#2)

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

 

Поиск подстроки в текстовом файле (grep)

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

Результат должен выводиться в виде:

123:строка текста

где 123 – номер строки в файле, “строка текста” – содержимое этой строки.

 

Программа для просмотра файлов (more)

Написать программу, выполняющую просмотр и прокрутку указанного текстового файла.

 

Вывод дерева каталогов (tree)

Вывод дерева каталогов, начиная с текущего или указанного.

Аналогично команде TREE MS-DOS.

 

Мониторинг лог файлов (tail -f)

Программа для мониторинга лог файлов.

Выводит указанный текстовый файл на терминал. Далее в цикле ожидает увеличения размера файла и выводит добавившиеся строки на терминал.

 

Сортировка текстового файла (sort)

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

 

Перекодировка текстового файла из одной кодировки в другую

Разработка программы-фильтра выполняющую перекодировку текстового файла из кодировки cp866, windows-1251, koi8-r в другую из того же набора (в зависимости от ключей командной строки). Файл должен читаться с потока стандартного ввода. Результат печататься на поток стандартного вывода.

 

Задания средней сложности

Динамические структуры в UNIX

Реализовать следующие структуры:

a) список с одиночными связями,

b) список с двойными связями,

c) бинарное дерево,

d) стек,

e) простую очередь,

f) циклическую очередь.

 

Декодирование почтовых форматов

Декодировать и распечатать файл в формате:

а) uuencode

б) quoted-printable

в) base64

 

Псевдографические стрелочные часы

Написать программу, выводящую на терминале (включая telnet/ssh терминал) псевдографические стрелочные часы с секундной стрелкой.

Использовать информацию о типе терминала в переменной окружения TERM, управляющие последовательности из файла termcap. Возможно использование библиотеки ncurses(3) или аналогичной.

 

2.4. TCP сервис “изменение регистра строк”

Напишите программу, которая занимает заданный порт TCP, ожидает установления соединения, принимает данные, переводит все символы латинского алфавита в верхний регистр и отправляет данные обратно.

Подсказка: см. toupper(3).

 

Сканер TCP портов

Напишите программу, которой в качестве аргументов передаются IP адрес хоста и диапазон портов. Программа должна вывести номера открытых портов TCP из указанного диапазона.

 

Пересылка файлов по TCP

Напишите программу N1, которая запрашивает у пользователя IP адрес, номер порта и имя файла, устанавливает TCP соединение с указанным адресом, и передает заданный файл.

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

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

 

Служба информации о системе

Сделать доступным в сети информацию о состоянии операционной системы (загрузка системы, активные пользователи, заполненность дисков) двумя способами: с использованием inetd и как пользовательский login.

 

Двухпоточные вычисления

Написать программу, порождающую двух потомков.

Первый потомок вычисляет простые числа от 2 до 1e9. Второй каждые 5 секунд вычисляет случайное число из диапазона 0…1e9. Оба потоска передают вычисленные значения родителю через pipe.

Родитель печатает получаемые от потомков значения на теринал в виде:

Simple: 2

Random: 431

При завершении родителя комбинацией клавиш Ctrl-C, он заверншает выполнение потомков отправкой сигнала SIGTERM и завершает свое выполнение.

 

Задания высокой сложности

Web сервер

Написать программу-сервер, которая принимает запросы по порту 10000 и выдает содержимое указанного в запросе файла. В качестве протокола взаимодействия сервера и клиента использовать подмножество протокола HTTP (запрос GET). Реализовать сообщение о недоступности файла (“404 Not Found”) и просмотр оглавления каталога (при запросе каталога выдается находящейся в этом каталоге файл index.html). Использовать стандартные функции организации соединения TCP/IP: socket(), bind(), linsten(), accept(), read(), write().

 

Пример взаимодействия:

Запрос:

GET /index.html HTTP/1.0

 

Ответ:

HTTP/1.1 200 OK

Server: 99soft server v1.0

Content-Length: 229

Content-Type: text/html

(пустая строка)

<html><body>test</body></html>

 

Чат-сервер

Многопользовательский чат-сервер.

Написать программу сервер и клиентскую программу.

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

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

Взаимодействие клиентов и серверов можно реализовать на одном из видов IPC или посредством сетевого взаимодействия.

Как и в задании 3.3 реализовать работу на различных видах терминалов.

 

3.5. “Транспьютер”

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

Сервисы создаются посредством вызова функции fork(). Передача параметров может выполняться через одно из средств IPC.

Возможно выполнение разными студентаи этого задания и использованием различных средств IPC.

 

Пример.

Вычисление выражения:

a*b+c/d

 

Создается вычислительная сеть из 3-х элементов: (1), (2), (3) на схеме.

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

Из головной программы (0) значения переменных передаются в вычислительную сеть.

Результат вычислений из сети передается в головную программу (0) и выводятся на экран.

 

(0)

a b c d

ß ß ß ß

(1 *) (2 /)

¯ ¯

(3 +)

¯

(0)

 

Распределенные вычисления

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

 

Например, система вычисления всех простых чисел из диапазона 2…1e9.

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

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

Сервер принимает подключения клиентов на определенном порту TCP. По окончании проверки всего диапазона завершает работу.

Клиент-вычислитель соединяется с сервером. Получает диапазон для вычислений (два числа). Проводит вычисления и отсылает найденные числа серверу. По окончании вычислений закрывает соединение и подключается снова. В случае невозможности подключения клиент прекращает попытки.

Сервер должен работать на unix машине.

Клиенты могут работать на любых ОС.

 

Реферативные работы

 

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

 

1. Установка и настройка VPN.

2. Установка и настройка сервисов FTP и SAMBA.

3. Установка и настройка прокси сервера (squid): организация доступа, авторизация, подсчет и контроль трафика.

4. Система X Windows: установка и настройка X-сервера на платформе Microsoft Windows с использованием некоммерческого ПО. Работа с unix X-клиентами по сети.

5. Установка и настройка PPP сервиса.

 

Контрольная работа №2

Задание №1: Теоретический вопрос

 

1. Управлению памятью, как часть подсистемы управления процессами. Концепция виртуальной памяти.

2. Физическая память и ее адресация: сегментный и страничный механизмы.

3. Страничное замещение основной памяти. Свопинг (swapping) страниц и процессов.

4. Аппаратная поддержка многозадачности и виртуальной памяти в архитектуре CPU Intel x86.

5. Управление процессами и нитями. Структуры данных процесса: контекст (user) и дескриптор (proc).

6. Создание и завершение процессов (системные вызовы fork, exec, wait, exit). Состояния процесса и переходы между ними.

7. Понятие потоков (нитей) и многопоточность процессов в OC UNIX. Планирование выполнения процессов, принципы организации многопользовательского режима, прерывание по таймеру.

8. Выполнение в режиме ядра. Системные вызовы. Начальный процесс init.

9. Драйверы устройств. Типы и базовая архитектура драйверов. Блочные и символьные драйверы. Псевдоустройства.

10. Взаимодействие процессов. Сигналы

11. Взаимодействие процессов. программные каналы

12. Взаимодействие процессов. разделяемая память

13. Взаимодействие процессов. семафоры

14. Взаимодействие процессов. очереди сообщений

15. Взаимодействие процессов. программные гнезда (sockets).

16. Запуск и останов системы. Конфигурирование системы. Обзор командных файлов запуска (инициализации) UNIX.

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

18. Сетевые интерфейсы UNIX и их драйверы. Базовый сетевой демон услуг Internet – inetd.

19. Сетевые порты и их связь с сетевыми сервисами UNIX. Демоны маршрутизации routed, gated.

20. Утилиты для конфигурирования и проверки состояния сети (ifconfig, etherfind, netstat, ping, traceroute, tcpshow, trafshow, tcpdump).

21. Удаленный доступ. Сервисные сетевые протоколы: FTP, Telnet, Ssh, Rlogin.

22. Система защиты и безопасности. Принципы защиты ОС и данных. Пароли и аутентификация пользователей.

23. Привилегии и права доступа, наследование прав (SetUID, SetGID). Контроль прав доступа.

24. Фильтрация пакетов на сетевом уровне (iptables, ipfw). Фильтрация трафика приложений.

25. Контроль системных регистрационных журналов. Резервное копирование и восстановление данных.

26. Шифрование данных (crypt, DES, bdes). Система сетевой защиты Kerberos.

27. Возможности и особенности работы OC Unix в качестве серверной платформы.

 

 

 

Задание №2: Практическое задание

Общая информация

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

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

В состав программы должен входить файл README с информацией о авторстве, функциях программы, краткой инструкцией по использованию и установке. Также необходимо указать необходимые нестандартные (не поставляемые вместе в ОС) библиотеки и модули. Текст должен быть либо на английском языке, либо на русском в кодировке koi8-r.

К реферативным работам предъявляются стандартные требования по оформлению. Выполнение реферата равносильно заданию повышенной сложности.

 

Задания малой сложности.

Частотный анализ текстового файла

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

Вывести первые 20 записей в порядке убывания количества символов в виде:

“A” 65 123

где A – символ (для непечатываемых символов – не выводить), 65 – код символа, 123 – количество символов “A” в файле.

Для решения задачи использовать mmap().

 

Список строк

Написать программу, которая вставляет строки, введенные с клавиатуры, в список. Память под узлы списка выделяется динамически с использование malloc(3).

Ввод завершается строкой “.”. Затем все строки из списка выводятся на экран.

 

Таблица поиска строк в текстовом файле

Написать программу, которая анализирует текстовый файл. После запроса, который предлагает ввести номер строки, с использованием printf(3) программа печатает соответствующую строку текста. Ввод нулевого номера завершает работу программы. Используйте open(2), read(2), lseek(2) и close(2) для ввода/вывода. Постройте таблицу отступов в файле и длин строк для каждой строки файла. Как только эта таблица построена, позиционируйтесь на начало заданной строки и прочтите точную длину строки. Предполагайте, что файл не длиннее сотни строк

 

Таблица поиска строк в текстовом файле (#2)

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