Внешняя память компьютера

     Добавление  элемента, называемое также проталкиванием (push), возможно только в вершину стека (добавленный элемент становится первым сверху). Удаление элемента, называемое также выталкиванием (pop), тоже возможно только из вершины стека, при этом второй сверху элемент становится верхним.

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

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

     В ЦВК стек называется магазином —  по аналогии с магазином в огнестрельном  оружии (стрельба начнётся с патрона, заряженного последним)

 

     О́чередь — структура данных с дисциплиной доступа к элементам «первый пришёл — первый вышел» (FIFO, First In — First Out). Добавление элемента (принято обозначать словом enqueue — поставить в очередь) возможно лишь в конец очереди, выборка — только из начала очереди (что принято называть словом dequeue — убрать из очереди), при этом выбранный элемент из очереди удаляется.

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

     [править]Массив

     Первый  способ представляет очередь в виде массива и двух целочисленных переменных start и end. 
 
Обычно start указывает на голову очереди, end — на элемент, который заполнится, когда в очередь войдёт новый элемент. При добавлении элемента в очередь в q[end] записывается новый элемент очереди, а end уменьшается на единицу. Если значение end становится меньше 1, то мы как бы циклически обходим массив и значение переменной становится равным n. Извлечение элемента из очереди производится аналогично: после извлечения элемента q[start] из очереди переменная start уменьшается на 1. С такими алгоритмами одна ячейка изn всегда будет незанятой (так как очередь с n элементами невозможно отличить от пустой), что компенсируется простотой алгоритмов.

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

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

     [править]Связный список

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

     Преимущества  данного метода: размер очереди ограничен  лишь объёмом памяти.

     Недостатки: сложнее в разработке; требуется  больше памяти; при работе с такой  очередью память сильнее фрагментируется; работа с очередью несколько медленнее.

     [править]Реализация на двух стеках

     Очередь может быть построена из двух стеков S1 и S2 как показано ниже:

     Процедура enqueue(x):

         S1.push(x)

 

     Процедура dequeue():

         если S2 пуст:

             если S1 пуст:

                 сообщить об ошибке: очередь пуста

 

             пока S1 не пуст:

                 S2.push(S1.pop())

 

         return S2.pop()

     Такой способ реализации наиболее удобен в  качестве основы для построения персистентной очереди.

 
 

     FIFO — акроним First In, First Out («первым пришёл — первым ушёл», англ. ), абстрактное понятие в способах организации и манипулирования данными относительно времени и приоритетов. Это выражение описывает принцип технической обработки очереди или обслуживания конфликтных требований путём упорядочения процесса по принципу: «первым пришёл — первым обслужен» (ПППО). Тот, кто приходит первым, тот и обслуживается первым, пришедший следующим ждёт, пока обслуживание первого не будет закончено, и т.д.

     Этот  принцип аналогичен поведению лиц, стоящих в очереди, когда люди получают обслуживание в том порядке, в котором они занимали очередь. То же самое происходит, например, на нерегулируемом перекрёстке, когда  водители ожидают своей очереди  на продолжение движения (в американских ПДД нет правила «помеха справа», приоритет определяется по принципу FIFO). ПППО также используется как сокращённое название для алгоритма FIFO планирования работы операционной системы, по которому процессорное время выделяется каждому процессу в порядке их поступления на обслуживание. В более широком смысле, абстракция LIFO или Last-In-First-Out («последним пришёл — первым ушёл») является противоположностью абстракции FIFO. Разница, возможно, станет яснее, если принять во внимание реже используемый синоним FILO, означающий First-In-Last-Out («первым пришёл — последним ушёл»). В сущности, обе абстракции являются конкретными случаями более общего понятия работы со списком. Разница не в списке (данных), а в правиле доступа к содержимому. В первом случае добавление делается к одному концу списка, а снятие с другого, во втором случае добавление и снятие делается на одном конце.[1]

     Вариантом очереди является очередь с приоритетом, для которой нельзя использовать название FIFO, потому что в этом случае обработка структуры данных происходит по другому принципу. Теория массового  обслуживания охватывает более общее  понятие очереди, а также взаимодействие между очередями, обслуживание в  которых осуществляется по принципу «строго-FIFO». LIFO — акроним Last In, First Out («последним пришёл — первым ушёл», англ. ), абстрактное понятие в способах организации и манипулирования данными относительно времени и приоритетов. В структурированном линейном списке, организованном по принципу LIFO, элементы могут добавляться и выбираться только с одного конца, называемого «вершиной списка».[1] Структура LIFO может быть проиллюстрирована на примере стопки тарелок: чтобы взять вторую сверху, нужно снять верхнюю, а чтобы снять последнюю, нужно снять все лежащие выше. Термин относится к абстрактным принципам обработки списков и временного хранения данных, в частности, когда нужно иметь доступ к ограниченному набору данных в определённом порядке. Принцип LIFO применяется в тех случаях, когда последние данные, добавленные в структуру, должны быть первыми удалены или обработаны. Полезная аналогия с офисным работником: человек может работать только с одной страницей в каждый момент времени, поэтому очередной документ добавляется в папку сверху к стопке предыдущих. По аналогии с этим в компьютере тоже есть ограничения, такие как ширина шины данных и тот факт, что в каждый момент времени система может манипулировать только с одной ячейкой памяти.[2] Абстрактный механизм LIFO, применяемый в вычислениях, реализуется в реальных структурах данных в виде стека, название кототого совершенно очевидно имеет отношение к «пачке бумаги», «стопке тарелок» и т. п. (англ. stack переводится как «штабель, кипа, стопка»). В качестве синонима иногда используется термин FILO («first in, last out», «первым пришёл, последним ушёл»), в котором акцентируется, что более ранние дополнения к списку должны ожидать, пока они не поднимутся в структуре на самый верх, после чего к ним будет получен доступ. В теории массового обслуживания иногда используется термин LCFS («last come, first served», «последним пришёл, первым обслужен»). Различие между обобщённым списком, массивом, очередью и стеком определяется правилами, используемыми в механизме доступа к данным.[2] В любом случае в структуре LIFO организован доступ в обратном порядке по сравнению с очередью. «Имеются определённые, часто встречающиеся ситуации в области компьютерных наук, когда нужно ограничить вставки и удаления в списки так, чтобы эти изменения могли происходить только в начале или в конце списка, но не в его середине. В таких случаях полезны две структуры данных: стеки и очереди».[3]

     2.2.Структры  управления.

     Процессы.

 
 
 
 
 
 
 
 
 
 

     Интерфейсы  объектов

 
 

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

 
 

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

 
 

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

 
 
 

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

     3.1.ОС

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

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

 

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

 

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

 

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

 

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

 

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