オペレーティングシステムJ/K (管理のためのデータ構造)

Slides:



Advertisements
Similar presentations
専門教科「情報」(2) 6/1/07. 各科目(続き) 課題研究 課題研究(1) 目標 情報に関する課題を設定し,その課題の解決 を図る学習を通して,専門的な知識と技術の 深化,総合化を図るとともに,問題解決の能 力や自発的,創造的な学習態度を育てる.
Advertisements

【事例演習5】  字句解析     解 説  “ハッシュを用いた字句解析の方法”.
アルゴリズムとデータ構造1 2009年6月8日
Generic programming と STL
プログラミング演習II 2004年11月 30日(第6回) 理学部数学科・木村巌.
5.データ構造入門 5-1.連結リスト(Linked List) 5-2.スタック(Stack) 5-3.キュー(Queue)
アルゴリズムとデータ構造 2013年6月18日
アルゴリズムとデータ構造 2010年7月5日
データ構造とアルゴリズム 第10回 mallocとfree
基礎プログラミングおよび演習 第9回
プログラミング演習Ⅱ 第12回 文字列とポインタ(1)
基本情報技術概論(第4回) 埼玉大学 理工学研究科 堀山 貴史
アルゴリズムとデータ構造 2012年6月14日
情報工学概論 (アルゴリズムとデータ構造)
情報システム基盤学 基礎1 アルゴリズムとデータ構造
オペレーティングシステムJ/K 2004年11月4日
アルゴリズムとデータ構造 第3回基本的なデータ構造(リスト) 2015/10/28 アルゴリズムとデータ構造 2015.
アルゴリズムとデータ構造 2011年6月13日
データ構造とアルゴリズム 分割統治 ~ マージソート~.
第7章 データベース管理システム 7.1 データベース管理システムの概要 7.2 データベースの格納方式 7.3 問合せ処理.
アルゴリズムと データ構造 第4回 スタック・キュー.
①データ構造 ②アルゴリズム ③プログラム言語 ④マークアップ言語
データ構造と アルゴリズム 第八回 知能情報学部 新田直也.
アルゴリズムとデータ構造 2011年6月14日
アルゴリズムとデータ構造 2011年6月20日
2009/10/16 いろいろなデータ構造 第3講: 平成21年10月16日 (金) 4限 E252教室 コンピュータアルゴリズム.
9.1 DOMの概要 9.2 DOMプログラミングの基礎 9.3 DOMのプログラミング例
ハッシュテーブル.
アルゴリズムとデータ構造 2013年6月17日
データ構造とアルゴリズム 第4回 リスト ~ データ構造(1)~.
アルゴリズムとデータ構造1 2005年7月26日
アルゴリズムとデータ構造1 2006年7月4日
データ構造とアルゴリズム 第6回 キュー ~ データ構造(2)~.
アルゴリズムとデータ構造1 2006年6月16日
データ構造と アルゴリズム第4回 知能情報学メジャー 和田俊和.
オペレーティングシステムJ/K (仮想記憶管理)
第9回 優先度つき待ち行列,ヒープ,二分探索木
アルゴリズムとデータ構造1 2005年7月1日
アルゴリズムとデータ構造1 2009年6月29日
データ構造と アルゴリズム 第五回 知能情報学部 新田直也.
Cプログラミング演習 第10回 二分探索木.
アルゴリズムとデータ構造1 2009年7月9日
アルゴリズムとデータ構造1 2005年7月5日
先進的計算基盤システムシンポジウム SACSIS2007併設企画 マルチコアプログラミングコンテスト 「Cellスピードチャレンジ2007」
アルゴリズムとデータ構造1 2005年6月10日
アルゴリズムとデータ構造1 2005年6月24日
アルゴリズムとデータ構造 2010年6月21日
プログラミング 3 スタックとキュー.
プログラミング言語論 第六回 理工学部 情報システム工学科 新田直也.
基本情報技術概論I (第4回) 埼玉大学 理工学研究科 堀山 貴史
6.データ構造入門 6-1.連結リスト(Linked List) 6-2.スタック(Stack) 6-3.キュー(Queue)
データ構造とアルゴリズム 第11回 リスト構造(1)
情報数理Ⅱ 第11章 データ構造 平成29年1月18日.
第9回 優先度つき待ち行列,ヒープ,二分探索木
アルゴリズムとデータ構造1 2006年7月4日
コンパイラ 2012年10月29日
アルゴリズムとデータ構造 2012年6月11日
アルゴリズムとデータ構造1 2006年6月23日
アルゴリズムとデータ構造1 2009年7月2日
第11回放送授業.
アルゴリズムとデータ構造1 2009年6月15日
ネットワーク・プログラミング Cプログラミングの基礎.
オペレーティングシステムJ/K (並行プロセスと並行プログラミング)
pf-6. スタック (Python プログラミング基礎を演習で学ぶシリーズ)
アルゴリズムとデータ構造 2012年6月21日
アルゴリズムとデータ構造 2010年6月17日
新人研修発表 平成13年5月14日(月) 探索アルゴリズム ハッシュ法について 株式会社 エーアイネット・テクノロジ          須田 哲生.
アルゴリズムとデータ構造1 2005年7月12日
アルゴリズムとデータ構造1 2007年7月6日
プログラミング演習II 2004年11月 16日(第5回) 理学部数学科・木村巌.
Presentation transcript:

オペレーティングシステムJ/K (管理のためのデータ構造) 2005年10月27日 酒居敬一(sakai.keiichi@kochi-tech.ac.jp) http://www.info.kochi-tech.ac.jp/k1sakai/Lecture/OS/2005/

配列 添え字とデータが1対1で対応 添え字は連続 データの挿入や削除は面倒 ディレクトリエントリ メモリ管理表(ページテーブルなど) 2 3 4 n … 添え字とデータが1対1で対応 添え字は連続 添え字が1から始まるとは限らない データの挿入や削除は面倒 ディレクトリエントリ メモリ管理表(ページテーブルなど) 添え字を用いてアクセスする(例では3)

配列上の探索 添え字を用いて 直接アクセス 先頭から 順に調べる 図2.1.4             図2.1.5 教科書30ページ 直接探索            線形探索

配列上の探索 半分ずつ調べます 1)半分に分ける 2)前半に存在するか調べる 前半にあれば前半について探索 後半にあれば後半について探索 ※探索のためにデータの整列が必要 図2.1.6 教科書31ページ 二分探索

※仮想記憶を説明するときに詳細を説明します。 [Intel, ``Software Developer Manual’’] ※仮想記憶を説明するときに詳細を説明します。

[Intel, ``Software Developer Manual’’]

The IA-32 Intel Architecture Software Developer’s Manual, Volume3: System Programming Guide 目に付くところに存在するCPUの一例。 [Intel, ``Software Developer Manual’’]

メモリと配列 計算機のメモリは一種の配列である プログラミング言語による多彩な要素をもつ配列 プロセッサの命令が扱える単位を要素としている byte, word, dwordのような整数 float, double, long doubleのような不動小数点数 qword, dqwordのようなショートベクタ整数 プログラミング言語による多彩な要素をもつ配列 プログラミング言語のコンパイラが変換してくれます 気にしなくてもいいんですが、場合によります…

待ち行列(FIFO) データ挿入 データ取得 図2.3.1・2.3.2・2.3.3 教科書38・39ページ 待ち行列(データの挿入・取得)

データを動かすことなく、要素の挿入・削除ができる 連結リスト データをそれぞれの要素に格納 要素どおし、つながってリストを形成 先頭 次 データ データを動かすことなく、要素の挿入・削除ができる

双方向連結リスト 連結リストを双方にリンクしたもの 先頭 次 データ 最後 前 両方向から探索できる

リングバッファ 配列の最初と最後を接続して環にしたもの 2つのポインタでデータの出し入れを管理 データの先頭を指すポインタ head, front データの最後尾を指すポインタ tail, rear 2つのポインタが重なったらデータは空 領域の大きさをnとしたらポインタの位置はnとおり データの数が0からnまでn+1とおりある ポインタが重なったら、空か満杯の状態が重なる…

スタック(LIFO) プッシュ ポップ スタックポインタ スタックポインタ スタックポインタ 一時変数、レジスタのセーブ先など

木構造 ルートとそれ以外の ルートノード ノードにちょうど1つだけ の経路しか存在しない エッジ ノード 図2.5.1 教科書46ページ 末端ノード エッジ ノード 図2.5.1 教科書46ページ

ハッシュテーブル データ キー1 キー2 キー3 ハッシュ関数 パスワードファイル、メイルのエイリアスデータベースなど

構造とは? 全体を形づくっている種々の材料による各部分の組み合わせ。作りや仕組み。 さまざまな要素が相互に関連し合って作り上げている総体。また、各要素の相互関係。 階層的な構造 わかりやすい文書やプログラム

データ構造 ひとつまたは複数のデータを編成し保持する構造のこと データ構造どうしは関連している 例:このppt原稿 見出し 箇条書きの内容

アルゴリズム アルゴリズムは必ず問題を解決するもの ひとつまたは複数のデータを操作し目的の結果を得るための一連の処理手順 例: 交差点を渡りたい(=問題) 信号があるか? 信号がないならば、どうするか?