オペレーティングシステムの理解]プロセスとLinuxスケジューリング(CFS)

# Intro

LinuxのCFS 스케쥴러と프로세스の特性(I/O, CPU burst boundなど)を理解するために、私が学部プロジェクトでやった仕事を紹介します.

プロセスのvruntimeが重み付けされ、normal, low, highの優先度がプロセスに与えられる.プロジェクトの目的は、このプロセスの累積値vruntimeと累積値CPU Burstをグラフィック形式で表示し、結果を分析することである.

このため,課題チュートリアルやリストなどを学習し,bootlinとカーネルコードによりtask_structおよびその他の必要な関数やコードを学習し,sched.h,fair.c,stats.h,make3種類のカーネルファイルのコードを修正した.

カーネルコードを変更した後、firefoxコマンドを使用してコンパイルとカーネル構築を行い、再起動後、ThunderBirdと프로세스プログラムを実行し、2つの任意のプロセスを作成します.次に,課題の説明に従って流れの優先度を変更し,約30分間のログを収集し,X線上でグラフィックを計算し解析した.

#プロセスとLinux CFSスケジューラの概念

-プロセス

메인 메모리とは、디스크に割り当てられて実行中のプログラムを指す.applicationのプログラムを実行すると、メモリが割り当てられて実行され、バイナリコードが割り当てられたメモリ領域にアップロードされます.この時点からプロセスと呼ばれます.
オペレーティングシステムカーネルを起動する準備ができている場合、ユーザレベルは、ディスクから자원をロードすることによって、다중 프로그램 시스템(メモリ、ファイル、ページング、信号、スタック、...)を割り当てることによって、動作を実行する最小単位を割り当てることができる.OSカーネルは、ユーザー・レベルの要件に応じて準備および作成されます.
CPUリソースと効率を最大限に利用するために、스케쥴링はCPU burstフローを採用する.つまり、I/O操作によってCPUが無効になった場合、CPUが何もしないように別のプロセスが割り当てられます.
プロセスの実行は、I/O burst(CPUが命令を実行する時間、ステップ)、CFS(Completely Fiar Scheduler)(I/O処理を待つステップ、時間)からなる.

-Linux CFSスケジューラ

2007年に発表されたLinuxカーネルスケジューラRSDL(Rotating Staircase Deadline)は、RB-트리スケジューラのO(logN)構造に基づく<linux/sched.h>性能を有するスケジューラである.struct sched_entityに定義された스케쥴러というスケジューラユニット構造を用いて情報を格納する.CFSの基本概念は,タスクにプロセッサ時間を提供する際のバランス(公平)を保つことである.これは、プロセスに公平なプロセッサ数を提供することを目標としています.
1つ以上のタスクが他のタスクに比べて公平な時間量を持たない場合は、指定したタスクの実行時間が指定したタスクより少なくなければなりません.CFSは、パフォーマンスと公平性のバランスを重視します.가상 런타임は、バランスを決定するために指定されたタスク(가상 런타임と呼ばれる)で提供される時間量を管理する.タスクのCFSが小さいほど、すなわちプロセッサへのアクセスが許可される時間が小さいほど、プロセッサに必要な時間が長くなる.また、CFSには「待機公平」という概念も含まれている.このコンセプトは、現在実行できないタスクが後でプロセッサを必要とする場合に、必要な時間内に対応するプロセッサ時間を取得することを保証します.vruntime(Virtula runtime)のうちvruntimeは、仮想CPUの使用時間、すなわち優先度(重み付け)のCPU時間を表す.ここで、優先度が高いほどウェイト値が高くなります.最終的に、vruntimeは、実行可能なすべてのプロセスの中で最小のプロセスである.したがって、長時間稼働しないプロセスは比較的小さい(starvation)ため、vruntime += execution time x (default weight/process weight)は発生しない.ready queueすなわち、プロセスの優先度はruntimeに直接並べ替えられないが、vruntimeはスケジューリング演算を考慮するため、(1) /usr/src/linux-4.20.11/include/linux/sched.hはスケジューリングに影響を及ぼす.

#変更されたカーネルソースの説明

sched.h

struct sched_entity {
	/* For load-balancing: */
	struct load_weight		load;
	unsigned long			runnable_weight;
	struct rb_node			run_node;
	struct list_head		group_node;
	unsigned int			on_rq;

	u64				delta_virtualruntime; 

	u64				exec_start;
	u64				sum_exec_runtime;
	u64				vruntime;
	u64				prev_sum_exec_runtime;

	u64				nr_migrations;

	struct sched_statistics		statistics;

sched_entity structのvruntimeからプロセスのdelta_virtualruntime値を出力するために、fair.cという新しい変数を宣言し、vruntimeファイルのstats.h値を更新するか、delta vruntimeファイルの(2) /usr/src/linux-4.20.11/kernel/sched/stats.h値を出力するために使用します.stats.h

#define SAMPLING_VALUE 1000 //#[////////][////////]
static inline void sched_info_depart(struct rq *rq, struct task_struct *t)
{
	unsigned long long delta = rq_clock(rq) - t->sched_info.last_arrival;
	//#[////////][////////]

	if ( (t->nivcsw) % SAMPLING_VALUE == 0 )
	{
		printk(KERN_INFO "tgid, %d / delta_vruntime, %lld / delta_rrun(CPU_burst), %lld / priority, %d \n",t->tgid, t->se.delta_virtualruntime, delta, t->prio);
	}



	rq_sched_info_depart(rq, delta);

	if (t->state == TASK_RUNNING)
		sched_info_queued(rq, t);
}

sched_info_departのSAMPLING_VALUE関数では、defineを1000としてtask_structを解析し、bootlinを用いてCPU burstを解析した.vruntimeおよびtask_structの値は、プロセススケジューリング1000回で1回だけサンプリングして記録する必要があり、if文が追加された場合、nivcswの커널 로그 (tgid / delta_vruntime / delta_rrun(CPU_burst) / priority )変数(コンテキスト切替回数を格納)を使用して1000回ごとにサンプリングし、sched_info_departを出力する.
周知のように、task_struct関数は、プロセスがCPU占有を完了したときに呼び出され、task_struct構造ポインタが入力として受信される.식별자(tgid)構造体の調査により、우선순위(prio)とsched_entity(se)、およびdelta_virtualruntime構造体が以前に私が定義したdelta値と課題説明で与えられた宣言された「CPU_burst」値は、(3) /usr/src/linux-4.20.11/kernel/sched/fair.c値を出力できることがわかる.fair.c

static void update_curr(struct cfs_rq *cfs_rq)
{
	struct sched_entity *curr = cfs_rq->curr;

	u64 delta_vruntime; //#[////////][////////]
	u64 now = rq_clock_task(rq_of(cfs_rq));
	u64 delta_exec;

	if (unlikely(!curr))
		return;

	delta_exec = now - curr->exec_start;
	if (unlikely((s64)delta_exec <= 0))
		return;

	curr->exec_start = now;
	delta_vruntime = calc_delta_fair(delta_exec, curr);
	curr->delta_virtualruntime = delta_vruntime;
	curr->vruntime += delta_vruntime;
	//curr->vruntime += calc_delta_fair(delta_exec, curr);
	schedstat_set(curr->statistics.exec_max,
		      max(delta_exec, curr->statistics.exec_max));

	curr->sum_exec_runtime += delta_exec;
	schedstat_add(cfs_rq->exec_clock, delta_exec);

vruntimeファイルにおいてupdate_currのvruntime関数が更新される.delta vruntime(累計sched_entity structではなく)を出力および使用できるようにするには、既存のコードを注釈し、delta_virtualruntimeでdelta_vruntimeという変数を使用し、calc_delta_fairで予め定義したvruntime、現在の関数で定義したdelta_vruntimeの変数でvruntimeの関数を使用します.結果値(Not累積値)を保存し、先に定義したfirefox変数(累積vruntime値)を使用して累積保存し、累積値(+=)ThunderBirdを更新します.

#CPU burst、vruntimeのグラフィックと結果分析

-駆動プロセスの分析

私が駆動するプロセスには、CPU-boundでYouTubeとThunderBirdプログラムを再生し、ユーザーが一定時間内に電子メールの状態を自由に更新できるようにすることが含まれています.Webブラウザによるビデオ再生は、典型的なCPU密集型、CPUバースト型のfirefoxプロセスである.I/O boundプロセスの主なプロセスは通信のためのI/O動作であり、topで油管を再生するプロセスと比較してCPU utilizationプロセスに対応する.これはLinuxコマンドCPU burstを実行し、各プロセスのfirefoxおよびNormalヒストグラムによって説明される.私が実行しているプロジェクトは、reniceプロセスの優先度を変更することです.

-結果グラフィックと実行プロセス

Lowの優先度については、niceコマンドは単独で実行されなかった(優先度=120).Highの場合、niceの値は、優先度が130になるように10に変更され、firefoxの場合、Total CPU-burstの値は、優先度が110になるように-10に変更された.いずれの場合も約30分、log 000を記録した.ログtxtファイルをxlsxファイルに移動し、EXCELのSUM関数とフィルタを使用して206,890,887 / 202,201,824 / 234,100,441プロセス(PID=3822)の値を取得し、EXCEL上でグラフィックを生成します.
Normal priorityLow priorityHigh priorityTotal CPU-burst206,890,887202,201,824234,100,441Total vruntime112,783,692920,048,60110,206,662
(1) Normal priority

(2) Low priority

(3) High priority

-結果分析

Low < Normal < Highの値はnormal priorityであり、vruntimeの順に並べられており、CPU burstでは図形の形状は似ているが、値は異なり、予想値であれば似ているはずだが、そうではない.CFS 스케쥴러の特性を考慮すると、優先度が高いほどprocess weightの値が高くなり、最終的にはvruntimeの減少(vruntime += execution time x (default weight/process weight))を招き、CFS 스케쥴러は最小のプロセスを選択する.その結果,優先度(低<正常<高)の順にCPUを用いて演算を行う時間が増加することが分かった.これは,そのプロセスがリソースを割り当てられ,CPUがそのプロセスを実行する命令,すなわちスケジューラがCPUに時間を割り当てることを意味する.vruntimeの値はTotal vruntimeです.112,783,692 / 920,048,601 / 10,206,662の値とは対照的に,我々が解析したように優先度が高いほどCPU-burstは小さくなるLow > Normal > Highの順序を見ることができる.図の個数と値から、vruntimeの増分優先度が高いほど増分が遅くなることがわかる.