Отчет по лабораторной работе 1 Системный таймер

Название	Отчет по лабораторной работе 1 Системный таймер
Дата	24.10.2021
Размер	285.45 Kb.
Формат файла
Имя файла	4851004_90002_-_Bezborodov_P_-_Laboratornaya_Rabota_1_-_Otchet.docx
Тип	Отчет #254768

Министерство образования и науки Российской Федерации
Санкт-Петербургский государственный политехнический университет
—
Институт кибербезопасности и защиты информации

ОТЧЕТ

по лабораторной работе №1

«Системный таймер»
по дисциплине «Операционные системы»

Выполнил
студент гр. 4851004/90002 П.Д.Безбородов

<подпись>

Проверил
асс. преподавателя В.М.Крундышев

<подпись>

Санкт-Петербург

2020

СОДЕРЖАНИЕ

1Формулировка задания 3

1.1Цель работы. 3

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

2Теоретические сведения 4

3Результаты работы 6

3.1Изучение работы системного таймера. 6

3.2Реализация алгоритма для предотвращения активного ожидания. 8

3.3Оценка реализованного решения. 11

4Выводы 15

Формулировка задания
1. Цель работы.

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

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

Изучение работы системного таймера и ознакомление с файлами devices/timer.c и devices/timer.h, threads/thread.h и threads/thread.c. Составление сводной таблицы по анализу исходных функций системного таймера. Построение блок-схемы алгоритма функции timer_sleep().
Разработка и реализация собственного алгоритма, позволяющего избежать активного ожидания, с целью повысить эффективность выполнения функции timer_sleep(). Построение блок-схемы алгоритма модернизированной функции timer_sleep().
Оценка реализованного решения, проведение внутренних тестов OS Pintos.

Теоретические сведения

Системный таймер является частью системы управления процессами. Функция timer_sleep(), реализованная в devices/timer.c, приостанавливает выполнение текущего процесса на заданное число тактов таймера ticks, в цикле while() проверяя текущее значение ticks и вызывая функцию thread_yield():
void timer_sleep (int64_t ticks)

{

int64_t start = timer_ticks ();

ASSERT (intr_get_level () == INTR_ON);

while (timer_elapsed (start) < ticks)

/*АКТИВНОЕ ОЖИДАНИЕ*/

thread_yield ()

}
Базовая (т.е. предоставленная разработчиками системы) реализация системного таймера содержит в себе цикл активного ожидания. Активное ожидание – это состояние процесса, при котором он многократно проверяет истинность некоторого условия, например, такого как доступность некоторых ресурсов или состояние других процессов. Очевидно, что такая реализация не только не выполняет никакой полезной работы, но и расходует ресурсы системы: использование активного ожидания приводит к бесполезному расходованию процессорного времени и, как следствие, снижению общей производительности системы. Кроме того, при некоторых стратегиях планирования времени ЦП в целом корректный алгоритм с активным ожиданием может привести к тупику.

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

Результаты работы
1. Изучение работы системного таймера.

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

Таблица 1 – Функции системного таймера (devices/timer.c и devices/timer.h).

Название функции	Аргументы	Описание (англ.)	Описание (рус.)
void timer_init (void);	void	Sets up the timer to interrupt TIMER_FREQ times per second, and registers the corresponding interrupt.	Устанавливает таймер на прерывание TIMER_FREQ раз в секунду и регистрирует соответствующее прерывание.
void timer_calibrate (void);	void	Calibrates loops_per_tick, used to implement brief delays.	Калибрует loops_per_tick, используемые для реализации коротких задержек.
void timer_sleep (int64_t ticks);	int64_t ticks	Sleeps for approximately TICKS timer ticks. Interrupts must be turned on.	Сон примерно на TICKS тактов таймера. Прерывания должны быть включенным.
void timer_msleep (int64_t milliseconds);	int64_t milliseconds	Sleeps for approximately MS milliseconds. Interrupts must be turned on.	Сон примерно на MS миллисекунд. Прерывания должны быть включенным.
void timer_usleep (int64_t microseconds);	int64_t microseconds	Sleeps for approximately US microseconds. Interrupts must be turned on.	Сон примерно на US микросекунд. Прерывания должны быть включенным.
void timer_nsleep (int64_t nanoseconds);	int64_t nanoseconds	Sleeps for approximately NS nanoseconds. Interrupts must be turned on.	Сон примерно на NS наносекунд. Прерывания должны быть включенным.
void timer_mdelay (int64_t milliseconds);	int64_t milliseconds	Busy-waits for approximately MS milliseconds. Interrupts need not be turned on.	Активное ожидание примерно MS миллисекунд. Прерывания должны быть выключенными.
void timer_udelay (int64_t microseconds);	int64_t microseconds	Sleeps for approximately US microseconds. Interrupts need not be turned on.	Активное ожидание примерно US микросекунд. Прерывания должны быть выключенными.
void timer_ndelay (int64_t nanoseconds);	int64_t nanoseconds	Sleeps execution for approximately NS nanoseconds. Interrupts need not be turned on.	Активное ожидание примерно NS наносекунд. Прерывания должны быть выключенными.
void timer_print_stats (void);	void	Prints timer statistics.	Печатает статистику таймера.
int64_t timer_ticks (void);	void	Returns the number of timer ticks since the OS booted.	Возвращает количество тактов таймера с момента загрузки ОС.
int64_t timer_elapsed (int64_t);	int64_t then	Returns the number of timer ticks elapsed since THEN, which should be a value once returned by timer_ticks().	Возвращает количество тактов таймера, прошедших с THEN, что должно возвращаться функцией timer_ticks ().

Была разработана блок-схема алгоритма функции timer_sleep(), включающей активное ожидание (см. сх. 1).

Схема 1 – Блок-схема алгоритма функции timer_sleep() до модернизации.

Реализация алгоритма для предотвращения активного ожидания.

После изучения работы системного таймера был продуман алгоритм по сохранению потоков на время их сна при помощи динамического массива структур (см. изменения файлов devices/timer.h и devices/timer.c в приложении А и Б соответственно).

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

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

Были добавлены следующие функции:

struct THREAD_SLEEP* FunctionInitializeThreadSleepArray(int64_t ticks, int64_t start); - Инициализация динамического массива для хранения спящих потоков.

struct THREAD_SLEEP* FunctionAddElementToThreadSleepArray(struct THREAD_SLEEP* ThreadSleepArray, int64_t ticks, int64_t start); - Добавление нового спящего потока в динамический массив структур.
struct THREAD_SLEEP* FunctionCheckAndUpdateThreadSleepArray(struct THREAD_SLEEP* ThreadSleepArray); - Проверка с целью переопределения памяти динамического массива структур для спящих потоков на случай, если число спящих потоков уменьшилось.
void ProcedureUpdateAndSortThreadSleepArray(struct THREAD_SLEEP* ThreadSleepArray); - Обновление переменной, отвечающей за оставшееся время сна, для каждого спящего потока и сортировка массива в порядке от большего к меньшему. Сравнение идет по количеству оставшегося времени.
void ProcedureQuickSortThreadSleepArray(struct THREAD_SLEEP* ThreadSleepArray, int LeftBorder, int RightBorder); - Процедура быстрой сортировки от большего к меньшему для исходного массива структур.

Были изменены функции timer_sleep() и timer_interrupt(). В случае с timer_sleep() (для блок-схемы алгоритма см. сх. 2) были добавлены условия для добавления нового потока в массив спящих потоков с дальнейшей блокировкой (thread_block()). Для timer_interrupt() были добавлены проверки на наличие потоков, которые должны вернуться в активное состояние (thread_unblock()).

Схема 2 – Блок-схема алгоритма модернизированной функции timer_sleep().

Оценка реализованного решения.

Ниже приведены результаты внутренних тестов Pintos OS для выполненных реализаций:

'alarm-single'

Executing 'alarm-single':

(alarm-single) begin

(alarm-single) Creating 5 threads to sleep 1 times each.

(alarm-single) Thread 0 sleeps 10 ticks each time,

(alarm-single) thread 1 sleeps 20 ticks each time, and so on.

(alarm-single) If successful, product of iteration count and

(alarm-single) sleep duration will appear in nondescending order.

(alarm-single) thread 0: duration=10, iteration=1, product=10

(alarm-single) thread 1: duration=20, iteration=1, product=20

(alarm-single) thread 2: duration=30, iteration=1, product=30

(alarm-single) thread 3: duration=40, iteration=1, product=40

(alarm-single) thread 4: duration=50, iteration=1, product=50

(alarm-single) end

'alarm-multiple'

Executing 'alarm-multiple':

(alarm-multiple) begin

(alarm-multiple) Creating 5 threads to sleep 7 times each.

(alarm-multiple) Thread 0 sleeps 10 ticks each time,

(alarm-multiple) thread 1 sleeps 20 ticks each time, and so on.

(alarm-multiple) If successful, product of iteration count and

(alarm-multiple) sleep duration will appear in nondescending order.

(alarm-multiple) thread 0: duration=10, iteration=1, product=10

(alarm-multiple) thread 1: duration=20, iteration=1, product=20

(alarm-multiple) thread 0: duration=10, iteration=2, product=20

(alarm-multiple) thread 2: duration=30, iteration=1, product=30

(alarm-multiple) thread 0: duration=10, iteration=3, product=30

(alarm-multiple) thread 1: duration=20, iteration=2, product=40

(alarm-multiple) thread 3: duration=40, iteration=1, product=40

(alarm-multiple) thread 0: duration=10, iteration=4, product=40

(alarm-multiple) thread 4: duration=50, iteration=1, product=50

(alarm-multiple) thread 0: duration=10, iteration=5, product=50

(alarm-multiple) thread 2: duration=30, iteration=2, product=60

(alarm-multiple) thread 1: duration=20, iteration=3, product=60

(alarm-multiple) thread 0: duration=10, iteration=6, product=60

(alarm-multiple) thread 0: duration=10, iteration=7, product=70

(alarm-multiple) thread 1: duration=20, iteration=4, product=80

(alarm-multiple) thread 3: duration=40, iteration=2, product=80

(alarm-multiple) thread 2: duration=30, iteration=3, product=90

(alarm-multiple) thread 4: duration=50, iteration=2, product=100

(alarm-multiple) thread 1: duration=20, iteration=5, product=100

(alarm-multiple) thread 3: duration=40, iteration=3, product=120

(alarm-multiple) thread 2: duration=30, iteration=4, product=120

(alarm-multiple) thread 1: duration=20, iteration=6, product=120

(alarm-multiple) thread 1: duration=20, iteration=7, product=140

(alarm-multiple) thread 2: duration=30, iteration=5, product=150

(alarm-multiple) thread 4: duration=50, iteration=3, product=150

(alarm-multiple) thread 3: duration=40, iteration=4, product=160

(alarm-multiple) thread 2: duration=30, iteration=6, product=180

(alarm-multiple) thread 3: duration=40, iteration=5, product=200

(alarm-multiple) thread 4: duration=50, iteration=4, product=200

(alarm-multiple) thread 2: duration=30, iteration=7, product=210

(alarm-multiple) thread 3: duration=40, iteration=6, product=240

(alarm-multiple) thread 4: duration=50, iteration=5, product=250

(alarm-multiple) thread 3: duration=40, iteration=7, product=280

(alarm-multiple) thread 4: duration=50, iteration=6, product=300

(alarm-multiple) thread 4: duration=50, iteration=7, product=350

(alarm-multiple) end

'alarm-simultaneous'

Executing 'alarm-simultaneous':

(alarm-simultaneous) begin

(alarm-simultaneous) Creating 3 threads to sleep 5 times each.

(alarm-simultaneous) Each thread sleeps 10 ticks each time.

(alarm-simultaneous) Within an iteration, all threads should wake up on the same tick.

(alarm-simultaneous) iteration 0, thread 0: woke up after 10 ticks

(alarm-simultaneous) iteration 0, thread 1: woke up 0 ticks later

(alarm-simultaneous) iteration 0, thread 2: woke up 0 ticks later

(alarm-simultaneous) iteration 1, thread 0: woke up 10 ticks later

(alarm-simultaneous) iteration 1, thread 1: woke up 0 ticks later

(alarm-simultaneous) iteration 1, thread 2: woke up 0 ticks later

(alarm-simultaneous) iteration 2, thread 0: woke up 10 ticks later

(alarm-simultaneous) iteration 2, thread 1: woke up 0 ticks later

(alarm-simultaneous) iteration 2, thread 2: woke up 0 ticks later

(alarm-simultaneous) iteration 3, thread 0: woke up 10 ticks later

(alarm-simultaneous) iteration 3, thread 1: woke up 0 ticks later

(alarm-simultaneous) iteration 3, thread 2: woke up 0 ticks later

(alarm-simultaneous) iteration 4, thread 0: woke up 10 ticks later

(alarm-simultaneous) iteration 4, thread 1: woke up 0 ticks later

(alarm-simultaneous) iteration 4, thread 2: woke up 0 ticks later

(alarm-simultaneous) end

'alarm-zero'

Executing 'alarm-zero':

(alarm-zero) begin

(alarm-zero) PASS

(alarm-zero) end

'alarm-negative'

Executing 'alarm-negative':

(alarm-negative) begin

(alarm-negative) PASS

(alarm-negative) end

Выводы

В ходе данной лабораторной работы удалось провести модернизацию системного таймера Pintos OS. Для выполнения данной цели были реализованы алгоритмы, позволяющие избежать активного ожидания на время сна для конкретного потока. Если раньше на каждый спящий поток выделялся отельный цикл с ожиданием до того момента, пока не настанет время для его выполнения, то теперь все потоки, которые должны будут перейти в неактивное состояние, будут храниться в динамическом массиве и извлекаться оттуда только в тот момент времени, когда они будут готовы к работе. Это весьма важная реализация, способная значительно ускорить работу ОС.

ПРИЛОЖЕНИЕ А

Изменения в файле devices/timer.h
struct THREAD_SLEEP

{

int64_t SleepTimeDuration;

int64_t SleepTimeBegin;

int64_t SleepTimeLeft;

struct thread* pThread;

};
struct THREAD_SLEEP* FunctionInitializeThreadSleepArray(int64_t ticks, int64_t start);

struct THREAD_SLEEP* FunctionAddElementToThreadSleepArray(struct THREAD_SLEEP* ThreadSleepArray, int64_t ticks, int64_t start);

struct THREAD_SLEEP* FunctionCheckAndUpdateThreadSleepArray(struct THREAD_SLEEP* ThreadSleepArray);

void ProcedureUpdateAndSortThreadSleepArray(struct THREAD_SLEEP* ThreadSleepArray);

void ProcedureQuickSortThreadSleepArray(struct THREAD_SLEEP* ThreadSleepArray, int LeftBorder, int RightBorder);

ПРИЛОЖЕНИЕ Б

Изменения в файле devices/timer.c

struct THREAD_SLEEP* pThreadSleepArray = NULL;

int ThreadSleepCount = 0;
struct THREAD_SLEEP* FunctionInitializeThreadSleepArray(int64_t ticks, int64_t start)

{

struct THREAD_SLEEP* Result = (struct THREAD_SLEEP*)malloc(sizeof(struct THREAD_SLEEP));

if (Result != NULL)

{

Result->pThread = thread_current();

Result->SleepTimeDuration = ticks;

Result->SleepTimeBegin = start;

Result->SleepTimeLeft = ticks;

ThreadSleepCount++;

}

return Result;

}
struct THREAD_SLEEP* FunctionAddElementToThreadSleepArray(struct THREAD_SLEEP* ThreadSleepArray, int64_t ticks, int64_t start)

{

struct THREAD_SLEEP* Result = (struct THREAD_SLEEP*)realloc(ThreadSleepArray, (ThreadSleepCount + 1) * sizeof(struct THREAD_SLEEP));

if (Result != NULL)

{

Result[ThreadSleepCount].pThread = thread_current();

Result[ThreadSleepCount].SleepTimeDuration = ticks;

Result[ThreadSleepCount].SleepTimeBegin = start;

Result[ThreadSleepCount].SleepTimeLeft = ticks;

ThreadSleepCount++;

return Result;

}

else

return ThreadSleepArray;

}
struct THREAD_SLEEP* FunctionCheckAndUpdateThreadSleepArray(struct THREAD_SLEEP* ThreadSleepArray)

{

if (ThreadSleepArray == NULL && ThreadSleepCount == 0)

return NULL;

else if (ThreadSleepArray != NULL && ThreadSleepCount == 0)

{

free(ThreadSleepArray);

return NULL;

}

else

{

struct THREAD_SLEEP* Result = (struct THREAD_SLEEP*)realloc(ThreadSleepArray, ThreadSleepCount * sizeof(struct THREAD_SLEEP));

if (Result)

return Result;

else

return ThreadSleepArray;

}

}
void ProcedureUpdateAndSortThreadSleepArray(struct THREAD_SLEEP* ThreadSleepArray)

{

for (int i = 0; i < ThreadSleepCount; i++)

ThreadSleepArray[i].SleepTimeLeft = ThreadSleepArray[i].SleepTimeDuration - timer_elapsed(ThreadSleepArray[i].SleepTimeBegin);

ProcedureQuickSortThreadSleepArray(ThreadSleepArray, 0, ThreadSleepCount - 1);

}
void ProcedureQuickSortThreadSleepArray(struct THREAD_SLEEP* ThreadSleepArray, int LeftBorder, int RightBorder)

{

int Left = LeftBorder, Right = RightBorder;

struct THREAD_SLEEP Middle = ThreadSleepArray[(Left + Right) / 2];

while (Left <= Right)

{

while (ThreadSleepArray[Left].SleepTimeLeft > Middle.SleepTimeLeft)

Left++;

while (ThreadSleepArray[Right].SleepTimeLeft < Middle.SleepTimeLeft)

Right--;

if (Left <= Right)

{

struct THREAD_SLEEP Temp = ThreadSleepArray[Left];

ThreadSleepArray[Left++] = ThreadSleepArray[Right];

ThreadSleepArray[Right--] = Temp;

}

}

if (LeftBorder < Right)

ProcedureQuickSortThreadSleepArray(ThreadSleepArray, LeftBorder, Right);

if (RightBorder > Left)

ProcedureQuickSortThreadSleepArray(ThreadSleepArray, Left, RightBorder);

}
void timer_sleep(int64_t ticks)

{

int64_t start = timer_ticks();

ASSERT(intr_get_level() == INTR_ON);
enum intr_level old_level = intr_disable();
pThreadSleepArray = FunctionCheckAndUpdateThreadSleepArray(pThreadSleepArray);
if (pThreadSleepArray)

{

pThreadSleepArray = FunctionAddElementToThreadSleepArray(pThreadSleepArray, ticks, start);

ProcedureUpdateAndSortThreadSleepArray(pThreadSleepArray);

}

else

pThreadSleepArray = FunctionInitializeThreadSleepArray(ticks, start);

thread_block();

intr_set_level(old_level);

}
static void

timer_interrupt(struct intr_frame* args UNUSED)

{

ticks++;

thread_tick();
for (int i = 0; i < ThreadSleepCount; i++)

pThreadSleepArray[i].SleepTimeLeft = pThreadSleepArray[i].SleepTimeDuration - timer_elapsed(pThreadSleepArray[i].SleepTimeBegin);
while (ThreadSleepCount && pThreadSleepArray[ThreadSleepCount - 1].SleepTimeLeft <= 0)

thread_unblock(pThreadSleepArray[--ThreadSleepCount].pThread);

}