Разработка программы, реализующей алгоритм двусвязного списка - Программирование, компьютеры и кибернетика курсовая работа
Главная
Программирование, компьютеры и кибернетика
Разработка программы, реализующей алгоритм двусвязного списка
Определение назначения и описание функций дискового кэша как промежуточного буфера с быстрым доступом к информации. Процесс кэширования внешних накопителей. Построение алгоритма, описание интерфейса и разработка программы для работы с двусвязным списком.
посмотреть текст работы
скачать работу можно здесь
полная информация о работе
весь список подобных работ
Нужна помощь с учёбой? Наши эксперты готовы помочь!
Нажимая на кнопку, вы соглашаетесь с
политикой обработки персональных данных
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Разработка программы, реализующей алгоритм двусвязного списка
2.4 Кэширование внешних накопителей
4. Список использованной литературы
Цель курсовой работы - закрепление и углубление знаний, полученных при изучении курса «Основы алгоритмизации и программирования» посредством разработки программного обеспечения для компьютера.
дисковый кэш алгоритм программа список
2. Теоритический вопрос Windows. Дисковый кэш
Снижение эффективности, замедление работы системы пользователь замечает в процессе выполнения команд.
Процессор сохраняет временные результаты своей работы в области, называемой регистрами. Так как регистры находятся внутри процессора, доступ к его содержимому осуществляется очень быстро. К сожалению, во время выполнения команд большая их часть (и данные) располагаются в памяти, и процессор должен ожидать завершения двух медленных операций системной шины:
Чтобы уменьшить количество операций, разработчики поместили в процессор дорогостоящие, но быстродействующие устройства памяти (оно называется КЭШ памяти процессора).
Кэш (англ. cache , от фр. cacher -- «прятать») -- промежуточный буфер с быстрым доступом, содержащий информацию, которая может быть запрошена с наибольшей вероятностью. Доступ к данным в кэше идёт быстрее, чем выборка исходных данных из оперативной (ОЗУ) и быстрее внешней (жёсткий диск или твердотельный накопитель) памяти, за счёт чего уменьшается среднее время доступа и увеличивается общая производительность компьютерной системы.
Впервые слово «cache» в компьютерном контексте было использовано в 1967 году во время подготовки статьи для публикации в журнале «IBM Systems Journal». Статья касалась усовершенствования памяти в разрабатываемой модели 85 из серии IBM System/360. Редактор журнала Лайл Джонсон попросил придумать более описательный термин, нежели «высокоскоростной буфер», но из-за отсутствия идей сам предложил слово «cache». Статья была опубликована в начале 1968 года, авторы были премированы IBM, их работа получила распространение и впоследствии была улучшена, а слово «кэш» вскоре стало использоваться в компьютерной литературе как общепринятый термин.
Кэш -- это память с большей скоростью доступа, предназначенная для ускорения обращения к данным, содержащимся постоянно в памяти с меньшей скоростью доступа (далее «основная память»). Кэширование применяется ЦПУ, жёсткими дисками, браузерами, веб-серверами, службами DNS и WINS.
Кэш состоит из набора записей. Каждая запись ассоциирована с элементом данных или блоком данных (небольшой части данных), которая является копией элемента данных в основной памяти. Каждая запись имеет идентификатор, определяющий соответствие между элементами данных в кэше и их копиями в основной памяти. Когда клиент кэша (ЦПУ, веб-браузер, операционная система) обращается к данным, прежде всего, исследуется кэш. Если в кэше найдена запись с идентификатором, совпадающим с идентификатором затребованного элемента данных, то используются элементы данных в кэше. Такой случай называется попаданием кэша . Если в кэше не найдена запись, содержащая затребованный элемент данных, то он читается из основной памяти в кэш, и становится доступным для последующих обращений. Такой случай называется промахом кэша . Процент обращений к кэшу, когда в нём найден результат, называется уровнем попаданий или коэффициентом попаданий в кэш.
Например, веб-браузер проверяет локальный кэш на диске на наличие локальной копии веб-страницы, соответствующей запрошенному URL. В этом примере URL -- это идентификатор, а содержимое веб-страницы -- это элементы данных.
Если кэш ограничен в объёме, то при промахе может быть принято решение отбросить некоторую запись для освобождения пространства. Для выбора отбрасываемой записи используются разные алгоритмы вытеснения.
При модификации элементов данных в кэше выполняется их обновление в основной памяти. Задержка во времени между модификацией данных в кэше и обновлением основной памяти управляется так называемой политикой записи . В кэше с немедленной записью каждое изменение вызывает синхронное обновление данных в основной памяти.
В кэше с отложенной записью (или обратной записью ) обновление происходит в случае вытеснения элемента данных, периодически или по запросу клиента. Для отслеживания модифицированных элементов данных записи кэша хранят признак модификации ( изменённый или «грязный» ). Промах в кэше с отложенной записью может потребовать два обращения к основной памяти: первое для записи заменяемых данных из кэша, второе для чтения необходимого элемента данных. В случае, если данные в основной памяти могут быть изменены независимо от кэша, то запись кэша может стать неактуальной . Протоколы взаимодействия между кэшами, которые сохраняют согласованность данных, называют протоколами когерентности кэша .
2.4 Кэширование внешних накопителей
Многие периферийные устройства хранения данных используют внутренний кэш для ускорения работы, в частности, жёсткие диски используют кэш-память от 1 до 64 Мбайт (модели с поддержкой NCQ/TCQ используют её для хранения и обработки запросов), устройства чтения CD/DVD/BD-дисков также кэшируют прочитанную информацию для ускорения повторного обращения.
Операционная система также использует часть оперативной памяти в качестве кэша дисковых операций (например, для внешних устройств, не обладающих собственной кэш-памятью, в том числе жёстких дисков, flash-памяти и гибких дисков). Часто для кэширования жёстких дисков предоставляется вся свободная (не выделенная процессам) оперативная память. Применение кэширования внешних накопителей обусловлено следующими факторами:
1. скорость доступа процессора к оперативной памяти во много раз больше, чем к памяти внешних накопителей;
2. производительность дисковых устройств хранения (жесткие, гибкие, оптические диски) максимальна при чтении-записи нескольких последовательно расположенных блоков и значительно уменьшается при одиночных запросах в разные места диска, что связано с инерцией механического привода головки.
3. крайне неравномерная частота обращения к различным блокам памяти внешних накопителей:
1. использование части блоков несколькими процессами одновременно, по чтению и записи (например, в базах данных)
2. очень частое чтение части блоков (индексные файлы, каталоги в файловой системе)
3. очень частая запись части блоков (файлы логов, журналов, баз данных; метаданные файловой системы).
При чтении кэш позволяет прочитать блок один раз, затем хранить одну копию блока в оперативной памяти для всех процессов и выдавать содержимое блока «мгновенно» (по сравнению с запросом к диску). Существует техника «предзапроса» -- в фоновом режиме операционной системой считываются в кэш также несколько следующих блоков (после нужного).
При записи кэш позволяет сгруппировать короткие записи в более крупные, которые эффективнее обрабатываются накопителями, либо избежать записи промежуточных модификаций. При этом все промежуточные состояния блока видны процессам из оперативной памяти.
Кэширование внешних устройств хранения значительно увеличивает производительность системы за счёт оптимизации использование ввода-вывода. Преимуществом технологии является прозрачная (незаметная для программ) автоматическая оптимизация использования памяти-дисков при неизменности логики приложений, работающих с файлами.
Недостатком кэширования записи является промежуток времени между запросом на запись от программы и фактической записью блока на диск, а также изменение порядка выполнения записей, что может приводить к потерям информации или несогласованности структур при сбое питания или зависании системы. Данная проблема сглаживается принудительной периодической синхронизацией (записью изменённых строк кэша).
Разработать программу, реализующую алгоритм двусвязного списка (20 элементов). В качестве элемента списка выбрать структуру:
Предусмотреть заполнение списка из файла (подготовить файл на 20 элементов).
2) Вставка элемента (с консоли) в список
b) вслед за указанным элементом (по ключу)
3) Вставка элементов (из файла) в список
b) вслед за указанным элементом (по ключу)
5) Очистка списка (с выводом удаляемых элементов)
6) Вывод элементов, содержащихся в списке
7) Вывод количества элементов в списке
Программа реализованная в данной курсовой работе предназначена для работы с двусвязным списком. Меню программы выглядит так:
При выборе первого пункта меню вызывается функция enter, пользователю предоставляется выбор: заполнить список с консоли или считать из файла желаемое количество элементов.
При выборе второго пункта меню вызывается функция insert1, пользователь вводит элемент с консоли и ему предоставляется выбор: добавить его в конец списка или по ключу.
При выборе третьего пункта меню вызывается функция insert2, элемент считывается их файла и пользователю предоставляется выбор: добавить в конец списка или по ключу.
При выборе четвертого пункта меню вызывается функция delet,
пользователю предоставляется выбор: удалить элемент по ключу или из конца списка.
При выборе пятого пункта меню вызывается функция clean, пользователю предоставляется выбор: отчистить список безвозвратно или с сохранением в файл.
При выборе шестого пункта меню вызывается функция print, пользователю предоставляется выбор: вывести список на экран или сохранить его в файл.
При выборе седьмого пункта меню вызывается функция number, на экран выводится количество элементов в списке.
При выборе восьмого пункта меню происходит завершение программы.
Закрепил и углубил знаний, полученные при изучении курса «Основы алгоритмизации и программирования» посредством разработки программного обеспечения для компьютера. Разработал программу, реализующую алгоритм двусвязного списка.
4. Список использованной литературы
1. Шилдт Герберт. Справочник программиста С,С++.
2. Онлайн справочник: http://autodor-book.com/publ/complex_hardware/lectures/tema_11_tverdotelnye_nakopiteli/2-1-0-52
3. Системное программирование: http://sistemprog.elitno.net/lec/modul_3/lec_09/lec_31-3.html
4. Википедия: http://ru.wikipedia.org/wiki/%D0%9A%D1%8D%D1%88
5. Введение в язык C++. Бьерн Страуструп, 1995.
"----------------------------------------"< - Вставка элемента в список с консоли"< - Вставка элемента в список из файла"< - Очистка списка с выводом их на экран"< - Вывод количества элементов в списке"< - заполнение с консоли"< - конец операции ввода"<3) throw (char*)"Ошибка ввода, попробуйте заново";
m:if(countelem==20) throw(char*)"Список полный, выберите другую операцию";
cout<<"Введите желаемое количество элементов в списке: ";
faculty *pf = new faculty; // временная переменная
cout< - вставить в конец списка"<3) throw (char*)"Ошибка ввода, попробуйте заново";
if(p==1) //вставка элемента в конец списка
if(countelem==20) throw(char*)"Список полный, выберите другую операцию";
cout<<"Введите название факультета: ";
cout<<"Введите количество кафедр: ";
if(phead==0) // вставка если первый элемент
phead=pf; //голова указывает на созданный элемент
catch(char *str) //сообщение и конец операции если список полон
else if(p==2) //вставка элемента по ключу
if(countelem==20) throw(char*)"Список полный, выберите другую операцию";
faculty *temp=phead; //создание временного элемента
cout<<"Введите название факультета: ";
cout<<"Введите количество кафедр: ";
cout<<"Список пуст, элемент будет первым"<code==last->code) //если элемент последний
else // если элемент в любой позиции
catch(char*str) // сообщение и рестарт операции если ошибка ввода
catch(char *str) //сообщение и конец операции если список полон
else if(p==3) return; //конец операции
catch(char*str) // сообщение и рестарт операции если не правильный выбор
void insert2() //вставка элемента из файла в список
while(true) //цикл для выбора операции вставки элемента
"<1> - вставить в конец списка"<3) throw (char*)"Ошибка ввода, попробуйте заново";
if(p==1) //вставка элемента в конец списка
if(countelem==20) throw(char*)"Список полный, выберите другую операцию";
f = fopen("Список_структур.dat","r");
while(temp!=NULL) // проверка совпадения
if(temp==0) // вставка первого элемента
phead=pf; //голова указывает на созданный элемент
catch(char*str) // сообщение и конец операции если список полон
else if(p==2) //вставка элемента по ключу
if(countelem==20) throw(char*)"Список полный, выберите другую операцию";
f = fopen("Список_структур.dat","r");
while(temp!=0) // проверка совпадения
if(temp==NULL) // вставка первого элемента
cout<<"Список пуст, элемент будет первым"<code==last->code) //если элемент последний
catch(char*str) // сообщение и рестарт операции если ошибка ввода
catch(char*str) // сообщение и конец операции если список полон
else if(p==3) return; //конец операции
catch(char*str) // сообщение и рестарт операции если не правильный выбор
void delet() //функция для выбора операции удаления элемента
faculty *temp=last; //создается временный элемент
faculty *ptemp=phead; //создается временный элемент
cout<<"Список пуст,сначала заполните его"< - удалить из конца списка"<3) throw (char*)"Ошибка ввода, попробуйте заново";
if(ptemp->code==temp->code) // если единственный элемент в списке
if(ptemp==NULL) throw(char*)"Элемента с таким ключом нет";
if(ptemp->code==phead->code && ptemp->code==last->code) // если элемент единственный
else if(ptemp->code==phead->code) // если элемент первый
else if(ptemp->code==last->code) //если элемент последний
catch(char*str) // сообщение и рестарт если ошибка ввода
else if(p==3) return; //конец операции
catch(char*str) // сообщение и рестарт операции если не правильный выбор
void clean() //функция для отчистки списка
faculty *temp=last; //создается временный элемент
faculty *ptemp=phead; //создается временный элемент
cout<<"Список пуст,сначала заполните его"< - отчистить безвозвратно"< - отчистить с сохранением в файл"<3) throw (char*)"Ошибка ввода, попробуйте заново";
if(p==1) //удаление списка безвозвратно с выводом на экран
while (ptemp!=0) // вывод на экран списка
cout<code<name<fio<numkaf<teacher< - вывод списка на экран"< - вывод списка в файл"< - конец операции ввода"<3) throw (char*)"Ошибка ввода, попробуйте заново";
cout<code<name<fio<numkaf<teacher<Разработка программы, реализующей алгоритм двусвязного списка курсовая работа. Программирование, компьютеры и кибернетика.
Правильное Оформление Реферата
Реферат по теме Спадкування за заповітом
Курсовая Работа На Тему Существенность В Аудите
Курсовая Работа На Тему Страхи Дітей Молодшого Шкільного Віку
Контрольная работа: Экологическая оценка церкви Петра и Павла
Курсовая работа по теме Логико-семантические идеи Г.Фреге
Этикетные Формы Общения Реферат
Красная Книга Растений Реферат
Контрольная работа по теме Налоговые агенты. Специальные налоговые режимы
Курсовая работа: Понятие и признаки преступления
Контрольная работа по теме Построение экономико-математических моделей производства продукции
Доклад по теме Гонконг
Реферат по теме Тушение пожаров на электроустановках, электростанциях и подстанциях
Сочинение На Тему Красота Природы 4 Класс
Курсовая работа по теме Проектирование трехэтажного кирпичного дома
Контрольная Работа Комбинаторика И Теория Вероятностей
Реферат по теме Реалізація концепції міжнародної кримінальної юрисдикції в заснуванні та діяльності Нюрнберзького і Токійського воєнних трибуналів
Дипломная Цена
Реферат: Особенности организации физкультурно-оздоровительной работы в детском саду
Обучение письменной речи на французском языке в старших классах
Основы и расчетные процедуры по определение надежности продукции - Менеджмент и трудовые отношения контрольная работа
Паризький університет - Педагогика контрольная работа
Ассортимент и свойства продуктов питания и промышленных товаров - Маркетинг, реклама и торговля контрольная работа