Порядок выполнения работы

Порядок выполнения работы

1. Подготовить последовательный алгоритм решения задачи, приведенной в конце описания (вариант задания соответствует номеру бригады). Реализовать его на языке программирования Ruby и другом известном языке (Pascal, C++ и др.). Использовать файловый ввод/вывод необходимых данных.

2. Сравнить полученные программы по количеству строк исходного текста, количеству операторов, количеству циклов, условных операторов.

Требования к программному обеспечению

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

Содержание отчета

1. Постановка задачи

2. Описание алгоритма решения задачи (схемы алгоритмов не обязательны)

3. Таблица с результатами сравнения 2-х реализаций

4. Выводы

5. Приложения

5.1. Результаты тестирования

5.2. Листинги программ

Варианты заданий

Отсутствующее число в массиве

Массив длины N в случайном порядке заполнен целыми числами из диапазона от 0 до N. Каждое число встречается в массиве не более одного раза. Найти отсутствующее число (дырку). Есть очень простой и оригинальный способ решения. Сложность алгоритма O(N), т.е. задача решается за один проход. Использование дополнительной памяти, пропорциональной длине массива, не допускается.

Черные квадраты

На дискретном (клетчатом) белом квадратном поле с длиной стороны N размещены несоприкасающиеся черные квадраты. Посчитать число квадратов.

 

 

Количество различных чисел

Массив длины N заполнен в случайном порядке числами из диапазона от 1 до k < N. Не используя других массивов, подсчитать количество различных чисел. Количество шагов порядка N + k.

Перестановка сегментов неодинаковой длины

Сегментом называется непрерывная последовательность элементов массива. Массив состоит из двух сегментов неодинаковой длины. Не используя дополнительную память, пропорциональную N, поменять сегменты местами.

 

5. Случайный спуск по дереву

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

Формат описания дерева следующий: tree::= leaf | (tree tree); leaf::= integer;

Например, (((3 5) 1) (9 4))

Результат: 4.50

 

Пересечение множеств

Вход — два множества натуральных чисел.

Выход — их пересечение (перечисление элементов через пробел в любом порядке без повторений) или слово empty если пересечение пусто.

Множества A={a₁, a₂,..., a_n} и B={b₁, b₂... b_k} Возможны повторения элементов, которые надо исключить.

ВХОД #1: 6 7 8 1 2 3 4 3 2 1 1	ВХОД #2: 1 2 34 4 5 5 6 6
ВЫХОД #1: 1 2 3	ВЫХОД #2: empty

 

Удаление повторяющихся чисел

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

 

Проверка транзитивности

Задан набор пар натуральных чисел, причем пары (a, b) и (b, a) считаются различными. Проверить, выполняется ли для вхождения чисел в данный набор свойство транзитивности: если набор содержит пары (a, b) и (b, c), то он обязательно содержит и пару (a, c).

 

Лабораторная работа № 2

Разделение ресурсов

Цель работы – приобретение навыков организации доступа нескольких параллельных процессов к общим ресурсам.

Порядок выполнения работы

1. Ознакомиться с методическими указаниями.
2. Подготовить параллельные алгоритмы решения задачи приведенной в конце описания (вариант определяется номером бригады). Согласовать формализацию с преподавателем (содержание формализации см. ниже). При решении использовать:

1) семафор (в качестве семафоров использовать https://www.imasy.or.jp/~fukumoto/ruby/semaphore.rb);

2) монитор.

1. Реализовать алгоритмы на языке Ruby.

 

Содержание отчета

1. Постановка задачи

2. Формализация решения

2.1. Типы потоков и их количество

2.2. Условия ожидания потоков каждого типа

2.3. Назначение и число семафоров

2.4. Методы монитора (название, назначение, параметры).

2.5. Указать классическую задачу, на которую похожа данная.

2.6. Случайные задержки, используемые программе.

3. Сопоставление эффективности мониторов и семафоров.

4. Выводы

5. Приложения

5.1. Результаты тестирования

5.2. Листинги программ

 

Методические указания

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

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

· неудовлетворительная скорость работы последовательного алгоритма, при наличии многопроцессорной системы;

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

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

Семафор представляет собой защищенную переменную, т.е. из программы пользователя над семафором нельзя совершать обычные арифметические операции или присваивать ему какое-либо значение. Допустима команда инициализации семафора целым неотрицательным числом. Доступ к нему разрешен только через операции P(S), V(S):

 

P(S) = IF S > 0 THEN S:= S - 1

ELSE ждать операции V(s);

 

V(S) = IF есть ждущие процессы на S THEN разрешить одному из процес­сов продолжить выполнение

ELSE S:= S + 1;

 

Выполнить любую из данных операций над конкретным семафором в один момент времени может только один процесс, т.е. выполняется правило взаимного исключения. Обычно процессы, ждущие на семафоре, организованы согласно дисциплине FIFO [1].

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

При разработке параллельных алгоритмов следует:

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

· не допускать взаимной блокировки процессов, т.е. ситуации, когда ни один из процессов не может продолжить свою работу;

· избегать режима активного ожидания;

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

· помещать в область взаимного исключения минимально необходимое число операторов.

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

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

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

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

· операция ожидания - блокирует вызывающий процесс;

· операция сигнализации - заставляет один из ожидающих процессов возобновиться.

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

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

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

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

Примеры решения классических задач (постановка задач см. лекции)

Производители и потребители

require 'semaphore'

t0 = Time.now

buf = Array.new(5)

tp = []

tc = []

c = 20

s1 = Semaphore.new(buf.size)

s2 = Semaphore.new(0)

m = Semaphore.new(1)

producer = Thread.new do

i = 0

c.times do

d = rand(10)

tp << d

puts "produce #{d} i=#{i}"

s1.P

m.P

buf[i] = d

m.V

s2.V

i = (i + 1) % buf.size

end

end

 

consumer = Thread.new do

i = 0

c.times do

s2.P

m.P

d = buf[i]

m.V

s1.V

tc << d

puts "consume #{d} i=#{i}"

i = (i + 1) % buf.size

end

end

 

producer.join

consumer.join

puts tp.join(',')

puts tc.join(',')

puts tp == tc

puts Time.now - t0

Писатели и читатели

require 'monitor'

 

class RWControl

include MonitorMixin

 

def initialize

@can_read = new_cond

@can_write = new_cond

@num_readers = 0

@is_writing = false

super()

end

 

def begin_reading

synchronize do

@can_read.wait if @is_writing or @can_write.count_waiters > 0

@num_readers += 1

@can_read.signal

end

end

 

def end_reading

synchronize do

@num_readers -= 1

@can_write.signal if @num_readers == 0

end

end

 

def begin_writing

synchronize do

@can_write.wait if @is_writing or @num_readers > 0

@is_writing = true

end

end

 

def end_writing

synchronize do

@is_writing = false

if @can_read.count_waiters > 0

@can_read.signal

else

@can_write.signal

end

end

end

 

end

 

m = RWControl.new

 

50.times do

Thread.new do

sleep rand * 2

m.begin_reading

puts Thread.current.to_s + ' reading'

sleep rand

m.end_reading

end

end

 

10.times do

Thread.new do

sleep rand * 2

m.begin_writing

puts Thread.current.to_s + ' writing'

sleep rand * 2

m.end_writing

end

end

 

Thread.list.each { |t| t.join unless t == Thread.main }

 

Философы

require 'semaphore'

N = 5

class Table

def initialize(n)

@forks = Array.new(n) { Semaphore.new(1) }

@m = Semaphore.new(n - 1)

end

def take_left(i)

@m.P

@forks[ i - 1 ].P

end

def take_right(i)

@forks[ i ].P

end

def put_left(i)

@m.V

@forks[ i - 1 ].V

end

def put_right(i)

@forks[ i ].V

end

end

 

table = Table.new(N)

N.times do |i|

Thread.new(i) do |k|

loop do

puts "thinking #{k}"; sleep rand

table.take_left(k); sleep 2*rand

table.take_right(k)

puts "#{k} eating"; sleep rand

table.put_left(k)

table.put_right(k)

end

end

end

 

Thread.list.each{ |t| t.join if t!= Thread.current }

 

require 'monitor'

class Table

include MonitorMixin

def initialize(n)

super()

@c = Array.new(n) { new_cond }

@forks = Array.new(n) { 2 }

end

def take_both(i)

synchronize do

@c[i].wait if @forks[i] < 2

@forks[i-1] -= 1

@forks[(i+1)%@c.size] -= 1

end

end

def put_both(i)

synchronize do

@forks[i-1] += 1

@forks[(i+1)%@c.size] += 1

@c[i-1].signal if @forks[i-1] == 2

@c[(i+1)%@c.size].signal if @forks[(i+1)%@c.size] == 2

end

end

end

 

table = Table.new(N)

N.times do |i|

Thread.new(i) do |k|

loop do

puts "thinking #{k}"; sleep rand

table.take_both(k);

puts "#{k} eating"; sleep rand

table.put_both(k)

end

end

end

 

Thread.list.each{ |t| t.join if t!= Thread.current }

 

Варианты задач

Вариант 1

Жил-был один человек, и звали его Полуэкт. И было у него две бабушки, одна мама и не менее одной девушки. Человек этот очень любил работать допоздна, а его бабушки, мама и девушки очень волновались, не случилось ли с ним чего-нибудь. И вот каждый вечер все эти мамы, бабушки и девушки начинают друг другу звонить, чтобы узнать, не случилось ли чего-нибудь с Полуэктом. Человек и каждая из мам, бабушек и девушек имеет один телефон и может говорить или ждать звонка (ждать они не любят, а вот говорить очень даже любят). Соединение Полуэкт->(бабушка | мама | девушка) может быть установлено только по звонку Полуэкта. Бабушки прекращают звонить, если они уже переговорили со всеми остальными ожидающими и получили подтверждение хотя бы от одного из них. Полуэкт прекращает звонить после первого успешного соединения. Задача: разработать систему, позволяющую всем бабушкам и т. п. получить подтверждение того, что Полуэкт ещё на работе и что-нибудь с ним ещё не случилось. Информацию может сообщить как сам Полуэкт, так и кто-нибудь из бабушек.

 

Вариант 2

Проблема курильщиков сигар. Три курильщика представлены процессами S1, S2 и S3. Три поставщика представлены процессами V1, V2 и V3. Каждому курильщику необходимы табак, папиросная бумага и спички. Когда эти ресурсы у него есть, он выкуривает сигару до конца и переходит в состояние готовности курить снова. У S1 есть табак, у S2 есть папиросная бумага, у S3 есть спички. V1 поставляет табак и бумагу, V2 поставляет бумагу и спички, V3 поставляет спички и табак. Для V1, V2 и V3 обеспечивается взаимное исключение. Следующий поставщик не может функционировать, пока ресурсы предыдущего поставщика не будут потреблены курильщиком.

 

Вариант 3

В общежитии института имеется совместная ванная комната. Если в ванной комнате есть женщина, то другая женщина может туда войти, а мужчина не может, и наоборот. На ванной есть индикатор, показывающий, в каком из трех состояний находится ванная: 1) никого нет; 2) в ванной женщины; 3) в ванной мужчины. Напишите систему, контролирующую доступ в ванную.

 

Вариант 4

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

а) предпочтение отдается западным бабуинам;

б) все бабуины равноправны.

 

Вариант 5

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

 

Вариант 6

Разработайте систему, управляющую игровым автоматом типа «однорукий бандит». Один контролирующий процесс отвечает за прием и выдачу денег, а также за запуск трех игровых процессов. Каждый игровой процесс «крутит» соответствующее колесо.

 

Вариант 7

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

а) лифт никого не подбирает при своем движении;

б) если есть вызовы, то лифт останавливается при движении вниз.

 

Вариант 8

Разработайте систему, управляющую пассажирским лифтом, с кнопками вызова «вверх» и «вниз». Реализуйте две схемы работы лифта:

а) лифт реагирует на вызовы в порядке их поступления;

б) лифт реагирует на все вызовы в направлении своего движения. Если в текущем направлении вызовов нет, то лифт меняет направление движения.

 

Контрольные вопросы

1. В каких случаях последовательный алгоритм решения целесообразней параллельного?
2. Что такое асинхронный процесс?
3. Чем определяется возможность разработки параллельной программы: операционной системой или системой программирования?
4. В каком случае необходимо использовать семафоры?
5. Приведите пример параллельного алгоритма, не требующего взаимного исключения.
6. Какими правилами следует руководствоваться при разработке параллельных программ.
7. Что такое монитор?
8. Какие преимущества дают мониторы?
9. В чем преимущество семафоров над мониторами?
10. Приведите пример тупика при использовании монитора.
11. В чем отличие семафоров от переменных типа условие?

 

Лабораторная работа № 3

Каркасы программных систем

Цель работы – приобретение навыков разработки оконных и Web интерфейсов, изучение паттерна Model-Controller-View.

Порядок выполнения работы

1. Для задания из лабораторной работы № 1 разработать оконное приложение на Ruby с возможностями:

- загрузки, редактирования и сохранения исходных данных;

- запуска требуемой реализации алгоритма;

- просмотра и сохранения результатов работы.

При разработке рекомендуется использовать библиотеку FXRuby (допустимо и другую, например WxRuby).

2. Разработать Web-приложение с использованием программного каркаса Rails. Приложение должно поддерживать все возможности оконного приложения.

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

 

Требования к программному обеспечению

При разработке необходимо соблюдать принцип DRY (Don't Repeat Yourself), т.е. не повторять один и тот же код в разных частях программы. Web приложение должно содержать реализацию модели, представления и котроллера (Model-View-Controller). Причем класс модели должен быть общим для оконного и Web приложения. Модель должна содержать методы ввода и вывода в файлы. В интерфейсе пользователя каждый элемент вводимых данных (элемент матрицы, вектора и т.д.) должен быть представлен как отдельный элемент управления.

Содержание отчета

1. Постановка задачи

2. Диаграмма классов

3. Сравнение программных реализаций

4. Выводы

5. Приложения

5.1. Результаты тестирования

5.2. Листинги программ

 

Методические указания

Разработка на Rails

Приведенные команды выполняются из командной строки. Во время выполнения необходима связь с интернет.

Установка Rails:

gem install rails

 

Создание приложения simpletable:

rails simpletable

 

 

Настройка приложения для выполнения лабораторной работы (для Rails 2.0.2)

В файле \config\environment.rb:

Указать параметры конфигурации

Не использовать базу данных:

config.frameworks -= [:active_record,:active_resource,:action_mailer ]

Выключить защиту от возможных атак на web-приложение:

config.action_controller.allow_forgery_protection = false

 

 

Запустить сервер WEBrick из командной строки

ruby script\server

 

В браузере набрать

https://localhost:3000

 

Создание контроллера из командной строки

ruby script\generate controller MyTable

 

 

Создать файл с моделью

app\models\my_table.rb

 

class MyTable

def load

s = File.open('1.txt','r').readlines

@d = Array.new(s.size) do |i|

a = s[i].split(' ')

a.each_index{ |j| a[j] = a[j].to_i }

a

end

end

def save

File.open('1.txt','w') do |f|

@d.each{ |r| f.puts r.join(' ') }

end

end

def get_table

@d

end

def set_table(t)

@d = t

end

def get_sum

s = 0

@d.each { |r| r.each{ |d| s+=d } }

s

end

end

 

 

Отредактировать файл контроллера:

app\controllers\my_table_controller.rb:

 

class MyTableController < ApplicationController

def index

@table = MyTable.new

@table.load

@t = @table.get_table

@s = @table.get_sum

end

 

def some_action

t = []

params['table'].each do |rnum, r|

s = []

r.each do |cnum, d|

s << d.to_i

end

t << s

end

table = MyTable.new

table.set_table(t)

table.save

redirect_to:action => 'index'

end

end

 

 

Создать файл представления

app\views\my_table\index.rhtml

 

<html>

<head>

<title>Table editor</title>

</head>

<body>

<h1>This is table</h1>

<form action="my_table/some_action" method="POST">

<% @t.each_with_index do |r,i| %>

<p>

<% r.each_with_index do |d,j| %>

<input name="table[<%= i %>][<%= j %>]" size=4 value="<%= d.to_s %>" />

<% end %>

</p>

<% end %>

<p>Summa=<%= @s %> </p>

<input type="submit" value="Ok" />

</form>

</body>

</html>

 

В браузере перейти по адресу

https://localhost:3000/my_table