Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 4.66/29: Рейтинг темы: голосов - 29, средняя оценка - 4.66
 Аватар для Visary_Master
17 / 18 / 1
Регистрация: 01.12.2010
Сообщений: 296

Алгоритмы замещения страниц(STL, вторая попытка)

26.02.2012, 19:19. Показов 6229. Ответов 6
Метки нет (Все метки)

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

Код:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include <iostream>
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <deque>
#include <algorithm>
#include <utility>
#include <cstdlib>
 
void show_fifo(const deque<int> &dq)
{
    deque<int>::const_iterator i;
    for (i=dq.begin(); i != dq.end(); ++i)
    {
        cout << *i << " ";
    }
     cout << endl;
}
int main()
{
    int mem_size = 5;
    int access_num;
    access_num = 13;
    int array[] = { 1, 2, 3, 4, 5, 2, 3, 4, 1, 5, 4, 1, 3};
 
    cout << "Vtoraya popbitka: " << endl;
    // Vtoraya popitka
    deque<int> dq;    
    
    for (int i=0; i<mem_size; i++)
    {
        dq.push_back(-1);
    }
    cout << "Memory: " << endl;
    show_fifo(dq);
 
    for (int i = 0; i < access_num; ++i)
    {
        cout << "Step " << (i+1) << ":" << endl;
        for (int j = 0; j < dq.size(); j++)
        {
                if ((find(dq.begin(), dq.end(), array[i]) != dq.end()) && (dq.size() != 0))
                {   
                    cout << "Page: " << array[i] << " has in memory" << endl;
                    int del = dq.at(array[i]);
                    dq.erase(dq.begin()+del);
                    dq.push_front(array[i]);
                    break;
                }
                else
                {
                    dq.push_front(array[i]);
                    dq.pop_back();
                    break;
                }
        }
        show_fifo(dq);
    }
Добавлено через 3 часа 57 минут
upppp!!!
0
cpp_developer
Эксперт
20123 / 5690 / 1417
Регистрация: 09.04.2010
Сообщений: 22,546
Блог
26.02.2012, 19:19
Ответы с готовыми решениями:

Помогите разобраться (STL, алгоритмы замещения страниц)
Здравствуйте, хочу реализовать алгоритм замещения страниц памяти FIFO. Не знаю как организовать проверку на присутствие страницы в...

Алгоритм замещения страниц LRU с помощью методов библиотеки STL
Здравствуйте! Мне нужно реализовать алгоритм замещения страниц LRU с помощью методов библиотеки STL. Подскажите пожалуйста, как это сделать...

Кэш память. Алгоритмы замещения страниц. Алгоритм вторая попытка. Модель.
Алгоритм вторая попытка. Я сделал ее модель в ввиде односвязного списка, очереди. Подскажите правильно ли я все реализовал? Вот...

6
DU
1500 / 1146 / 165
Регистрация: 05.12.2011
Сообщений: 2,279
26.02.2012, 20:15
не совсем понятно что у вы там хотели

У меня сделано так, что находится страница которая есть в памяти, и удаляется по ее позиции...
Вот это довольно неясная формулировка. Должна была удалятся найденная страница страница, у которой индекс в деке совпадает с знацением найденной страницы. Скорее всего имелось в виду первое. Если так, то ошибка в строках 45 и 46.
Вот маленько порефакторенный и исправленный код

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include <iostream>
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <deque>
#include <algorithm>
#include <utility>
#include <cstdlib>
 
using namespace std;
 
void show_fifo(const deque<int>& dq)
{
  deque<int>::const_iterator i;
  for (i=dq.begin(); i != dq.end(); ++i)
  {
    cout << *i << " ";
  }
  cout << endl;
}
 
int main()
{
  const int mem_size = 5;
  const int access_num = 13;
  const int array[] = {1, 2, 3, 4, 5, 2, 3, 4, 1, 5, 4, 1, 3};
 
  cout << "Vtoraya popbitka: " << endl;
  deque<int> dq(mem_size, -1);
 
  cout << "Memory: " << endl;
  show_fifo(dq);
 
  for (int i = 0; i < access_num; ++i)
  {
    cout << "Step " << (i+1) << ":" << endl;
 
    deque<int>::iterator pageIter = find(dq.begin(), dq.end(), array[i]);
    if (pageIter != dq.end())
    {       
      cout << "Page: " << array[i] << " has in memory" << endl;
      dq.erase(pageIter);
    }
    else
    {
      cout << "Page: " << array[i] << " not found" << endl;
      dq.pop_back();
    }
 
    dq.push_front(array[i]);
  }
 
  show_fifo(dq);
 
  return 0;
}
1
 Аватар для Visary_Master
17 / 18 / 1
Регистрация: 01.12.2010
Сообщений: 296
26.02.2012, 20:31  [ТС]
Ошибку странную выдает...
Миниатюры
Алгоритмы замещения страниц(STL, вторая попытка)  
0
DU
1500 / 1146 / 165
Регистрация: 05.12.2011
Сообщений: 2,279
26.02.2012, 21:09
хм. у меня без таких глюков.
код в чистом виде скопипастил или модифицировалось что-то после этого?
1
 Аватар для Visary_Master
17 / 18 / 1
Регистрация: 01.12.2010
Сообщений: 296
26.02.2012, 21:28  [ТС]
Цитата Сообщение от DU Посмотреть сообщение
код в чистом виде скопипастил или модифицировалось что-то после этого?
Чисто скопипастил, ну и убрал там немного, чтобы переопределений не было, просто у меня 3 алгоритма, фифо, лру, и вторая попытка. Ошибка всегда на последнем элементе последовательности возникает, прога не знает как завершить успешно работу. Может там нужно обработать какое-то исключение?
0
DU
1500 / 1146 / 165
Регистрация: 05.12.2011
Сообщений: 2,279
26.02.2012, 21:31
очевидно, что где-то там ошибка. и нет смысла о ней говорить не видя кода. может быть все, что угодно. весь код сюда выкладывайте.
1
 Аватар для Visary_Master
17 / 18 / 1
Регистрация: 01.12.2010
Сообщений: 296
26.02.2012, 22:49  [ТС]
Все, разобрался. Просто последовательность страниц у меня была организована как динамический массив, для проверки я создал и инициализировал обычный массив, просто забыл в конце закомментить освобождение памяти.

Добавлено через 7 минут
А можете помочь с более сложным алгоритмом LRU?
Наработки есть, мне помогали в другой теме.

Добавлено через 41 минуту
Ссылка на тему с LRU
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
raxper
Эксперт
30234 / 6612 / 1498
Регистрация: 28.12.2010
Сообщений: 21,154
Блог
26.02.2012, 22:49
Помогаю со студенческими работами здесь

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

Реализация механизма замещения страниц в ОП
Необходимо реализовать модель «реализация механизма замещения страниц в ОП». Существует список из N активных страниц (по желанию можно...

вторая попытка ввода функции
помогите с задачей:вычислить значение функции y=4X^3-2X^2+5 для значений X,изменяющихся от -3 до1 с шагом 0.1

Замещение страниц - Модели алгоритмов замещения станиц (LRU)
нужно написать программу,а точнее курсовую на тему: &quot;Модели алгоритмов замещения станиц(LRU)&quot; помогите понять,если можно,то и...

STL алгоритмы сортировки
Здрасти. В STL есть алгоритмы sort - упорядочивает последовательность и stable_sort - упорядочивает последовательность, не меняя...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
7
Ответ Создать тему
Новые блоги и статьи
делаю науч статью по влиянию грибов на сукцессию
anaschu 13.03.2026
прикрепляю статью
SDL3 для Desktop (MinGW): Создаём пустое окно с нуля для 2D-графики на SDL3, Си и C++
8Observer8 10.03.2026
Содержание блога Финальные проекты на Си и на C++: hello-sdl3-c. zip hello-sdl3-cpp. zip Результат:
Установка CMake и MinGW 13.1 для сборки С и C++ приложений из консоли и из Qt Creator в EXE
8Observer8 10.03.2026
Содержание блога MinGW - это коллекция инструментов для сборки приложений в EXE. CMake - это система сборки приложений. Здесь описаны базовые шаги для старта программирования с помощью CMake и. . .
Как дизайн сайта влияет на конверсию: 7 решений, которые реально повышают заявки
Neotwalker 08.03.2026
Многие до сих пор воспринимают дизайн сайта как “красивую оболочку”. На практике всё иначе: дизайн напрямую влияет на то, оставит человек заявку или уйдёт через несколько секунд. Даже если у вас. . .
Модульная разработка через nuget packages
DevAlt 07.03.2026
Сложившийся в . Net-среде способ разработки чаще всего предполагает монорепозиторий в котором находятся все исходники. При создании нового решения, мы просто добавляем нужные проекты и имеем. . .
Модульный подход на примере F#
DevAlt 06.03.2026
В блоге дяди Боба наткнулся на такое определение: В этой книге («Подход, основанный на вариантах использования») Ивар утверждает, что архитектура программного обеспечения — это структуры,. . .
Управление камерой с помощью скрипта OrbitControls.js на Three.js: Вращение, зум и панорамирование
8Observer8 05.03.2026
Содержание блога Финальная демка в браузере работает на Desktop и мобильных браузерах. Итоговый код: orbit-controls-threejs-js. zip. Сканируйте QR-код на мобильном. Вращайте камеру одним пальцем,. . .
SDL3 для Web (WebAssembly): Синхронизация спрайтов SDL3 и тел Box2D
8Observer8 04.03.2026
Содержание блога Финальная демка в браузере. Итоговый код: finish-sync-physics-sprites-sdl3-c. zip На первой гифке отладочные линии отключены, а на второй включены:. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru