ซอฟต์แวร์ระบบ

คอมพิวเตอร์มีทรัพยากรมากมาย (เวลา CPU, หน่วยความจำ,ดิสก์, I/O) และโปรแกรมหลายตัวแข่งขันกันใช้ หน้าที่ OS แบ่งปันทรัพยากรอย่างยุติธรรมและมีประสิทธิภาพ เพื่อให้ทรัพยากรแต่ละชนิดถูกใช้ประโยชน์สูงสุดและระบบยังคงตอบสนองได้:

• Multi-tasking — สลับ CPU ไปมาอย่างรวดเร็วระหว่างกระบวนการ ทำให้ดู好像หลาย程序同時运行。
• การจัดการหน่วยความจำ — assigning Each process the memory it needs; use disk paging when RAM runs out.
• Spooling และการ buffering — คิวงานพิมพ์บนดิสก์เพื่อให้ CPU ไม่ต้องรอเครื่องพิมพ์
• Caching — เก็บข้อมูลดิสก์ที่เพิ่งใช้งานไว้ใน cache / RAM

อินเทอร์เฟซผู้ใช้ซ่อนฮาร์ดแวร์ไว้เบื้องหลังการ 추ณธรรมที่เข้าใจง่าย: ผู้ใช้เห็นหน้าต่าง เมนู และโฟลเดอร์ ไม่ใช่ที่อยู่หรือเซกเตอร์ การคลิกเพียงครั้งเดียวบนไอคอนทำให้ระบบปฏิบัติการค้นหาโปรแกรมในดิสก์ จัดสรรหน่วยความจำ โหลดมันและเริ่มทำงาน CLI (บรรทัดคำสั่ง) มีพลังและเขียนสคริปต์ได้สำหรับผู้เชี่ยวชาญ; GUI (กราฟิก) ง่ายต่อการเรียนรู้ ระบบส่วนใหญ่มีทั้งสองอย่าง

"อธิบายสองวิธีที่ความซับซ้อนของฮาร์ดแวร์ถูกซ่อนจากผู้ใช้" (1) ผู้ใช้ทำงานกับ ไฟล์และโฟลเดอร์โดยใช้ชื่อ และ OS แปลงพวกมันเป็นเทรค เซกเตอร์ และบล็อกของดิสก์; (2) ผู้ใช้รันโปรแกรมด้วย การคลิกหรือคำสั่ง และ OS โหลดมัน จัดสรรหน่วยความจำและจัดตารางเวลาให้โดยไม่ทราบที่อยู่ใดๆ; (3) ไดรเวอร์อุปกรณ์ ทำให้ผู้ใช้พิมพ์หรือบันทึกได้โดยไม่ต้องรู้วิธีการควบคุมเครื่องพิมพ์หรือดิสก์; (4) อินเทอร์เฟซกราฟิก แทนที่คำสั่งระดับเครื่องด้วยไอคอน หน้าต่าง และเมนู ประโยชน์สำหรับนักเรียน พร้อมตัวอย่าง: OS ทำให้ฮาร์ดแวร์ ใช้งานได้โดยไม่จำเป็นต้องมีความรู้ด้านเทคนิค ตัวอย่างเช่น บันทึกเอกสารลงใน USB drive โดยการลากไอคอนของมัน

"แสดงวิธีที่ OS ใช้ประโยชน์จากทรัพยากรสูงสุด" มัน จัดตารางเวลาโปรเซสเซอร์ เพื่อให้มันไม่หยุดนิ่งในขณะที่มีกระบวนการพร้อมใช้งาน; มัน จัดการหน่วยความจำ โดยจัดสรรให้กับกระบวนการ รวบรวมกลับมาและขยายด้วยหน่วยความจำเสมือน; มัน จัดการอินพุตและเอาต์พุต โดยใช้บัฟเฟอร์และการสPOOLเพื่อให้เร็วและช้า دستگاهซ้อนทับงานของพวกเขา; และมัน จัดการพื้นที่เก็บข้อมูล โดยติดตามพื้นที่ว่างและไฟล์ แต่ละจุดระบุทรัพยากรและสิ่งที่ OS ทำกับมัน

กระบวนการ คือโปรแกรมที่กำลังทำงาน — โค้ด สถานะปัจจุบัน หน่วยความจำ และไฟล์ที่เปิดอยู่ของมัน

การจัดตารางเวลา

ตัวจัดตารางเวลา เลือกว่า กระบวนการที่พร้อมใช้งาน ตัวไหนจะรันต่อไป และนานแค่ไหน:

• รอบเวียน — แต่ละกระบวนการได้รับ ช่วงเวลาตายตัว แล้วไปต่อท้ายคิว
• เข้าก่อนรับบริการก่อน; งานสั้นก่อน; เวลาที่เหลือสั้นที่สุด (รันงานที่มีงานเหลือน้อยที่สุด); ความสำคัญ; คิวป้อนกลับหลายระดับ

การแลกเปลี่ยนคือความไวต่อการตอบสนอง vs ผลผลิต vs ความยุติธรรม

"อธิบายความหมายของการมัลติทาสก์以及如何 benefiting การจัดการกระบวนการ" กระบวนการหลายกระบวนการถูกเก็บไว้ในหน่วยความจำในเวลาเดียวกันและโปรเซสเซอร์สลับระหว่างพวกเขาอย่างรวดเร็วจนดูเหมือนวิ่งไปพร้อมกัน แต่ละคนได้รับส่วนแบ่งของเวลาโปรเซสเซอร์ตามลำดับ ประโยชน์: โปรเซสเซอร์ ไม่ถูกทิ้งให้หยุดนิ่ง ในขณะที่กระบวนการหนึ่งรออินพุตหรือเอาต์พุต ดังนั้น ผลผลิต สูงขึ้น และผู้ใช้สามารถทำงานกับหลายโปรแกรมพร้อมกันได้ "อธิบายเหตุผลที่ต้องมีการจัดตารางเวลา" มี กระบวนการมากกว่าโปรเซสเซอร์ ดังนั้นต้องตัดสินใจเกี่ยวกับ กระบวนการ ตัวไหนรันต่อไปและ นานแค่ไหน; การจัดตารางเวลาทำให้มั่นใจว่าทุกกระบวนการ มีความคืบหน้า, ว่าโปรเซสเซอร์ ถูกใช้งานเต็ม, ว่า เวลาตอบสนอง เป็นที่ยอมรับได้, และว่า ความสำคัญ สามารถเคารพได้

dirnameการจัดตารางเวลา ตามที่ข้อสอบต้องการให้บรรยาย

ตัวอย่างวิธีทำ. สามกระบวนการมาถึงพร้อมกันพร้อม CPU times of 8, 4 และ 2 ms. เปรียบเทียบเวลารอเฉลี่ยภายใต้ FCFS (ตามลำดับการมาถึง A, B, C) และภายใต้งานสั้นก่อน

FCFS: A รอ 0, B รอ 8, C รอ 12; ค่าเฉลี่ย $(0 + 8 + 12)/3 = 6.7\ \text{ms}$. SJF ทำงานตามลำดับ C, B, A: C รอ 0, B รอ 2, A รอ 6; ค่าเฉลี่ย $2.7\ \text{ms}$. ปริมาณงานทั้งหมดเท่ากัน 14 ms ในทั้งสองกรณี; ลำดับการดำเนินการคือสิ่งที่กำหนดว่าใครต้องรอ Round robin ด้วย slice ขนาด 2 ms จะทำให้ A, B และ C ได้โอกาสใช้งาน轮流 each a turn in the first 6 ms, ดังนั้น C เสร็จที่ 6 ms, B ที่ 12 ms และ A ที่ 14 ms: ตอบสนองเร็วที่สุด แต่ไม่ใช่วิธีที่รวดเร็วที่สุดในแง่ค่าเฉลี่ย

สถานะของกระบวนการ

กระบวนการมีสถานะคือ ใหม่ (new), พร้อมทำงาน (ready) (รอใช้ CPU), กำลังทำงานอยู่ (running), ถูกบล็อก (blocked) (รอ I/O หรือการล็อก) หรือ สิ้นสุด (terminated) เมื่อเวลาในการดำเนินการ (time slice) สิ้นสุด จะเปลี่ยนจาก running → ready; เมื่อขอ I/O จะเปลี่ยนจาก running → blocked; เมื่อ I/O เสร็จจะเปลี่ยนจาก blocked → ready

สามสถานะและเหตุผลที่กระบวนการเคลื่อนที่ กำลังทำงาน: กระบวนการมีหน่วยประมวลผล พร้อมทำงาน: สามารถทำงานได้แต่รอใช้หน่วยประมวลผล ถูกบล็อก: ไม่สามารถทำงานจนกว่าจะมีเหตุการณ์อื่นเกิดขึ้น เหตุผลของการเปลี่ยนแต่ละแบบ ซึ่งข้อสอบถามทีละอย่าง: กำลังทำงานไปพร้อมทำงาน เมื่อ time slice สิ้นสุด หรือเมื่อกระบวนการที่มี ความสำคัญสูง (higher-priority) ยอมให้มาทำงานแทน (pre-empt) (เกิด interrupt); กำลังทำงานไปถูกบล็อก เมื่อขอ อินพุตหรือเอาต์พุต หรือรอทรัพยากรหรือกระบวนการอื่น; ถูกบล็อกไปพร้อมทำงาน เมื่อ I/O ที่รอนั้น เสร็จสิ้น (ส่งสัญญาณโดย interrupt); พร้อมทำงานไปกำลังทำงาน เมื่อ ตัวจัดตารางงาน (scheduler) จัดสรรให้ทำงาน กระบวนการที่ถูกบล็อกไม่สามารถไปกำลังทำงานโดยตรงได้ ต้องกลายเป็นพร้อมทำงานก่อน

บล็อกควบคุมกระบวนการและการสลับบริบท

สำหรับแต่ละกระบวนการ ระบบปฏิบัติการจะเก็บ บล็อกควบคุมกระบวนการ (PCB) — ค่าโปรแกรมเคาน์เตอร์ที่บันทึกไว้, registers, สถานะ และข้อมูลหน่วยความจำ

• การสลับบริบท (context switch) หยุดการทำงานชั่วคราวของกระบวนการหนึ่งและเริ่มอีกกระบวนการหนึ่ง: บันทึกสถานะลงใน PCB หนึ่งและเรียกคืนจากอีก PCB หนึ่ง ค่าใช้จ่ายเล็กน้อยนี้ถูกจ่ายทุกครั้งที่สลับ
• เคอร์เนล (แกนกลางของระบบปฏิบัติการ) ทำหน้าที่เป็น ตัวจัดการ interrupt เมื่ออุปกรณ์หรือไทม์เมอร์ส่ง interrupt, การจัดการ interrupt จะบันทึกกระบวนการที่กำลังทำงานและรัน routine ที่ถูกต้อง — นี่คือสิ่งที่ขับเคลื่อนการจัดตารางงานระดับต่ำ

"อธิบายว่าเคอร์เนลทำหน้าที่เป็นตัวจัดการ interrupt ได้อย่างไร (สองคะแนน)" เมื่อมีการส่ง interrupt, เคอร์เนลจะ บันทึกสถานะ ของกระบวนการที่กำลังทำงาน (registers และโปรแกรมเคาน์เตอร์, ใน process control block ของมัน), ระบุแหล่งที่มาและความสำคัญ ของ interrupt, รัน service routine ที่เหมาะสม, และหลังจากนั้นจะ เรียกคืน กระบวนการที่ถูก interrupt (หรือกระบวนการที่มีความสำคัญสูงกว่า) เพื่อให้การดำเนินงานดำเนินต่อ นี่คือวิธีที่ไทม์เมอร์จบ time slice และวิธีที่ I/O operation ที่เสร็จสิ้นปลดล็อกกระบวนการ

การสื่อสารระหว่างกระบวนการ

กระบวนการถูกแยกออกจากกัน ดังนั้น OS จึงให้บริการ การสื่อสารระหว่างกระบวนการ: ท่อ (pipes) (เอาต์พุตของโปรแกรมหนึ่งป้อนเข้าอินพุตของอีกโปรแกรมหนึ่ง), หน่วยความจำร่วม (shared memory) (พื้นที่ที่หลายกระบวนการสามารถใช้ได้), และการส่งข้อความ

แต่ละกระบวนการได้รับ พื้นที่ที่อยู่virtual address space ของตัวเอง — ช่วงที่อยู่ที่เป็นระเบียบและต่อเนื่องที่ OS map เข้ากับหน่วยความจำจริง สิ่งนี้ทำให้แต่ละกระบวนการมีพื้นที่ที่เรียบง่าย, ปกป้องกระบวนการ друг друг, และทำให้หน่วยความจำรวม เกิน RAM จริง ได้

ใน ** paging**, พื้นที่ virtual ถูกแบ่งเป็น หน้า (pages) ขนาดคงที่ และหน่วยความจำจริงเป็น เฟรม (frames) ขนาดเดียวกัน ตารางหน้า (page table) map แต่ละหน้าเข้ากับเฟรม หากหน้าที่เข้าถึงไม่ได้อยู่ใน RAM — หน้าผิดพลาด (page fault) — OS อ่านมันจาก ไฟล์สวอป (swap file) เข้าเฟรม, ล้างหน้าอื่นออกถ้า RAM เต็ม ความผิดพลาดบ่อยครั้งทำให้เกิด thrashing (disk thrashing), ที่ OS ใช้เวลาส่วนใหญ่ในการสลับหน้าแทนการทำสิ่งที่มีประโยชน์

ใน ** segmentation**, หน่วยความจำถูกแบ่งเป็นส่วนเชิงตรรกะขนาดแปรผัน (code, stack, heap), แต่ละส่วนมีสิทธิ์ของตนเอง ระบบหลายระบบใช้ paging ภายใน segmentation

"อธิบายความหมายของหน่วยความจำเสมือน (สามคะแนน)" พื้นที่เก็บข้อมูลรอง (ดิสก์) ใช้เพื่อขยาย RAM, ทำให้หน่วยความจำที่ใช้งานได้อาจดูใหญ่กว่าหน่วยความจำจริง; พื้นที่ที่อยู่ของกระบวนการถูกแบ่งเป็น หน้า, และเฉพาะหน้าที่จำเป็นในปัจจุบัน就会被保存在 RAM ในขณะที่其余部分在磁盘上等待; หน้า被 swapped ระหว่าง RAM และ磁盘 as required, and the OS translates each virtual address into a physical one. ทำไม OS ถึงต้องการมัน: โปรแกรมที่运行可能需要比已安装的RAM更多的内存; 它允许更多(或更大)的程序同时运行; 程序可以大于物理内存; 内存使用效率高因为程序的活跃部分才占用RAM。

Paging เทียบกับ Segmentation: ความแตกต่างที่ข้อสอบต้องการ Paging แบ่งหน่วยความจำเป็นบล็อก ขนาดคงที่ (pages และ frames) ที่เลือกโดย hardware, ไม่มี consideration กับโครงสร้างของโปรแกรม, และการ map เป็น invisible ต่อ programmer; segmentation แบ่งโปรแกรมเป็น หน่วยเชิงตรรกะขนาดแปรผัน (procedure, array, stack) ที่มีขนาดและขอบเขตตามโปรแกรม, ดังนั้น segment สามารถ protect หรือ share เป็น unit ได้ "อธิบายกระบวนการของ segmentation": โปรแกรมถูกแบ่งเป็น segments ขนาดต่างกัน, แต่ละส่วนได้รับ หมายเลขส่วน (segment number); ตารางส่วน (segment table) บันทึกว่าแต่ละส่วนเริ่มที่ไหนในหน่วยความจำและยาวเท่าไหร่; ที่อยู่เชิงตรรกะคือหมายเลขส่วนบวกกับ offset, และ OS เพิ่ม offset เข้ากับ base address ของส่วนเพื่อหาตำแหน่งจริง

"อธิบายความหมายของ disk thrashing" และเมื่อไหร่มันเกิดขึ้น. Disk thrashing คือสภาวะที่หน้าข้อมูล (pages) ถูก สลับเข้า-ออกจากรAM บ่อยมาก จนทำให้โปรเซสเซอร์ใช้เวลาเคลื่อนย้ายหน้าข้อมูลมากกว่าการประมวลผลคำสั่ง ทำให้ระบบช้าลงเกือบหยุดนิ่ง. มันเกิดขึ้นเมื่อ RAM เล็กเกินไป สำหรับหน้าข้อมูลที่ต้องการโดยกระบวนการที่กำลังทำงาน (working sets): หน้าข้อมูลที่ถูกย้ายออกเพิ่งถูกนำกลับมาใช้ทันที จึงต้องดึงกลับมาใหม่ ซึ่งดันหน้าข้อมูลอื่นออกไปที่อาจถูกใช้เร็วๆ นี้ไป และ seterusไป. กระบวนการมากเกินไป หรือโปรแกรมที่เข้าถึงความจำอย่างไม่คาดคิด จะทำให้เกิดปัญหานี้; การเพิ่ม RAM หรือลดจำนวนกระบวนการจะช่วยแก้ได้

Interpreter ทำการแปลและรันซอร์สโค้ด พร้อมกัน. สำหรับแต่ละคำสั่ง มันอ่านบรรทัดนั้น ทำการวิเคราะห์.lexical และ syntax ตรวจสอบประเภท แล้ว ดำเนินการ ตามคำสั่ง และข้ามไปยังข้อถัดไป. หากเกิดข้อผิดพลาดจะถูกแจ้งทันทีและมักจะหยุดทำงาน; ไม่มีการสร้างไฟล์ executable. การแปลจะทำซ้ำทุกครั้งที่รัน (ช้ากว่า) แต่มันให้ feedback ในการพัฒนาที่รวดเร็วและเป็น portable ได้ดี

"อธิบายวิธีการที่ interpreter ทำงานกับโปรแกรมโดยไม่สร้างเวอร์ชันที่แปลแล้ว" (3 คะแนน). Interpreter รับ คำสั่งหนึ่งบรรทัด มา แปล (วิเคราะห์) และ รัน ทันที ก่อนที่จะข้ามไปบรรทัดถัดไป; ไม่มีการสร้างหรือจัดเก็บเวอร์ชันที่แปลแล้ว ของทั้งโปรแกรม ดังนั้นแต่ละคำสั่งจึงถูกแปล ทุกครั้ง ที่被执行 รวมถึงทุกครั้งที่วนลูป; หากคำสั่งใดมีข้อผิดพลาด การรันจะ หยุดลงที่จุดนั้น และรายงานข้อผิดพลาด. นี่คือสิ่งที่ทำให้ interpreter ดีสำหรับการพัฒนาและทดสอบ (พบข้อผิดพลาดเมื่อถึงจุดนั้น และสามารถลองแก้ไขได้ทันที) แต่จะช้ากว่าในการรันโปรแกรมที่เสร็จสมบูรณ์แล้ว

Compiler แปลงซอร์สโค้ดเป็น machine code เป็นขั้นตอน:

1. ** lexical analysis** — lexer จัดกลุ่มตัวอักษรให้เป็น tokens (keywords, identifiers, operators, literals) และลบช่องว่างหรือคอมเมนต์ออก
2. syntax analysis (parsing) — ตรวจสอบว่า tokens เข้ากับไวยากรณ์หรือไม่และสร้าง abstract syntax tree. การขาดวงเล็บจะทำให้เกิด syntax error
3. semantic analysis — ตรวจสอบว่าโปรแกรมมีความหมาย (ตัวแปรถูกประกาศแล้ว, ประเภทข้อมูลตรงกัน)
4. code generation — traverse ต้นไม้และสร้างโค้ดเป้าหมาย เลือกใช้ registers และ layout ที่เหมาะสม
5. code optimisation — ลบงานซ้ำซ้อน, คำนวณค่าคงที่ล่วงหน้า, เรียงลำดับเพื่อประสิทธิภาพ pipeline

ผลลัพธ์คือไฟล์ที่รันได้ (executable)

วัตถุประสงค์ของแต่ละขั้นตอน ตามคำศัพท์ที่ได้คะแนน การวิเคราะห์ Lexical: ลบ ช่องว่างและ_heading; แปลงตัวอักษรของโค้ดต้นทางให้เป็น token (คีย์เวิร์ด, ตัวระบุชื่อ, ออเปอเรเตอร์, ค่านิยาม), ตรวจสอบว่าแต่ละ token ถูกต้อง ในภาษาที่ใช้งาน; บันทึกตัวระบุชื่อลงใน ตารางสัญลักษณ์ การวิเคราะห์ Syntax: ตรวจสอบว่าลำดับ token เป็นไปตาม ไวยากรณ์ (กฎ Syntax) ของภาษานั้น; สร้าง parse tree (ต้นไม้ Syntax แบบนามธรรม); แจ้ง ข้อผิดพลาดทาง Syntax; การตรวจสอบประเภทข้อมูลและการตรวจสอบการประกาศตัวแปร บางครั้งถูกนับอยู่ในส่วนของการวิเคราะห์ Semantic การสร้างโค้ด: แปลงต้นไม้ที่ผ่านการตรวจสอบแล้วให้เป็น object code หรือโค้ดเครื่อง (อาจผ่านโค้ดกลางก่อน), จัดสรรหน่วยความจำและรีจิสเตอร์ การปรับปรุงประสิทธิภาพ: ทำให้โค้ด ทำงานเร็วขึ้น หรือใช้ หน่วยความจำน้อยลง, โดยการลบคำสั่งที่ซ้ำซ้อน, รวมหรือลดรูปการคำนวณ, และจัดระเบียบวงลูปใหม่ โดยไม่เปลี่ยนพฤติกรรมของโปรแกรม ข้อสอบจับคู่จะจับคู่แต่ละขั้นตอนกับคำอธิบายหนึ่งจากคำอธิบายเหล่านี้

ไวยากรณ์ บอกว่าลำดับ token แบบใดเป็นโปรแกรมที่ถูกต้อง

Backus-Naur Form- (BNF) เป็นรูปแบบข้อความ Production rule มีรูปแบบดังนี้:

<symbol> ::= alternative1 | alternative2 | ...

ทางเลือกแต่ละอันเป็นลำดับของสัญลักษณ์ Terminal (ข้อความตามตัวอักษร) และสัญลักษณ์ Non-terminal (ชื่อกฎอื่น):

<digit>      ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
<identifier> ::= <letter> | <identifier> <letter> | <identifier> <digit>

กฎแบบ RecursiveRULE ที่สามแสดงถึง "ตัวอักษรตามด้วยตัวอักษรหรือตัวเลขจำนวนเท่าใดก็ได้" คำสั่ง IF:

<if-statement> ::= IF <condition> THEN <statement> ENDIF
                 | IF <condition> THEN <statement> ELSE <statement> ENDIF

แผนภาพ Syntax (railroad diagram) แสดงสิ่งเดียวกันในเชิงกราฟิก: กล่องสำหรับ Non-terminal, กล่องมุมโค้งสำหรับ Terminal, ลูกศรสำหรับเส้นทางที่ถูกต้อง, วงวนสำหรับการซ้ำซ้อน ทั้งสองรูปแบบมีความเทียบเท่ากัน Parser ใช้ไวยากรณ์เพื่อตัดสินใจว่าโปรแกรมนั้นถูกต้องหรือไม่

การอ่านแผนภาพข้อสอบ แผนภาพแต่ละแบบกำหนดตัวแปรที่ไม่สิ้นสุด (non-terminal) หนึ่งตัว ให้ติดตามลูกศรจากจุดเริ่มต้นไปยังจุดสิ้นสุด และทุกเส้นทางที่คุณสามารถลากได้คือสตริงที่ถูกต้อง ตัวเลือก ของกล่องวางเรียงกันข้างๆ คือชุดทางเลือก; ลูปย้อนกลับ หมายถึง "ทำซ้ำเท่าที่ต้องการ"; กล่องสำหรับตัวแปรที่ไม่สิ้นสุดอื่นหมายถึง "ใส่สิ่งที่กฎนั้นอนุญาตให้ใส่ได้" คำว่า "อธิบายเหตุผลที่สตริงนี้ไม่ถูกต้อง" ต้องการระบุกฎที่ละเมิดด้วยคำพูด: 9K ไม่เป็นไปตามเงื่อนไขในฐานะตัวแปรเพราะตัวแรกต้องเป็น ตัวอักษร ไม่ใช่ตัวเลข; JJ90 เป็นรหัสผ่านที่ไม่ถูกต้องหากกฎอนุญาตให้มี ตัวอักษรเพียงหนึ่ง ตัวก่อนตัวเลข หรือหาก J ไม่อยู่ในชุดตัวอักษรที่กำหนดไว้เสมอ ตรวจสอบสตริงกับชุดอักขระที่แผนภาพอนุญาตให้ใช้จริง ไม่ใช่สิ่งที่ภาษาโปรแกรมมิ่งทั่วไปจะยอมรับ

การเขียน BNF จากแผนภาพ แผนภาพแต่ละอันกลายเป็นกฎหนึ่ง <name> ::= ...; ทางเลือกแยกกันด้วย |; ลำดับเขียนสัญลักษณ์ต่อจากสัญลักษณ์; และ การซ้ำซ้อนเขียนด้วยการทำซ้ำ (recursion) เพราะ BNF ไม่มีสัญลักษณ์วงลูป: "ตัวอักษรหนึ่งตัวขึ้นไป" คือ <word> ::= <letter> | <letter><word>, และ "ตัวเลขศูนย์หรือมากกว่าหลังตัวอักษร" คือ <variable> ::= <letter> | <letter><digits> โดยมี <digits> ::= <digit> | <digit><digits>

ตัวอย่างวิธีทำ เติมเต็ม BNF สำหรับทะเบียนยานพาหนะที่ต้องเริ่มต้นด้วยตัวอักษรสองตัว (จาก A B C) ตามด้วยตัวเลขหนึ่ง, สอง หรือสามหลัก (จาก 0 1 2)

<letter>       ::= A | B | C
<digit>        ::= 0 | 1 | 2
<digits>       ::= <digit> | <digit><digit> | <digit><digit><digit>
<registration> ::= <letter><letter><digits>

AB12 ถูกต้อง; A12 ไม่ถูกต้อง (มีเพียงตัวอักษรหนึ่งตัว); AB1234 ไม่ถูกต้อง (มีสี่ตัวเลข); AD1 ไม่ถูกต้อง (D ไม่ใช่ตัวอักษรที่ระบุไว้) เมื่อถูกถามให้เพิ่มเงื่อนไขเช่น "ตัวที่สามอาจเป็นสัญลักษณ์ได้" ให้เพิ่มทางเลือกเพิ่มเติมเข้าไปในกฎสำหรับตำแหน่งนั้นเท่านั้น และกำหนด <symbol> ด้วยกฎของตัวเอง

ตัวอย่างวิธีทำ เขียน BNF สำหรับนิพจน์ที่เป็นตัวแปร, ตามด้วยออเปอเรเตอร์, ตามด้วยทั้งตัวแปรหรือตัวเลข, โดยที่ตัวแปรคือตัวพิมพ์เล็กหนึ่งตัวจาก a b c และออเปอเรเตอร์คือ + หรือ -

<variable>   ::= a | b | c
<operator>   ::= + | -
<number>     ::= <digit> | <digit><number>
<expression> ::= <variable><operator><variable> | <variable><operator><number>

กฎ <number> แบบ Recursion อนุญาตให้มีตัวเลขจำนวนเท่าใดก็ได้; ทางเลือกทั้งสองของ <expression> ครอบคลุมกรณีทั้งหมดที่ระบุไว้ในนิยาม รักษาสัญญาณ Non-terminal ไว้ในเครื่องหมายมุมทั้งหมด และสัญญาณ Terminal โดยไม่มีเครื่องหมายมุม

ใน Programming Notation แบบอินฟิกซ์ (infix) ตัวดำเนินการจะอยู่ระหว่าง operands (3 + 4 * 2) ซึ่งต้องใช้วงเล็บและกฎลำดับความสำคัญ ใน Programming Notation แบบ Reverse Polish (RPN, postfix) ตัวดำเนินการจะตามหลัง operands (3 4 2 * +) โดยไม่ต้องใช้วงเล็บ

การแปลงจาก infix เป็น RPN

ใช้ Stack ของตัวดำเนินการ สแกนจากซ้ายไปขวา: ออกพุต operand; สำหรับตัวดำเนินการ ให้ pop ตัวดำเนินการที่ซ้อนกันซึ่งมี ลำดับความสำคัญสูงกว่าหรือเท่ากัน ออกมาก่อน แล้วจึง push ตัวดำเนินการนั้น; push (; เมื่อเจอ ) ให้ pop ออกพุตจนกว่าจะเจอ ( ที่จับคู่กัน ท้ายสุดให้ pop ตัวดำเนินการทั้งหมดออก ตัวอย่าง: (3 + 4) * 2 → 3 4 + 2 *

การประเมินผล RPN

ใช้ Stack ของ operands สแกนจากซ้ายไปขวา: push แต่ละ operand; เมื่อเจอตัวดำเนินการ ให้ pop 2 ตัวบนสุด มาคำนวณแล้ว push ผลลัพธ์กลับเข้าไป การประเมินผล 3 4 2 * +:

ผลลัพธ์: 11 RPN ไม่ต้องการวงเล็บในช่วงการประเมินผล และเหมาะสำหรับเครื่องแบบ Stack — ซึ่งเป็นวิธีที่ JVM และตัวแปลภาษา bytecode หลายชนิดทำงาน

"อธิบายเหตุผลที่ใช้ RPN ในการประเมินผลนิพจน์" (2 คะแนน). ใน RPN ตัวดำเนินการปรากฏ ตามลำดับที่นำไปใช้จริง ดังนั้นนิพจน์สามารถประเมินผลได้ใน รอบเดียวจากซ้ายไปขวา โดย ไม่มีวงเล็บ และ ไม่มีกฎลำดับความสำคัญ; จึงทำให้compiler หรือ interpreter ประมวลผลได้ง่ายและเร็วกว่า "ระบุโครงสร้างข้อมูลที่เหมาะสมพร้อมเหตุผล": Stack, เพราะการประเมินผลจำเป็นต้องใช้ operands ที่ถูก push เข้าไป ล่าสุดเป็นอันดับแรก (last in, first out): แต่ละ operandจะถูก push入, และแต่ละตัวดำเนินการจะpop出 2 ตัวบนสุด มาคำนวณแล้วpush入 ผลลัพธ์กลับเข้าไป แสดงสถานะของStack หลังแต่ละtoken เมื่อถูกถามถึง

การแปลง infix เป็น RPN ด้วยตนเอง. (1) ใส่วงเล็บให้ครบถ้วนตามกฎลำดับความสำคัญ; (2) ย้ายตัวแต่ละตัวไปต่อท้ายวงเล็บปิดของคู่เดียวกัน; (3) ลบวงเล็บออก ดังนั้น $(a - b) * (a + c) / 7$ จะกลายเป็น $((a - b) * (a + c)) / 7$, จากนั้น a b - a c + * 7 / หมายเหตุว่า * และ / ถูกประมวลผลจากซ้ายไปขวา ดังนั้นเครื่องหมายหารคือตัวสุดท้าย ไม่ใช่เครื่องหมายคูณ การแปลงเพิ่มเติม: $((7 + 3) - (2 * 8)) / 6$ คือ 7 3 + 2 8 * - 6 /; $(7 - 2 + 8) / (9 - 5)$ คือ 7 2 - 8 + 9 5 - /; $a * b + b - d + 15$ คือ a b * b + d - 15 +; $(2 - 6) * (13 + 7) / 5$ คือ 2 6 - 13 7 + * 5 /

การแปลง RPN กลับเป็น infix. ทำความเข้าใจ RPN โดยใช้ stack ของ expressions: ดัน operand แต่ละตัว; สำหรับ operator แต่ละตัว ให้ดึงออกมาสองตัว เขียนใส่ด้านข้างของ operator ในวงเล็บ, แล้วดันผลลัพธ์กลับเข้าไป. ดังนั้น a b / 4 * a b + - คือ $((a / b) * 4) - (a + b)$; 5 2 + 9 3 - / 3 * คือ $((5 + 2) / (9 - 3)) * 3$; b a c - + d b + * c / คือ $((b + (a - c)) * (d + b)) / c$; a b - c + c a - * d / คือ $(((a - b) + c) * (c - a)) / d$. รักษาวงเล็บไว้: การถอดออกอาจเปลี่ยนความหมายได้

ตัวอย่างทำข้อสอบ ประเมินผล a b - c d + * e / เมื่อ $a = 17$, $b = 5$, $c = 7$, $d = 3$ และ $e = 10$ โดยแสดงสถานะของStack

ผลลัพธ์ 12. ลำดับของการ pop สำคัญสำหรับ - และ /: ค่าที่ถูก pop ครั้งที่สอง คือ operand ทางซ้าย ดังนั้น a b - จึงเป็น $a - b$ ไม่ใช่ $b - a$. อีกสองตัวอย่างในทำนองเดียวกัน: d a b + * c a - / กับ $a = 6, b = 12, c = 15, d = 5$ ให้ $5 \times (6 + 12) / (15 - 6) = 90 / 9 = 10$; c a - b d + * b c + / กับ $a = 4, b = 12, c = 24, d = 6$ ให้ $(24 - 4) \times (12 + 6) / (12 + 24) = 360 / 36 = 10$.

ตัวอย่างที่คำนวณแล้ว. แปลง $(A + B) \times (C - D)$ เป็น RPN แล้วประเมิน $(3 + 4) \times (5 - 2)$. สแกนจากซ้ายไปขวาโดยใช้ stack ของ operator. Push (; output A; push +; output B; เมื่อเจอ ) ให้ pop กลับไปที่ matching (, ทำให้ได้ A B + จนปัจจุบัน. Push ×, และวงเล็บที่สองทำงานแบบเดียวกัน, ได้ C D -. ในตอนท้าย pop ×. ผลลัพธ์: A B + C D - ×. เพื่อประเมินค่าตัวเลข ใช้ stack ของ operands: push 3, push 4; + pop ทั้งสองและ push 7; push 5, push 2; - pop ทั้งสองและ push 3; × pop 7 และ 3 และ push 21. สิ่งสองอย่างที่ทำให้สิ่งนี้เชื่อถือได้คือ: operands รักษา ลำดับเดิม ผ่านการแปลง (มีแต่ operators ที่เคลื่อนย้าย), และแต่ละ operator ทำงานกับ สองค่าที่อยู่ใต้มันโดยตรง บน stack.

คำถามคำนิยามจะให้คะแนนตามข้อความที่กำหนดไว้你必须 exact. เรียนรู้ให้ถูกต้องและตอบเพียงคำตอบเดียวเท่านั้น

• ข้อสอบเกี่ยวกับ OS ถูกให้คะแนนตามกลไกที่กำหนดชื่อ: การจัดตารางเวลา, การจัดการหน่วยความจำ, การ buffering และการ spooling ของ I/O, การจัดการไฟล์; สำหรับอินเทอร์เฟซ: ชื่อไฟล์ไม่ใช่ที่อยู่, การคลิกไม่ใช่คำสั่ง, ไดรฟ์, GUI.
• สถานะของกระบวนการพร้อมกับการเปลี่ยนผ่านและเหตุผลของแต่ละอย่าง;Routineการจัดตารางเวลาเป็นฟังก์ชันบวกประโยชน์บวกข้อเสีย; เควอูทบันทึกสถานะ, ระบุการขัดจังหวะ, บริการ, ฟื้นฟู.
• หน่วยความจำเสมือน: ดิสก์ขยาย RAM, หน้าถูกสลับ, การแปลงที่อยู่; การแบ่งหน้ามีขนาดคงที่และไม่มองเห็นได้, การแบ่งส่วนมีขนาดแปรผันและเป็นตรรกะ; การสะเทือนคือการสลับแทนการทำงาน
• ตัวแปลภาษา: ทีละบรรทัด, แปลแล้ว被执行, ไม่มีอะไรถูกเก็บ. ขั้นตอนของคอมไพลเออร์: tokens และตารางสัญลักษณ์, grammar และ parse tree, โค้ด, การเพิ่มประสิทธิภาพ.
• BNF: กฎต่อแผนภาพ, | เพื่อทางเลือก, การเรียกซ้ำสำหรับการซ้ำ, terminals ล้วนและ non-terminals ในวงเล็บมุม. บอกว่ากฎใดที่ string ทำลาย.
• RPN: operators หลัง operands, คำนวณด้วยส栈, แสดงทุกขั้นตอน; แปลงโดยการใส่วงเล็บเต็มรูปแบบ; เมื่อแปลงกลับ, รักษาวงเล็บไว้

ข้อผิดพลาดที่พบบ่อย

• การอธิบาย multi-tasking ว่า "被执行หลายโปรแกรมในเวลาเดียวกัน" โดยไม่กล่าวถึงการสลับของโปรเซสเซอร์ระหว่าง них
• ส่งกระบวนการ blocked ไปยัง running โดยตรง, หรือให้ "time slice ends" เป็นเหตุผลสำหรับการเปลี่ยนจาก running เป็น blocked
• สับสนระหว่าง shortest job first (non-pre-emptive) กับ shortest remaining time (pre-emptive), หรือ round robin กับ priority
• นิยามของ virtual memory ว่า "การใช้ hard disk เป็น RAM" โดยไม่กล่าวถึงการสลับของหน้า
• การบอกตัวแปลภาษาว่า "แปลงโปรแกรมเป็นโค้ดเครื่องแล้ว被执行" นั่นคือคอมไพลเออร์
• การตรวจสอบ syntax ใน lexical analysis, หรือ optimization ก่อน code generation ในคำถามจับคู่
• การเขียน BNF การซ้ำเป็น <letter>* หรือด้วยจุดสาม; ใช้การเรียกซ้ำ. ทิ้งวงเล็บมุมออกจาก non-terminals
• การกลับด้านของ operands ของ - หรือ / เมื่อคำนวณ RPN, หรือการเขียน RPN ของ $a * b + c$ เป็น a b c + *