Skip to content

Latest commit

 

History

History
365 lines (274 loc) · 28.2 KB

Лекция-4.md

File metadata and controls

365 lines (274 loc) · 28.2 KB

ЛЕКЦИЯ 4

СОДЕРЖАНИЕ

Использование программами компьютерной памяти

<< к содержанию лекции

Полезный материал на эту тему в четком изложении имеется также здесь

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

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

Дополнительно, о том, что такое процесс в вычислительной системе, можно посмотреть, например, здесь

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

Использование концепции виртуальной памяти в вычислительной сиситеме дает следующие преимущества

  • освобождает программиста от необходимости вручную управлять загрузкой частей программы в память и согласовывать использование памяти с другими программами
  • позволяет предоставлять программам больше памяти, чем физически установлено в системе (за счет использования дискового пространства, т.е. за счет так называемого свопинга)
  • в многозадачных системах (таких как Windows, Linux) позволяет изолировать друг от друга одновременно выполняющиеся программы, путём назначения им непересекающихся адресных пространств

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

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

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

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

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

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

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

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

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

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

В языке Julia (как и в Python, но только не в C/C++) реализован механизм так называемой автоматической сборки мусора, который автоматически освобождает фрагменты динамической памяти, после того как программа утрачивает ссылки на на эти фрагменты. Например,

r=Robot()
r=0

здесь после второго присваивания ссылка на объект типа Robot будет утрачена.

Автоматическая сборка мусора исключает так называемую утечку памяти - очень неприятный эффект, возможный при программировании на языках, где управлеине памятью возлагается на программиста (как, например, в C/C++), если только программист допустит соответствующую ошибку.

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

<< к содержанию лекции

Промежуточные утверждения

Каждая подпрограмма или даже просто участок кода предполагаю свое условие "ДАНО" и условие "РЕЗУЛЬТАТ". Поэтому если программный код включает последовательный вызов подпрограмм (или просто логически законченных участков код), то в промежутки между ними целесообразно включать комментарии, содержащие соответствующие утверждения.

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

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

@assert x>0

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

@assert isborder(r,Sud) && isborder(r,West)

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

Циклы

<< к содержанию лекции

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

Cвойство цикла с предусловием

Для любого цикла с предусловием верно:

while Условие_продолжения_цикла == true
    ...
end
#УТВ: Условие_продолжения_цикла == false

что очевидно.

Инвариант цикла и метод доказательства правильности цикллического алгоритма

<< к содержанию лекции

Инвариантом цикла с предусловием называется какое-либо условие (предикат), которое имеет значение true перед началом выполнения этого цикла и после любого числа его повторений.

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

Пример использования инварианта в доказательстве правильности алгоритма: замаркировать ряд от начала до конца

<< к содержанию лекции

Первый вариант

function mark_beg_end(r,side) # - маркировать от начала до конца
    putmarker!(r)
    #ИНВАРИАНТ: В клетке с Роботм и во всех передыдущих (по ходу движения) стоят маркеры
    while isborder(r,aide)==false
        move!(r,side)
        putmarker!(r)
    end
    #УТВ: Робот - в последней (по ходу движения) клетке
end

Имеем доказательство правильности алгоритма:

ИНВАРИАНТ && УТВ => весь ряд замаркирован от начала до конца

Второй вариант

function mark_beg_end(r,side) # - маркировать от начала до конца
   
    #ИНВАРИАНТ: Во всех передыдущих (по ходу движения) клетках стоят маркеры
    while isborder(r,aide)==false
        putmarker!(r)
        move!(r,side)      
    end
    #УТВ: Робот - в последней (по ходу движения) клетке
    putmarker!(r)
end

Имеем тоже самое доказательство правильности алгоритма: ИНВАРИАНТ && УТВ => весь ряд замаркирован от начала до конца

Но, с точки зрения следования принципу повторного использования кода, лучше было бы так

mark_beg_end(r,side) = (putmarker!(r); putmarkers!(r,side))

где

function putmarkers!(r,side)
    #ИНВАРИАНТ: Во всех передыдущих (по ходу движения) клетках, за исключением начальной, стоят маркеры
    while isborder(r,side)==false
        move!(r,side)
        putmarker!(r)
    end
end

ЗАМЕЧАНИЕ. Если в теле цикла с предусловием имеются операторы break или return, то они могут нарушать "естественный" порядок выполнения операторов, составляющих тело этого цикла, и, следовательно, метод доказательства правильности такого цикла на основе инварианта цикла будет не применим. Точно также для цикла с постусловием понятие инварианта цикла не работает.

Опасность и нежелательность цикла с постусловием*

<< к содержанию лекции

В языке Julia, как и в языке Python специальной конструкции "цикл с постусловием", нет, но вот, например, в языке C/C++ она есть:

do
    ....
while(Условие_продолжения_цикла == true)

Но в Julia такой цикл тоже можно организовать

while true
    ....
    if Условие_продолжения_цикла == false
        break
    end
end

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

С помощью цикла с предусловием решение запищется так:

while isborder(r,Ost)==false
    move!(r,Ost)
end

И это, очевидно, будет правильно во ВСЕХ возможных случаях. А вот если мы попытаемся записать решение с помощью цикла с постусловием, т.е. так:

while true
    move!(r,Ost)
    if isborder(r,Ost) == true
        break
    end
end

то получимм код, который правильно работает во вех случаях КРОМЕ одного, а именно, кроме случая, когда Робот изначально стоит рядом с перегородкой. Опасность такого кода состоит в том, что его многократно можно тестировать и не обнаружить никакой ошибки, но она есть (!), и может проявиться в самый не подходящий момент.

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

С помощью цикла с предусловием это запишется так:

# n - заданое целое неотрицательное число
p=1
while n>0
    n -= 1
    p *= 2
end
#УТВ: p=2^n

А вот использование цикла с постусловием и в этом случае может породить ошибку:

# n - заданое целое неотрицательное число
p=1
while true
    n -= 1
    p *= 2
    if n<0
        break
    end
end
#УТВ: p=2^n при n>0, НО ТОЛЛЬКО НЕ ПРИ n=0 (!)

При n=0 вместо требуемой 1 получится 2 (!).

Вывод: циклом с постусловием лучше всего никогда не пользоваться.

Пример: алгоритм подсчёта числа перегородок в ряду

<< к содержанию лекции

Пусть требуется решить следующую задачу.

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

РЕЗУЛЬТАТ: Робот - противоположной грагицы поля и функция возвращает число горизонтальных перегородок, находящихся непосредственно над рядом с роботом

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

Метод переменной состояния

<< к содержанию лекции

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

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

function num_borders(r::Robot,side::HorizonSide)
    state = false # по условию у границы перегородки сверху быть не может
    num=0
    #ИНВАРИАНТ: num = число ранее (по ходу движения) обнаруженных перегородок
    while move!(r,side)==false
        move!(r,side)
        if state==false 
            if isborder(r,Nord)==true
                num += 1
                state = true
            end
        end
    end
    #УТВ: Робот - в конце ряда (следовательно, больше в этом ряду необнаруженных перегородок нет)
    return num
end
Альтернативный способ

<< к содержанию лекции

В этом решении состояние алгоритма фиксировалось в специальной переменной, однако для фиксации состояния можно обойтись и без перемнной. А именно, можно использовать две вспомогательные функции: пойти_промежуток и пройти_мимо_перегородки, и две ити функции выполнять в цикле поочередно в указанном порядке, пока не будет достигнут конец ряда. Тогда во время выполнения первой из вспомогательных функций алгороитм будет находиться в одном состоянии, а при выполнении второй функции, алгоритм будет находиься во втором состоянии. Вот реализация этой идеи.

function num_borders(r::Robot,side::HorizonSide)
    num=0
    while isborder(r,side)==false
        if попытка_пройти_промежуток(r,side) = true
            #УТВ: Робот в начале очередной перегородки 
            num += 1
            пройти_мимо_перегородки(r,side)
        end
    end
    return num
end

function попытка_пройти_промежуток(r::Robot,side::HorizonSide) 
    while isborder(r,Nord)==false 
        if isborder(r,side) = true
            return false
        end
        move!(r,side) e
    end
    return true
end

пройти_мимо_перегородки(r::Robot,side::HorizonSide) = while isborder(r,Nord)==true move!(r,side) end

<< к содержанию лекции